Review of Various A* Pathfinding Implementations in Game Autonomous Agent
Abstract
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.
Downloads
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-ShareAlike International License (CC-BY-SA 4.0) that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Copyright without Restrictions
The journal allows the author(s) to hold the copyright without restrictions and will retain publishing rights without restrictions.
The submitted papers are assumed to contain no proprietary material unprotected by patent or patent application; responsibility for technical content and for protection of proprietary material rests solely with the author(s) and their organizations and is not the responsibility of the IJNMT or its Editorial Staff. The main (first/corresponding) author is responsible for ensuring that the article has been seen and approved by all the other authors. It is the responsibility of the author to obtain all necessary copyright release permissions for the use of any copyrighted materials in the manuscript prior to the submission.
