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

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

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.