| PathEngine home | previous: | next: |
The paradigm chosen for PathEngine is the result 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.
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.
For games requiring a 'cinematic' quality,
situations where character walk through the environment must 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.
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 and
the collision that is actually applied to agent movement.
Because it is based on a fairly sophisticated collision model,
PathEngine enables game architectures where the collision applied is either
closely related, or identical to the collision model used in agent planning.
PathEngine also supplies methods for advancing along paths
that handle approximation of interpolated points in a robust way.
PathEngine provides a dynamic obstacles feature and a '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 a postulated state of collision.)
For games where realistic movement is not so important it might make more sense to simplify the collision applied to agent movement, as opposed to pathfinding with a more sophisticated model of collision.
While PathEngine guarantees to find the geometrically shortest path to a given point,
it does not guarantee to find the quickest path for an agent that moves with inertia
and turn constraints.
PathEngine does provides methods to take turn contraints into account as a post process.
See
Note that pathfinding 'correctly' with respect to inertia and turn constraints is a very difficult problem,
and so shortcuts are usually inevitable.
Unless solving inertial and turn constraints is a key feature of your application, path post processing
remains the recommended solution.
If this issue is important for your application then you should consider application level post processing
as well as the post processing built into PathEngine.
The PathEngine collision model is based on agents that translate,
but do not rotate.
Agents that are approximately circular are handled easily by using a regular polygon
to approximate a circle.
There is then no need for the rotation to be taken into account when generating paths.
PathEngine cannot generate paths that take into account the rotation of long thin agents.
Again, pathfinding correctly with respect to long thin agents is a very difficult problem,
and unless this is a key feature of of your application there are various tricks that can be used
within the PathEngine collision model,
based on the use of bounding shapes or chaining smaller shapes together.
Because PathEngine uses a continuous-space movement model RTS-style influence mapping techniques are harder to implement than in a straightforward tile-based pathfinder.
| Documentation for PathEngine release 5.16 - Copyright © 2002-2008 PathEngine | next: |