Hello everybody,

So I have been working on a open source fish package that utilizes boids, you can check it out here.

Boids which is used for flocking, herding, and schooling in virtual simulations was originally invented in 1986 by Craig Reynolds.

I found, like most people do when they first implement boids, the straightforward implementation of the boids algorithm has an asymptotic complexity of O(n^2). I used this tutorial.

This has already been reduced through a process of creating neighborhoods to O(N) (Research Paper)](http://gamedevelopment.tutsplus.com/series/understanding-steering-behaviors--gamedev-12732). Instead of a fish iterating through all of its neighbors and determining which neighbors are within a certain distance and iterating over those neighbors again, the neighborhood method splits up the scene into a grid and each cube represents a neighborhood. When a fish wants to calculate where it should go, it no longer needs to evaluate all fish in the scene, only those within it’s neighborhood.

My implementation also has a asymptotic complexity of O(N). I originally used the straightforward implementation, and it was causing framerate issues when using them in game. I originally didn’t know about the neighborhood method, so I created my own very simple approach that is just as efficient and easier to implement. I do not claim that I am the first one to have done this, but I could not find any research using this approach. If you know of some, please pass on the link :).

My approach gives each boid actor an interaction sphere thats radius is the distance of the boids you want to account for. When a event overlap fires, the incoming neighbor is added to the neighbor array, and upon event end overlap, the actor is removed from the array. This gives the boids a asymptotic complexity of O(N). That’s it! No cutting up your entire scene for neighborhoods or anything. Let me know what you guys think.

GitHub to see my implementation.

Cheers,

Komodo