How to best simulate complex flocking behaviors in a real time graphics application.
Goals
My main purpose in this project was to gain a better understanding of the general techniques involved in generating real time flocking behavior with autonomous agents. Once I had sufficient knowledge I wanted to tackle the problem of making 2D and 3D flocking simulations as well as a 2D simulation which included a predator/prey dynamic.
What I Read
I have included my summarys of these papers in the handin directory.
Flocks, Herds, and Schools: A Distributed Behavior Model. Craig Reynolds.
Boids: Background and Update. Reynods' website.
Social Force Model for Pedestrian Dynamics. Dirk Helbing and Peter Molnar.
Constrained Animation by Matt Anderson, Eric McDaniel, and Stephen Chenney.
Not Bumping Into Things. Craig Reynolds.
Interaction with Groups of Autonomous Characters. Craig Reynolds.
Steering Behaviors for Autonomous Characters. Craig Reynolds.
Group Motion Graphs. Yu-Chi Lai, Stephen Chenney, and ShaoHua Fan.
Methodology Details
For simplicity's sake all of the implementations described below use explicit integration. I did notice some jitter artifacts which I think were probably a result of this choice, but they did not impair the overall movement of the agents.
Cow agents flocking in two dimentions. See also the video.
I started off with a basic boids implementation in two dimensions. My agents have a limited distance and angle of vision (145 degrees from the direction they face) and use the standard three forces from the boids paper. In order to combine the three forces the agents simply average them all. The agents also have a maximum turning force that they can exert, so they do not just bounce around like balls in a pinball machine. I spent quite a bit of time calibrating the agent's balance of forces and trying to find an optimal equation for the separation force. I eventually settled on weighting the separation and alignment forces equally and the cohesion force at about 1/100th of the weight of the other two. I found that if I made the cohesion force any stronger, the agents would tend to collide with each other. I was quite amused to discover that by simply tweaking the weights of the forces I could make my agents behave like herd animals, birds, or fish, though the standard forces my program defaults to are about half way between birds and herd animals.
I ended up using a hyperbolic curve for the separation function because I wanted the agents to react more gradually when they were far from each other and more sharply the closer they got. I found that the best I could do was to keep them from colliding once the simulation had 'settled down' a bit. When they were initially placed randomly, they would sometimes run into each other because they had insufficient turning force available to escape.
I also had some complications with how to contain the agents. Eventually I settled on simply teleporting them inside of an invisible box. This allowed the agents to stabilize into a flock without wandering out of sight, but it added the complication of implementing vision across the edges of the world-box.
Cow agents flocking in three dimentions. See also the video.
Once I had agents flocking in two dimensions I implemented a three dimensional flocking simulation. This did not require a great deal of code but it turned up a number of tricky bugs in my previous implementation. I also had the issue of finding the up vector of my flying cows to address. Following the boids paper I tried to correctly calculate the up that would cause the agents to bank in a aerodynamically reasonable way, but found that the small amount of jitter I had noticed caused the agents to swing about wildly. If I had more time I would have liked to keep a longer (and thus more smooth) memory of the agent's movements so as to implement more realistic banking angles. In the video presented above I have simply used a naive up for my agents based on the direction they are facing and the world up.
Cow agents being chased by a block. See also the video.
In order to allow the agents to flee from predators, I implemented a two dimensional simulation with a cube that you can use to chase the cows around. I allowed the cows to see this cube from twice as far away as they could see normal cows in the hopes of getting them to react to it sooner. I even set the repulsion force on the cube to be a linear force rather than hyperbolic like the force between the cows. However I found that in order to make the agents avoid the cube early on I had to weight it much more highly than their other forces. This would cause a large number of collisions between the agents as the jostled to escape from the cube.
Results and Observations
The application I created.
My resulting program is very flexible and allows you to switch between the three simulation modes, tweak the weights of the forces on the agents and change the number of agents in the simulation. I have handed in an executable that can be run in Mac OSX from the command line (it will lack textures, but this should not impair your ability to see what's going on) and a number of videos of my program in action.
I felt that overall I was relatively successful. While certain aspects of the simulation eluded me for more time that I liked, I got a good overall idea of how independent agent simulations work and how flocking can be done in particular.
Future Work
I did not meet my goal of creating a predator/prey simulation, but I feel that I was not so very far from doing so. Had I more time I would have also liked to incorporate a spacial data structure into the simulation. Performance analysis showed that the program spends most of its time trying to decide which cows can see which other cows, which is not surprising given that this task is O(n^2), where n is the number of cows. Unfortunately I did not have time to get my code compiling on Windows. I will probably do this on my own time after graduation.
