Three Real-Time Pathfinding Strategies in Games: From A* Ideas to Machine Learning Approaches
Xinyu Hong, Xiao Hu, Yixing Lin · 2024
As the complexity of video games escalates, the presence of more agents, diverse game environments and richer game mechanisms are continuously drawing attention to real-time pathfinding algorithms. Researchers have delved into enhancing traditional algorithms to reduce the time cost in discovering a satisfying path. Based on the classic A* algorithm, new variants, including Time-Bound A* algorithm (TBA*), are proposed and achieved better performance than the traditional version. Additionally, reinforcement learning techniques, including Monte Carlo Tree Search, have been implemented to mitigate environmental dependency in games. Furthermore, based on the classification prowess of neural networks, several deep learning approaches like MAPFASTER use neural networks as selectors of pathfinding algorithms. In this work, these three approaches are discussed, including their ideas, principles, merits, limitations, contributions and prospective. This paper offers comprehensive insights and can serve as a reference for researchers investigating real-time pathfinding algorithms that integrate multiple domains.