Overview

PathEngine's 'mesh federation' functionality is designed to enable seamless pathfinding over environments of effectively unlimited size, or complexity, but at the expense of imposing a 'minimum guaranteed query range' constraint.
The feature can also be used to improve performance, or to tradeoff memory footprint and performance, for environments of moderate complexity.

This page provides a high level description of the functionality provided, with a working implementation of the technique provided in an example project.
In addition to providing a reference implementation, simply running this example and moving around in the environment can be very helpful for understanding exactly how the technique works.

Overview

The basic idea is that the world is divided into a set of horizontal tiles (so based on PathEngine x and y coordinates). Each tile has a 'represented region', specified by a horizontal range.

A 'tileStep' parameter defines a base square tiling, but each tile then also overlaps other tiles in the increasing x and y directions with the overlap amount controlled by an 'overlap' parameter.

A PathEngine iMesh instance is created for each tile, with each iMesh instance covering the represented region for the relevant tile.

When pathfinding queries are made, these are dispatched to one of the iMesh instances on the basis of the horizontal range relevant to the query.

A path in one federation tile, starting in the tile centre and ending in where the tile overlaps the tile to the right.

A subsequent path query against the neighbouring tile.

The first of the two images above shows a (very basic) world, with an agent (in light green) standing in a hut and a path for that agent to a target point in another hut. The represented region for the iMesh instance handling this query is highlighted in orange.

The second image shows the situation after the agent arrives at their destination and subsequently wishes to move again. A different iMesh instance is used to handle this query, with the represented region for this second iMesh highlighted in purple.

Adjustable parameters and constraints

The amount of overlap between tiles can be varied, and this directly determines the 'minimum guaranteed query range' constraint mentioned above.
This is the minimum range guaranteed to be considered for queries, in the worst case scenario.

This worst case scenario occurs, specifically, in the case where the query range is centred exactly midway across the area that overlaps two tiles.

(Playing with the 'MeshFederation' example is a good way to get a feel for how this actually works out, in practice.)

In addition to the amount of overlap you can also vary the size of the base tiling, which enables you to trade off things like total memory / disk footprint for the whole set of pathfinding tiles against maximum complexity of individual tiles.

Represented regions and world bounds

Starting from release 5.35, tile represented regions are no longer clipped to world bounds.

SDK Reference

The PathEngine SDK provides support both for generating a suitable set of tiled iMesh interfaces, at content-time, and then for working with these tiled meshes at run-time.

The iMeshFederation interface encapsulates the bulk of PathEngine's support for the technique, with iPathEngine::buildMeshFederation_FromWorldMesh() and iPathEngine::buildMeshFederation_TilingOnly() provided for the creation of an initial mesh federation object, which can be saved at content time and then loaded back in with iPathEngine::loadFederation() when required.

Tile Mesh Management

For some applications it will make sense to simply hold all iMesh instances in memory simultaneously, but for other applications it is desirable to perform some kind of scheme for managing a working set of iMesh instances, with instances loaded only when they are actually required.
For some applications it is desirable to go a step further, and distribute iMesh instances across multiple machines.

So a minimal approach has been chosen for the run-time functionality, with iMeshFederation providing key methods for directing queries to the relevant tile mesh and translating positions between overlapping meshes, and with the client application responsible for managing the actual tile iMesh instances and forwarding queries to the relevant instance.

Queries supported

All of PathEngine's collision and pathfinding queries are supported with federated overlapping meshes, subject to the federation range constraint.

Because of the minimal approach taken for the iMeshFederation the calling application needs to take care of directing each query to the relevant iMesh instance and setting ranges appropriately.