Unobstructed Space Optimisation

By default PathEngine performs an exact expansion of the obstruction boundaries defined by the pathfinding movement model, during unobstructed space construction.

In some situations this can be important or necessary (e.g. in order to ensure that certain constraints are met for higher level movement code, or to guarantee that obstructed space definitions match exactly across overlapping ground mesh pieces).
In other situations, however, an exact expansion may not be a requirement, and you can then tell PathEngine to simplify unobstructed space boundaries, reducing the complexity of subsequent query operations.

Controlling the optimisation

The optimisation is controlled by the 'optimiseWithRange' unobstructed space generation attribute.
Setting this attribute turns on the optimisation, with the attribute value then also specifying an error threshold for optimisation.

Error threshold values

The error threshold for the optimisation actually specifies a maximum horizontal range for errors.
The optimisation works by collapsing vertices on the unobstructed space boundary, where this can be done without invalidating the boundary and where the resulting optimised boundary remains within a horizontal range defined by the error threshold value (i.e. where both X distance and Y distance are within the specified threshold).

Error threshold values are limited by the agent shape used for expansion (this is to ensure that optimised boundary cannot fall outside of the base ground mesh, but also that approximation to the integer grid from positions inside obstructed space cannot result in positions outside of the base mesh).

Specifically, the square shape with radius of [horizontal_error_threshold + 1] must be inside the agent shape used for expansion.
This means that axis aligned square agent shapes are generally the best choice if unobstructed space optimisation is being used, with the maximum allowed error threshold then determined as [radius_of_expand_shape - 2].
For a square pathfinding agent shape with vertices [(-20,-20),(-20,20),(20,20),(20,-20)], for example, the maximum allowed threshold value is 18.

Effects of optimisation

Turning on unobstructed space optimisation can be expected to reduce both memory footprints (and preprocess file sizes) and run-time query times for all of the core pathfinding and collision queries, but with the most significant effects then being those relating to pathfind preprocess memory sizes and queries.

The optimisation also reduces the complexity of preprocess generation operation (and in particular pathfind preprocess generation), but speedups here offset by the additional cost of the optimisation step itself (with the possibility for total preprocess generation times, with all steps taken together, to actually take longer than when this optimisation is turned off).

A benchmark point with optimised unobstructed space has been added to the benchmark example project (and benchmark values that include this should be available on the benchmarks page of the PathEngine website).

Unobstructed space boundaries for part of the 'Thainesford' benchmark mesh, shown in the PathEngine testbed.

The same part of the scene shown with optimised boundaries (horizontal range value set to 10 centimetres).

Other related optimisations

Note that this optimisation is separate from, and complementary to PathEngine's small convex split pathfinding space optimisation, and so both of these optimisations can potentially be used together where even more significant speedup are desired.

Reference

For detailed reference about preprocess generation refer to iMesh::generateUnobstructedSpaceFor(), in the API Reference section.