Sweet!

-=[ Megahertz ]=-

Nice work - yeah, I reckon you might be able to sell this. You'd need to make it so that it could be plugged in to stuff, or at least have some kind of interface to other software.

Hey, this is great work!
I don't know realy, but I think it's going to be hard to sell it unless you are not going to make a strong branding like Havoc, but that is just my opinion. It would be great to see it as an OpenSource project.

What kind of interface do you have in mind, and into what stuff do you want to plug it in? Just curious.

Great Work.

I have often wondered who something like this would work. Commandos is one of my favourite games, and was always in awe about how, the character, would always find a path between where they were and where the wanted to go, (depending on where the user clicked). From seeing this and looking at your site, it is more complex than I then believed.

What is Middleware? Somewhere between ShareWare and Full Comercial Products?

Giant

I think the best selling argument is to have the pathfind engine successfully implemented in a game. Maybe you can find a little game group, where you can implement (and test your engine in real applications, not in test programs only) your stuff.

Middleware means that it is something that you incorporate in your apps without really knowing how it works. You just plug it in and voila you got the services offered by the middleware software. All you have to know is how you interface with it.

They key word here is services.

Yes, you have a point - one would want to incorporate the pathengine into whatever software was finally going to use it, for example a game engine. It might in that case also need to be incorporated in to a game editor. For most people I suppose this would require that pathengine was supplied as source. Maybe, I dunno :)

By interface I meant: "What do you input to the path engine?" and "How can I get my results from the engine?", because without some way to format the data you're sending and recieving, the middleware is probably not going to be very attractive to developers.

That is wicked! I'm not really a "programming person" (as someone once put it, "maybe [programming] isn't your cup of tea?" :) ) but does this use "nodes" or path points or something, or can it figure out on it's own how to get from point A to point B?

I would recommend that you make a game out of your work- probably the best way for people to notice it is to compete with it!

I've often thought Middleware would feature heavily in the future of games. As games get bigger and more complicated, the more time (and money) than can be saved with products like this the better... The only problem is that middleware often tends to be more generalised, and therefore slower or less memory efficient than a system explicity written for a particular game.

I would be interested to know how much your system suffers from this, and to see some stats about how fast/efficient it is.

Those generalisation problems will probably become less important as processors get faster and memory gets cheaper anyway... My advice would be to try and get it to be implemented in a game (maybe for free), and that will give other people the confidence to invest in it. Even if you don't sell many licences at first, I'd try and keep developing it because, like I said before, I think the time of Middleware is near...

Good luck :)

I think the main issue for integration is generation of the pathfinding mesh. This mesh needs to correspond with the walkable surface in game. (Although it doesnt need to take the shape of the pathfinding agent into account.)

Currently the mesh can be edited by hand in Max, or generated by a modifier stack of booleans from a ground surface and a set of obstacles. The second method is a pain to set up but this way the mesh is automatically updated when an obstacle is moved.
I will be looking for ways to make it easier for people to generate this mesh.

The second issue for integration is the relationship between pathfinding and collision. I hope to put an article up soon explaining the possibilities for this relationship. By defining a relationship between pathfinding and collision, the pathfinder can take responsibility for making sure that behaviour can actually be implemented through collision.

Apart from those issues a pathfinder can really be pretty autonomous.

I agree with Twig - good quality middleware might come in VERY handy
for many things in a large game project - especially when the teams
are small (maybe amateur projects).

Many developers already uses middleware for sound (in my case I use
FMOD rather than doing my own 3d sound library)... and I guess you
might say we also use "middleware" when we use graphics APIs like
D3D or openGL (I remember the days where I wrote my own gouraud
shading routines for rasterizing my triangles...)

If a good, clean and efficient interface were developed for a system
like this pathfinding library then I would probably be interested in
using it. Basically I should be able to throw in a polygon soup and
define some waypoints in 3d space.. And then simply query the system
for a path from waypoint A to waypoint B.

I'm not sure how much I would be willing to PAY for such a system - I
guess it kinda depends on what features is implemented. But I would
probably also consider if I NEED any fancy features... maybe I just
want a simple functionality like described above. But I guess a $100
license or so would always be cheaper than putting a man on the job
(in a commercial project).

