Multi-Agent Pathfinding in a Real-Time Strategy GameAntešić, Ivan (Avtor) Sadikov, Aleksander (Mentor) multi-agent pathfindingreal-time strategy gamesheuristic searchWHCA*To solve the multi-agent pathfinding (MAPF) problem, a collision-free path must be found for every individual in a group of agents. Over the years several MAPF algorithms were developed by researchers who claim their approaches are suitable for real-time strategy games. However, there appears to be a disconnect between scientific research and practical game development. Algorithms are being presented and tested without considering the crucial properties of a complex game environment. To determine whether MAPF really is a good approach to the games’ pathfinding problem, we implemented Windowed Hierarchical Cooperative A* (WHCA*), a seminal MAPF algorithm, in an existing real-time strategy game engine. We then compared it to the single-agent pathfinding approach, which is used by most games in the industry. Our experimental results show that our WHCA* implementation greatly improves the path quality and agent movement, can prevent congestion and solve difficult scenarios that the single-agent approach cannot. This comes at a price, as WHCA*'s search times are found to be too long for our use case, where even a slight delay is noticeable to the players. Despite this, we think MAPF has potential in game development. Discoveries presented in this work can be helpful for future research and game development.20222022-10-10 10:00:00Magistrsko delo/naloga141866VisID: 34641COBISS_ID: 125573635sl