Design Decisions

Description

The paradigm chosen for PathEngine is the result of a number of design decisions. This page explains some of the reasoning behind the functionality provided by PathEngine, from a higher level design perspective.

The architecture behind PathEngine evolved through lessons learnt over a number of projects in the application domain of real time computer games.
Initially, the design targeted computer games with 'cinematic' style realistic character animation, a great deal of content (large game worlds), and requiring robust agent movement to support in-game cut scenes and interesting AI.
The architecture subsequently proved to be just as effective in other, more action orientated games, and also in other application domains, but an understanding of the requirements and priorities behind the original design decisions made in choosing PathEngine's architecture is still useful in understanding the key strengths and weaknesses of the engine.

Design priorities

Content

For games with a lot of content it is essential to burden the content creators with as little pathfinding related hassle as possible.
A pathfinding system will naturally impose constraints on the kinds of world it can support. A lot of effort has been made with PathEngine to relax these constraints.
PathEngine is built around continuous spaces and polygonal boundaries because there is nothing worse for stifling creativity than restricting designers to the blocky shapes most easily supported by a tile-based pathfinder. Better still, PathEngine supports arbitrary self-overlapping geometry (bridges, tunnels and so on).

Also very important, but not obviously relevant to the content side, a pathfinding system needs to behave robustly for all the potential pathological configurations of geometry that it is possible to create in your world editor.
Content creators should not find themselves being asked to tweak the world because a particular AI fails, given certain configuration of geometry.
(If they are, then all of a sudden the content creation process becomes a brittle process, where creators are afraid of making changes in case this breaks something.)

From the content side, a requirement to place waypoints and to ensure that all parts of the world are reachable from at least one waypoint is a killer.
This is why PathEngine uses 'points of visibility' pathfinding, with code to expand geometry automatically and place waypoints at each point of visibility.

For games with small worlds, for which content creation is a less important consideration, different design decisions might be made.

Realistic looking movement

For games requiring a 'cinematic' quality, character blocking against or walking through the scenery must absolutely be avoided.
Given that we don't want simplistic looking environments, and that we want characters to be able to effectively plan movement around the environment, the conclusion is that we need our pathfinder to supports a collision model that corresponds as closely as possible to the apparent reality of the game world.
This is why PathEngine is based on continuous spaces and polygonal boundaries and supports pathfinding for agents of different sizes.

For games that don't require a 'cinematic' quality, and for which other goals are more important than realism, different design decisions might be made.

Interesting and robust behaviours

There can be a number of reasons why robust agent movement is important.
When implementing in-game cut scenes a common technique is to have scripts that wait for agents to reach their target position. In this case it's a very bad thing for an agent to fail to reach their target because of some quirk in the pathfinding.

Robust and predictable pathfinding is also key in enabling AI programmers to create more interesting behaviours.
Most importantly, AI programmers shouldn't be spending their time tweaking behaviour code to fix problems with agents failing to negotiate obstacles. This should be guaranteed at a more fundamental level.
Furthermore, a pathfinding system should include facilities to enable reasoning about the possibilities for movement.

The key to robust pathfinding is the relationship between pathfinding, on the one hand, and the collision actually applied to agent movement, on the other.
Because it is based on a fairly sophisticated and well defined movement model, PathEngine opens up various possibilities for robust pathfinding being factored in at a fundamental architectural level.
For example, it is possible to use exactly identical collision for both movement planning and subsequent motion execution, in many cases.
Or, because the PathEngine movement model is geometrically well defined, this is also well suited for application in parallel with more complicated collision, or as part of a hierarchy of collision systems. (Powerful 'find closest unobstructed position' functionality being available to then map back into pathfinding unobstructed space as required.)

PathEngine then provides a dynamic obstacles and 'collision context' mechanism enabling the AI to easily represent states of collision and to query possibilities for movement for any given state. (A state of collision might represent a 'real' state of collision, an agent's 'knowledge' of collision, or even a virtual, or postulated world state.)

For games where realistic movement is not so important it might make more sense to simplify the collision applied to agent movement.

Other requirements

Vehicles and 'racing game' paths

The PathEngine movement model, and therefore the configuration space through which pathfinding takes place, is based on agents that translate, but do not rotate, and without turn constraints.
While PathEngine guarantees to find the geometrically shortest path to a given point, then, for a given, rotationally symmetrical agent shape, it does not solve for more complex motion possibilities such as for vehicles with limited turning circles or for fastest racing game paths.

But pathfinding 'correctly' with respect to things like agent rotation, inertia and turn constraints is a very difficult problem.
Some academic motion planning, or commercial robot movement planning systems handle these kinds of additional constraints essentially by adding extra dimensions to the pathfinding configuration space, but at very significant cost in terms of the data representations then required to query against that space, and resulting query times.
And in most practical situations for application in real time games or simulations, therefore, shortcuts are inevitable.

Unless solving for these kinds of additional movement constraints is a key feature of your application, then, and unless this is applied in situations with significantly reduced complexity, or unless very significant processing resources can be devoted to this problem, this basically means searching through a simplified configuration space, augmented with direct tests and custom logic to take additional movement constraints into account as best as possible, in the context of a specific set of overall behaviour and motion requirements.

In the context of PathEngine, our fast agent collision testing functionality can then provide a very good base for this kind of thing.
One example is provided by PathEngine's built-in path post processing, which is based on a 'generate and test' mechanism for adapting a base path to a given set of turn constraints.
But it is also possible to break this kind of post processing completely out of the API, so that this can be adapted to match a more specific set of movement constraints, or for other game specific tweaking, and there are other ways in which PathEngine's dynamic obstacle functionality can also be applied to this problem.

RTS-style large numbers of blocking agents

In a traditional RTS situation with large numbers of agents and with each individual agent treated as a 'hard obstacle' for other agents, 'old style' tiled pathfinding is probably still more appropriate, because of the possibility to represent all blocking agents through a one bit per tile setup.
(But note that PathEngine has been applied successfully against very dynamic situations, and within the RTS genre. In situations where looser inter-agent interactions can be applied, the example shows how an approach based on double buffering pathfinding preprocess can be applied very effectively for these kinds of requirements.)

RTS-style influence mapping

Because PathEngine uses a continuous-space movement model RTS-style influence mapping techniques are harder to implement than in a straightforward tile-based pathfinder.