Game Development Reference
In-Depth Information
Chapter 11. Advanced
NavMesh
Generation
Navigation mesh generation is one of the most important topics in game AI. We have
been using navigation meshes in almost all the chapters in this topic, but haven't
looked at them in detail. In this chapter, we will provide a more detailed overview of
navigation meshes and look at the algorithm used to generate them. Then, we'll look
at different options of customizing our navigation meshes better.
In this chapter, you will learn about:
• The working of navigation mesh generation and the algorithm behind it
• Advanced options for customizing navigation meshes
• Creating advanced navigation meshes with RAIN
An overview of a NavMesh
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.
