Navmesh Generation

The navigation mesh can be generated automatically from the geometry in the game.

Surface Merging

Take all the surfaces that is walkable and simplify them as far as possible by merging them with each other to convex polygons. Cull away the really small nodes and then take all things that block out the navmesh. Subdivide all polygons it covers, remove the ones below them and then merge the navmesh polygons again.

• Generating 2D Navmeshes - 2014
• Automatic Generation of Suboptimal NavMeshes - 2011
• Fredrik Farnstrom, Improving on Near-Optimality: More Techniques for Building Navigation Meshes. AIGPW3 p113-p128. - 2006.
• Paul Tozour, Building a near-optimal navigation mesh, AIGPW1 p171-p185. - 2002.

Voxelization

This system takes all the walkable and blocking surfaces and sample them to voxels. Then these voxels are used to calculate walkable areas and turn them into navmesh polygons. One common lib for this is Recast and a description of how it works can be found at the NMGen Study homepage.

• Building and Traversing Navigation Meshes with Recast and Detour - 2009
• Navigation Mesh Generation via Voxelization and Watershed Partitioning - 2009
• Crowds In A Polygon Soup Next-Gen Path Planning - 2006

Reference

• Unreal 3: Navigation Mesh Reference
  • Automatic Navigation Mesh Generation in Configuration Space - 2013
  • Improving on Near-Optimality: More Techniques for Building Navigation Meshes, AIGPW3 p112-128. - 2006.