Volume 14 • Issue 1 • PP: 66-80 • 2024
Toward the Believability of Non-Player Characters (NPC) Movement in Video Games
View PDF Abstract
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.
Keywords
References
[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.
Cite This Article
Choose your preferred format