This thesis details the implementation of a navigation mesh within the interior space planning software CET Designer. The motivation for this is to investigate whether a navigation mesh is a suitable alternative to its current path finding solution which is based on a waypoint graph. An empirical analysis between the navigation mesh and the waypoint graph was also conducted. A navigation mesh is successfully implemented and an alternative triangulation method is also tested. The alternative method which is referred to as "narrowest first-ear clipping" seems to create a navigation mesh that produces slightly shorter paths than a navigation mesh that utilizes an arbitrary triangulation method. It is argued that the navigation mesh alleviates much work from the user since it requires less user input. The mesh is also able to generate paths between any two given points within it. This makes it much more dynamic than the waypoint graph. The conducted analysis shows that the navigation mesh seems to generate paths that are generally shorter than the waypoint graph. The path generation time for the navigation mesh is on average slower than the waypoint graph. We failed to provide an environment where the navigation mesh was faster on average than the waypoint graph. However, the time difference between the navigation mesh and the waypoint graph seemed to reduce as the test environment size increased.

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.