Artificial intelligence‎ > ‎Pathfinding‎ > ‎Navmesh‎ > ‎

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