To use navigation meshes effectively, also referred to as NavMeshes, the first things we need to know are what exactly navigation meshes are and how they are created. A navigation mesh is a definition of the area an AI character can travel to in a level. It is a mesh, but it is not intended to be rendered or seen by the player; instead, it is used by the AI system. A NavMesh usually does not cover all the area in a level (if it did, we wouldn't need one) as it's just the area a character can walk. The mesh is also almost always a simplified version of the geometry. For instance, you could have a cave floor in a game with thousands of polygons along the bottom that show different details in the rock; however, for the navigation mesh, the areas would just be a handful of very large polygons that give a simplified view of the level. The purpose of a navigation mesh is to provide this simplified representation to the rest of the AI system as a way to find a path between two points on a level for a character. This is its purpose; let's discuss how they are created.

It used to be a common practice in the games industry to create navigation meshes manually. A designer or artist would take the completed level geometry and create one using standard polygon mesh modeling tools and save it. As you might imagine, this allowed for nice, custom, efficient meshes, was also a time sink, as every time the level changed, the navigation mesh would need to be manually edited and updated. In recent years, there has been more research in automatic navigation mesh generation.

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