Title: Pathfinding within a Hierarchical Navmesh Based on Geometry Analysis Author: Miroslav Chomut Department / Institute: Department of Software and Computer Science Education Supervisor of the master thesis: Mgr. Tomáš Plch, Media and Communications Office Abstract: Pathfinding is a common problem in the computer science dealing with navigation from a starting point to a destination point. Common algorithms today are mostly based on A* search on a graph representation of navigated world. Another common approach is creation of navigation structure of convex navigation meshes and navigating on them. Our goal is to propose pathfinding algorithm on hierarchical navigation meshes, based on the terrain geometry, which benefits from complexity of hierarchical search yet provides paths comparable in length to reference ones. This thesis analyses and describes our proposed approach of navigation including generation of the navigation structure. Keywords: navmesh, pathfinding, A*, hierarchy, terrain analysis, geometry

The current state of 3D path-planning leaves room for improvement. To navigate a 3D environment, techniques which were developed for 2D navigation are used and slightly adapted to generate convincing motion. However, these techniques often constrict the motion to a single plane. This constriction is not only a limitation, but also increases the error. We created a new method to compute a path in a 3D world without a planar constraint. We will discuss the computation of a Navigation Volume Network (NavNet), and how it finds a path. A NavNet is the 3D generalization of NavMeshes, and holds boundary and connection information which is utilized when planning a path for motion. Similar to how NavMeshes allow path-planning by simplifying the ground meshes, the NavNet simplifies the search space by approximating the 3D world through sampling. / Thesis / Master of Applied Science (MASc)

The usage of navigation meshes for path planning in games and otherdomains is a common approach. One type of navigation mesh that recently has beendeveloped is the Local Clearance Triangulation (LCT). The overall aim of the LCT isto construct a triangulation in such a way that a property called theLocal Clearancecan be used to calculate a path in a more efficient and cheap way. At the time ofwriting the thesis there only exists one solution that creates an LCT, this solution isonly using the CPU. Since the process of creating an LCT involves the insertion ofmany points and edge flips which only affects a local area it would be interesting toinvestigate the potential performance gain of using the GPU.Objectives.The objective of the thesis is to develop a GPU version based on thecurrent CPU LCT solution and to investigate in which cases the proposed GPU al-gorithm performs better.Methods.A GPU version and a CPU version of the proposed algorithm has beendeveloped to measure the performance gain of using the GPU, there are no algorith-mic differences between these versions. To measure the performance of the algorithmtwo tests have been constructed, the first test is called the Object Insertion test andmeasures the time it takes to build an LCT using generated test maps. The sec-ond test is called the Internal test and measures the internal performance of thealgorithm. A comparison between the GPU algorithm with an LCT library calledTriplanner was also done.Results.The proposed algorithm performed better on larger maps when imple-mented on a GPU compared to a CPU implementation of the algorithm. The GPUperformance compared to the Triplanner was faster in some of the larger maps.Conclusions.An algorithm that builds an LCT from scratch is presented. Theresults show that using the proposed algorithm on the GPU substantially increasesthe performance of the algorithm compared to when implementing it on a CPU.

The usage of navigation meshes for path planning in games and otherdomains is a common approach. One type of navigation mesh that recently has beendeveloped is the Local Clearance Triangulation (LCT). The overall aim of the LCT isto construct a triangulation in such a way that a property called theLocal Clearancecan be used to calculate a path in a more efficient and cheap way. At the time ofwriting the thesis there only exists one solution that creates an LCT, this solution isonly using the CPU. Since the process of creating an LCT involves the insertion ofmany points and edge flips which only affects a local area it would be interesting toinvestigate the potential performance gain of using the GPU.Objectives.The objective of the thesis is to develop a GPU version based on thecurrent CPU LCT solution and to investigate in which cases the proposed GPU al-gorithm performs better.Methods.A GPU version and a CPU version of the proposed algorithm has beendeveloped to measure the performance gain of using the GPU, there are no algorith-mic differences between these versions. To measure the performance of the algorithmtwo tests have been constructed, the first test is called the Object Insertion test andmeasures the time it takes to build an LCT using generated test maps. The sec-ond test is called the Internal test and measures the internal performance of thealgorithm. A comparison between the GPU algorithm with an LCT library calledTriplanner was also done.Results.The proposed algorithm performed better on larger maps when imple-mented on a GPU compared to a CPU implementation of the algorithm. The GPUperformance compared to the Triplanner was faster in some of the larger maps.Conclusions.An algorithm that builds an LCT from scratch is presented. Theresults show that using the proposed algorithm on the GPU substantially increasesthe performance of the algorithm compared to when implementing it on a CPU.

