Joran Vandenbroucke

Master Thesis: Minimum Distance Encoding for Recast Navmesh

Abstract: A navigation mesh (or Navmesh) is a data structure that allows characters to plan and traverse paths through 2D and 3D environments. Most Navmesh generators create a separate Navmesh for each fixed agent radius by subtracting that radius from the traversable space. Methods that generate a unified Navmesh are currently too limited to be used in a standard game development workflow. In this thesis, we work towards letting a state-of-the-art Navmesh (Recast) support arbitrary agent radii. For this, we have defined a new concept, Local Clearance Minimum (LCM), a specific line segment that allows us to unify all Navmeshes into one. We show how to extract all LCMs of an environment in Recast using a new watershed implementation. We show that the performance of this new watershed algorithm is on par with Recast’s built-in watershed algorithm. We also show that the algorithm can extract most LCMs accurately, but there are some limitations due to the current (voxel-based) Recast pipeline. Because these issues can be resolved in future work, we argue that LCMs are a promising practical concept for enabling any-radius pathfinding on a single Navmesh.