Game Development Reference
In-Depth Information
In recent years, there has been more research in automatic navigation mesh gener-
ation.
There are many approaches to automatic navigation mesh generation, but the most
popular is
Recast
, originally developed and designed by Mikko Monomen. Recast
takes in level geometry and a set of parameters that define the character, such as
the size of the character and how big of steps it can take, and then does a multi-
pass approach to filter and creates the final NavMesh. The most important phase of
this is
voxelizing
the level based on an inputted cell size. This means the level geo-
metry is divided into voxels (cubes), creating a version of the level geometry where
everything is partitioned into different boxes called cells. Then, the geometry in each
of these cells is analyzed and simplified based on its intersection with the sides of
the boxes and is culled based on things such as the slope of the geometry or how
big a step height is between geometry. This simplified geometry is then merged and
triangulated to make a final navigation mesh that can be used by the AI system.
Note
The source code and more information on the original C++ implementation of
Recast is available at
https://github.com/memononen/recastnavigation
.
