Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


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.

  • You cannot reply to this topic
3 replies to this topic

#1 zaloo   Members   -  Reputation: 119

Like
0Likes
Like

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!



Sponsor:

#2 ApochPiQ   Moderators   -  Reputation: 17497

Like
0Likes
Like

Posted 18 November 2013 - 04:40 PM

http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/smarter-steering-using-context-for-direction-r3149



#3 zaloo   Members   -  Reputation: 119

Like
0Likes
Like

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.



#4 ApochPiQ   Moderators   -  Reputation: 17497

Like
0Likes
Like

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.






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.



PARTNERS