[This is preliminary documentation and is subject to change.]

The navigation mesh is the primary data model for the navigation system. The only user component that deals directly with the mesh on a regular basis is the component that is responsible for creating the mesh and managing its state. Normal navigation clients, the one's needing to perform pathfinding and such, rarely if ever interact directly with the navigation mesh.

Core Class: Navmesh

The Data Model

Tiles

At the core of the navigation mesh is the tile. Tiles hold the vast majority of structural and state information. In fact, the Navmesh class is little more than a tile manager. It may consist of a single tile, or many tiles laid out in a grid that can be swapped in and out at runtime.

The tile based structure of the navigation mesh adds a lot of flexibility. As mentioned, tiles can be swapped in and out at runtime. This means that the mesh can represent a large area, but not all tiles have to be loaded and active, reducing the mesh's memory footprint. This also allows for a situation where individual tiles can be rebuilt without the need to rebuild the entire mesh.

Structural Elements

The tile's structural data is what defines the navigation graph used for pathfinding. It consists of two types of elements: Polygons and off-mesh connections.

The core of the structure is a mesh of convex polygons with between three and MaxAllowedVertsPerPoly vertices. This mesh is in the same format as NMGen's PolyMesh structure, and usually represents an abstraction of a scene's static geometry.

Off-mesh connections are optional. They consist of two connected endpoints, at least one of which resides within a polygon in the polygon mesh. Off-mesh connections are added to the navigation graph as a single edge and represent special travel routes not defined by scene geometry. Think: The route an agent travels if it jumps over a railing that normally blocks movement.

State Data

Tiles also contain state data. This data is associated with individual polygons and off-mesh connections. State data includes area and flags.

Areas are used to associate traversal cost to structural elements. This effects pathfinding. For example, the area representing swampland can have a higher cost than the area representing smooth surfaces such as meadowland.

Flags can be used to control when a structural element is traversable. For example, a flag can be set on the polygon below a door to indicate that it is closed and locked. Or a flag can indicate that only agents of a particular type are allowed to traverse the element.

It is important to note that areas and flags have no meaning within the navigation mesh itself. The interpretation of the values is dependant on the NavmeshQueryFilter used by each navigation client. For example: One filter may define a cost of 10 for area id 5, while another may define a cost of 2 for the same area. One flag may be set when a door is closed with one filter checking for the flag during pathfinding, while another filter, used by a ghost, ignores the flag completely.

Structure Versus State

Why is it important to know the difference between structural elements and state data?

The first reason is that it is possible to save and load state separately from structure. One common use case is to have a serialized version of the full navigation mesh that represents its default state. Then serialized versions of various states, such as the last runtime state, are used to overwrite the default state as needed.

The main limitation is that a state is only valid for a particular structure. So you can't, for example, save the state, change the tile structure, then load the original state into the new structure.

The second reason for understanding the difference between structure and state has to to with tile and polygon references...

Tile and Polygon References

The last bit of information needed to understand the navigation mesh is the concept of tile and polygon references. These values are one of the few data types that are defined by the navigation mesh rather than the tiles within the mesh. It is important to understand what references are because they are used by various classes to automatically invalidate pathfinding data if the structure of a navigation mesh changes.

Essentially, tile and polygon references are unsigned integer 'handles' to structural elements within a navigation mesh. Tile references are rarely used by navigation clients, while polygon references are all over the place. Polygon references are unique for the navigation mesh, so they are useful for easily identifying a polygon without needing to know which tile it belongs to. Despite the name, polygon references can refer to a either a polygon or an off-mesh connection.

References can become invalid. If they are used after they are invalidated, then methods will return a failure status. Polygon references are based on the tile reference. So they will be invalidated whenever their associated tile reference is invalidated.

Structural changes govern the life of a reference. Changing the configuration of a navigation mesh or the internal structure of a tile will invalidate all associated references.

References are preserved during tile state changes such as changes flags and areas. They are also preserved during normal runtime loading and unloading of tiles, and during normal serialization/de-serialization of a navigation mesh.

Creating a Navigation Mesh

There are various pipelines for creating a navigation mesh. If you are using Unity, the Unity extensions make it easier. Otherwise, the basic steps are as follows:

Generate packed tile data:

  1. Generate PolyMesh and PolyMeshDetail data using NMGen.
  2. Optionally create a ConnectionSet. (Off-mesh connections.)
  3. Load the data into a NavmeshTileBuildData object.
  4. Create a NavmeshTileData object from the build data.

The tile's structure and default state is now locked into a packed data format that is ready to be loaded into a navigation mesh.

Note:

Using the NavmeshTileBuildData class directly can be a bit daunting. The GetBuildData(BuildContext, Int32, Int32, PolyMeshData, PolyMeshDetailData, ConnectionSet, Boolean) utility method provides a standard way of creating the build data.

Create a navigation mesh:

Single tile navigation meshes are created using the the single step Create(NavmeshTileBuildData, Navmesh%) method.

Multi-tile navigation meshes are created then loaded using multiple methods. Use the Create(NavmeshParams, Navmesh%) method to initialize an empty mesh. then add tile data using the AddTile(NavmeshTileData, UInt32, UInt32%) method.

Navigation Mesh Serialization

The Navmesh class supports byte serialization using the GetSerializedMesh()()()() method. This saves the entire mesh.

It is possible to serialize state separately from structure on a tile-by-tile basis. Get the tile from the mesh using the GetTile(Int32) method, then use the GetState(array<Byte>[]()[][]) and SetState(array<Byte>[]()[][]) methods.

See Also