Heuristiset reitinhakualgoritmit videopeleissä: vertailu ja käyttökohteet

Abstract

Monissa videopeleissä käytetään reitinhakualgoritmeja liikuttamaan hahmoja, jotka eivät ole pelaajan ohjaamia. Aikaisemmin reitinhakualgoritmit etsivät maalin sokkona, mutta nykyään varsinkin videopeleihin käytetään heuristisia reitinhakualgoritmeja, joilla on tietoa maalin sijainnista. Heuristiset reitinhakualgoritmit ovat lähes aina nopeampia, resurssitehokkaampia ja yleensä löytää lyhyimmän mahdollisen reitin. Siitä huolimatta pelinkehittäjät saattavat valita vanhan algoritmin uuden sijaan, koska ne esiintyvät useammin kirjallisuudessa. Tässä tutkielmassa esitetään eri heuristisia reitinhakualgoritmeja, joita kirjallisuudessa esiintyy. Näiden reitinhakualgoritmien toiminta sekä vahvuudet ja heikkoudet selitetään. Lisäksi näille reitinhakualgoritmeille annetaan esimerkkejä käyttökohdemahdollisuuksista. Tutkielmassa myös lajitellaan heuristiset reitinhakualgoritmit toimintaperiaatteiden mukaan. Esitetyt luokat ovat helposti ymmärrettäviä, jotta pelinkehittäjät voivat löytää nopeasti ja helposti omaan peliin soveltuvan reitinhakualgoritmin. Esitettyjen luokkien reitinhakualgoritmeilla on samankaltainen käyttökohde, johon konkreettisena esimerkkinä annetaan videopeli, jossa reitinhakualgoritmia voitaisiin käyttää.

Many video games use pathfinding algorithms to move characters that are not controlled by any player. In the past, pathfinding algorithms used blind search to find the goal, but nowadays heuristic pathfinding algorithms, which have some information about the position of the goal, are commonly used in video games. Heuristic pathfinding algorithms are almost always faster, more resource efficient, and generally find the shortest possible path. Despite this, game developers may choose an older algorithm instead of a newer one, because they show up more in literature. This thesis presents various heuristic pathfinding algorithms found in literature. The operation, as well as strengths and weaknesses of these pathfinding algorithms are explained. In addition, examples of potential use cases for these algorithms are provided. The thesis also categorizes heuristic pathfinding algorithms based on their operating principles. The presented categories are easy to understand, to let game developers quickly and easily find a suitable pathfinding algorithm for their game. The pathfinding algorithms in the presented categories share a similar use case, and a video game where the algorithm could be used is provided as a concrete example.