2692-4048ISSN (Online)
2770-0070ISSN (Print)
Volume 14 , Issue 1 , PP: 66-80, 2024 | Cite this article as | XML | Html | PDF | Full Length Article
Rawia Mohamed 1 * , Waleed Al Adrousy 2 , Samir Elmougy 3
Doi: https://doi.org/10.54216/FPA.140106
In video games, artificial intelligence is the effort of going beyond scripted interactions, however complex into the arena of truly interactive systems. To make a game world appear more real, these video games must be responsive, adaptive, and intelligent. For example, in real time strategy games, if there is an enemy seeking/hunting the player, it will be moving in paths, turning around and even maybe jumping in order to find the player. In this case, if the enemy acts/moves more real like human, it will be a benefit for making the game more attractive and exciting. This paper aims to develop a fast, intelligent, and realistic pathfinding approach that makes a user feel that he/she is playing with a human being instead of a machine. To achieve this, this paper presents a Heap Heuristic A* Algorithm as an enhancement of A* algorithm, in which the Chebyshev distance is used to control the smoothness of the resulted path and heapsort algorithm to sort the nodes easily without a lot of memory consumption. Compared to the pervious improved A* algorithms, the proposed algorithm produces a smoother path while consuming less memory to get a final result of human like movement. The experiments results showed that the proposed algorithm reduced the computing time by 66.6% using a grid size of 200*200 compared with A*MOD algorithm. Also, they showed that the proposed work takes almost 91ms to find the path compared to 363 ms and 116 ms when Native A* and A*MOD algorithms are used, respectively, Furthermore, the proposed algorithm performance remains stable in the case of increasing the number of visited nodes, despite the changing order of obstacles.
NPC , artificial agent , path finding , games theory
[1] Marek Kopel, and Tomasz Hajas (2018) Implementing AI for non-player characters in 3D video games. Intelligent Information and Database Systems. DOI:10.1007/978-3-319-75417-8_57
[2] Christian Arzate Cruz, and Jorge Adolfo Ramirez Uresti (2018) HRLB⌃ 2:A reinforcement learning based framework for believable bots. Applied Sciences. https://doi.org/10.3390/app8122453
[3] Mohsen Tavakoli (2019) Performance Evaluation of Competing Data Structures in Pathfinding. Electronic Theses and Dissertations. Performance Evaluation of Competing Data Structures (uwindsor.ca)
[4] Nam Kyu Kang, Ho Joon Son, and Soo-Hong Lee (2018) Modified A-star algorithm for modular plant land transportation. Journal of Mechanical Science and Technology 32.12 : 5563-5571. https://doi.org/10.1007/s12206-018-1102-z
[5] Phuoc Gia Ngo (2020) Game Application Using A* Pathfinding Algorithm to Help Improving Dementia. Game Application Using A* Pathfinding Algorithm To Help Improving Dementia (calstate.edu)
[6] Jakub Smołka et al. (2019), A* pathfinding algorithm modification for a 3D engine. MATEC Web of Conferences. EDP Sciences 252. DOI:10.1051/matecconf/201925203007
[7] Chandra OR, Istiono W (2022) A-star Optimization with Heap-sort Algorithm on NPC Character. Indian Journal of Science and Technology 15(35): 1722-1731. https://doi.org/ 10.17485/IJST/v15i35.857.
[8] Qiang Meng, and Jianjun Zhang (2019) Optimization and application of artificial intelligence routing algorithm. Cluster Computing. 22, :8747–8755 DOI:10.1007/s10586-018-1963-z
[9] ZhenGuo Zhao, RunTao Liu (2015) A optimization of A* algorithm to make it close to human pathfinding behavior. International Conference on Electrical, Computer Engineering and Electronics. https://doi.org/10.2991/icecee-15.2015.140
[10] Jacob Hell, Michael Clay, and Hala ELAarag (2017) Hierarchical dungeon procedural generation and optimal path finding based on user input. Journal of Computing Sciences in Colleges 33.1:175-183.
[11] Xiaoyan Guo, and Xun Luo (2018) Global Path Search based on A* Algorithm. International Conference on Transportation & Logistics, Information & Communication, Smart City (TLICSC 2018). Atlantis Press. https://doi.org/10.2991/tlicsc-18.2018.59
[12] Paulus Harsadi, Siti Asmiatun, and Astrid Novita Putri (2021) Dynamic Pathfinding for Non-Player Character Follower on Game. Jurnal Teknik Informatika CIT Medicom https://doi.org/10.35335/cit.Vol13.2021.68.pp51-58
[13] Ade Candra, Mohammad Andri Budiman, and Rahmat Irfan Pohan (2021) Application of A-star algorithm on Pathfinding Game. Journal of Physics: conference series. IOP Publishing 1898. 10.1088/1742-6596/1898/1/012047 (harvard.edu)
[14] Daniel Foead, Alifio Ghifari, Marchel Budi Kusuma, Novita Hanafiah, and Eric Gunawan (2021) A systematic literature review of A* pathfinding. Procedia Computer Science 179 : 507-514. https://doi.org/10.1016/j.procs.2021.01.034.
[15] Salvetti, M., Botea, A., Gerevini, A., Harabor, D., & Saetti, A. (2018, June). Two-oracle optimal path planning on grid maps. In Proceedings of the International Conference on Automated Planning and Scheduling (Vol. 28, pp. 227-231).
[16] Jubair, F., & Hawa, M. (2020). Exploiting Obstacle Geometry to Reduce Search Time in Grid-Based Pathfinding. Symmetry, 12(7), 1186.
[17] Nasseer K. Bachache, Ali Muhssen Abdul-Sadah, Bashar Ahmed Khalaf. (2023). The Steering Actuator System to Improve Driving of Autonomous Vehicles based on Multi-Sensor Data Fusion. Fusion: Practice and Applications, 11 (1), 77-86.
[18] Muhammad A. S. Mohd Shahrom, Nurezayana Zainal, Mohamad F. Ab. Aziz, Salama A. Mostafa. (2023). A Review of Glowworm Swarm Optimization Meta-Heuristic Swarm Intelligence and its Fusion in Various Applications. Fusion: Practice and Applications, 13 (1), 89-102.
[19] Jeff Craighead, Jennifer Burke, and Robin Murphy (2008) Using the unity game engine to develop sarge: a case study. Proceedings of the 2008 Simulation Workshop at the International Conference on Intelligent Robots and Systems (IROS 2008). Using-the-Unity-Game-Engine-to-Develop-SARGE-A-Case-Study.pdf (researchgate.net).
[20] Carlsson, S. (1992). A note on HEAPSORT. The Computer Journal, 35(4), 410-411.
[21] Weddle, C. (2008). Artificial intelligence and computer games. Florida State University.
