Dynamic Obstacle Avoidance and Flocking

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

Recommended Posts

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!

Share on other sites

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.

Share on other sites

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.

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 9
• 15
• 14
• Forum Statistics

• Total Topics
634070
• Total Posts
3015332
×