Aborting Pathfinding Early

The following methods are provided to enable the client application to abort pathfinding queries early:

• iMesh::findShortestPath_WithQueryCallBack()
• iAgent::findShortestPathTo_WithQueryCallBack()
• iMesh::findPathAway_WithQueryCallBack()
• iAgent::findPathAway_WithQueryCallBack()

Overview

When a pathfinding query is aborted the query will return the best path found up to that point. This path will not extend all the way to the desired goal position, and in some situations this path may even lead into a dead end. Nevertheless this functionality can be useful for certain situations, for example where it is not absolutely essential for an agent to take the shortest path, or to enable an agent to start moving whilst waiting for a longer query to complete.

In order to use the query callback methods, the client application needs to create a class deriving from the iQueryCallBack interface.
An object of that class is then created and a pointer to the object passed in with the pathfinding query.

Choosing a approach for limiting query time

The actual code used to decide when a query should be aborted can depend on the specific constraints of the client application. In general, however, the most common approach is to use either a time limit, or a limit on the number of steps in the pathfinding query.

Time based approaches have the advantage of giving more direct control over the actual query time.
Approaches based on the number of steps executed have the advantage of being repeatable between executions of the application, across platforms, and so on.
For some situations a hybrid approach might be suitable, based on aborting after a fixed time limit but also counting the number of iterations so that the result can be repeated exactly later if desired.

Polling frequency

In addition to specifying when a query should be aborted a callback also controls the frequency with which PathEngine polls the callback during a search.
Higher frequencies enable finer control over eventual query time, whereas lower frequencies reduce the overhead for calling back to the callback object.
The frequency is based on the number of corners successfully explored by the search. A frequency of 1 indicates that PathEngine should call back for every corner successfully explored.

An example callback implementation

The following provides a simple example implementation of a callback object:

class cQueryCallBack : public iQueryCallBack
{
    int32_t _frequency;
    int32_t _count;

public:

    cQueryCallBack(int32_t frequency, int32_t count) :
      _frequency(frequency),
      _count(count)
    {
        assert(_count);
    }

    int32_t desiredCallBackFrequency()
    {
        return _frequency;
    }
    bool abort()
    {
        --_count;
        return _count == 0;
    }
};

This could then be used as follows (to abort after 20 corners are explored):

{
        cQueryCallBack callBack(5, 4);
        pathResult = mesh->findShortestPath_WithQueryCallBack(shape, context, start, goal, &callBack);
    }
    

Some example paths

The following show the result of aborting pathfinding after successively larger numbers of iterations for a path on the 'thainesford' example mesh:

frequency = 5, count = 1

frequency = 5, count = 5

frequency = 5, count = 8

frequency = 5, count = 10