Path Finding and Path Following
The path finding and path following system is the highest-level service provided by Autodesk Navigation. It applies many other subsystems provided by the toolbox layer, including the query system.
The system is based around the Bot class and its sub-components, which manage many of the complexities involved in providing pathfinding for characters in a three-dimensional game, including:
- Taking into account the terrain of the world to plan efficient, realistic paths around both static obstacles and dynamic, destructible and interactive obstacles.
- Following those paths at each frame inside the NavMesh, and outside the NavMesh using NavGraphs.
- Avoiding other characters passing close by, even when their trajectories imply imminent collision.
- Reacting to events that may invalidate the path, such as NavData being streamed out.
Each NPC that you want to use the Autodesk Navigation path finding and path following system should have its own instance of the Bot class. If you have already followed the steps in the integration tutorial (see Integrating Navigation into your Game Engine), you have already written a minimal amount of code to initialize, update and destroy a Bot for a character in your game.
Each instance of the Bot class uses the same general process for finding and following paths, outlined in the following sections.
The first step in the path following system is to compute an initial path through the NavData, that connects a starting point (typically the current position of the Bot) to a desired destination. This initial path is represented by an instance of the Path class, a static immutable structure that consists of nodes connected by edges.
For example, in the image below, the yellow Bot has planned a path to a destination on the rooftop. The path goes through the NavMesh on the ground, follows a NavGraph edge that connects the ground to the rooftop, then has a final segment on the rooftop from the end of the NavGraph edge to the destination.
By default, every Bot has access to a query that can compute a Path, which it retrieves from an object called its NavigationProfile. When you want to calculate a new path, you use the Bot API to request the path calculation, and the Bot carries out the query asynchronously during the next update.
There are several different ways to request your Bot to calculate the path; or, you can provide your Bot with a pre-calculated path. For details, see Getting a Static Path.
Once the Bot has successfully calculated a Path, or when you inject your own Path, the path following system analyzes the new path and builds a new structure called the LivePath from it. The LivePath is a dynamic structure that maintains several important items of contextual information about the path and the state of the Bot's path following process, including a list of PathEvents that you can browse at any time to retrieve information about the path. You can use these PathEvents to scan along the path for upcoming transitions to different terrain types, smart objects, or invalid areas.
For example, in the image below, the flags mark transition events in the LivePath: each time the path crosses into an area with a different NavTag, and at the start and end of the NavGraph edge.
For details on these PathEvents and how you can interact with them, see Monitoring PathEvents.
In each frame, the Bot calls a Trajectory object to determine what movement it should make in the current frame. The Trajectory is responsible for evaluating the current conditions of the Bot and its path, and taking into account any other influences such as moving obstacles that may produce collisions. Based on these factors, and on a set of configuration parameters that control the character's locomotion, it produces a recommended velocity for the character to pursue in the current frame.
By default, Bots are set up to use in instance of the Trajectory class. This implementation of Trajectory can use either of two different strategies for computing the final velocity:
It can use a strategy based on straight-line shortcuts, computed by a ShortcutTrajectory object. The ShortcutTrajectory chooses a target point on the path that is both visible and a little ahead of the character's current position—by default, up to 10 meters ahead—and generates a velocity that heads toward that target point in a straight line. As it approaches the target point, it periodically updates the target to a new visible location farther along the path.
For example, in the image below, while the Bot is approaching the corner, it continues to aim for the last visible point along the LivePath. When it gets close enough to the corner that it can see more of the LivePath, it advances its target point as far along the path as possible.
This strategy provides a relatively simple and high-performance way for the character to skip past sharp turns in its initial path. However, it can allow the character to make abrupt changes in velocity and facing direction when a new shortcut becomes available.
It can use a strategy based on channels and splines, computed by a SplineTrajectory object. This strategy is based on a channel: a representation of the navigable space around the initial path that is computed at the same time as the path. The SplineTrajectory examines the upcoming configuration of the channel's boundaries, and computes a spline that keeps the character's trajectory within those bounds.
For example, in the image below, you can see the boundaries of the channel in orange. Note that the boundaries squeeze closer together in the narrow gap between the obstacles. Also note that there is no channel for the segment of the path that follows the NavGraph; the first channel ends at the start of the NavGraph edge, and a second channel begins on the rooftop. As with the shortcut example above, the Bot periodically computes a new spline (shown in red) as it progresses along the path.
This strategy tends to produce more rounded trajectories that use a greater amount of the available space around the initial path, at the cost of slightly higher CPU usage during both the path finding phase (in order to generate the channel data) and the path following phase.
You determine which trajectory mode is used at the time you initialize your Bot, and you can change on the fly at any time after initialization. See also Customizing Path Following.
Regardless of which strategy the Trajectory is currently using in any given frame, it may apply the following conditions:
- While the Bot is in the valid area of the NavMesh, the trajectory can use a dynamic avoidance system to generate trajectories that avoid collisions with nearby objects such as moving obstacles and other bots. The avoidance computer may adjust either the direction of movement, the speed of the Bot, or both.
- While the Bot is traversing a NavGraph, the trajectory always produces a velocity that leads straight to the next vertex in the NavGraph, without any dynamic avoidance.
The classes involved in the trajectory and dynamic avoidance systems contain a wide range of configuration parameters that you can tune for each character. See also Customizing Path Following.
To retrieve the final result of the path following system at each frame, you need to access BotOutput as shown in the following example:
m_velocity = m_navBot->GetBotOutput().m_outputVelocity();
It is your responsibility to apply this velocity to your game character, subject to any additional constraints implied by your animation or physics systems.
Autodesk Navigation does not make any assumption on how your game entity moves and steers in your game. Your characters can be completely animation driven, or completely physics driven. This is why the Bot does not move itself automatically; you interpret the suggested velocity produced by the path following system, adapt it to your needs, and inform the Bot of the actual changes in position and velocity that you apply to your character.
The path following system does not expect the character to be in the position it predicts at all times. Several things may explain why your game entity may move differently:
- Discrete velocity locomotion models may not be able to follow closely our recommended velocity.
- Physics collision, avoidance or other gameplay-specific events may push your characters off-course.
In most cases the Bot will be able to carry on following the path transparently, regardless of minor differences between the suggested velocity computed by the path following system and the actual position and velocity, or events in the game that push it off course.
However, if significant difference can occur in your game, such as a character being pushed off a cliff, it is a good idea to test the validity of the character's progress along its path at each frame. If the character's position on its path becomes unreachable and a new one cannot be determined, you may want to re-calculate a new path to the destination. See also Monitoring Path Following.
As your characters follow their paths, you may need to respond to many different kinds of events. It is your responsibility to watch for events that you want to respond to, and handle them appropriately when they do arise.
For a detailed discussion, see Monitoring Path Following.