A*:n ja Flowfieldin vertailu Unity-pelimoottorissa

Abstract

Reitinlöytö on nimensä mukaisesti reittien etsintää. Etsintä toteutetaan matemaattisesti laskien. Tässä opinnäytetyössä esiintyvät reitinlöytöalgoritmit laskevat reitit graafien avulla. Taustatietona käydään läpi Dijkstran algoritmin toiminta.

Reitinlöydöllä on monia applikaatioita. Tässä työssä vertaillaan kahta reitinlöytöalgoritmia erityisesti strategiapelien näkökulmasta. Työssä käytetään laajasti alalla käytössä olevaa Unity-pelimoottoria algoritmien implementointiin sekä testaukseen.

Reitinlöytö on tärkeä osa peliohjelmointia. Reitinlöytöä täytyy käyttää, kun pelin sisäiset hahmot navigoivat pelimaailmaa itsenäisesti, joko tekoälyn tai sitten pelaajan käskyttämänä. On erityisen tärkeää, että reitinlöytö tehdään tehokkain keinoin, jotta pelien kuvataajuus säilyy pelin ohjautuvuuden kannalta hyväksyttävällä tasolla.

Työn kaksi algoritmia, A* sekä Flowfield, valittiin niiden miltei päinvastaisten käyttötarkoitusten takia. Flowfield on tehty suurien hahmomäärien liikuttamiseen pelikentällä, minkä vuoksi se laskee koko kentän kattavan reitistön aina kun algoritmia käytetään. A* on tehty laskemaan yksi reitti pisteestä A pisteeseen B, jolloin sen täytyy laskea jokaiselle liikkuvalle yksikölle oma reittinsä päämäärään. A* sekä Flowfield käyttävät pohjanaan Dijkstran algoritmia.

Algoritmien vertailua varten määriteltiin testejä, joiden tarkoituksena oli tarkastella algoritmien skaalautuvuutta eri tilanteissa. Toteutusvaiheessa haastavimmaksi osoittautui algoritmien toteutus pelimoottorissa sekä tulosten ulossaanti.

Työn tulokset vastasivat odotuksia: algoritmien skaalautuvuus riippui eri asioista. A* skaalautui hahmojen määrän sekä laskettavan reitin pituuden mukaan. Flowfield skaalautui kartan koon sekä monimutkaisuuden mukaan. Pohdintoihin lisättiin vielä huomautus reitinlöydön muista teknisistä osista, jotka tulee ottaa huomioon reitinlöytöä implementoidessa.

This thesis examines two path finding algorithms, A* and Flowfield especially from the perspective of strategy games. Pathfinding is as the name implies, the process of finding paths on a map, this search for viable paths is done with mathematical calculation. Though this study examines the aforementioned algorithms and pathfinding in general mostly from a game programming perspective, pathfinding has many other real-world applications as well. The study uses the Unity game engine, which is widely used in the videogame industry.

Pathfinding is a key part in modern game programming. As it is performed frequently and can be quite calculation heavy it is paramount that it be done in a cost-effective way while balancing performance with results. The frames-per-second of a game must be kept high enough so as not to negatively affect the players ability to control the game and understand the state the game is in.

The two algorithms examined in the study, A* and Flowfield were chosen because of their diametrically opposed use cases. A* is used for calculating a singular path from point A to point B, in which case a separate path calculation is needed for each unit we command in a game even if their destination is the same. The Flowfield algorithm calculates routes from every point in the navigable map to the end point, this means that every unit can follow the route closest to them and there is no need to repeat calculations.

To measure the performance of these algorithms in different circumstances that are favorable to one or the other, tests were devised to check how the algorithms scale in these circumstances. The most difficult part when implementing the coding in this study was to be implementing the algorithms into the Unity game engine and determining how to extract the performance results out of Unity.

The results were as expected, the algorithms scaled with different parameters that the tests had. A* scaled according to the unit count as well as the length of the calculated route. Flowfield scaled according to the size of the map, as well as the complexity of said map.