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.

Background. Neural Networks have mainly been used in behavior and gameplayrelated areas in games, but they have not yet been used specifically for intersection testing. This thesis explores the possibility to use deep neural networks for intersection testing of two 3D meshes. Objectives. The main goal of the thesis is to train a Deep Neural Network that can be used to replace traditional intersection test algorithms by having similar accuracy and a faster execution time. Methods. The research methods used in this thesis are implementation and experimentation. The deep neural network is trained using TensorFlow. Two different mesh generation techniques are implemented, one generating heightmaps and one generating planets. The two mesh types are combined to test all combinations of generated meshes. Attempts to make the network as general as possible are done through importance sampling to expose the network to tricky situations. A test application is developed where the intersection testing can be performed and compared to the Separating Axis Theorem (SAT). Heatmaps are also created to see how accurate the network is. Results. The results show that the network is accurate at classifying intersection between meshes similar to the ones it trained on. However, the network lacks generality and has bad accuracy if new meshes are introduced. The measured execution times show that the trained Deep Neural Network is 15.6 times as fast as a singlethreaded implementation of the SAT and 2.3 times as fast as the multi-threaded SAT. Conclusions. The trained network can be used as an early exit intersection test before using more expensive algorithms. The faster intersection testing can be useful in game physics by allowing faster classification of which meshes need to be tested for collisions. However, the main outcome is the shown potential for future work in the area including training a more general network, allowing variable mesh sizes, and providing information for solving collision responses. / Bakgrund. Neurala Nätverk har främst använts för beteende- och spelmekanikrelaterade områden inom spel, men de har ännu inte använts för genomskärningstester. Det här examensarbetet utförskar möjligheten att använda djupinlärning för att utföra genomskärningstester mellan två tredimensionella spelobjekt. Syfte. Huvudmålet med det här examensarbetet är att träna ett djupinlärt neuralt nätverk som kan ersätta traditionella genomskärningstestalgoritmer genom likvärdig precision och snabbare exekveringstid. Metod. Forskningsmetoderna som användes under examensarbetet är implementation och experimentation. Det djupinlärda neurala nätverket tränas med TensorFlow. Två olika spelobjektsgenereringsmetoder implementeras, där den ena genererar heightmaps och den andra genererar planeter. De två objekttyperna kombineras så att alla kombinationer av spelobjekt kan testas. För att göra nätverket så generellt som möjligt används importance sampling som utsätter nätverket för svåra situationer. Ett testprogram utvecklas där genomskärningstester kan utföras och jämföras mot Separating Axis Theorem (SAT). Grafer av typen heatmaps skapas också för att visa hur hög precision nätverket har. Resultat. Resultaten visar att nätverket har hög precision vid klassificering av spelobjekt liknande de som den tidigare har tränat på. Nätverket har sämre precision när nya spelobjekt introduceras. De uppmätta exekveringstiderna visar att det neurala nätverket är 15.6 gånger så snabbt som singeltrådade implementationen av SAT och 2.3 gånger så snabbt som den flertrådade SAT-implementationen. Slutsatser. Det tränade nätverket kan användas som ett tidig avbrott innan en dyrare algoritm används. Den snabbare genomskärningstestningen kan vara användbar i spelfysik eftersom den tillåter snabbare klassificering av vilka spelobjekt som behöver testas för kollision. Det huvudsakliga utfallet är den visade potentialen för vidare forskning inom området vilket inkluderar träning av ett mer generellt nätverk, möjlighet att variera spelobjektens storlek samt ge information för att kunna lösa kollisioner.