Most components and subsystems of Autodesk Navigation rely on NavData: a set of data structures within the World that provide an abstract representation of the geometry of your game terrain, modeled to support high-performance spatial queries and pathfinding.

NavData is a crucial resource for the AI in your game. It informs your characters of the places they can and cannot move, and ultimately provides a basis for the decisions and movements they make. As such, it is crucial that you use NavData that accurately maps your game world in order to get the most out of Autodesk Navigation.

This chapter provides detailed information on NavData, and how to effectively generate NavData for your game world that suits the demands of your project.

Your characters use NavData to determine what areas of the game world are navigable for them. Therefore, NavData must necessarily reflect the physical attributes and movement capabilities of the characters who are intended to use it. Characters with different dimensions, or that move in very different ways, may require very different NavData. For example, a representation of the places that a human being can travel in a world will not be a valid representation of the places that a car or a dinosaur could move in the same world.

If you have different kinds of characters with different proportions, you may need to have different sets of NavData to represent their movement opportunities. If their proportions are close enough, and if it causes no strange trajectories in your game at runtime, you may be able to save memory by making both types of characters share one set of NavData. However, if you do so, you should always generate for the larger character.

See also Using Multiple Databases.

The following sections introduce the main types of NavData used in Autodesk Navigation: NavMeshes and NavGraphs.

A NavMesh is a representation of the areas in the static 3D world that are accessible to a character that walks on the ground. The NavMesh consists of a set of connected triangles that define the area in which the character is allowed to move around freely (said to be "inside the NavMesh"). Any areas that are not covered by NavMesh triangles are said to be "outside the NavMesh". Under normal circumstances Autodesk Navigation will not direct your characters outside of the NavMesh during their path following (except through the use of NavGraphs; see below).

The following image shows a visual representation of a NavMesh. Note that the colored triangles of the NavMesh form a surface that fills the walkable areas of the terrain. Note also that the boundaries of the NavMesh are a short distance away from the walls and static obstacles. This distance is roughly equal to half the width of the character using the NavMesh. Preventing the center of the character (where its position is assumed to be) from moving any closer than this to the static obstacles avoids the possibility of collision with the static obstacles.

Although the NavMesh is essentially a two-dimensional surface, it fully supports areas of great three-dimensional complexity with multiple floors, spiral staircases, etc.

The Autodesk Navigation pathfinding and path following systems use NavMeshes primarily to determine the location of static and dynamic objects in the terrain, and to determine what obstacles if any lie in the direct path between two points. This is particularly useful when a character attempts to smooth its path, or find a shortcut to a point farther along its path. Without the NavMesh, a character has no way of knowing whether an obstacle intervenes between itself and another location in the world except by conducting expensive ray casts and collision tests against the physics world. Using the NavMesh significantly increases the performance of the pathfinding system, as it reduces the number of these expensive tests that bots and other components need to perform in your game world.

You can also conduct your own high-performance spatial queries against the NavMesh, to make use of its optimized spatialization in your own code for your own purposes. See Using the Query System.

Note that the triangles of the NavMesh in the image above are colored differently in different areas. These colors represent different user-defined data values, known as NavTags, that have been assigned to the triangles to represent different types of terrain. You can take advantage of these tags when setting up pathfinding for your characters, to specify the kinds of terrain that your characters can and cannot traverse, or you can associate them to smart objects that take control of characters' path following within those areas. See Tagging with Custom Data.

The triangles in the NavMesh lie roughly at the same altitude as the ground. However, by default their altitude is intended only as an approximation of the ground altitude, good enough to distinguish multiple overlapping navigable areas like multiple floors in a building. The NavMesh may even pass below the ground in some areas.

If you want to rely on the altitude of your NavMesh for other purposes, such as for clamping your characters to the ground without using a physics system, you can configure the NavData generation system to increase the accuracy with which the NavMesh follows the altitude of the terrain mesh. For details, see Increasing Altitude Precision.

NavGraphs are spatial structures that consist of vertices located at positions in 3D space, connected by edges. You can use them to create new topological connections between points in disconnected areas of the NavMesh, such as elevators, jumping spots, or teleporters. NavGraphs are typically linked to smart objects that control your characters' ability to traverse its edges, and that may take complete control of the character's motion while it traverses the edges. See also Creating Smart Objects.

NavGraph edges can cross the boundaries of the NavMesh, and they may contain vertices that lie outside of the NavMesh. They may be as simple as a single edge between two vertices, or they may form complex networks of off-NavMesh navigation possibilities like ziplines.

For instance, in the following image, the arrows represent NavGraph edges that connect points on the ground to points on the roof. These can be associated with a smart object that manages path following for any characters that plan a path along one of the edges, by playing a jump animation or computing a custom trajectory.

NavGraphs are an optional enhancement to the NavMesh, which you create and add to your NavData when you need them for a special movement type or smart object in your game. The NavData generation system never creates NavGraphs automatically on its own. You create them yourself, either during the data generation process (typically in a post-processing phase that you run after generating the NavMesh for a sector), or dynamically at runtime. See also Creating NavGraphs.

The NavMesh and NavGraphs described above are static data structures that you pre-generate for your terrains and load into memory at runtime. However, the static NavData can be enriched and modified within each World during the course of your game by dynamic elements like TagVolumes, BoxObstacles and CylinderObstacles.

See Using Dynamic Obstacles and TagVolumes.