The usage of navigation meshes for path planning in games and otherdomains is a common approach. One type of navigation mesh that recently has beendeveloped is the Local Clearance Triangulation (LCT). The overall aim of the LCT isto construct a triangulation in such a way that a property called theLocal Clearancecan be used to calculate a path in a more efficient and cheap way. At the time ofwriting the thesis there only exists one solution that creates an LCT, this solution isonly using the CPU. Since the process of creating an LCT involves the insertion ofmany points and edge flips which only affects a local area it would be interesting toinvestigate the potential performance gain of using the GPU. The objective of the thesis is to develop a GPU version based on thecurrent CPU LCT solution and to investigate in which cases the proposed GPU al-gorithm performs better. A GPU version and a CPU version of the proposed algorithm has beendeveloped to measure the performance gain of using the GPU, there are no algorith-mic differences between these versions. To measure the performance of the algorithmtwo tests have been constructed, the first test is called the Object Insertion test andmeasures the time it takes to build an LCT using generated test maps. The sec-ond test is called the Internal test and measures the internal performance of thealgorithm. A comparison between the GPU algorithm with an LCT library called Triplanner was also done. The proposed algorithm performed better on larger maps when imple-mented on a GPU compared to a CPU implementation of the algorithm. The GPU performance compared to the Triplanner was faster in some of the larger maps. An algorithm that builds an LCT from scratch is presented. Theresults show that using the proposed algorithm on the GPU substantially increasesthe performance of the algorithm compared to when implementing it on a CPU.

I nästan alla moderna datorspel så återfinns datorstyrda karaktärer, vilka behöver kunna navigera i spelvärlden. Dessa karaktärer kan vara olika typer av fiender i ett förstapersonskjutarspel, eller motståndare och medhjälpare i ett sportspel (exempelvis fotboll- eller rallyspel) med mera. Det finns många tekniker för att realisera vägplanering och det kan vara stora skillnader, både prestandamässiga och funktionella, mellan dem. Detta arbete jämför två olika sökrymdsrepresentationer för vägplanering, nämligen vägpunktsgrafer och navigationsnät, där sökrymderna automatgenererats. Jämförelsen görs med ett experiment och avser såväl prestanda (tids- och minneskostnad) som funktionalitet (optimal väg och antal svängar). Experimentmiljön stödjer godtyckliga vägar och ger detaljerad statistik för en noggrann jämförelse av vägplaneringsteknikerna. Arbetet visar på att navigationsnätet presterar bäst vad gäller funktionalitet. Vad gäller prestanda så presterar navigationsnätet generellt sett bäst, men vägpunktsgrafen kan ge bättre prestanda om nodavståndet hålls relativt högt. Det finns också många möjligheter att vidareutveckla arbetet, exempelvis förfina vägarna och kombinera vägplaneringsteknikerna med robotik.

Artificiell intelligens (AI) är en stor del i dagens datorspel. För att få inblick i komplexiteten runt AI i spelutveckling och för att förstå delar som AI består av har detta projekt genomförts. Målet var att skapa en AI-motor från grunden med bra grundplattform som är enkel att bygga vidare på. Innan projektet startade utfördes en förundersökning där olika alternativ för kartrepresentationer och grafsökningsalgoritmer togs fram. Utvecklingen av AI-motorn har haft ett starkt beroende till projektet där en spelmotor utvecklats av Niklas Ekman och Christian Mesch. Detta projekt har utförts enligt den agila systemutvecklingsmetoden Scrum. Ett versionshanteringssystem har använts för att enkelt kunna dela källkod mellan projekten. AI-motorn har utvecklats i C++ och för operativsystemen Ubuntu och OSX. AI-motorn består av fyra huvuddelar; logik, navigering, kommunikation och AI-objekt. Logiken är hjärnan i AI-motorn, navigeringen använder sig av navmesh som kartrepresentation och A*-algoritmen är den grafsökningsalgoritm som har valts. Kommunikation sker mellan AI-motorn och spelmotorn för att kunna dela på funktionalitet. AI-objekten är främst informationsklasser som t.ex. håller reda på antalet registrerade datorstyrda spelare. Valet av metod för kartrepresentation avgjordes av att navmesh enkelt kunde genereras automatiskt med hjälp av verktyg vilket var svårare för de andra alternativen. A* valdes som grafsökningsalgoritm eftersom den gav en korrekt väg med minst antal beräkningar. AI-motorn uppfyller de krav som ställdes innan utvecklingen påbörjades och är en bra grund för att lätt kunna utöka motorn med mer avancerad funktionalitet, men det finns så klart förbättringar som kan göras.