'MeshFederation'

Description

Provides a worked example of PathEngine's support for working with 'federated' sets of tiled overlapping pathfinding meshes.

PathEngine supports pathfinding across federated sets of tiled meshes (or 'mesh federations'), for seamless pathfinding across environments of effectively unlimited size, but at the cost of a constraint on the maximum distance considered for individual queries.
See Mesh Federations for an overview of this functionality.
This example project then provides a working reference implementation of the technique.

Overview

The example loads a prebuilt world mesh from the resource directory, and uses iPathEngine::buildMeshFederation_FromWorldMesh() to split this into an array of smaller overlapping meshes.
An agent is then placed randomly in the world and can be moved via point-and-click mouse control.

Running the Example

When run, the example first generates (and then saves to disk) a set of tiled meshes, and then loads these meshes back in and generates preprocess for pathfinding.
In a real application the tiled mesh generation, and subsequent preprocessing, would most probably be performed off-line during content creation.

During preprocess generation, the relevant tile meshes are displayed briefly, with boundaries of the tile's represented regions drawn (in red).

After preprocess generation is completed an agent is placed into the world, and can be moved around under user control.
A point-and-click interface is supplied, with left mouse clicks against the ground mesh selecting positions for the agent to move to.
The camera can be rotated around the agent by moving the mouse whilst the right mouse button is held down.

Things to Note

The agent switches between tiles as necessary to move across the world.
You can see this switch graphically because the set of geometry included in the current tile changes, and because the ground texture shifts when switching.

The tile switch is delayed until the user clicks a new target position, or until the agent reaches the end of a path.
So, in the testbed, this means that while the agent is moving along a path outside the current tile's handled region you cannot see all the geometry that is potentially reachable by the next pathfind.
In a real application, of course, the set of pickable geometry will usually be managed separately from PathEngine's ground meshes.

Implementation Issues

This example uses a relatively large tile size, and a relatively low overlap value.
The code then allows pathfinding within the entire represented region for the current tile, by preconfiguring collision contexts with the relevant query bounds, as follows:

// set up a collision context for each tile
// with query bounds that restrict pathfinding to the tile's represented region
// query bounds act on agent origin, so the region is brought in by agentSize
// so that the agent's shape does not overlap outside the represented region
    contexts[i] = tileMeshes[i]->newContext();
    int32_t minX, minY, maxX, maxY;
    federation->getRepresentedRegion_Local(i, minX, minY, maxX, maxY);
    assertD(maxX - minX > agentSize * 2); // the tile overlap must be large than agent size
    assertD(maxY - minY > agentSize * 2);
    minX += agentSize;
    minY += agentSize;
    maxX -= agentSize;
    maxY -= agentSize;
    contexts[i]->setQueryBounds(minX, minY, maxX, maxY);

The is the recommended general approach for many situations because this allows the agent to pathfind quite a long way from most positions, at minimal cost in terms of total overlap across all the tile meshes, but with the drawback that there are positions where the agent cannot pathfind further than that overlap distance.
(Try moving the agent up to just before the point where tiles switch, to see the worst case situation. If moving out of the tile you can then only click up to the edge of the red represented region boundary.)
If more consistent pathfinding limits are required then an alternative approach is to adjust the pathfinding query bounds dynamically to a square region around the agent's current location.
In this case a larger value for the overlap distance is usually required.

Choosing Values for Federation Tile Step and Overlap in a Real Application

Tile step and overlap values can be expected to vary greatly from one application to another depending on specific requirements with respect to things like pathfinding performance, memory footprint, file sizes, and preprocessing tiles.
The actual values to use for federation tile size and overlap in a real application can only really be determined by benchmarking against the kind of environments you need to work with in that application, and for the kind of useage scenarios you expect to see in the application.

Changing the World Mesh or Tiling Parameters

It is straightforward to change the world mesh used in the example, and the values for the federation tile step and overlap.
This is a great way to get a feel for how well federated pathfinding will work against your specific environments.

Switching to 'tile by tile' federation construction

As supplied, this example builds the mesh federation from a supplied world mesh, but the example also includes code for construction of a tile by tile mesh federation, with both 2D and 3D content processes.

Code paths for tile-by-tile construction using the 2D content process can be found in 'BuildFederation_TileByTile.cpp'.
This code is based on a set of content chunks and the same placement script setup used in the 'contentchunks' example.

Code paths for tile-by-tile construction using the 3D content process can be found in 'BuildFederation_TileByTileCP3D.cpp'.
These code paths require the the 3D Content Processing Demo to be run first to generate a set of ground pieces that can then be loaded and combined to form a suitable set of federation tile meshes.

To switch to one of these tile by tile construction methods simply comment out the following lines, in 'SDKRoot/samples/meshfederation/Main.cpp', and uncomment a call below corresponding to the desired construction method:

const int32_t tileStep = 8000;
    const int32_t overlap = 2000;
    const int32_t agentSize = 20;
    BuildFederation_FromWorldMesh(pathEngine, testBed, "thainesford_town", tileStep, overlap);