AbstractGraphs are another type of NavData. They are an abstract lightweight static representation of possible paths in NavMeshes.

AbstractGraphs are used for finding very long paths into large worlds. You can find a path using AbstractGraphs and NavMeshes only at the start point and end point. It is faster to find a path using AbstractGraphs than using NavMeshes only. Additionally, using AbstractGraphs can save memory and CPU time.

The following figure shows a path computed using AbstractGraphs with NavMeshes only at the start point and end point.

The following figure shows how a path is not found using only NavMeshes because of the box extent. If you increase the box extent, the path finding fails due to lack of working memory.

You can create AbstractGraphs only for NavData with a specified cell box. For information about cell boxes, see Using fixed-step or grid-based partitioning under Handling Sector Overlaps.

AbstractGraphs are not created by default. To create AbstractGraphs, you must set m_doGenerateAbstractGraph to true in m_abstractGraphParams, which is the GeneratorAbstractGraphParameters member.

You can use one AbstractGraph or several AbstractGraphs to cover the NavData. To define the length of the cell box that an AbstractGraph covers, set GeneratorAbstractGraphParameters::m_extentsInNumberOfCells. You can limit the potential size of concrete paths using this property. By default, it is set to 0, which generates one AbstractGraph to cover the entire NavData.

The GeneratorAbstractGraphParameters::m_workingMemorySizeLimit parameter gives the size limit (in Bytes) of the WorkingMemory, which is used to run MultiDestinationPathFinderQuery when computing the edge costs in an AbstractGraph.

AbstractGraphs are static and do not consider the dynamic NavMesh, NavTag, and NavGraph changes during runtime. To set the AStarQuery to traverse or not to traverse the AbstractGraphs, call SetAbstractGraphTraversalMode() and pass either PATHFINDER_ TRAVERSE_ABSTRACTGRAPHS or PATHFINDER_DO_NOT_TRAVERSE_ABSTRACTGRAPHS. The propagation on the NavMesh is limited to the cells covered by the AbstractGraphs at the start and end positions.

If a path is found using AbstractGraph, it is set into AStarQuery::m_abstractPath and the usual AStarQuery::m_path. The m_abstractPath contains the AbstractPath, and m_path contains the first concrete path (from the starting point to the first AbstractGraph node).

To follow the AbstractPath, run the AStarQuery to the next AbstractPath node, and find the next concrete path that the bot can follow. An example of following an AbstractGraph is given in the labengine sample library. The LabEngine::AbstractPathFollower class creates the query to find a concrete path using the following:

• PATHFINDER_DO_NOT_TRAVERSE_ABSTRACTGRAPHS – Traverses only the concrete data and ignores AbstractGraphs, so it uses AStarQuery::GetPropagationBoxExtent().
• PATHFINDER_TRY_TO_HOOK_ON_NAVMESH – Allows the bot to find a concrete path even though an abstract node cannot be reached when out of NavMesh. For example, if a dynamic obstacle punches the NavMesh, the bot can approach the node and when close to it, the bot can compute a path to the next abstract node before leaving the NavMesh.

Note: AbstractGraphs are not dynamic. They do not consider holes punched in the NavMesh during runtime, or traversibility of a NavTag and its cost. However, the LabEngine::AbstractPathFollower class provides limited tolerance to sparse use of the dynamic NavMesh.