Using the Query System

Autodesk Navigation provides a set of high-performance runtime queries for use against the NavData you have loaded into memory. You can use these queries to answer a wide range of perceptual questions about your terrain and your characters’ movement opportunities, such as:

• Can a character move from here to there in a straight line?
• How far can this character move in a given direction?
• If the character hits an area with a custom data tag while moving in this direction, what type of tag is it?
• How much open space is around this position?
• Is this position valid for a character of a given width?
• What is the altitude of the NavMesh (and therefore, the height of the terrain) at these X,Y coordinates?
• What other spatialized dynamic objects (i.e. Bots, obstacles, points of interest, etc.) lie nearby?

The types of available queries include:

• CanGo queries test whether a ray, sphere or segment can pass from a starting point to a destination point without colliding with a border of the NavMesh.
• Cast queries test how far a ray, sphere or segment can go from a starting point in a given direction without colliding with a border of the NavMesh.
• Queries that find valid positions within the NavMesh.
• Queries that find NavData elements that meet certain criteria that you specify: i.e. the nearest triangle to a given position, the nearest border to a given position, etc.
• Path finding queries, such as the A* query, which plan a path over the NavMesh from a starting point to a destination point.
• The CollisionRayCastQuery, which conducts collision tests against the NavData. See also Using the Collision System.
• etc.

Each type of query is encapsulated in its own class. For a full list, see the classes that implement the IQuery class. For a complete description of each query type, including its inputs and outputs, see its class description.

Each query takes into account the full set of NavData currently loaded into a single Database. Single queries cannot be made against multiple Databases at the same time (although you can execute multiple copies of a query in parallel against different Databases), nor can a query be restricted to a subset of the sectors loaded into the Database.

Each class of query is either atomic or time-sliced.

• Atomic queries complete their computation within a single frame. They block the calling thread during their calculations, and their results are guaranteed to be available immediately after you request them to be processed. These query classes all derive from IAtomicQuery.
• Time-sliced queries, which are typically more computationally intensive, can split their calculations across multiple frames in order to avoid peaks in CPU usage. These query classes derive from ITimeSlicedQuery.

Every query needs some working memory: a buffer that it uses during its calculations to store temporary data. For example, the AStarQuery needs to use its working memory to store the list of candidate nodes that it explores when finding a path through the NavData.

Each time you process a query, you can provide an instance of the WorkingMemory class for that query to use during its calculations. If you do not provide one, the query will use a shared buffer that is maintained by the Database that the query is configured to explore.

Note that each WorkingMemory instance can only be in use by one query at any time.

You can run each query you create in one of two modes:

• Immediately on demand. This blocks the calling thread while the query is processed, but guarantees that the result of the query will be immediately accessible.
• Asynchronously, during the next Autodesk Navigation update phase. This allows the calling thread to continue with other tasks during the calculations, and takes advantage of the system built in to the World for avoiding CPU peaks. If the CPU budget for processing queries in the current frame has elapsed, the processing of atomic queries can be deferred to the next frame, and time-sliced queries can be paused and resumed in the next update. However, using this approach means that the results of your query will not be accessible for at least one frame, and possibly for several frames.

Note that if you want to launch a query outside of a game loop, such as in a post-processing phase of your data generation process, you must use the blocking method.

To set up a query:

1. Create an instance of the query class you want to run.
2. Call its BindToDatabase() method to associate it with the Database whose NavData the query will use during its processing. This call also resets the value of all optional configuration parameters, and returns the query to a default state.
3. Set up any optional configuration parameters for the query by calling the accessor methods offered by your query class. The kinds of configuration parameters you can set depend on the type of query you are using; for details, see the class description for your query class.

4. Call the query's Initialize() method to set it up with the input data it requires. For details, see the class description for your query class. Remember to convert the input data from the coordinate system of your game to the Autodesk Navigation coordinate system (if necessary).

   Note that this call does not reset the values of any other configuration parameters, so that you can re-use the same configuration values across multiple runs of the same query without having to re-set them each time you initialize the query with new input data.

For example, the following code sets up a RayCastQuery.

Kaim::RayCastQuery<Kaim::DefaultTraverseLogic> rayCastQuery;
rayCastQuery.BindToDatabase(m_world->GetDatabase(0));

// Optional configuration ...
rayCastQuery.SetDynamicOutputMode(Kaim::QUERY_SAVE_TRIANGLES);

rayCastQuery.Initialize(start, move2D);

If you want to re-run a query with the same configuration against the same Database, you only have to call Initialize() to provide the new input values.

Many types of queries can take into account the custom NavTags associated with the NavData they explore. These queries all accept a predicate as a template argument. The query invokes class methods from this predicate when it detects a transition between NavTags, to determine whether or not the new NavTag should be forbidden, and whether or not the transition can be crossed.

This predicate is the same as the one accepted by the PathFollower class, and relies on most of the same methods as the customizer used by the AStarQuery. For details on the requirements for the interface that you must implement in your predicate class, see Forbidding, Avoiding, and Preferring NavTags.

For more information about setting up NavTags, see also Tagging with Custom Data.

You launch a query differently depending on whether you want it to run immediately or asynchronously.

To launch a query in immediate mode, call its PerformQueryBlocking() method.

For example:

