Skip to main content
GameDev.net gamedev.net
🔒 Locked

Dynamic Obstacle Avoidance and Flocking

Started by zaloo Nov 18, 2013 at 10:16 PM 2 replies 5k views
Original Post
zaloo
zaloo

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!

zaloo
zaloo

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.

ApochPiQ
ApochPiQ

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.