Hi,

I'm looking into vector field path planning for large amounts of units at once over 3D environments. I came across navigation meshes which I don't really know much about but from some brief research I was thinking about storing the vector field in a navigation mesh instead of in a conventional grid. Has anyone got any advice on this and should I research more into navigation meshes or is it not a good idea???

Thanks

I'm trying to think of how that would work and/or what you're getting at here. Usually vector field stuff doesn't have much to do with typical path planning things in the A*/navmesh way.

I'm dubious as well. The whole idea behind a navmesh is that you are looking for large, convex polygons that accurately describe the traversable space. You want the polygons to be large, because the smaller they are the more of them you will have, and the deeper your search will have to go to find a path. On the other hand, a vector field relies on a much more fine-grained mesh, so that you can have different forces for each node. The larger the tiles in your mesh, the less information your vector field will contain, which will quickly lead to degradation in the appearance of the result.

With that said, if what you want is to represent large scale flows with little or no granularity, maybe this could work - but in that case, rather than a force in each navmesh cell, why not just have a pointer to the cell that you should travel to next? Which is really just a way to hard-code paths, I suppose - not sure if that's what you need.

The typical solution when moving a formation of characters is to do the pathplanning for just one of the characters, and then have the others follow parallel paths with some fixed offset. Obviously, this gets tricky if your path takes your formation too close to an obstacle (were some of the parallel paths would pass through the obstacle), so you either have to write your path planning so that doesn't happen, or use local collision avoidance to handle it when it does.

Dave just cited Chris Jurney's AIGPW4 article on this thread:

http://www.gamedev.net/community/forums/topic.asp?topic_id=588212

That might be a good article to read for this problem as well...

There is some robotics literature on doing exactly this.

Do you want to solve the single-source problem? I.e., you want to get lots of units to a single goal point? Then your idea makes tons of sense.

The basic idea is to do a breadth-first flood-fill out from the goal node, filling your navmesh with distances from the goal (along the shortest path). Then the vector field is the negative gradient of this function.

Makes total sense.

Thanks for the replies.

Yes Emergent that sounds pretty much exactly what I want to do. Can you suggest any literature I might look in to please.

And also do you think this would be scalable?? i.e could cope with a large environment.

Also Kevin Dill thanks, I am aware of the method you are talking about and have read up on getting one unit to perform a search such as A* and getting the other units to follow them using methods such as flocking and vector fields. I was trying to steer clear of A* and look deeper into vector fields. Maybe by having a couple which influence each other (local and global). I'll have a look at that Chris Jurney's article when I get a chance.

There's a bunch of stuff, e.g. this and this. There are lots of variations.

That's exactly what I'm after, very interesting, thank you.

Those papers are very interesting, I'm going to set about trying to implement some of the ideas explained for my project.

Can anyone give any examples of games which use vector fields primarily for there path finding please??

Not a lot at all. There was a good article in one of the AI Game Programming Wisdom books about how Blood Wake used local flow fields for the boat navigation. Each boat carried with them a flow field that would "suggest" to other boats that they should pass behind them rather than cut in front of them.

It is not confirmed that I know of, but the speculation is that Starcraft 2 uses temporary flow fields and/or path following (not finding) to do large groups of units moving together (there's a video of hundreds of zerglings moving together).

Yea, I've seen Starcraft 2 and supreme commander 2 as well I think does. I'll see if I can find this article you speak of.

Thanks.