Performance Considerations

General characteristics

The two key performance measures here are, one the one hand, pathfinding query times, and on the other hand, pathfinding preprocess update times.

Pathfinding query times are affected significantly by the number of dynamic obstacles placed. Query times will increase as dynamic obstacles are added, and then decrease again once a preprocess update has been performed and the dynamic obstacles are 'burnt-in' to pathfinding preprocess.

Both query and update times are affected by the total number of obstacles placed and complexity of the pathfinding environment, with certain key factors described below.

The number of changes made per update is irrelevant

A full set of pathfinding preprocess is actually being generated each update, so preprocess update times (and subsequent query times against the resulting preprocess) are effectively independent of the number of changes made in the update.

For situations where only a small number of changes are being made this may seem wasteful, but in most application situations efficiency for minimum load conditions is actually irrelevant - the maximum expected load situation is the one you need to worry about.
This demo essentially assumes that it is possible for all hell to break loose and affect large numbers of placed obstacles in short periods of time.
When this happens pathfinding query and update times will be unaffected.

Mesh partitioning

For situations with significant numbers of dynamic, or semi-dynamic obstacles it can be very important to get suitable partitioning set up on the base mesh.
By default, PathEngine's internal partitioning is affected only by the external mesh detail, and, in the case of this demo, we don't want to assume anything about the final distribution of obstacles, so the best approach is to get the base mesh set up with a fixed mesh subdivision passed through into the internal partitioning.

Subdivision of the base mesh is taken care of by the cPartitionedTerrain class, instantiated with suitable parameters in Demo.cpp. The amount of subdivision is something that can then be tweaked depending on the expected obstacle density, and in conjunction with suitable benchmarks.
The 'useIdentityMapping' attribute is then pased into iPathEngine::buildMeshFromContent(), to specificy that this subdivision should be passed through for PathEngine's internal partitioning.

Note that a 'partitionTranslationTo3D' is also supplied at this point, to ensure fast conversion between PathEngine internal and world coordinates.
The code snipped to pass these attributes is as follows:

const char* options[5];
    options[0] = "partitionTranslationTo3D";
    options[1] = "true";
    options[2] = "useIdentityMapping";
    options[3] = "true";
    options[4] = 0;
    return gPathEngine->buildMeshFromContent(&groundParts.front(), groundParts.size(), options);
    

The small convex optimisation, and obstacle clumping

Placing large numbers of obstacle on a big empty square often results in situations with very high visibility between obstacles, in which case it is essential for the 'small convex obstacle' optimisation to be applied effectively. (See Pathfinding Through Forests for details about this optimisation.)

Placing small 'clumps' of obstacles can reduce the effectiveness of this optimisation, so situations with lots of intervisibility between clumps of obstacles should be avoided.

Improving pathfinding query times

The actual required load on the pathfinding depends on a number of factors, such as the number of pathfinding agents placed, but also the exact behaviours applied and the kinds of queries generated by these behaviours.

If faster pathfinding is required then there are a number of steps that can be taken to achieve this.

Applying dynamic obstacles for collision only

As implemented, the demo uses the standard dynamic obstacle mechanism to include any newly placed obstacles immediately in any subsequent pathfinding queries.
An equally valid choice (depending on the exact application context) could be to add dynamic obstacles to a collision context used only for collision queries, but not for pathfinding.
Fast collision queries can then be used by agents to check for path obstruction (or pending obstruction), with the possibility for obstacles to then be added to temporary pathfinding contexts if necessary to resolve the situation before the next update completes.

Other ways to speed up pathfinding

The query bounds mechanism should be used whenever the actual range needing to be considered for pathfinding is less than total world size.

The query callback mechanism enables maximum query times to be capped, at either a fixed number of internal iteration, or directly on a time-elapsed basis.

Advance along path overhead

The agents in this demo use PathEngine's internal advance along path functionality for simplicity. This approach adds a certain amount of checking in order to modify paths as agents move forward and ensure that the modified paths remain valid in all possible situations.
But where large numbers of agents are placed, and relatively simple behaviours are required, this is probably overkill. In this case the (per frame) advance along path calls agents could be replaced with linear interpolation to obtain a rendering position, and an actual advance along path call then only dispatched when an agent needs to generate a new path.

Update frequency

As implemented in the demo, agent updates (for both connected region assignment, and advancing along paths) are performed for every agent in every rendering frame.
This is not necessary in most real applications.
The cost of these updates should usually be split across multiple rendering frames, with perhaps only a certain percentage of the total placed agents updated in each frame.

Slowdown when running inside a debugger

You may see a very significant slowdown when building and running the demo inside Visual Studio.
This appears to be related to overhead from DirectX debugging hooks, perhaps for logging information being redirected to the Visual Studio output window.
You can avoid this slowdown by using 'Start Without Debugging' to run the demo, instead of 'Start Debugging'.