Multi-Agent Pathfinding in a Real-Time Strategy Game

Antešić, Ivan (author), Sadikov, Aleksander (mentor)

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.

• Language: English
• Keywords: multi-agent pathfinding, real-time strategy games, heuristic search, WHCA*
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2022
• PID: 20.500.12556/RUL-141866
• COBISS.SI-ID: 125573635
• Publication date in RUL: 10.10.2022

Secondary language

• Language: Slovenian
• Title: Iskanje poti za več agentov za strateško igro v realnem času

Abstract

Problem iskanja poti za več agentov (angl. kratica MAPF) rešimo tako, da poiščemo pot brez trkov za vsakega posameznika v skupini agentov. V preteklih letih so raziskovalci razvili več MAPF algoritmov, za katere trdijo, da so primerni za strateške igre v realnem času. Vendar obstaja razcep med znanstvenimi raziskavami in praktičnim razvojem iger. Algoritmi so predstavljeni in testirani brez upoštevanja ključnih lastnosti kompleksnega okolja iger. Da bi dognali, ali je MAPF pristop res primeren za iskanje poti v igrah, smo implementirali pomemben MAPF algoritem, WHCA*, v obstoječem igralnem pogonu za strateške igre v realnem času. Nato smo ga primerjali s pristopom iskanja poti za enega agenta, ki ga uporablja večina iger v industriji. Eksperimentalni rezultati kažejo, da naša implementacija WHCA* algoritma znatno izboljša kvaliteto poti in premikanje agentov, lahko prepreči zastoje ter reši težke primere, ki jih iskanje poti za enega agenta ne more. Toda časi iskanja poti za WHCA* so predolgi za naš primer, kjer je že majhen zastoj očiten igralcem. Kljub temu menimo, da MAPF ima potencial v razvoju iger. Odkritja, predstavljena v tem delu, lahko pripomorejo k nadaljnjim raziskavam in razvoju iger.

• Keywords: iskanje poti za več agentov, strateške igre v realnem času, hevristično preiskovanje, WHCA*