Overview

The VR-Forces Navigation Library is a set of classes that allows ground entities to navigate the terrain. It also allows sim engine plugins to perform queries related to navigation. Using the terrain library you can do things such as:

Calculate paths paths between locations on the terrain.
Find specially marked points, such as cover points, within the terrain.
Modify the navigation data to affect path planning.

The VR-Forces simulation engine uses the navigation library to perform path planning for lifeforms and ground vehicles.

Navigation Data

The VR-Forces navigation API is built around the Autodesk Gameware Navigation artificial intelligence middleware. Gameware requires that the terrain be processed into Navigation Data. Navigation Data consists of a topological model of the terrain, tagged with relvant information required for decision making, that allows VR-Forces to compute an optimized path for entity movement.

The Navigation Data (or NavData) used in VR-Forces is made of several parts: the NavMesh, TagVolumes, and NavGraph. Each of these is tagged with specific information VR-Forces reads to understand what type of terrain this represents. The information in these NavTags is used to make cost calculations when finding the best path through the terrain.

To learn more about generating Navigation Data, please see the VR-Forces Users Guide.

NavMesh

The NavMesh is a representation of the triangles in your terrain which has been optimized and tagged during Navigation Generation. As a result, the NavMesh may not exactly match the triangles in the original terrain database. Sometimes simplifications and modifications are required for optimal use by Gameware. Each triangle has a NavTag that indicates what type of terrain is being represented. Often this is an indication of the soil type. See the section on NavTags for further details.

TagVolumes

TagVolumes can be used to represent an obstacle or zone whose extents are integrated into the NavMesh. The area contained within these volumes can be tagged in specific ways, or can be excised from the mesh entirely. During Navigation Generation, VR-Forces creates TagVolumes based on feature data queries that you can configure in the navigation profiles settings (./appData/settings/vrfSim/navigationProfiles.mtl). Generally these queries consist of finding roads, sidewalks, crosswalks, and water. This provides more specific information about these areas than soil type alone can. See the seciton on NavTags for further details.

NavGraph

The NavGraph adds further locations and paths to the NavData on top of the NavMesh. These can be added to the NavData either during generation, or at run-time.

Special locations in the NavData are created using vertices. These vertices can represent anything. The primary use for navigation vertices in VR-Forces is the creation of cover points, which entities can use to find cover from threats.

Additional paths through the terrain can be created using nav edges. These edges can be used to connect locations that are not otherwise connected in the NavMesh, or to create a path between two locations with a new NavTag, which can be used to affect the traversal cost between these points. The primary use for navigation vertices in VR-Forces is to indicate the location of doors. There are also some tactical graphics that can be placed at run-time which will insert nav edges into the NavGraph to create pedestrian paths or crosswalks.

NavTags

A NavTag can be associated with any triangle in the NavMesh, any TagVolume, and any vertex or edge in the NavGraph. The NavTag is what tells VR-Forces what type of terrain is being traversed. This is used to determine path cost, so that the entity may choose the optimal path to the destination. The NavTag is simply an array of 32 bit integers. Currently VR-Forces creates NavTag arrays of up to three integers. See the documentation navDatTag.h for more details on possible nav tag values.

How a NavTag affects path cost is determined by the navigation preference controller as configured in the movement system of the entity. The navigation preference controller may have multiple settings of navigation preferences which can be switched at run-time to alter entity behavior. For instance, humans usually try to avoid crossing roads as much as possible, but have a configured setting to "Ignore Roads" in cases where this does not make sense.

Navigation Areas

In order to generate Navigation Data you must first define the Navigation Areas, or Nav Areas, where the data should be generated. See VR-Forces Users Guide for more details on creating Nav Areas and generating Nav Data. Sim engine plugins that need to perform navigation queries will likely need to find and access the relevant Nav Area for their current location and entity type. The current Nav Areas are loaded and owned by the Nav Area Manager, DtVrfNavAreaManager. Most plugins interested in performing navigation queries only need to be concerned with three methods of DtVrfNavAreaManager: findNavAreaForLocation, findNavAreasForLocation, and findNavAreaForArea. These functions return the Nav Area (or Nav Areas) that match the specified criteria. These functions return one or more pointers to DtNavArea objects. DtNavArea then provides functions for performing queries on the Navigation Data.

For example, perhaps you wish to find the farthest distance a human entity can travel in a given direction without hitting an obstacle in the navigation data (such as a wall or a body of water).

DtVecor resultLocation;
// Find a Nav Area at the location of interest using the "lifeform" profile, the standard
// profile for human entities.
DtNavArea* navArea = simulationServices()->vrfNavAreaManager()->
   findNavAreaForLocation(localPosition, "lifeform");
   
if (navArea)
{
   // Query the Nav Area for the farthest position we can reach if we walk in a specified
   // direction.
   bool reachedMax = false;
   bool foundResult = navArea->findFarthestPositionAlongHeading(
      "lifeform", // some Nav Areas support multiple profiles, so tell it the one we want
      localPosition, // current position
      heading, // the heading (radians) in which we want to travel
      maxDistance, // the max distance (meters) we want to travel
      resultLocation, // the location of the result
      reachedMax); // set to true if we reached maxDistance without hitting an obstacle
}

