Influence map based boids in Flash
My friend Jonas Flensbak is about to finish his bachelor project in Computer Science. His subject of choice is flock behavior, with a focus on simulating flocks in computer games.
The study and simulation of flock behavior, which is called boids, was pioneered by Craig W. Reynolds who defined the following three simple rules for each member of a flock.
- Separation steer to avoid crowding local flockmates
- Alignment steer towards the average heading of local flockmates
- Cohesion steer to move toward the average position of local flockmates
Using these simple rules you are able to make very impressive — and realistic looking — flock simulations in both 2D and 3D. Sadley the basic algorithms does not scale very well, as it has a complexity of O(n2). Of course better algorithms, using advanced data structures and other tricks, have been developed.
Here is a flash implementation using the naive algorithms.
View result
Download source
New target
As with any computer program, one of Jonas’ goals was to be able to simulate as many flock members as possible. But instead of implementing someone else’s algorithm he choose to build his solution on influence maps (a system normally used for more complex AI). The idea is that you can offload the CPU by generating a lookup table in memory instead of calculating every single boid relation for each loop.
The resulting algorithm works like this.
For each rule you have an array with the same dimensions as your world (2D for 2D worlds, 3D for 3D worlds)*
- Reset all influence maps
- Iterate over all boids and add there influence to all affected fields
- Iterate over all boids again, this time reading nearby fields and adjusting each boid accordingly
Those of you who have played with computer code on a lover level will recognize that this can be done in O(n*2) –> O(n) as you can just use pointers to address the memory lookup table.
Implamentation
While discussing the project with Jonas, I felt the urge to make a 2D flash implementation of his ideas. As my Flash version of choice was 8 I did not have access to fast memory management as I would had I chosen to use flash 9’s and therefore I had to come up with something better then the naive implementation. After a bit of thinking I realized that everything could be hacked on top of the bitmapData class which supports fast Draw, set- and get-Pixel operations.
The idea is fairly simple, instead of trying to manage the data structure yourself, one can just draw each influencing factor on a bitmap canvas, and then for each boid use getPixel to read relevant values. Of course the data has to be drawn in such a way that each factor does not influence the other factors.To solve this issue I simply represent Separation using the red spectrum, Cohesion using the blue spectrum and have a separate bitmap where I use the full color spectrum to represent Alignment.
Also to make the engine work the influence of a flock should be greater the larger the flock is, such that a single flock member will adjust accordingly to the sum of the nearby flock members. To archive this I clear the canvas for each loop and use addictive color mixing when I draw. To allow for dense flocks each boids only use color values betwean 0-16(4 bits), as it allows for any boid to have 15 nearby neighbors.
Separation & Cohesion
Separation and Cohesion are both really easy to implament, I simply made a circular gradient — with high color intensity in the middle and none at the bord — for each, one small in read to give each boid some personal space, and one around three times as large in green to attract nearby flock mates. However as Separation and Cohesion are always drawn exactly on top of each other I optimized the engine by combining the two gradients into one single containing both.
Alignment
Alignment is a bit more complex as we need to represent rotation such that we can draw it with additive color mixing. The solution I choose was to represent the rotation of each boid as a unit vector then drawing a circle, using additive color mixing, where each vectors x value is drawn using the green color spectrum and each vectors y value drawn using the blue color spectrum. For each x and y value a variable between 0-16 is used, this gives us the same resolution as with Separation & Cohesion and again allows us to have 16 boids in the same small area.
All in all the result of this is that we can sample any point on the Alignment canvas and get the sum of the x and y values, of course to be able to calculate the average unit vector we need to know how many boids was actually effecting the sampled area. To archive this, whenever a color circle was drawn it also contained a red tint of 1 the red color spectrum, effectively using the red spectrum as a counter. Now having the counter its a rather simple matter of dividing the sum of x and y values with the vector count to get the average Alignment for any point.
Product
Although it might sound rather complex, the entire thing only uses around 200 lines of code.
View final result.
Download source code
One side effect of using this canvas implementation is that you can simply draw obstacle as red areas and targets as green areas on the Separation & Cohesion canvas.
Afterthoughts
If I where to rewrite the engine today I would use the alpha channel the blue spectrum from the Separation & Cohesion canvas to represent rotation. It was atually the original intention but I was afraid that 12 bits for for the unit — giving each boid a movement resolution of 4 — would not be enough. One could of course steal one bit from both Separation & Cohesion giving them a resolution of 8 instead of 16 and Alignment the same resolution as now. It might add a bit of complexity but it would make the engine a lot faster and a bit more impressive.
More
Jonas’ project page has a lot more information about influence map based boids and also includes a OpenGL implementation of whats described above which of course is very fast given that he write it in C and the the drawing power of modern graphics cards!
This work is licensed under a Creative Commons Attribution 2.5 License.
on September 11th, 2007 at 8:57 am
Dear Chris Benjaminsen
I am a professor in Korea who is very interested in Flocking.
But I never use the flash.
Now, I have a request for getting the source code of Visual C++ for the above works.
Is it possible? Did you have the source code of Visual C++ for the above works?
If you have, how can I get it?
Plaease let me know it as soon as possible.
Thanks
Jae Moon Lee