So I have been working on a open source fish package that utilizes boids, you can check it out here.
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.