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 'maximum guaranteed query distance' 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 on the basis of x and y (horizontal) coordinates into a regular set of rectangular tiles. Each tile has both a 'handled region', from the base tiling, and a 'represented region', that extends outside the handled region.

A PathEngine iMesh instance is created for each tile. Each iMesh instance covers the represented region for the relevant tile. The represented regions, and therefore the iMeshes, overlap.

When pathfinding queries are made, these are dispatched to one of the iMesh instances on the basis of the x and y coordinates of the query start point. This iMesh instance will then be able to pathfind to a query end point anywhere within the represented region for that tile.

A path out of the handled region of one pathfinder tile, in a highly simplified environment.

A subsequent path is queried against a 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 handled region and represented region for the iMesh instance handling this query are highlighted in dark orange and light orange respectively.

The second image shows the situation after the agent arrives at their destination and subsequently wishes to move again. The agent is now in a different handled region, and so a different iMesh instance is used to handle this query (with the handled and represented regions for this iMesh highlighted in dark purple and light purple respectively).

Represented regions and federation world bounds

The represented region for each tile is clipped to the federation world bounds.

Adjustable parameters and constraints

The amount of overlap between tiles can be varied, and this directly determines the 'maximum guaranteed query distance' constraint mentioned above.
This is the maximum distance that can be guaranteed to be considered for queries in the worst case, specifically the case where an agent is standing right at the edge of a tile and wants to pathfinding out into the adjacent tile. In most other cases queries can actually extend further, and in many cases a lot further.

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. This enables you to trade off things like total memory / disk footprint for the whole set of pathfinding tiles against maximum complexity of individual tiles.

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 can be considered as queries with 2D coordinates for a start (or root) position, plus an effective horizontal range, and can therefore be applied in the content of federated overlapping meshes.
For something like iMesh::findClosestUnobstructedPosition(), for example, the start coordinates are taken from the initial point passed into the query, and the range is controlled by a parameter passed into the query.

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.