Reitinhakualgoritmien käyttö videopeleissä

Abstract

Reitinhaku on sekä videopeleissä että tekoälyn ja robotiikan puolella hyvin tuttu ongelma. Sen tutkimiseen on käytetty viime vuosina paljon resursseja lisääntyneen tekoälykiinnostuksen vuoksi. Tässä tutkielmassa keskitytään videopeleissä tapahtuvaan reitinhakuun, josta käsitellään lyhyesti sen historiaa, joitain käytettyjä algoritmeja ja pelialueen esitysmenetelmiä sekä vertaillaan niiden tehokkuutta keskenään. Tutkielma on kirjallisuuskatsaus, joka perustuu muihin tieteellisiin teoksiin. Keskeisinä tuloksina tulee esille alueen kolmioinnin sekä kolmiointia hyödyntävän TRA*-algoritmin vahvuudet verrattuna alueen ruudukkoesitykseen ja perinteiseen A*-algoritmiin. Tämän vuoksi pelialueet pitäisi esittää jonain muina kuin ruudukkoina, jotta tehokkaammat algoritmit voivat toimia paremmin.

Pathfinding is a known problem in video games, artificial intelligence (AI) and robotics. In recent years more and more resources have been spent in researching AI and its problems because of growth in interest. In this study I focus on pathfinding in video games, whereof I briefly introduce its history, some algorithms that are used and how the game area is represented, and finally compare their efficiency. The study is a review that depends on other studies. The key results are the benefits of triangulation and TRA*-algorithm in comparison with using a grid map and A*-algorithm. Therefore game areas should be represented as something else than a grid map, so more efficient algorithms can perform better.