Functionality Overview

Purpose

The demo shows how PathEngine can be applied to reduce overhead, when there are large numbers of agents, and hard collision between these agents is required.

Update paradigm

In situations with lots of agents, it's important, instead of updating each agent one at a time, for us to implement independent agent update logic.

So the process for updating any given agent, in a given update step, should not depend on or interact with the update process for other agents in the same update step.

The main reasons for this are:

• To make it possible for the agents to all perform collision queries against one single snapshot of world state (which is immutable for the duration of the update step), and
• To make it possible for this update step to be run in parallel, on parallel hardware or multiple cores

(Note that, in this example, we don't actually run the individual agent updates in parallel, but that part should be fairly straightforward, and is left as an exercise for the reader!)

Move all agents and then collide

What we do in this example is to move all the agents along their paths, as a first update step, and then check for agent collision as a result of that update, with some collision propagation then required as a final step.

The movement part of the update is independent, because we just generate a new position for each agent, based on their current path, with collision against the world, but no collision against other agents.

Collision testing between agents after that update is then performed against a single world state (the world state after all the agents have moved), and is also an independent update step.

In cases where agents find themselves in collision, our resolution strategy is just to move them back to the position they were in before the movement update. It is possible that this now puts them into collision with some other agents, which is why a propagation step is then required in order to guarantee the hard collision invariant (but the number of collisions actually propagated in this way is small in normal situations, and doesn't affect update performance).

World state and internal collision preprocess

Note that PathEngine manages some (fairly minimal) collision preprocess, that must be updated after collision context changes.

This preprocess generation is very fast, but if there are a very large number of agents, and those agents are moved one at a time, then the overhead for this this can become significant.

By performing all agent collision tests against the same collision context, without any state changes, we ensure that this collision preprocess update only happens once per frame, and avoid a lot of unnecessary overhead.

Point collision

Using point collision queries (collision queries for agents as they are placed at a given postion) rather than of line collision queries (collision queries for agents moving along a line segment) is more efficient, and also helps to speed up the update.

A simpler update paradigm without propagation

Code for a simpler update paradigm, which does not require the collision propagation step, is also provided. (See CheckAndCollisionsAndRevert_Simple(), in the example code.)