Sign in to follow this  
scubabbl

Pathfinding through multiple moving objects.

Recommended Posts

scubabbl    132
Problem: you have objects moving across a plane and you need to find a path through them avoiding collision. Question: What's the best way to find a path through them avoiding collision given that you know their speed and heading when you start and they won't change course. All the pathfinding algorithms I know tend to deal with searching through static obstacles. Are there any methods out there for searching through moving obstacles?

Share this post


Link to post
Share on other sites
Think128    124
Off the top of my head, I'm thinking of something like this:

1) Calculate the time it would take for your script to intercept the path of the moving object. Then calculate where at that time the object will be. If the object is not in the way then you are in the clear. If the object is in the way then decide how much of a change in the path you will need to miss the object. There is probably some really nifty way to do this with degrees and knowing the speeds/directions of the two objects.

No warranty implied, this suggestion is based on zero experience :)

Share this post


Link to post
Share on other sites
corysama    342
If your obstacles are sparse enough I've had great success just applying Craig Reynold's steering behaviors to situations like this.

http://www.red3d.com/cwr/steer/

The only complicated part is coming up with a quick way to determine which objects you really need to pay attention to each frame. Otherwise its just

if (there is something in your way)
{ turn slowly away from the obstacle }
else
{ turn slowly toward your goal }
move forward.

It gives very lifelike motion and works great in highly dynamic situations.

Share this post


Link to post
Share on other sites
kaysik    382
The steering behavoiur stuff is really the best way todo it. Its quick, easy to compute and you can do it quite simply. I personally implimented it with a few weighted vectors like so:

- Get the vector from the current position to the goal and normalise it
- for ever object thats closer than MAX_DIST
--> get the vector from your position to the moving object
--> scale to something like MAX_DIST/vecLength so that the closer you get the larger the vector gets gets.
--> add to the goal vector
- cap that final vector to your maximum speed

Thats it. You'll always move towards your goal till you get close to something then you'll steer away from it. The closer you are the more you'll try to move away from the objects. If you have walls or a maze to navigate through as well you'll need something like A* to generate the maze path, then use steering to get to each checkpoint in your path. However if its an open terrain you don't need the path at all.

You can tweak the weights and also add things like a turning circle so that things can't change direction instantly but they're pretty easy once you have the base system which itself is extremely easy to code!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this