Optimizing Real-Time Path Planning for NPC Navigation: Leveraging CentA* Algorithm to Enhance Efficiency and Adaptability

Modern game development heavily relies on AI pathfinding to enable non-player characters (NPCs) to navigate the game world efficiently. The use of pathfinding algorithms is essential for creating a believable and immersive gaming experience. A popular choice among the various pathfinding algorithms used in game development is the A
^*
algorithm, which combines heuristic and graph search techniques to find the optimal path for NPCs. In this paper, the CentA
^*
algorithm is introduced as an extension of A
^*
that enhances the selection of starting and ending nodes, triggering NPC behaviours before reaching their destination. The gaming model is built using Unreal Engine 5 Blueprints, which incorporates the pathfinding algorithm and detection of enemy behavior that can be reused for different creature types with various character models. The pathfinding algorithm ensures that NPCs move in a realistic and efficient manner, enhancing the overall gaming experience. The introduction of CentA
^*
offers an improvement over the traditional A
^*
algorithm. A comparison of the proposed algorithm is done over the other existing algorithms and a minimization of the overall tour length is encountered. Compared to other existing algorithms, the proposed algorithm offers superior performance by reducing the overall tour length by a minimum of 0.67%. Although the proposed algorithm may lead to a slight increase in tour length by approximately 1.42%, it remains time-efficient and computes fewer blocks than other algorithms. These results demonstrate the potential of the proposed algorithm for optimizing tours in various contexts such as route planning and logistics. This paper emphasizes the significance of pathfinding algorithms in game development, particularly in creating a realistic and immersive gaming experience for players. The implementation of CentA
^*
has significantly enhanced the behavior of NPCs in games.