To the author: maybe you could consider a license scheme somewhat like
the one FMOD offers. Ie. free (and uncrippeled) for evaluation and
freeware projects - but a fee is charged for commercial projects.
That way the product could be well known among amateur programmers and
when they later get a job in the industry they might point at your
product and get their tech-lead to buy a license...

- Telemachos

To actually use the pathfinder you have an API based around the set of queries that can be made to the pathfinder.

Examples of queries are:
testing collision at a point or for a movement line,
finding the shortest path between two points,
finding the closest valid point to an obstructed point

Dynamic obstacles are managed by passing 'context' objects into a query.

A path is returned as a sequence of points (in a buffer managed internally by the pathfinder).

The overlapping geometry complicates things slightly. This is managed by functions that translate between points defined by position in the mesh and 3d points.

I'll be adding some documentation about the API soon on the website.

In fact there are a number of games I worked on that used pathfinding systems functionally very similar to this one, although internally very different. (and not as well featured)

"The only problem is that middleware often tends to be more generalised, and therefore slower or less memory efficient than a system explicity written for a particular game. "

This is true, but on the flip side with a middleware solution I can implement optimisations that I am hard pressed to find time for in a typical game schedule. And I can continue to improve the system as time goes by.

The code is currently not so fast. It currently takes about 6 milliseconds for worst case in that demo on my p3-800. That is much too slow but it is still missing some major optimisations. The goal is for a worst case of a couple of hundred microseconds on a reasonable spec PC or next gen console, with much more complicated maps.

It figures it out on its own :)

I like Kasper's idea for lisensing. Programmers are much more likely to push a product if they have used it before, but they dont usually want to pay money to make a freeware game of their own. Your biggest problem is going to be working with whatever geometry format the client game is using though. Maybe your best bet is to integrate it with a geometry format, and force the client game to be based on that. It is a little restricting, but it takes away many problems of interfacing. Just a thought.

They key word here is services.

Do you work for Microsoft? I swear I heard that sentiment somewhere in the latest DirectX spec.

You said the geometry can overlap itself in the vertical direction, but can the paths? In other words, is the pathfinding really 3D or basically 2D? Your screenshot shows essentially a 2D map.

The pathfinding looks really good though, in the sample map.

You might say the pathfinding is 2.5D.
The paths describe possible movement for an agent that moves on the surface of the mesh.
So yes where the mesh overlaps itself so can the paths.
In the centre of the image you can see an example of this.

I have to check out yer site. I've been mulling over a technique that sounds very similar to yours for the last few months. I actually intended to start programming it as my first foray into C++ (I'm a C guy). Nice work!

Since you don't know if it would sell then why not make it OpenSource and commercially free under the LGPL. Then just make a clause that you have to credit using your lib, and a nice donation would be welcome if the project goes mainstream, IMHO devs would donate if they use it in a successful project. You can always later make it closed source and charge for it, after it has gained popularity and features.

Hm...if the demo works fine and interesting, there's no problem to sell it...
have to got the marketing instinct

>The first twist is that the geometry is allowed to overlap itself
>in the vertical direction.

Is that a twist? With the appropriate connectivity data, this just shouldn't matter. First, you extract the connectivity graph from geometry, then you just pathfind in the graph. Neither seems like it would need "twisting" to work in 3D.

>The second twist is that dynamic obstacles are supported and the
>shapes of those obstacles expanded at run time.

This is useful, although dangerous. You have to allow the calling
application to hint that it knows how to remove obstacles (open
doors, kill guards, whatever) else the algorithm may oscillate as guards patrol in/out of corridors, or automatic doors open/close, or whatever.

The controls don't seem to be working for me. I put it in the number pad and the numbers above the letters, nothing :/

It is difficult to know what to do when these kinds of problems come up.

Stinky: what operating system are you running on?
Let me know if it works after a reboot or anything like that.
Did anyone else have any problems with the controls?

I'll sort another version of the testbed with more checking.
Also after I find a bit of time to tidy up the source for this testbed a bit I'll make this source available.
This way at least there is the possibility for whoever is experiencing the problem to be able to debug what exactly is going on on their system.

Perhaps some people will also find this kind of testbed useful.
(Although I know there are millions of dx wrappers available already.)

bgl:

>>The first twist is that the geometry is allowed to overlap itself
>>in the vertical direction.
>
>Is that a twist? With the appropriate connectivity data, this just
>shouldn't matter. First, you extract the connectivity graph from
>geometry, then you just pathfind in the graph. Neither seems like it
>would need "twisting" to work in 3D.

If the pathfinder simply returned a sequence of mesh faces to connect start and goal then yeah you would be right - the overlapping geometry would be no problem at all.
But in fact it is a bit more complex than this.
For the shortest path query, the pathfinder returns a guaranteed shortest path between start and goal points for unobstructed movement of the agent with the specified collision model.

To do this the pathfinder must expand the edges of the mesh by adding the negated shape of the agent.
This expansion must be clipped against the overlapping geometry to prevent the expanded edges incorrectly being applied to overlapped parts of the geometry.
This is what adds the 'twist' to the problem.

>>The second twist is that dynamic obstacles are supported and the
>>shapes of those obstacles expanded at run time.
>
>This is useful, although dangerous. You have to allow the calling
>application to hint that it knows how to remove obstacles (open
>doors, kill guards, whatever) else the algorithm may oscillate as >guards patrol in/out of corridors, or automatic doors open/close, or >whatever.

Yes this is an important point. From a behaviour point of view the pathfinder should ignore these kinds of obstacles when generating long distance paths.

PathEngine provides a context management system for organising different sets of obstacles into different 'obstruction contexts'.

This makes it easy, for example, to exclude these kinds of obstructions when making pathfinding calls but to include them for checking collision a short distance ahead along a path as an agent travels along that path. When a collision is detected behaviour or animation code can take the right action to deal with the obstruction, e.g. kill the hapless obstructing agent, wait for the automatic door to open, or whatever.

The context mechanism also makes it easier to deal with any obstacles that change state but that cannot simply be treated in this kind of temporary manner.
For example if a guard discovers that a particular door is locked then an entry can be added to that guard's personal context to represent knowledge about the state of obstructions in the world.
This entry might be given a timeout to represent the fact the as time goes by it is more likely for the state of the obstacle to change.

I have also used the context mechanism for more complex interactions with other characters. For example you can create some interesting avoidance behaviours by detecting future collisions with other moving characters then and placing imaginary obstacles at the positions of the expected collisions.

I hope to put some articles on the site in the future about these kinds of issues along with example code for implementing these kinds of behaviours with PathEngine.

Hmm odd. 30 minutes later I gave it another try, worked fine...

The main problem with middleware is that you must know what functionality does offer it. For an example, take Oracle: You can download the complete version and try it, but if you want to use it "Comercially" then you must pay for it. As long as it is stable and easy to use (eg. OpenGL) then everyone would use it. Think about the FMOD issue!!

Hi Thomas,

good to see yet another AI IOTD. It looks good. I suppose this corresponds to your AI Programming Wisdom chapter?

This would be attractive AI path-finding middleware to me when:
- the effort involved in developing/nicking something similar myself is less than the duration of the contract negotiation (which easily takes 1 month);
- it would offer, behind a narrow interface, a wide range of pathfinding algorithms, so I have the flexibility to use and swap:
--- pre-computed path tables (in a few variants, trading path retrieval time for memory consumption)
--- hierarchichal on-the-fly pathfinding
--- on-the-fly (A*) pathfinding with per NPC path caching policies
--- efficient multi-path pathfinding (so an NPC picks one of multiple 'good enough' paths to a destination, reducing its (artificial) predictability);
--- pathfinding optimized to large open terrain or indoors
--- take into account various movement constraints (accumulating falling damage, rocket jumps, ...)
--- take into account dynamic obstacles (often, proximity checks during movement and replanning is cheaper than trying to predict all exceptions the future might bring);
- it would provide as free downloads sample code and impressive benchmarks, so I have a chance at convincing my producer.

Think of C++'s STL: one interface to containers, and the ability to swap container implementation without much fuss.

There seems to be an interesting contrast between your experience "[...] a load of games that could all have used the same pathfinding system [...]" and mine (tactical fps AI):
in my case, a single game typically has multiple pathfinding algorithms (although all based on waypoints), in order to get the best performance for short paths, path length comparisons, squad level pathfinding and tactical pathfinding.

I'm looking forward any additional info you will provide on your site.

William

p.s. on your pathfinding.htm, 3rd bullet underneath "what can you do with pathfinding", the sentence looks garbled.