Heap Optimization in A* Pathfinding for Horror Games - Putra, Risaldi Angga Buana; Prihatmanto, Ary Setijadi; Yusuf, Rahadian; Sukoco, Agus (Universitas Bina Darma, 2025)
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.