Heap Optimization in A* Pathfinding for Horror Games

Risaldi Angga Buana Putra; Ary Setijadi Prihatmanto; Rahadian Yusuf; Agus Sukoco

doi:10.51519/journalisi.v7i1.941

Risaldi Angga Buana Putra Bandung Institute of Technology Bandung, Indonesia
Ary Setijadi Prihatmanto Bandung Institute of Technology Bandung, Indonesia
Rahadian Yusuf Bandung Institute of Technology Bandung, Indonesia
Agus Sukoco Bandung Institute of Technology Bandung, Indonesia

DOI: 10.51519/journalisi.v7i1.941

Keywords: Horror, Horror Games, AI, A*Pathfinding, Binary Heap

Abstract

This paper examines the implementation of the A* pathfinding algorithm with binary heap optimization in a horror game environment. The horror genre in gaming uniquely engages players by placing them at the center of fear-driven experiences, where intelligent and unpredictable enemy behavior is critical for immersion. To achieve this, adaptive AI—specifically for apparitions or monsters—is controlled using A*, an algorithm renowned for its efficiency in determining the shortest path. Heap optimization is introduced to enhance A* performance by reducing the time required to identify the lowest-cost node in the Open List. Experimental results from a Unity-based prototype demonstrate that the optimized A* achieves an average pathfinding time of 1.6 ms, compared to 3.16 ms without optimization—representing a 49.37% improvement. This speed increase allows for faster and more responsive enemy behavior, resulting in heightened difficulty and more dynamic, fear-inducing gameplay. The findings highlight the potential of algorithmic optimization to significantly enhance both technical performance and player immersion in horror game design.

Downloads

Download data is not yet available.

References

L. Nummenmaa, “Psychology and neurobiology of horror movies,” PsyArXiv Prepr., Turku PET Centre, Dept. of Psychology and Turku Univ. Hospital, Univ. of Turku, Finland, 2020.

E. S. de Lima, B. M. C. Silva, and G. T. Galam, “Towards the design of adaptive virtual reality horror games: A model of players’ fears using machine learning and player modeling,” in Proc. Brazilian Symp. Games Digit. Entertain. (SBGAMES), Nov. 2020, pp. 171–177, doi: 10.1109/SBGames51465.2020.00031.

G. A. da Silva and M. W. de Souza Ribeiro, “Development of Non-Player Character with Believable Behavior: a systematic literature review,” in Proc. XX Brazilian Symp. Games Digit. Entertain., 2021, pp. 319–323, doi: 10.5753/sbgames_estendido.2021.19660.

J.-H. Kim, J. Lee, and S.-J. Kim, “Navigating Non-Playable Characters Based on User Trajectories with Accumulation Map and Path Similarity,” Symmetry, vol. 12, no. 10, p. 1592, 2020, doi: 10.3390/sym12101592.

D. Liu, “Research of the Path Finding Algorithm A* in Video Games,” Highlights Sci. Eng. Technol., vol. 39, 2023.

S. R. Lawande, G. Jasmine, J. Anbarasi, and L. I. Izhar, “A Systematic Review and Analysis of Intelligence-Based Pathfinding Algorithms in the Field of Video Games,” Appl. Sci., vol. 12, no. 11, p. 5499, 2022, doi: 10.3390/app12115499.

O. R. Chandra and W. Istiono, “A-star Optimization with Heap-sort Algorithm on NPC Character,” Indian J. Sci. Technol., vol. 15, no. 35, pp. 1722–1731, 2022, doi: 10.17485/IJST/v15i35.857.

Z. Zhang, J. Jiang, J. Wu, and X. Zhu, “Efficient and optimal penetration path planning for stealth unmanned aerial vehicle using minimal radar cross-section tactics and modified A-Star algorithm,” ISA Trans., vol. 134, pp. 42–57, 2023, doi: 10.1016/j.isatra.2022.07.032.

