Comparing the efficiency of Pathfinding Algorithms for NPCs in platform games

Abstract

Pathfinding has been a significant video game research area for decades. It is usually utilised as the core of any Artificial Intelligence moves in computer games. This research aims to identify a better suited and more efficient pathfinding algorithm for the platformer video game genre. This study compared two algorithms: the A* and Dijkstra algorithms. Both algorithms were implemented in a platform game environment and tested with several different obstacles for non-player characters (NPCs). The parameters measured were processing time, the length of the path taken, and the number of blocks/nodes played in the computational process. To evaluate the algorithms’ performance, the travel time taken, the computed nodes, and the distance travelled by the NPC to reach its destination were analysed for each algorithm. The findings indicate that both algorithms are suitable for specific conditions in a platformer environment; Dijkstra’s performed accurately and managed to find the shortest path when the route to the objective required less vertical movement, while A* performed more efficiently when the NPC was required to reach an objective that required more vertical movement. The results also suggest that A* performed better than Dijkstra’s algorithm, as it has a heuristics function that increased its flexibility.