Map Marker: a Multi-Agent Pathfinder for Cohesive Groups in Real-Time Strategy Games - Rivas, Enrique Wicks; Souza, Rodrigo (Anais do Simpósio Brasileiro de Jogos e Entretenimento Digital (SBGames), 2021)
Multi-agent pathfinding algorithms are essential to studies on graph navigation with more than one agent. Their importance is especially evident in Real-Time Strategy (RTS) games, as even modern implementations can still lead to unintended agent behaviors that cause frustration. One such problem occurs if a group of agents breaks military formation when given the order around a big obstacle, becoming more vulnerable to enemies. To mitigate this problem, we propose Map Marker, an extension of the A* algorithm that takes in concepts from ant colony optimization to improve group cohesion. To evaluate the new algorithm we constructed three scenarios that stress the separation of groups. These scenarios were simulated with different parameters and the best results were then recreated inside the engine of the game StarCraft II and compared to A*. As a result, we found that the new algorithm effectively maintained group cohesion in all scenarios, resulting in fewer casualties and less time needed to reach the destination when the group is ambushed by enemies, in addition to being 2.8 faster than A* when computing multiple paths.