AStarQuery Options

This page describes some of the configuration options offered by the AStarQuery class.

Note that when using the simplified path calculation API, these options are unavailable or set to default values. In order to set these options for a Bot, you must either customize the NavigationProfile used by the Bot, or retrieve the query from the NavigationProfile, set it up, and provide it in a call to Bot::ComputeNewPathAsync(). For details on these alternatives, see Getting a Static Path.

Starting or ending the query in a NavGraph

Most of the time, the start and destination points you will use for your path calculation will both be on the ground within the borders of the NavMesh. In this common scenario, the query transparently takes care of finding the NavMesh triangles that correspond to the start and destination points you provide when you initialize the query.

However, if you use NavGraphs and smart objects extensively in your game, you may want to allow a Bot to begin a path calculation while it is in the middle of traversing a NavGraph outside the borders of the NavMesh. Similarly, you may want to allow a Bot to move to a destination that lies on a vertex or an edge of a NavGraph outside the borders of the NavMesh. However, there is no built-in spatialization system for associating arbitrary points in 3D space with NavGraph vertices and edges.

You can support these cases by explicitly setting up the AStarQuery with a pointer to a NavGraph vertex or edge that should be used as the start or the destination for the query. Use the following methods:

void AStarQuery::SetStartNavGraphEdgePtr(const NavGraphEdgePtr& startNavGraphEdgePtr, NavGraphEdgeDirection navGraphEdgePathfindMode);
void AStarQuery::SetStartNavGraphVertexPtr(const NavGraphVertexPtr& startNavGraphVertexPtr);
void AStarQuery::SetDestNavGraphEdgePtr(const NavGraphEdgePtr& startNavGraphEdgePtr, NavGraphEdgeDirection navGraphEdgePathfindMode);
void AStarQuery::SetDestNavGraphVertexPtr(const NavGraphVertexPtr& startNavGraphVertexPtr);

For example, if your Bot is in the process of climbing a ladder, and you want it to re-compute its path, you can set up your path finding query to use the NavGraph edge that the Bot is currently following as the starting point for the path computation.

Note that the methods for setting an edge as the start and end points accept an additional enumeration value that indicates whether or not the specified edge can be traversed in both directions. For example, while a Bot is following a ladder, you might allow the new path to go in either direction along the starting edge. This would allow the Bot to change directions in the middle of the ladder. However, while a Bot is using a smart object that controls a jump, you would likely want to force the direction of travel along the starting edge to go only in one direction, in order to prevent the Bot from changing directions in mid-jump.

Note also that if you use one of these methods to set up a NavGraph vertex or edge as the start or the destination of the query, it overrides whatever start point or destination position you set up for the query.

Hooking to the NavMesh

Sometimes, a start or destination point for a path finding query might be slightly outside the NavMesh boundaries. For example:

A Bot might get pushed outside of the NavMesh by a game event such as, an explosion or by a collision with a physics object such as, a moving vehicle.
You might need a Bot to end its path at a specific off-NavMesh point for game play reasons such as, to play an animation.

If the AStarQuery cannot find a valid NavMesh triangle for either the start or destination point, it considers that the point is outside of the boundaries of the NavMesh. In this case, it tries to hook on to a nearby NavMesh. It runs an InsidePosFromOutsidePosQuery to find the closest valid point inside the NavMesh, and uses that valid point (and its associated NavMesh triangle) as the start or destination for the path computation. If the path through the NavMesh is computed successfully, a small segment is added to the path to lead from the original invalid starting point to the first path node, or from the last path node to the original invalid destination point.

The maximum distance from the start point and destination point along the X axis and Y axis that is searched for the NavMesh is set by TraversalParameters::m_fromOutsideNavMeshDistance and TraversalParameters::m_toOutsideNavMeshDistance. The default maximum distance is 1.5f meters. The search looks for triangles within an axis-aligned bounding box around the start point and destination point with a half extent on the X and Y axes equal to m_fromOutsideNavMeshDistance and m_toOutsideNavMeshDistance.

You can disable hooking by setting these maximum distance values to 0.f meters.

Performance tuning options

The AStarQuery offers several options that you may be able to use to increase the performance of your path calculations.

Limiting propagation

When you use an A* algorithm to find a path to a destination point that is not reachable from the starting point (for example, on an isolated island or rooftop), the algorithm will eventually explore the entire terrain before it can be certain that no path can possibly exist to the requested destination. On large maps, such impossible path requests can waste enormous amounts of CPU time.

For example, in the image below, the entire large area on the left will be explored before the A* can determine that no possible path exists to the far side of the water:

To avoid this possibility, the propagation of the AStarQuery is constrained within a 2D box whose extents are measured on the horizontal (X,Y) plane, in meters, from the straight line between the starting position and the destination.

For example, the image below shows the constraining box in green, with the extent of the box shown by the white arrows. The area outside of this 2D box is never explored.

By default, the extent of the box (shown by the white arrows above) is set to 200.0f, making the full width of the box 400 meters. Therefore, by default, no path will deviate more than 200 meters from the straight line between the start position and the destination.
Depending on the layout of your game level, and the length of the paths you need to calculate, you may need to raise the default value in order to successfully complete very roundabout or circuitous path calculations with significant deviations from the straight-line path. You can configure the threshold value by calling AStarQuery::SetPropagationBoxExtent().

Checking for straight-line reachability

Sometimes, the destination point of a path calculation is directly reachable from the start point. In these cases, it is typically unnecessary and wasteful of CPU resources to initiate an A* algorithm, search through the NavData, and refine the static path. It is more efficient to simply adopt the direct path from start point to destination as the path right away, and skip the A* computation entirely.

To handle these kinds of cases, the AStarQuery can internally conduct a CanGo query to test whether the direct path to the destination is clear of obstacles. If it is, the AStarQuery adopts the direct path immediately.

However, the reachability test is not free; it too demands a small amount of CPU to perform the check. Therefore, although this check does increase performance for the subset of path requests where the destination is directly reachable from the start point, the check itself uses unnecessary CPU in cases where the direct path is clear of obstacles. Depending on the ratio between the number of path requests in your game that are directly reachable and the number that must use an A*, overall performance may or may not be improved by activating the reachability check.

The reachability check is more likely to increase overall path finding performance in proportion to the likelihood that the destination of your path requests is directly reachable from the start point. So, for example, you might consider activating this direct-line check in wide-open terrains with fewer obstacles, or when you need to frequently compute very short paths (e.g. when following another character).

The AStarQuery does not check the direct path to the destination point by default.
You can enable and disable checking the direct path by calling AStarQuery::SetTryCanGoMode() and passing an element from the AStarQueryTryCanGoMode enumeration.

Note that, if the direct-line test succeeds, the A* is never launched. Therefore, any NavGraphs that lie in between the starting point and the destination will not be taken into consideration. If you use NavGraphs with custom costs that are lower than the cost of moving through the NavMesh (e.g. teleporters), a Bot will not prefer paths that include those NavGraphs the way it would when the path is calculated by the A*.