Comparison of grid-based pathfinding algorithms in different map types

Abstract

Pathfinding is the process of finding a viable path between two points, usually the shortest one. Pathfinding is used in many applications, such as video games and robotics. The path is solved with an algorithm in these applications and the environment can be presented as a two dimensional grid with some cells marked as obstacles. This thesis focuses on the performance effects of map types with differing layouts and shapes for obstacles and whether the pathfinding process can be optimized by selecting an algorithm that performs better in a specific map type.

Dijkstra’s algorithm, the A* algorithm and the Jump Point Seach algorithm were implemented for the comparison. The maps used in the comparison were two maze maps, three maps based on real-life locations and three custom maps made based on possible use cases. The results were gathered by repeatedly creating two random points on the map, running each algorithm between those points and averaging the resulting execution times.

The results showed that Jump Point Search was the fastest algorithm on nearly every map, but its effectiveness was still affected by the map type. Dijkstra’s algorithm only had comparable performance to the other two algorithms on the maze maps, especially the maze map with one cell wide walls and corridors. A* performed consistently worse than Jump Point Search but still much better than Dijkstra’s algorithm.

The results of this thesis are not definitive as each application has a map different from the ones used in the tests and if the application requires a grid with different costs for each cell, Jump Point Search cannot be used. Additionally, each algorithm can be optimized further to varying extents.

Reitinhaku on prosessi, jossa etsitään kahden pisteen välinen reitti, yleensä lyhyin mahdollinen. Reitinhakua käytetään monissa käyttötarkoituksissa, kuten videopeleissä ja robotiikassa. Reitti ratkaistaan näissä tapauksissa algoritmin avulla, ja ympäristö voidaan esittää kaksiulotteisena ruudukkona, jossa osa ruuduista on merkitty esteiksi. Tämä opinnäytetyö keskittyy karttatyyppien erilaisista esteiden asetteluista ja muodoista johtuvien suorituskykyvaikutusten tarkasteluun, sekä siihen, voiko reitinhaun prosessia optimoida valitsemalla tietyssä karttatyypissä parhaiten suoriutuva algoritmi.

Vertailua varten toteutettiin Dijkstran algoritmi, A*-algoritmi ja Jump Point Search -algoritmi. Vertailussa käytettiin kahta labyrinttikarttaa, kolmea todellista sijaintia, sekä kolmea mahdollisiin käyttötapauksiin perustuvaa mukautettua karttaa. Tulokset kerättiin toistuvasti luomalla kartalle kaksi satunnaista pistettä, suorittamalla kukin algoritmi niiden välillä ja laskemalla suoritusajoista keskiarvot.

Tulokset osoittivat, että Jump Point Search oli nopein algoritmi lähes kaikilla kartoilla, mutta karttatyyppi silti vaikutti sen tehokkuuteen. Dijkstran algoritmi oli suorituskyvyltään verrattavissa toisiin algoritmeihin ainoastaan labyrinttikartoilla, erityisesti labyrinttikartalla, jossa oli yhden ruudun levyiset seinät ja käytävät. A*-algoritmi suoriutui tasaisesti Jump Point Searchiä heikommin, mutta selvästi paremmin kuin Dijkstran algoritmi.

Tämän opinnäytetyön tulokset eivät ole lopullisia, sillä jokaisessa käyttötapauksessa käytettävä kartta tulee poikkeamaan testikartoista, eikä Jump Point Search -algoritmia voida käyttää, jos ruudukon liikkumiskustannukset vaihtelevat ruudusta toiseen. Lisäksi kaikkia algoritmeja voidaan optimoida edelleen vaihtelevissa määrin.