Heap Optimization in A* Pathfinding for Horror Games

Journal: Journal of Information Systems and Informatics

Publication: 2025-03-31 · Vol. 7 No. 1 · pp. 924–940

DOI: 10.51519/journalisi.v7i1.941

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.