M. Foxman, “United We Stand: Platforms, Tools and Innovation with the Unity Game Engine,” Soc. Media Soc., vol. 5, no. 4, 2019, doi: 10.1177/2056305119880177.

[10] B. Wang, Z. Liu, Q. Li, and A. Prorok, “Mobile Robot Path Planning in Dynamic Environments Through Globally Guided Reinforcement Learning,” IEEE Robot. Autom. Lett., vol. 5, no. 4, pp. 6932–6939, 2020, doi: 10.1109/LRA.2020.3026638.

R. Subari, N. Radita, and B. Prakoso, “The Implementation of A* Algorithm for Developing Non-Player Characteristics of Enemy in A Video Game Adopted from Javanese Folklore ‘Golden Orange,’” Teknika, vol. 13, no. 2, pp. 164–174, 2024.

R. A. Gunawan, W. Istiono, J. Scientia Boulevard Gading, C. Sangereng, and K. Tangerang, “Optimizing RPG Pathfinding: A Hybrid Approach for Static and Dynamic Obstacle Avoidance,” Int. J. Inf. Syst. Comput. Sci. (IJISCS), vol. 7, no. 3, 2023.

A. Andreychuk, K. Yakovlev, D. Atzmon, and R. Stern, “Multi-Agent Pathfinding with Continuous Time,” in Proc. 28th Int. Joint Conf. Artif. Intell. (IJCAI), 2019, pp. 39–45, doi: 10.24963/ijcai.2019/6.

T. Lynch and N. Martins, “Nothing to Fear? An Analysis of College Students’ Fear Experiences with Video Games,” J. Broadcast. Electron. Media, vol. 59, no. 2, pp. 298–317, 2015, doi: 10.1080/08838151.2015.1029128.

M. Ponsen and P. Spronck, “Improving Adaptive Game AI with Evolutionary Learning,” unpublished.

V. Morina and R. Rafuna, “A Comparative Analysis of Pathfinding Algorithms in NPC Movement Systems for Computer Games,” unpublished.

S. R. Lawande, G. Jasmine, J. Anbarasi, and L. I. Izhar, “A Systematic Review and Analysis of Intelligence-Based Pathfinding Algorithms in the Field of Video Games,” Appl. Sci. (Switz.), vol. 12, no. 11, 2022, doi: 10.3390/app12115499.

E. B. Aydogan and Y. Atay, “Unity Based A∗ Algorithm Used in Shortest Path Finding Problem for Helicopters,” in 2021 Int. Conf. Control, Autom. Diagn. (ICCAD), 2021, doi: 10.1109/ICCAD52417.2021.9638762.

J. Moss, C. O’Brien, J. Cook, and P. Camargo, “Performance effects of heap structure choice for path finding: A traffic modelling perspective,” in Proc. 44th Australas. Transp. Res. Forum (ATRF), Perth, WA, Australia, Nov. 2023.

T. Lynch and N. Martins, “Nothing to fear? An analysis of college students’ fear experiences with video games,” J. Broadcast. Electron. Media, vol. 59, no. 2, pp. 298–317, 2015, doi: 10.1080/08838151.2015.1029128.

A. Candra, M. A. Budiman, and R. I. Pohan, “Application of A-Star Algorithm on Pathfinding Game,” J. Phys.: Conf. Ser., vol. 1898, no. 1, 2021, doi: 10.1088/1742-6596/1898/1/012047.

C. Ying, C. Yuhang, and W. Yaodong, “Research on Monster Path Planning Scheme in Horror Game Based on Whale Optimization Algorithm,” in Proc. 6th IEEE Int. Conf. Intell. Comput. Signal Process. (ICSP), 2021, pp. 111–114, doi: 10.1109/ICSP51882.2021.9408889.

R. Subari, N. Radita, and B. Prakoso, “The Implementation of A* Algorithm for Developing Non-Player Characteristics of Enemy in A Video Game Adopted from Javanese Folklore ‘Golden Orange,’” Teknika, vol. 13, no. 2, pp. 164–174, 2024, doi: 10.34148/teknika.v13i2.799.