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)](Understanding Steering Behaviors - Envato Tuts+ Game Development Tutorials). 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.
Erm, what do you think causes the event overlap? that isn’t exactly free you know.
The Physx implementation of pairs checking for overlap is pretty efficient though, broad phase sweep-and-prune (aka sort-and-sweep) with some form of temporal islands I believe. But anyway, yes it essentially does some spatial sorting so you aren’t doing an N squared check.
There’s a whole load of information about this kind of thing in Christer Errikson’s book “Real time collision detection” if anyone is interested. Although apparently we can get the PhysX source code now, so maybe that would be worth looking at.
My own favourite approach to this was John? Ratcliffe’s sphere tree implementation. Sphere trees being somewhat like spherical BVH with some velocity information used to inform a temporal component to the update cycle.
You’re right there, with the event overlaps, they do add complexity. I was considering implementing a “Boid Node” system if you will to reduce the number of overlaps firing. Essentially I could have only a few fish in a school that have these interaction spheres and the other fish would get information about neighbors from these fish.