Combining Influence Maps and Potential Fields for AI Pathfinding

This thesis explores the combination of influence maps and potential fields in two novel pathfinding algorithms, IM+PF and IM/PF, that allows AI agents to intelligently navigate an environment. The novel algorithms are compared to two established pathfinding algorithms, A* and A*+PF, in the real-time strategy (RTS) game StarCraft 2. The main focus of the thesis is to evaluate the pathfinding capabilities and real-time performance of the novel algorithms in comparison to the established pathfinding algorithms. Based on the results of the evaluation, general use cases of the novel algorithms are presented, as well as an assessment if the novel algorithms can be used in modern games. The novel algorithms’ pathfinding capabilities, as well as performance scalability, are compared to established pathfinding algorithms to evaluate the viability of the novel solutions. Several experiments are created, using StarCraft 2’s base game as a benchmarking tool, where various aspects of the algorithms are tested. The creation of influence maps and potential fields in real-time are highly parallelizable, and are therefore done in a GPGPU solution, to accurately assess all algorithms’ real-time performance in a game environment. The experiments yield mixed results, showing better pathfinding and scalability performance by the novel algorithms in certain situations. Since the algorithms utilizing potential fields enable agents to inherently avoid and engage units in the environment, they have an advantage in experiments where such qualities are assessed. Similarly, influence maps enable agents to traverse the map more efficiently than simple A*, giving agents inherent advantages. In certain use cases, where multiple agents require pathfinding to the same destination, creating a single influence map is more beneficial than generating separate A* paths for each agent. The main benefits of generating the influence map, compared to A*-based solutions, being the lower total compute time, more precise pathfinding and the possibility of pre-calculating the map.Denna rapport utforskar kombinationen av influence maps och potential fields med två nya pathfinding algoritmer, IM+PF och IM/PF, som möjliggör intelligent navigation av AI agenter. De nya algoritmerna jämförs med två existerande pathfindingalgoritmer, A* och A*+PF, i realtidsstrategispelet StarCraft 2. Rapportens fokus är att utvärdera de nya algoritmernas pathfindingförmåga samt realtidsprestanda i förhållande till de två existerande algoritmerna, i sex olika experiment. Baserat på resultaten av experimenten presenteras generella användningsområden för algoritmerna tillsammans med en bedömning om algoritmerna kan användas i moderna spel. De fyra pathfindingalgoritmerna implementeras för att jämföra pathfindingförmåga och realtidsprestanda, för att dra slutsatser angående de nya algoritmernas livsduglighet. Med användningen av StarCraft 2 som ett benchmarkingvertyg skapas sex experiment där olika aspekter av algoritmerna testas. Genereringen av influence maps och potential fields i realtid är ett arbete som kan parallelliseras, och därför implementeras en GPGPU-lösning för att få en meningsfull representation av realtidsprestandan av algoritmerna i en spelmiljö. Experimenten visar att de nya algoritmerna presterar bättre i både pathfindingförmåga och skalbarhet under vissa förhållanden. Algoritmerna som använder potential fields har en stor fördel gentemot simpel A*, då agenterna kan naturligt undvika eller konfrontera enheter i miljön, vilket ger de algoritmerna stora fördelar i experiment där sådana förmågor utvärderas. Influence maps ger likväl egna fördelar gentemot A*, då agenter som utnyttjar influence maps kan traversera världen mer effektivt. Under förhållanden då flera AI agenter ska traversera en värld till samma mål kan det vara förmånligt att skapa en influence map, jämfört med att generera individuella A*-vägar till varje agent. De huvudsakliga fördelarna för de influence map-baserade algoritmerna är att de kräver lägre total beräkningstid och ger en merexakt pathfinding, samt möjligheten att förberäkna influence map-texturen