Doug Kavendek - Portfolio


Flocking pt. 2
Title Flocking simulation
Date 2006
Platforms Windows
Created For Theory of Object Oriented Design
Download All files (2.4 MB)
Boids flying about in the new, hierarchical binning system

My flocking program always seemed woefully incomplete, needing an actual environment in which the boids could fly about, dodging predators, finding food, and multiplying. The black background and big yellow spheres just didn't seem enough. Realizing I now had some semblance of a terrain engine to work with, I decided to finagle a class project however I could so that I could make something more of it.

I did this as my final project for the Theory of Object Oriented Design class. Half the work was put into designing object interactions within a modeling language called Alloy, after which we had to actually implement this design. I developed a model of the world that involved not just boids and spheres, but boids, falcons, cats, ground, food, and boundaries. The various interactions, desires, and such were formalized in this modeling language.

Land-based creatures!

I then tried to dig through my terrain code in an effort to make it work with something other than what it was initially designed for. There actually were quite a few conversion problems, most of which resulted from trying to undo some of the last-minute changes I had made to the code when I was last working on it -- undocumented, untested hacks implemented in the middle of the night mere days before the deadline do not make for very portable or reusable code. Through both luck and providence, I did manage to get it to work with an environment comprised of just my creatures, and I sculpted out the C++ representations of the Alloy models.

Boids, falcons, and cats testing the limits

One major bit of original work in this project involved developing a much better binning system. One of the problems with my older bin system was that just finding the appropriate bin could be fairly time-consuming, because it had to go through a list of active bins to find which one has the right coordinates. This kept the time requirements from staying linear, so I came up with a hierarchical structure that would simply drop down a tree to find a particular bin, so no matter how many bins are active, it will only search through however many bins are located in the lowest tree branch near the target bin. This allowed many more creatures to be active at once, since it was now brought much closer to linear.

A falcon giving chase

However, as seems to always be the case, I had less time than I thought, and so couldn't fully test the various parameters. The tolerances of the creatures, and the weights of their individual forces do not seem to balance as well as I'd hoped, making the movement not very realistic. Falcons and cats do pursue and kill boids, boids try to avoid them while searching out food, but it just does not appear as elegant as it could be. Also, graphical effects serve to limit the number of creatures far more than the calculations themselves, as the rendering is not handled terribly well. As you can see, they are all very simple shapes, with the cats being nothing more than blue boxes -- I had worked with models and such already, but just didn't have the time to enhance it more. One day I plan on making a flocking version that I actually like.

Of course, there are still some nice touches to it. The boid trails look rather interesting, while showing the flocking behavior much more easily. The bin system really does allow many more boids than the previous version. Boids actually can land on the ground and walk around a bit to rest, and will take off if they notice a predator approaching them. And finally, the boid-cam is even more dizzying and crazy, which can be fun if your stomach can handle it.

Performance was definitely taking a hit around 20,000 creatures
Circling about in the air
Displaying only boids
A flock lowers towards the food (the wire sphere)
A few boids lifting off while the rest of their flock remains perched
A cat prepares to take its meal