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

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 vertical direction. 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 octagon.)

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 industry).

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.

Image of the Day Gallery



Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.