Map Marker: a Multi-Agent Pathfinder for Cohesive Groups in Real-Time Strategy Games
Resumo
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.
Referências
A. Nylund and O. Landfors, “Frustration and its effect on immersion in games: A developer viewpoint on the good and bad aspects of frustration,” M.S. thesis, Dept. Informatics, Umea Univ., Umea, Sweden, 2015.
R. Lara-Cabrera, C. Cotta, and A. J. Fernandez-Leiva, “A review of computational intelligence in RTS games,” in 2013 IEEE Symposium on Foundations of Computational Intelligence (FOCI), 2013, pp. 114–121.
P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.
E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 269–271, Dec. 1959.
F. Pentikainen and A. Sahlbom, “Combining influence maps and potential fields for AI pathfinding,” M.S. thesis, Dept. Computer Science, Blekinge Institute of Technology, Karlskrona, Sweden, 2019.
X. Cui and H. Shi, “A*-based pathfinding in modern computer games,” Int. Journal of Computer Science and Network Security, vol 11, no. 1, pp. 125–130, Jan. 2011.
A. Botea, M. Muller, and J. Schaeffer, “Near optimal hierarchical pathfinding,” J. Game Dev., vol. 1, no. 1, pp. 1-30, 2004.
C. W. Reynolds, “Flocks, herds and schools: A distributed behavioral model,” in ACM SIGGRAPH Computer Graphics, vol. 21, no. 4, July 1987, pp. 25-34.
E. Emerson, “Crowd pathfinding and steering using flow field tiles,” in Game AI Pro 360, S. Rabin, Ed., Boca Raton, FL, USA: h. 23, pp. CRC Press, 2019, pp. 307-316.
M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29–41, 1996.
N. Sturtevant, “Benchmarks for grid-based pathfinding,” Transactions on Computational Intelligence and AI in Games, vol 4, no. 2, pp. 144-148, 2012.
M. D. B. S. Supriyadi, S. M. S. Nugroho, and M. Hariadi, “Fuzzy coordinator based AI for dynamic difficulty adjustment in StarCraft 2,” in 2019 Int. Conf. Artif. Intell. and Inf. Technol. (ICAIIT), 2019, pp. 322–326.
L. Critch and D. Churchill, “Combining influence maps with heuristic search for executing sneak-attacks in RTS games,” in 2020 IEEE Conference on Games (CoG), 2020, pp. 740–743.
A. Geramifard, P. Chubak, and V. Bulitko, “Biased cost pathfinding,” in Proceedings of the Second AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE’06), 2006, pp. 112–114.
J. Hagelback, “Hybrid pathfinding in StarCraft,” IEEE Transactions on Computational Intelligence and AI in Games, vol.8, no. 4, pp. 319–324, 2015.
