Heuristic Pathfinding Algorithms in Video Games Indepth Analysis and Performance
DOI:
https://doi.org/10.61173/k583am18Keywords:
Heuristic Pathfinding, Hierarchical Pathfind-ing, Dijkstra’s Algorithm, Jump Point Search (JPS), Bidi-rectional SearchAbstract
The creation of artificial intelligence in video games is mostly dependent on heuristic pathfinding algorithms. The ability to move of the agent is one of the biggest obstacles in the construction of accurate artificial intelligence (AI) in video games. Before the A* algorithm emerged as a provably optimum solution for pathfinding, several search algorithms, including Dijkstra’s algorithm, the bread first search algorithm, and depth first search algorithm, were developed to tackle the shortest route issue. Since its inception, it has drawn the interest of several scholars who have decided to work on it. This paper provides an in-depth analysis of these algorithms, focusing on their development, evolution, and performance. Beginning with an overview of classical algorithms like A*, the paper explores recent advancements and optimizations. Performance metrics and practical applications are discussed, with case studies from contemporary video games. This analysis highlights the balance between computational efficiency and path optimality, guiding future developments in game AI.
References
[1] Mathew, G.E., 2015. Direction based heuristic for pathfinding in video games. Procedia Computer Science, 47, pp.262-271. https://www.sciencedirect.com/science/article/pii/ S1877050915004743
[2] Rafiq, A., Kadir, T.A.A. and Ihsan, S.N., 2020, February. Pathfinding algorithms in game development. In IOP Conference Series: Materials Science and Engineering (Vol. 769, No. 1, p. 012021). IOP Publishing. https://iopscience.iop.org/ article/10.1088/1757-899X/769/1/012021/meta
[3] Monzonís Laparra, D., 2019. Pathfinding algorithms in graphs and applications. https://diposit.ub.edu/dspace/ handle/2445/140466
[4] Foead, D., Ghifari, A., Kusuma, M.B., Hanafiah, N. and Gunawan, E., 2021. A systematic literature review of A* pathfinding. Procedia Computer Science, 179, pp.507- 514. https://www.sciencedirect.com/science/article/pii/ S1877050921000399
[5] Barnouti, N.H., Al-Dabbagh, S.S.M. and Naser, M.A.S., 2016. Pathfinding in strategy games and maze solving using A* search algorithm. Journal of Computer and Communications, 4(11), pp.15-25. https://www.scirp.org/journal/ paperinformation?paperid=70460
[6] Sidhu, H.K., 2020. Performance Evaluation of Pathfinding Algorithms (Master’s thesis, University of Windsor (Canada). https://search.proquest.com/openview/3998aa7641a5c816dde91 ddf8fe9b8f0/1?pq-origsite=gscholar&cbl=18750&diss=y
[7] Kapi, A.Y., Sunar, M.S. and Zamri, M.N., 2020. A review on informed search algorithms for video games pathfinding. International Journal, 9(3). https://web.pdx. edu/~arhodes/ai8.pdf
[8] Duarte, F.F., Lau, N., Pereira, A. and Reis, L.P., 2020. A survey of planning and learning in games. Applied Sciences, 10(13), p.4529. https://www.mdpi.com/2076- 3417/10/13/4529
[9] Dijkstra’s algorithm, developed by Edsger Dijkstra in 1956, focuses solely on finding the shortest path from a starting node to all other nodes in the graph, evaluating every possible route. https://www.academia.edu/download/65634054/G0810014047. pdf
[10] Yao, Q., Zheng, Z., Qi, L., Yuan, H., Guo, X., Zhao, M., Liu, Z. and Yang, T., 2020. Path planning method with improved artificial potential field—a reinforcement learning perspective. IEEE access, 8, pp.135513-135523. https:// ieeexplore.ieee.org/abstract/document/9146273/
[11] Zhou, W.J., Subagdja, B., Tan, A.H. and Ong, D.W.S., 2021. Hierarchical control of multi-agent reinforcement learning team in real-time strategy (RTS) games. Expert Systems with Applications, 186, p.115707. https://www.sciencedirect.com/ science/article/pii/S0957417421010897
[12] Černý, M., 2016. Reducing Complexity of AI in Open- World Games by Combining Search-based and Reactive Techniques. https://dspace.cuni.cz/handle/20.500.11956/82390
[13] Sharma, M. and Jindal, H., 2022. Pathfinding Visualizer. http://www.ir.juit.ac.in:8080/jspui/bitstream/123456789/3757/1/ Pathfinding%20Visualizer.pdf
[14] Harabor, D. and Stuckey, P., 2018. Forward search in contraction hierarchies. In Proceedings of the International Symposium on Combinatorial Search (Vol. 9, No. 1, pp. 55-62). https://ojs.aaai.org/index.php/SOCS/article/view/18454
[15] Lawande, S.R., Jasmine, G., Anbarasi, J. and Izhar, L.I., 2022. A systematic review and analysis of intelligence-based pathfinding algorithms in the field of video games. Applied Sciences, 12(11), p.5499. https://www.mdpi.com/2076- 3417/12/11/5499
[16] Alkazzi, J.M. and Okumura, K., 2024. A Comprehensive Review on Leveraging Machine Learning for Multi-Agent Path Finding. IEEE Access. https://ieeexplore.ieee.org/abstract/ document/10506521/
[17] Chan, L., Hogaboam, L. and Cao, R., 2022. Artificial intelligence in video games and esports. In Applied Artificial Intelligence in Business: Concepts and Cases (pp. 335-352). Dean&Francis ISSN 2959-6157 Cham: Springer International Publishing. https://link.springer. com/chapter/10.1007/978-3-031-05740-3_22
[18] Churchill, D.G., 2016. Heuristic search techniques for real-time strategy games. https://era.library.ualberta.ca/items/ c3589c0d-9b9e-46d5-b1a1-b4004379faad
[19] Ennabili, T.Y., 2023. A Comparison of Traditional Game Design vs. AI-Driven Game Design. https://www.theseus.fi/ handle/10024/816173
[20] Zeng, J., Ju, R., Qin, L., Hu, Y., Yin, Q. and Hu, C., 2019. Navigation in unknown dynamic environments based on deep reinforcement learning. Sensors, 19(18), p.3837. https://www. mdpi.com/1424-8220/19/18/3837.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 by the authors.
This work is licensed under a Creative Commons Attribution 4.0 International License.
