Review of Various A* Pathfinding Implementations in Game Autonomous Agent

Among many pathfinding algorithms, A* search algorithm is an algorithm that most commonly used in grid-based pathfinding. This is due to implementation of A* search which proven to be able to generate the optimal path in a relatively short time by combining two characteristics of Djikstra's and best-first search algorithm. In the implementation of A* search, the selection of heuristic function and data structure can affect the performance of the algorithm. The purpose of this research is to find the best heuristic function and data structure with regards of the performance in A* search implementation as a pathfinding algorithm in a 3D platform. In the experiment, some known heuristic functions and data structures will be tested on the various 3D platform with a different size and obstacle percentage. Based on experiment that have been done, euclidean squared distance is best heuristic function for 3D pathfinding problem, with regards of the implementation performance. In addition, we also found that binary heap is the best data structure to be implemented for 3D pathfinding problem, with regards of implementation performance.