Some queries, like the one above, can be performed quickly and return a result immediately. Others can take more time, and so they are performed asynchronously. Such queries instead return a pointer to a Nav Area query, DtNavAreaQuery::Ptr. Calling code must retain this pointer and check the query periodically to determine if it has completed.

For example, to initiate a path plan query:

// Find a Nav Area at the location of interest using the "lifeform" profile, the standard
// profile for human entities.
DtNavArea* navArea = simulationServices()->vrfNavAreaManager()->
   findNavAreaForLocation(localPosition, "lifeform");
   
if (navArea)
{
   // Initiate the query. myQuery is a DtNavAreaQuery::Ptr owned by this current object
   // which will be  checked in future ticks.
   myQuery = navArea->findPathToLocation(
      "lifeform", // some Nav Areas support multiple profiles, so tell it the one we want
      localStartPosition, // starting position
      localEndPosition, // ending position
      useAbstractGraphs, // setting to true can speed up long path planning queries
      localPointToAvoid, // optional position to avoid
      avoidanceRadius); // radius (m) to go around point to avoid
}

Then in subsuquent ticks, the owner of this query must check to see if it has completed.

if (myQuery && myQuery->complete())
{
   // Did the query succeed?
   if (myQuery->success())
   {
      // Process the results. A path planning query will return a series of points
      // that define the route the entity should move along to get from the starting
      // location to the destination. What your code does with these locations is
      // up to you.
      std::vector<DtVector> path = myQuery->results();
   }
}

Navigation Interface

Each sim object that interacts with the Nav Areas in some way (e.g. entities that can perform navigation or objects that represent obstacles to navigation) have a Navigation Interface. The Nav Interface provides the object with the API it needs to interract with the Nav Area. There are multiple types of Nav Interface, each of which is a subclass of DtVrfObjectNavInterface.

DtActiveBotNavInterface - Used by entities to navigate the terrain.
DtStaticObstacleNavInterface - Inserts a static obstacle into the Nav Data.
DtDynamicObstacleNavInterface - Inserts an obstace into the Nav Data that is expected to move. Used for remote entities.
DtTagVolumeNavInterface - Creates a Tag Volume in the Nav Mesh, retagging the Nav Data in this location.
DtCoverPointNavInterface - Inserts a cover point into the Nav Graph.
DtNavEdgeNavInterface - Inserts a Nav Edge into the Nav Graph, connecting points in the Nav Mesh.

The Nav Interface most frequently used in plugins is the DtActiveBotNavInterface. Most lifeforms and ground vehicles will use this interface. This interface creates a Nav Bot, which represents this entity in the Nav Area. The entity's movement system will inform the Nav Interface of its current location and destination. The Nav Interface uses this information to update its Nav Bot. Then, every frame, Gameware determines the direction and speed it thinks the bot should move. This is based on path planning as well as obstacle avoidance. The movement system then queries the Nav Interface to retrieve this information before making its own movement decisions and updating its internal state.

Some Nav Interfaces, most notably DtActiveBotNavInterface, also provide convenience functions for performing other navigation queries related to this sim object. For instance, if you want to initiate a path planning query that would be applicable to the current entity, rather than look up the entity's current Nav Area and query the Nav Area, you can query the Nav Interface itself.

// Lookup the DtActiveBotNavInterface for this entity 
DtActiveBotNavInterface* iface = dynamic_cast<DtActiveBotNavInterface*>(DtNavigationLocalObjectFacade(entity()).navInterface());
if (iface)
{
   // Initiate the query. myQuery is a DtNavAreaQuery::Ptr owned by this current object
   // which will be  checked in future ticks.
   myQuery = navArea->findPathToLocation(
      localStartPosition, // starting position
      localEndPosition, // ending position
      useAbstractGraphs, // setting to true can speed up long path planning queries
      localPointToAvoid, // optional position to avoid
      avoidanceRadius); // radius (m) to go around point to avoid
}

Navigation Data Generation

In order to use the navigation API on a particular area of a terrain, you must first generate Navigation Data. (Please see Chapter 61 of the Users Guide for details on how to run Navigation Data generation.) VR-Forces has a separate application, the Nav Generator (vrfNavGenerator.exe), that performs this generation. When you initiate Nav Data generation through the VR-Forces GUI, it executes the Nav Generator to actually generate the data.

The Nav Generator does have a limited plugin API if you wish to customize some of the data that is generated. Plugins to be loaded are defined in navigationProfiles.mtl. Nav Generator plugins allow you to define new functions to create Nav Edges and Nav Vertices to be added into the Nav Graph in the generated Nav Data. The Nav Generation Functions (navGenerationFunctions) example (./examples/navGenerationFunctions) shows how to add a such functions. The functions genereated by this example are loaded and used by default in the Nav Generator. Please see the example for more details for how these functions work and how they are configured in navigationProfiles.mtl.

Nav generation can also occur in the sim engine at run-time in response to changes in the terrain. This most often occurs due to dynamic terrain updates, such as building damage or crater creation due to explosions. When this happens, the sim will regenerate a portion of the Nav Data around the effected area. This run-time Nav Data regeneration uses the same DtNavDataGenerator class that is used by the Nav Generator, and thus follows the same generation rules and configuration settings.

Table of Contents