A Navigation Mesh-Based Pathfinding Implmentation in CET Designer : An Alternative to a Waypoint Graph-Based Solution

Sammanfattning: 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.