PATHFINDING ALGORITHMS FOR COMPUTER GAMES
Igor Udalov, V.A. Dokuchaev,
Network Information Technologies and Services, MTUCI, Moscow, Russia
igor.udalov.95@mail.ru, v.a.dokuchaev@mtuci.ru
DOI: 10.36724/2664-066X-2024-10-6-8-16
SYNCHROINFO JOURNAL. Volume 10, Number 6 (2024). P. 8-16.
Abstract
The development of gaming software, which is used for both entertainment and educational purposes, is becoming increasingly important at present time. Pathfinding algorithms play a special role in this type of software. Pathfinding algorithms are needed to solve problems related to finding the optimal path between two points on a graph, which can be a computer game map or any other system of interconnected objects and take into account various restrictions and conditions, such as network congestion, the presence of various obstacles, cost, etc. This paper focuses on various pathfinding algorithms used in modern technologies such as artificial intelligence, robotics, and computer games. The strengths and weaknesses of the algorithms are analyzed with a focus on video game applications. Recommendations for selecting the optimal algorithm for specific tasks in different game scenarios are also discussed in the paper.
Keywords: pathfinding algorithms, computer games, game maps, algorithm selection
References
[1] N. V. Apatova, A. A. Zosimenko, “Trends in the development of digital economy,” Theory and Practice of Economics and Entrepreneurship: Proceedings of the XIX International Scientific and Practical Conference, Simferopol – Gurzuf, 14-16 April 2022. Simferopol: V.I. Vernadsky Crimean Federal University. V.I. Vernadsky, 2022, pp. 289-290.
[2] V. A. Dokuchaev, “Digital Transformation: New Drivers and New Risks,” 2020 International Conference on Engineering Management of Communication and Technology (EMCTECH), Vienna, Austria, 2020, pp. 1-7, doi: 10.1109/EMCTECH49634.2020.9261544.
[3] V. A. Dokuchaev, A. A. Kalfa, V. V. Maklachkova, “Architecture of Data Processing Centres,” Moscow: Goryachaya Liniya – Telecom Publishing House, 2020.
[4] V. A. Dokuchaev, V. V. Maklachkova, I. D. Udalov, “Application of Entity Component System in Game Development,” Economics and quality of communication systems. 2025. No. 1 (35), pp. 57-66.
[5] Sharmad Rajnish Lawande, Graceline Jasmine, Jani Anbarasi and LilaIznita Izhar, “A Systematic Review and Analysis of Intelligence-Based Pathfinding Algorithms in the Field of Video Games,” [Electronic resource]. Access mode: https://www.mdpi.com/2076- 3417/12/11/5499 (Date of access: 23.03.2024).
[6] Silvester Dian Handy Permana, Ketut Bayu Yogha Bintoro, Budi Arifitama, Ade Syahputra, “Comparative Analysis of Pathfinding Algorithms A*, Dijkstra, and BFS on Maze Runner Game,” [Electronic resource]. Access mode: https://www.researchgate.net/publication/325368698_Comparative_Analysis_of_Pathfinding_Algorithms_A_Dijkstra_and_BFS_on_Maze_Runner_Gam (Date of access: 18.03.2024).
[7] Abdul Rafiq, “Pathfinding Algorithms in Game Development,” [Electronic resource]. Mode of access: https://iopscience.iop.org/article/10.1088/1757-899X/769/1/012021/pdf (Date of address: 20.03.2024)
[8] Edward Minieka, “Optimization Algorithms for Networks and Graphs by Edward Minieka,” 1978, ISBN: 9780824766429
[9] M. N. S. Swamy, “Thulasiraman K. Graphs, networks, and algorithms,” New York, Wiley Interscience, 1981, 592 p.
[10] H. Frank, and I. T. Frisch, “Communication, Transmission and Transportation Networks,” Addison-Wesley, Reading, MA, 1972.
[11] D. V. Gadasin, A. V. Shvedov, “Application of the transport problem for load balancing in conditions of vagueness initial data,” TComm, 2024, no. 1, pp. 13-19.
[12] Fatima Rubio, “Sr. Data Scientist The 5 Most Powerful Pathfinding Algorithms,” [Electronic resource]. Mode of access: https://www.graphable.ai/blog/pathfinding-algorithms/ (Date of address: 17.03.2024). Harinder Kaur Sidhu Performance Evaluation of Pathfinding Algorithms Performance Evaluation of Pathfinding Algorithms Development [Electronic resource]. Mode of access: https://scholar.uwindsor.ca/cgi/viewcontent.cgi?article=9230&context=etd (Date of address: 15.03.2024).
[13] V I. Dubrovin, S A. Subbotin, “Heuristic classification algorithm and its neural network interpretation,” Radioelectronics, Informatics, Control [Electronic resource]. Access mode: https://cyberleninka.ru/article/n/evristicheskiy-algoritm-klassifikatsii-i-ego-neyrosetevaya- interpretatsiya (Date of address: 01.10.2024).
[14] Adi Botea, Martin Muller, Jonathan Schaeffer, “Near Optimal Hierarchical Path-Finding// Department of Computing Science,” University of Alberta Edmonton, Alberta, Canada T6G 2E8. 2019. URL: https://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf (accessed 19.09.2023).
[15] Alex Kring, Alex J. Champandard, Nick Samarin, DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds 2010 URL: https://cdn.aaai.org/ojs/12397/12397-52-15925-1-2-20201228.pdf (accessed 19.09.2023).
[16] G. T. Heineman, G. Pollice, S. Selkow, “Algorithms in a Nutshell,” Moscow: O’Reilly Media, 2008. 364 p.
[17] В. L. Dolnikov, O. P. Yakimova, “Basic algorithms on graphs,” [Electronic resource]. Mode of access: http://www.lib.uniyar.ac.ru/edocs/iuni/20110210.pdf (Date of address: 23.03.2024).
[18] Junjie Zeng, Long Qin, Yue Hu, Cong Hu and Quanjun Yin, “Combining Subgoal Graphs with Reinforcement Learning to Build a Rational Pathfinder,” College of System Engineering, National University of Defence Technology, Changsha 410073, Hunan, China 2019. URL: https://www.mdpi.com/2076-3417/9/2/323 (accessed 13.08.2024).