• Advertisement

Archived

This topic is now archived and is closed to further replies.

Obstacle Avoidance

This topic is 5025 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I haven''t been able to find a whole lot of information on solid obstacle avoidance techniques. Basically, I know how to use A* or best first pathfinding to create a path from one point to another. My problem is that I want to have 10+ moving objects creating and running these paths in a restricted space. Also, the player will be crossing over these paths from time to time. I am looking for a way for the moving objects to be able to avoid other moving objects without forgetting their path. (They will need to avoid other obstacles and then resume their path to their destination). I have a few ideas that I''m tossing around: 1. Have objects drop all pathing when they enter the proximity of another moving object. The objects will avoid each other and then compute a new path from their new position. 2. Objects will all repulse other objects, thus keeping them from intersecting. Once an object is no longer in repulsion range, it will continue to move to the next point on its path. 3. Objects will simply collide. On collision, objects will move around each other (Only want to do this if I have to). I know obstacle avoidance is a shady field, but are any of my ideas plausible, or is there something better? Thank you!

Share this post


Link to post
Share on other sites
Advertisement
http://www.red3d.com/cwr/steer/

Check out Queuing and Unaligned Collision Avoidance.

Share this post


Link to post
Share on other sites
if it''s real time, have them collide or slide in some fashion, and take that as the que to recalculate the path for those units. If it''s turn based, just recalculate the paths for everyone every so often and you''ll get a natural "avoidance" feel to their motions. In your pathfinding alg of course, you need to up the cost of moving anywhere that has another unit inside a local area. That way, the pathing favors ways around other units instead of through them. If you redo everyone''s paths with this in mind, they will move around each other in most cases.

Share this post


Link to post
Share on other sites
Thank you everyone
It will be real time so the slide sounds like a good and simple idea. I guess that''s how most games I''ve seen have done it. Thanks!

Share this post


Link to post
Share on other sites
You can do that by having two walk states: something like follow_path and evade_unit. Also have each unit know where it should go next along it''s path.

While in follow_path, have your units check for other units slightly ahead of them. If another unit is found, switch to evade_unit.

While in evade_unit, calculate a "strafe" vector around the blocking unit. You do that by calculate the cross product between the vector from the evading unit to the blocking unit and your world up vector. Then you feed the evading unit that vector, and repeat in every iteration. That way the evading unit will beautifully circle around the blocking unit.

You also need to calculate the dot product between the vector from the evade unit to the blocking unit and the path vector (vector from the origin path node and the destination path node). When the dotproduct becomes negative, it''s time to stop evading and go back to the path, since this means the character got past the obstacle. If you want it to stpo evading only when it gets very close to the original path, perform the dot product using normalized vectors, and stop evading when it gets smaller than -0.7 or something.

Additionally, you could add extra actions to perform if the unit collides with something else while evading.

Share this post


Link to post
Share on other sites

  • Advertisement