• Advertisement
Sign in to follow this  

Flocking, Inter-Boid collision detection and proximty checking?

This topic is 4419 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

In the most naive implementation, flocking boids has an O(n^2) complexity, as each boid needs to compare with every other boid to find neighbor proximity info and to detect collisions. http://www.red3d.com/cwr/boids/ here Reynolds briefly mentions that near O(n) cost can be achieved with a 'spatial data structure' Is anyone familiar with the details of what he is reffering to? Thanks

Share this post


Link to post
Share on other sites
Advertisement
Yeah he's talking about spatial data structures as generally implemented in games for rendering/collision-detection optimization: quad-trees, oct-trees, etc. The name of a good spatial tree for moving objects is escaping me at the moment...look around in the articles & resources section of this site.

Then basically you query the spatial partition tree for the position of the boid of interest and get back the few nearest neighbors. performance on most of those trees is O(n log(n)) or better.

-me

Share this post


Link to post
Share on other sites
Though it's only a constant-factor improvement, if you divide your space up into regular-sized buckets, you ought to be fine looking on only the nearest 1 to 4 buckets ( assuming they're square ).

It should be quite simple to try in any case, even if it's not the fastest. It would be trivial to support moving objects in it too, since you'd just remove the pointer from one bucket and put it in the other.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement