UMN Knowledge Center

Review of Various A* Pathfinding Implementations in Game Autonomous Agent

Suryadibrata, Alethea and Young, Julio Cristian and Luhulima, Richard (2019) Review of Various A* Pathfinding Implementations in Game Autonomous Agent. IJNMT (International Journal of New Media Technology), 6 (1). ISSN 2355-0082

Full text not available from this repository.
Official URL: https://ejournals.umn.ac.id/index.php/IJNMT/articl...

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.

Item Type: Article
Subjects: 000 Computer Science, Information and General Works > 000 Computer Science, Knowledge and Systems > 005 Computer Programming (Algorithm, Programming Language, Applications, Software, Data Security)
700 Arts and Recreation > 790 Outline of Sports, Games and Entertainment
Divisions: Fakultas Teknik Informatika > Program Studi Informatika
Depositing User: mr admin umn
Date Deposited: 06 Oct 2021 06:15
Last Modified: 06 Oct 2021 06:15
URI: http://kc.umn.ac.id/id/eprint/18552

Actions (login required)

View Item View Item