I was looking a way to improve the performance of the FlockDraw project and while I was reading a post on Robert Hodgin blog I saw a very interesting lib named OpenSteer created by the guru Craig Reynolds (he was the first one to simulate the Boid artificial behavior).
This lib seems to have what I need, an optimal and tested algorithm to do the flocking simulation (among other plugins).
Why I need it?
On flocking simulation the boids need to know where the oter boids are located to calculate its own movement (all of them are autonomous), knowing where the other boids are located, it need to verify if the other one is on its “action radius”, if it is, the movement calculation is called.
The first implementation (and it is what works better in my trials) was the brute force where the algorithm compares each boid to all the others resulting in amortized O(n²) comparisons. So if we work with 2.500 particles, 6.250.000 (3.125.000 with a little optimization) comparisons would be done each frame, in my humble opinion this number is too big to be processed 60 times per second.
I have tried to implement a very simple and rudimentary spatial index, but the time of insertion of the boids was taking too much CPU time, and the boids need to be reinserted on every quadrant change. This method took the double of CPU time than the brute force, although it have resulted in much fewer comparisons. If the boids didn’t move, this would be the perfect solution.
After the frustration I’ve decided to use an stable solution to do it. Everyone that have worked once with game coding know that some physics libraries are available. So I got the Box2D, made some modifications and used his space index and collision engine as the method to detect which boid was in the other “action radius”. The problem is that those collision libraries are prepared to manage, guess what? COLLISIONS!! And not hundreds of invisible fields that are the whole time invading each other.
I considered the usage of RVO2 library, but it provides other behavior the expected. It seems that Craig Reynolds’ OpenSteer is the most adequate.
First I’ll integrate the lib to libCinder as I did with with Box2D leading to CinderBox2D. After this integration, that may be called OpenSteerBlock or something like that, I’ll integrate it into FlockDraw, and let’s see what happens.