Not logged in, Join Here! or Log In Below:  
 
 News Articles Search    
 


Submitted by Thomas Young, posted on February 19, 2002



Image Description, by Thomas Young



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


[prev]		 Image of the Day Gallery
www.flipcode.com
[next]

 
Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Thomas Young

February 28, 2002, 10:04 AM

Hi William,

"I suppose this corresponds to your AI Programming Wisdom chapter?"

In fact I didn't write anything for Programming Wisdom, but the two I wrote for Gems 2 are both relevant, as well as one of the ones coming up in Gems 3.

You have some good points there. It is quite a demanding list, but if I can meet the requirements of someone like yourself then I will know I'm onto a winner :)

Look out for a release around the end of March / beginning of April that I hope will address a number of the issues you raise.
This release will include benchmarks for different kinds of maps, for example indoor maze-like maps and large open outdoor maps. The purpose is to show that the system performs reasonably well on both kinds of maps (although it will still not be fully optimised) and to communicate targets for further optimisations.

In the past I have used very different kinds of optimisations for indoor and outdoor maps. Currently I am looking at something that promises to be a bit of a 'magic bullet' and provide good optimisation for both kinds of maps. Where different optimisations are required this will be hidden below the interface.

PathEngine is organised in terms of a set of geometric queries, and these queries are just as applicable to short paths, long paths, or path length determination for decision making and so on. The idea is to provide a simpler interface for developers by hiding the implementation details for these queries below the API. Perhaps it is a good idea to enable the developer to provide 'hints' to save the pathfinder a bit of time when a choice of optimisations has to be made.

Per NPC caching is organised in terms of updating a path that has already been generated (with a new start and/or end point for example).

The tradeoff between memory and speed is an important issue and I will certainly be looking to give developers control over this tradeoff. I would like to hide the details about this as much as possible, so this will probably be organised an interface involving the developer setting a target amount of memory for the preprocess to use. PathEngine would then report the actual amount of memory used, which might fail to meet the target. A set of standard benchmarks would also be provided in the interface to allow the developer to make comparisons between unrestricted preprocess and restricted preprocess.

The movement constraints is the most difficult point.
Something like falling off a cliff can be represented by an edge in the ground mesh with a specified cost to traverse in each direction.
This model doesn't extend to something like accumulating damage, but features like this are not difficult to add. Support for the system will include this kind of minor customisation.

Stuff like rocket jumps are more difficult. For this kind of feature you really need something like the 'reachabilities' generated for the Quake3 AAS. But the process of generating these kind of reachabilities requires specific knowledge about the collision and movement code that will actually arbitrate this kind of movement.
I will be looking at the best way for developers to be able to generate their own 'reachibilities' and integrate these into PathEngine, if navigational support for this kind of 3d movement is required.

 
This thread contains 31 messages.
First Previous ( To view more messages, select a page: 0 1 ... out of 1) Next Last