Submitted by , posted on 19 February 2002
Image Description, by
Here is a screenshot from an early demo for the pathfinding system I am hoping
to sell as middleware.
The demo can be found on www.pathengine.com.
The system works by expanding the edges of obstructed space inwards by a
minkowski sum with the shape of the pathfinding agent.
The pathfinding is then performed by treating the agent as a point in the
expanded geometry, and using points of visibility pathfinding.
The first twist is that the geometry is allowed to overlap itself in the
The second twist is that dynamic obstacles are supported and the shapes of those
obstacles expanded at run time.
Any convex shape is supported for the pathfinding agent. A separate expanded
geometry has to be generated for each agent used.
The collision model doesnt include agent rotation, so in practice it makes sense
to use a rotationally symmetric shape to approximate a circle. (The demo uses an
The demo is not heavily optimised but intended mainly to demonstrate the
functionality of the system.
What I really need to know is what people think of the basic idea of selling
this kind of system as middleware (particularly those of you working in the
From my personal experience I have worked on a load of games that could all have
used the same pathfinding system. I've also found that the interface to
pathfinding can be narrow and very well specified.
In fact, for my last two projects most of the development was done at a distance
without any major problems.
As the systems I am working on get more sophisticated it seems a shame for them
to be only used for one project.