Comparative Analysis of Pathfinding Algorithms A *, Dijkstra, and BFS on Maze Runner Game

Silvester Dian Handy Permana(1*), Ketut Bayu Yogha Bintoro(2), Budi Arifitama(3), Ade Syahputra(4),

(1) Universitas Trilogi
(2) Universitas Trilogi
(3) Universitas Trilogi
(4) Universitas Trilogi
(*) Corresponding Author

Abstract


Maze Runner game is a game that requires pathfinding algorithm to get to the destination with the shortest path. This algorithm is used in an NPC that will move from start node to destination node. However, the use of incorrect algorithms can affect the length of the computing process to find the shortest path. The longer the computing process, the longer the players have to wait. This study compared pathfinding algorithms A *, Dijkstra, and Breadth First Search (BFS) in the Maze Runner game. Comparison process of these algorithms was conducted by replacing the algorithm in the game by measuring the process time, the length of the path, and the numbers of block played in the existing computing process. The results of this study recommend which algorithm is suitable to be applied in Maze Runner Game.


Full Text:

PDF

References


D. Perez-Liebana, J. Liu, A. Khalifa, R. D. Gaina, J. Togelius, and S. M. Lucas, “General Video Game AI: a Multi-Track Framework for Evaluating Agents, Games and Content Generation Algorithms,” 2018.

H. M. Vo, “Optimizating Power Consumption Using Multi-Bit Flip-Flop Technique,” pp. 0–3, 2017.

B. Arifitama and A. Syahputra, “Implementing Augmented Reality on a Multiple Floor Building as a Tool for Sales Product Knowledge,” Int. J. Technol. Bus., vol. 1, no. 1, 2017.

S. M. Kim, M. I. Peña, M. Moll, G. N. Bennett, and L. E. Kavraki, “A review of parameters and heuristics for guiding metabolic pathfinding,” J. Cheminform., vol. 9, no. 1, pp. 1–13, 2017.

H. Reddy, “PATH FINDING - Dijkstra ’ s and A * Algorithm ’ s,” pp. 1–15, 2013.

P. Singal Dcsa and R. R. S. Chhillar, “Dijkstra Shortest Path Algorithm using Global Positioning System,” Int. J. Comput. Appl., vol. 101, no. 6, pp. 975–8887, 2014.

A. A. Jamal and W. J. Teahan, “Alpha multipliers breadth-first search technique for resource discovery in unstructured peer-to-peer networks,” Int. J. Adv. Sci. Eng. Inf. Technol., vol. 7, no. 4, 2017.

A. Zafar, K. K. Agrawal, W. Cdr, and A. Kumar, “Analysis of Multiple Shortest Path Finding Algorithm in Novel Gaming Scenario,” Intell. Commun. Control Devices, Adv. Intell. Syst. Comput., pp. 1267–1274, 2018.

I. Zarembo and S. Kodors, “Pathfinding Algorithm Efficiency Analysis in 2D Grid,” Environ. Technol. Resour. Proc. Int. Sci. Pract. Conf., vol. 2, p. 46, 2015.

P. Singhal and H. Kundra, “A Review paper of Navigation and Pathfinding using Mobile Cellular Automata,” vol. 2, no. I, pp. 43–50, 2014.

A. Sazaki, Yoppy, Primanita and M. Syahroyni, “Pathfinding Car Racing Game Using Dynamic Pathfinding Algorithm and Algorithm A *,” 3rd Int. Conf. Wirel. Telemat. 2017, pp. 164–169, 2017.




DOI: https://doi.org/10.30645/ijistech.v1i2.7

Refbacks

  • There are currently no refbacks.







Jumlah Kunjungan:

View My Stats

Published Papers Indexed/Abstracted By: