I’ve worked with graph and tile based pathing, but I need something that will work for true 3d real-time pathing. What I have basically is a bunch of sphere’s moving in 3d space. I would like to make a pathing method that will get an object from point A to point B, while avoiding these other ships. As the location of all these obstacles (which will be using this algorithm to get to their destination) changes rapidly, I would think it would be best to create a greedy method that will look at the current state and make a choice based on what’s an immediate threat of running into. This would be opposed to pre planning an entire path every time objects move (something like A*). This also needs to be done fast as thousands of objects will be doing this at 10 frames per second. This takes away ideas like creating a potential field and following a gradient , or something of that nature. I have some ideas on how to do this, but would like to read or discuss this before trying to completely recreate the wheel. Any one have any good information or links that would be helpful?

If your spheres are not too dense, you can just program this as a combination of steering behaviours:



You can use some soft function to make the avoidance part smoother.

If this type of solution is not appropriate, post some typical situation, so we have a better idea of what might work.

Thanks for the reply alcaro,

The problem with that method is it very well could allow collisions to happen. I want a method that will not have that as a possibility. More details: the objects can go forward and turn up, down, left and right. They can do this while moving forward or are not moving.

A good example would be like in the Starwars movies, in space there are many fighters that are in combat with one another, ships costly pass by other ships without (ideally) hitting another ship.

Well, there are many optimizations you can do with a potential field approach that would make things go faster. With potential fields, the problem is that you may have to do many many comparisons and calculate all the composite effects of attraction and repulsion. However, this bottleneck can be overcome by simply setting a cut off-point beyond which you don't do any comparisons. You can easily apply a octree query to root out any objects too far away from the potential field calculations.

Also, since you have fast moving obstacles, it may be a good idea to add a doppler effect to the potential field/gradient calculations. So, an obstacle moving towards you would have a greater effect than an object moving away from you. Also, the affect will be proportional to the speed at which the object is coming towards or moving away from you. This is just one suggestion.

One important thing to think about is pathing for formations. If you have 5000 things going the same way, why check for a path for each of them?

Try to desgin your pathing around groups, so even if there is only one unit in that group, you still have the option to send 50 more units with it at no real extra pathing cost. I think that would be rather important in any kind of starwars style battles.

Quote: Original post by Talroth
One important thing to think about is pathing for formations. If you have 5000 things going the same way, why check for a path for each of them?

Try to desgin your pathing around groups, so even if there is only one unit in that group, you still have the option to send 50 more units with it at no real extra pathing cost. I think that would be rather important in any kind of starwars style battles.

That won't be that simple when you consider that not all units in a group will be in the same area.

Quote: Original post by xor

Quote: Original post by Talroth
One important thing to think about is pathing for formations. If you have 5000 things going the same way, why check for a path for each of them?

Try to desgin your pathing around groups, so even if there is only one unit in that group, you still have the option to send 50 more units with it at no real extra pathing cost. I think that would be rather important in any kind of starwars style battles.

That won't be that simple when you consider that not all units in a group will be in the same area.

Well, gameplay hot-key groups are something different, I was talking about formationed groups. If they're not in the same area, then they're not in the same AI pathing group.


I'm thinking about it a bit more now, and my design idea could go either way as far as being better/faster or slower/harder to work with. Needs more thought.

Quote: Original post by skow
The problem with that method is it very well could allow collisions to happen. I want a method that will not have that as a possibility.

It's not possible to eliminate the chance of all collisions unless you are willing to grant your object infinite acceleration and velocity. Or unless there are other constraints to the system that aren't mentioned above.

If you set up the steering behaviours to have an almost infinitely high repulsion force at close distances (eg. 1/distance) you might find it works ok. You may even be able to build in some very simple planning to an avoidance behaviour, so that when a potential collision is forseen you can generate a few possible scenarios (eg. based on turning left, turning right, accelerating, decelerating) and determining which is best.

Another optimisation you can make if you're worried about speed of a simple algorithm, is to be very selective with the objects you compare against. Apart from the obvious thing of not checking objects that are too far away, you can also ignore objects that are near but which are heading away from you, at least for the near future. In fact you can generalise that to any object as there are constraints on how far they can move in a given time span.

Ahh, I forgot to say, objects instantly can stop, or hit full speed. And each object moving will be running this avoidance method, so it is possible.

Thanks for the discussion I think I have the ideas I need to create this.

Unless you know the trajectory of all objects for all time, then global path planning is going to be a waste of computational resources. If the objects moving around the domain can make decisions about how and where to move, then you're really into the 'difficult' end of the spectrum for path planning. You should definitely look at local, reactive techniques, such as steering behaviours or even subsumptive architectures.

I'd suggest using a heirarchy of local techniques. If your space has no fixed objects (so, for example, it is indeed space with lots of flying vessels, or asteroids), then a straight line between the current object and its goal is the best 'first guess' at a path. At another level in the heirarchy, local avoidance techniques will be necessary. However, if the object you are trying to avoid can also attempt to avoid you, then you have a problem with regards to coordination. If your objects are truly independent in their choices and there are no agreed upon norms for how two objects handle such situations, then collisions are always possible.

In addition to have a global strategy for the direction of the path and a local avoidance algorithm, I'd add another layer in the heirarchy that preferred avoidance toward regions of lower object density.

All of this leads me to think that a subsumptive architecture, or a mixture of expert models might be the way to go. Obviously though, there are many solutions that while being sub-optimal, might be completely satisfactory for your purposes. My best advice is to try several, play with them, tune them and then pick the one that works most efficiently and most robustly.

Cheers,

Timkin