rayCastQuery.PerformQueryBlocking();

It is safe to launch immediate queries from any thread, as long as you do not launch any queries while the update of the World is in progress.

To launch a query asynchronously during the next update of the World, call the World::PushAsyncQuery() method and pass your query object. The World places your query in a queue, and performs the query as soon as its CPU budget permits.

For example:

m_world->PushAsyncQuery(&rayCastQuery);

You can set up your own QueryQueue objects, with your own CPU budgets, to manage the processing of your queries. When you process a QueryQueue, it performs the queries at the head of the queue in order until its CPU budget is exhausted. It then pauses its calculations until you process it again (typically in the next frame).

See the QueryQueue class for details.

Like running queries in immediate mode, it is safe to process QueryQueues from any thread, as long as you do not process them while the update of the World is in progress.

However, like running queries in asynchronous mode, the results of each query is not guaranteed to be available immediately after the queue is finished processing in the current frame.

You can retrieve the current results of a query by calling its GetResult() method at any time.

Every query indicates the state and results of its processing using an enumeration specific to the query class. This enumeration has the same name as the query class, with the suffix Result. For example, the RayCastQuery produces a RayCastQueryResult.

Note that if you launch your queries asynchronously, you can use the result code to determine whether or not the query has finished its processing successfully. Generally, any enumeration value that includes DONE indicates that the query is finished its calculations. For example, the RayCastQuery returns RAYCAST_NOT_INITIALIZED or RAYCAST_NOT_PROCESSED until it has completed its processing, then it might return any of RAYCAST_DONE_START_OUTSIDE, RAYCAST_DONE_ARRIVALPOS_FOUND_MAXDIST_REACHED, RAYCAST_DONE_LACK_OF_WORKING_MEMORY, etc.

Depending on the type of query, and the result of the processing, you may also be able to retrieve additional outputs from the other data members of the query. See below.

Some types of queries that propagate through the NavMesh can store the data that they cross. For example, queries may be able to store a list of the triangles that they cross during their propagation, or a list of sub-segments that cross different NavTags. After the query, you can retrieve the list of crossed data and search for the properties of the terrain crossed by the query. For instance, your characters could make decisions based on the NavTags associated with the triangles, changes in altitude, etc.

These queries all contain a SetDynamicOutputMode() method, which you must call to tell your query which types of output data it should record. By default, crossed data are not recorded; you must explicitly instruct your query to record it by calling SetDynamicOutputMode() and passing it the desired value from the DynamicOutputMode enumeration.

You can retrieve the crossed data by calling the GetQueryDynamicOutput() method. This returns a pointer to a QueryDynamicOutput object, whose methods offer access to the saved data. Remember to convert the output data back to the coordinate system of your game (if necessary).

For example, the following code shows how to set up a RayCastQuery to retrieve the NavMesh triangles it crosses:

Kaim::RayCastQuery<Kaim::DefaultTraverseLogic> rayCastQuery;
rayCastQuery.BindToDatabase(m_world->GetDatabase(0));
...
// enable saving triangles
rayCastQuery.SetDynamicOutputMode(Kaim::QUERY_SAVE_TRIANGLES);

rayCastQuery.Initialize(start, dir2D, maxdist);
rayCastQuery.PerformQueryBlocking();

// retrieve data
Kaim::QueryDynamicOutput* qoutput = rayCastQuery.GetQueryDynamicOutput();

// iterate through the list of triangles
KyUInt32 numberOfTriangles = qoutput->GetNavTrianglePtrCount();
for (KyUInt32 i_triangle = 0; i_triangle < numberOfTriangles; i_triangle++)
{
   const Kaim::NavTrianglePtr thisTriangle = qoutput->GetNavTrianglePtr(i_triangle);
   // handle the triangle here.
}

You can render visual debugging data about any query by calling its SendVisualDebug() method at each frame. While the Navigation Lab is connected to the game, the query will automatically construct a display list and send it to the Navigation Lab.

The contents of the display list, and consequently the data displayed in the Navigation Lab, vary depending on the type of query. To interpret the significance of the visual data shown for your queries, see the inline implementations in the QueryDisplayListBuilder classes in the sdk\gwnavruntime\queries\blobs directory.

When you perform queries asynchronously, or you place them in queues for processing, it can be helpful to receive a notification when the query has been completed instead of having to poll the query result to determine the current state of the processing.

To get notified of a query's completion:

1. Write a custom class that implements the IOnDone interface.
2. Before you launch your query, create a new instance of your custom class, and set the m_onDone member of your query class to a pointer to the new instance.

If you push your query to the World for execution, the IOnDone::OnDone() method of your object is called automatically during the update of the World, after the query has been processed. If you use your own QueryQueue, your object is called the next time you call QueryQueue::FlushQueries() after that query has been processed.

Note that the m_onDone member of the query class is reset to KY_NULL after its IOnDone::OnDone() method is called. If you want to re-launch the same query instance, and you want to receive notification again, you need to set up the m_onDone member again.

Many of the queries in the Autodesk Navigation API are also exposed in the Navigation Lab, which runs the query and provides visual feedback on the results of the query. This can be useful for testing the NavData generated for your terrains, and for understanding the different input and output values of each query.

For an introduction to running queries in the Navigation Lab, see Getting Started with the Navigation Lab.