Alternative Path Finding Queries
The AStarQuery class is generally recommended for use for the most common path calculation scenario: finding a path through the NavMesh and NavGraphs to a particular pre-determined destination. It offers options for controlling the characteristics of the paths it produces, and for tuning the performance of the path finding calculations.
However, for special cases, you may want to use a different class of query to generate a Path that fulfills certain particular criteria. This could be an alternative class of path finding query supplied in the Gameware Navigation SDK; or, it could be a custom class of query you write yourself in order to meet some specific needs of your game scenario.
This page describes the alternative path finding query classes supplied in the Gameware Navigation SDK, and the requirements for writing your own custom path finding query.
For details on how to set up a Bot to use an alternative path finding query, see Getting a Static Path.
BestGraphVertexPathFinderQuery
Unlike the AStarQuery, the BestGraphVertexPathFinderQuery does not find a path to a pre-determined destination. Instead, it allows you to choose the destination, which must be a vertex in a NavGraph, dynamically during the path calculation. For example, you could use this query in order to make a Bot move to the best nearby cover point, sniping position, med-pack, weapon upgrade, etc.
The query propagates outward through the NavMesh in all directions from a specified starting point. For each NavGraph vertex that it discovers as a potential destination, the query invokes an instance of a customizer class that you write and provide as a template parameter, similar to the customizer that you can provide to the AStarQuery, to determine whether or not the vertex should be chosen as the final destination.
The query continues to explore the NavMesh looking for candidate NavGraph vertices until the customizer indicates that the search should stop, or until the maximum path cost set for the query has been exceeded.
Getting data into NavGraph vertices
Because this query class tests only NavGraph vertices as potential destinations, you need to make sure that you have created a NavGraph vertex at each point in 3D space that you want the query to potentially select. For example, if you want to use this query to select a cover point, you have to create a NavGraph, add a vertex for each potential cover point, and add the NavGraph to the Database that you use for the query.
For details on this process, see Creating NavGraphs.
Implementing the VertexFinderLogic
The template class that you provide to the BestGraphVertexPathFinderQuery is expected to implement the usual TraverseLogic interface for determining whether or not transitions to different NavTags should be forbidden, and it requires the same typedef that determines whether or not one-way NavTag transitions are allowed. For details, see the SimpleTraverseLogic class, and Forbidding, Avoiding, and Preferring NavTags.
In addition, you must provide implementations for the following virtual methods that monitor the propagation of the query through the NavData:
static OnGraphVertexVisitedResult OnGraphVertexVisited(void* userData, const NavGraphVertexRawPtr& currentGraphVertex, const NavGraphVertexRawPtr& bestGraphVertex, Ptr<Path> pathToBest);
The query invokes this method systematically each time it encounters a NavGraph vertex during its exploration. This method is expected to evaluate the suitability of the NavGraph vertex passed in the currentGraphVertex parameter, and to determine whether or not it is a better destination than the vertex passed in the bestGraphVertex parameter. It indicates by its return value whether or not to remember the candidate vertex as the best destination found so far, and whether or not the search should continue.
If you need to examine the path to the candidate vertex before deciding whether or not the vertex should be adopted as the best destination found so far, the OnGraphVertexVisited() method can instead request the query to calculate the path. In this case, the query calls the OnPathToGraphVertexComputed() method, shown below.
static OnPathToGraphVertexComputedResult OnPathToGraphVertexComputed(void* userData, const NavGraphVertexRawPtr& currentGraphVertex, Ptr<Path> pathToCurrent, const NavGraphVertexRawPtr& bestGraphVertex, Ptr<Path> pathToBest);
The query calls this method only when the OnGraphVertexVisited() method indicates that it needs to examine the path to the candidate vertex before it determines whether or not the candidate should be adopted as the best destination found so far. This method can compare the path to the current candidate vertex with the path to the best vertex found so far. It indicates by its return value whether or not to remember the candidate vertex as the best destination found so far, and whether or not the search should continue.
Other options
The BestGraphVertexPathFinderQuery class supports most of the same options offered by the AStarQuery. For details, see AStarQuery Options.
The only difference is that instead of using a rectangular box to constrain propagation, this query uses a circle with a radius that you can set by a call to BestGraphVertexPathFinderQuery::SetPropagationRadius().
PathFinderFromPolyline
Typically, the AstarQuery or BestGraphVertexPathFinderQuery is used for finding a path to a destination. However, if you know the consecutive 3D positions (polyline) that form the path to follow at runtime, you can use the PathFinderFromPolyline query instead of other queries. The PathFinderFromPolyline query takes the input 3D positions of a polyline to create an instance of Kaim::Path. The polyline must be entirely inside the NavMesh for the PathFinderFromPolyline query to be successful.
Writing a custom path finding query
You can write your own class of query to find a path for your Bots to follow. This allows you to take total control over path calculations without affecting any other sub-systems of the Bot path following system. As long as your class follows the outlines given below, it should be fully compatible with the rest of the path finding and following system.
You must derive your class from Kaim::IPathFinderQuery, or from one of the path finding query classes supplied in the Gameware Navigation SDK such as the AStarQuery.
You must provide implementations for all of the pure virtual methods in the Kaim::IPathFinderQuery base class, as described in the following sections. See also the documentation and header files for the Kaim::IPathFinderQuery, Kaim::ITimeSlicedQuery and Kaim::IQuery base classes.
See also the implementations in the AStarQuery and BestGraphVertexPathFinderQuery classes for sample implementations.
Advance
This is the main method of the API, which is called by the Bot to perform the actual path calculation in response to your calls to Bot::ComputeNewPathAsync(). Your implementation should:
- Create a Path object, set it up with the nodes that should make up the path, and store a pointer to the object in the m_path class member.
-
Note that to ensure that the path following system used by the Bot will be compatible with the settings used to generate the path, each Path maintains the unique ID of a NavigationProfile that must be used to follow that path. As long as a Bot is following an injected path, its path following system will automatically use that NavigationProfile to retrieve any customizable objects that it should use to control path following, such as the TraverseLogic and IPathEventListObserver.
By default, new Path objects that you create from scratch are set up to use the default NavigationProfile maintained by the World. If your new Path has any special requirements on the way it should be followed that require the use of a custom NavigationProfile, you have to set the appropriate profile ID in your Path by calling Path::SetNavigationProfileId().
- The Advance() method is expected to complete its calculations in a very small amount of time. If your path calculation takes longer than 1ms, you should split your calculations across multiple frames. To do so, you should store any temporary data for later reuse, and set the m_processStatus class member to QueryInProcess. The query will automatically be re-called each frame until it indicates that it has finished its computations.
- When the computations are complete, set the m_processStatus class member to QueryDone.
- You may be able to use the WorkingMemory object passed to the method in order to store temporary data for use in future frames.
GetType
This method is expected to return a unique identifier for each class of query. Edit the QueryType enumeration in iquery.h to add a new entry for your query after the QueryType_FirstCustom value, and return that value from this method.
Visual debugging information
These functions are called when preparing data to be sent through the visual debugging system for display in the Navigation Lab.
This method should return the destination point for the query, or KY_NULL if the query has no destination.
This method should indicate the current status of the path calculation.
This method is called to get a text description of the current state of the query calculation. Implementing it is optional.
Release working memory
This method is called when the query is canceled during the course of its calculations.
- If your query uses the WorkingMemory object that is passed to its Advance() method to store temporary data across multiple frames, this method should release any resources used by that WorkingMemory object.
- It should set the m_processStatus class member to QueryDone.
Except where otherwise noted, this work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. Please see the Autodesk Creative Commons FAQ for more information.