View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Dynamic Obstacle Avoidance and Flocking

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

#1zaloo  Members

Posted 18 November 2013 - 04:16 PM

I'm working on an RTS and I've implemented a pathfinding approach that creates sub goals for units to reach, each of which should be able to be reached by steering forces alone. I've now implemented flocking and am about to start implementing obstacle avoidance (for dynamic obstacles), but I'm having trouble figuring out how to combine the two.

I've found a paper that describes an obstacle avoidance algorithm using steering (the algorithm is called ClearPath and can be found here: http://gamma.cs.unc.edu/CA/). The naive way to combine these steering forces (seek for the destination, flocking, and obstacle avoidance) is to find your initial velocity using seek, then add the flocking forces. Finally you use this velocity to calculate your obstacle avoidance steering force using an algorithm of your choice (ClearPath in this situation).

My question is that is this a good way to implement steering? It seems tough to make any strong guarentees when you just add various steering forces together. I'm also concerned with problems with choke points in the future, I don't my units to get stuck in bottlenecks. This solution obviously doesn't take that into account, and if there is some implementation that does, I'd rather use that.

If you know any research papers that deal with these issues, I'd appreciate links!

#2ApochPiQ  Moderators

Posted 18 November 2013 - 04:40 PM

Wielder of the Sacred Wands

#3zaloo  Members

Posted 18 November 2013 - 05:10 PM

Your approach seems nice, but much less efficient than the ClearPath approach. I assume that in high density situations, your obstacle avoidance produces many "collisions" that have to be handled, which can be quite expensive. If you look at the ClearPath algorithm, there is a incredibly low number of collisions. In every simulation in the video on the page linked, there are 0 collisions, even in situations where there are >1000 units that are densely packed.

I found a paper just 5 minutes after posting this that might be of use: http://homepages.dcc.ufmg.br/~chaimo/public/DARS2012.pdf . I haven't read it yet, but from the abstract it seems promising.

#4ApochPiQ  Moderators

Posted 18 November 2013 - 05:14 PM

Context maps are a solution to blending obstacle avoidance and flocking forces, not a solution for obstacle avoidance per se. As long as you generate a context map that handles zeroing out/negating the forces that lead towards obstacles, it works great.

Wielder of the Sacred Wands

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.