Flocking - Final Report

In order to deal with this, a less rigidly defined system must be implemented, such that the animated characters do not follow strict paths, but rather adhere to a specified behavioral model. I have developed such a system, with a basis in the paper "Flocks, Herds, and Schools: A Distributed Behavioral Model", by Craig W. Reynolds. I have done a few things differently, but for the most part, my system uses the fundamental ideas expressed in this paper.

It is important to discuss the individual forces that interact with the boids. The most important of these forces would be the goal-seeking force, which invariable aims the boids towards a specific goal. Once the boids reach it, the next goal in a list becomes the new goal, and so on. This list can be randomly generated (for arbitrary flock movement), or scripted by simply plotting out the goal points and adding them to the initial goal list. This is not the most powerful of the forces (meaning, it has only an average weight), however, since it is important to let the lower-level flock interactions show while the boids move generally towards the goal. The goal force is calculated simply by finding the vector from the boid to the goal, and then normalizing it. Then, as with all the forces, the normalized force is multiplied by a weight specific to the force type before being concatenated with the other forces.

To keep flocks coherent (rather than having each boid set out for the goal on its own), there also has to be a willingness for the boids to form into flocks. This is satisfied through an attractive force that aims boids towards their neighboring boids. This is accomplished by finding the center of mass of the boid's surrounding set of boids, and then finding the vector towards this point and normalizing it. Of course, with just this, the boids would then simply converge onto all of their neighbors, which would not be very accurate behavior. So then, a repulsive force is calculated whenever boids are within a given range of each other, which is proportional to how close they are (so as to have less rigid boundaries - boids can then bump and almost bounce off each other a bit).

In regards to the previous two forces, however, I must mention the binning system. Actual flocks of birds are not influenced greatly by birds outside of their limited neighborhood of senses, and as such, flocks can grow to any size without birds losing the ability to deal with the amount of birds. However, if the boids in this simulation were to perform the previous checks against all the boids currently active, the computation time would grow exponentially, and high flock numbers would become unfeasible. To deal with this, I have developed a binning system that stores boids within large bins that divide the simulation space, and when a boid needs to check it's neighbors, it only refers to boids within the neighboring bins.

Flocks should also have a way of dealing with obstacles - actual birds have to steer around trees, telephone poles, and other such objects - so it would be useful to allow boids a way to interact with and avoid obstacles. The simulation space is populated with randomly placed spheres, which the boids then have to avoid. These obstacles are placed similarly to the goals, and as such, they can be preset if needed. To ensure collision avoidance, the boids actually have several precautionary methods of calculating forces. Several angles are calculated: the first is the angle between the boid and the obstacle (theta_a), the second is the angle the boid is facing (theta), and the third is the angle of offset from theta_a that theta must be within to be facing the sphere. Depending on which side of theta_a the boid's angle falls, the repulsion direction can be calculated (so as to turn towards to easier angle). This has the shortcoming of providing false negatives if the boid is within approximately (1.4*radius of obstacle), so if a boid finds itself within this range, it will automatically be given a force perpendicular to the obstacle, in order to keep it away. This generally works well, though it sometimes fails when there are many (somewhat more than 10) obstacles active.

The paper on which I have based this also mentioned an additional force, which is used to match the velocities and orientations of boids with its neighbors. However, after implementing these other forces, the boids already appear to have a very realistic (or at least pleasing) behavior, which already has a wide range of possible different types, given the different weights and tolerances that can be defined. Matching forces would do little to keep the boids coherent and pointed in the same direction, since they almost always already are. In fact, they seemed to match each others orientations so well that I found it somewhat unrealistic, and so I have added an additional force that is purely random, with a fairly low weight, such that their behavior is slightly perturbed (and can even become highly erratic if given a high enough value).

Scripting goals and obstacles isn't quite as simple, but it is still fairly straightforward, for someone with the source code. By default, the goal list and obstacle list are populated randomly, but if a user were to specify each specific goal and/or obstacle, scripted events could be set up.

Of course, there is also the option to pause and unpause the action, using the space bar. This is very useful in taking screen shots, or to further examine specific boid interactions.

One of the more interesting features, at least in terms of simply playing around with the simulation, is the ability to switch to boid cam mode, where a single boid is selected and the camera sees what that boid would see as the simulation runs its course. However, it is kind of rough, as a result of small but quick adjustments the boids sometimes make in avoiding other boids as well as obstacles (these adjustments do not appear jerky in third person, luckily). It is still somewhat fun though.

There are a lot of keys used in controlling the simulation's various variables, so I have included the keys on the screen overlay. Information displayed to the left of the screen deals with the various variables that can be changed, and the bottom of the screen deals with simple display toggles. By default, the boids are paused when the simulation begins, so to begin, simply press space. Changes to variables can be made whenever, whether paused or unpaused. However, if the simulation is paused and the user tries to add boids, the new boid positions are offset somewhat from their parent boids, because otherwise, upon unpausing, the boids would fly off somewhat randomly in their effort to become "unstuck" on each other. This is not as drastic if it occurs while unpaused. Similarly, if all the boids are removed, and the user then tries to add more, the first boid will spawn at the origin.

Perhaps most importantly, however, is the ability to look around and move the camera. While in free camera mode (not in boid cam mode), left clicking and moving the mouse will look around the scene. Holding down both mouse buttons and moving the mouse will move the camera forward, back, left, and right. Holding down just the right mouse button and moving the mouse will move the camera up, down, left, and right. This allows for quick movement and rotation of the camera. Additionally, while in boid cam mode, if you hold down the left mouse button, the camera's position will follow the boid, but you will be able to move the mouse around to look in any direction. Releasing the button will revert to looking in the boid's direction.

The update rate in the above graph is a measurement of how many times the boids completed the boid_update function within a fixed period of time, taken as an average over 20 sampled times during program execution. This function was tested as this is where the critical forces are calculated, and the boids are subsequently affected and updated. This function is where the boids get their behavior (without it, they would simply fly perfectly straight paths). It has been tested with various bin sizes, and as expected, the performance drops off quicker with higher bin sizes - higher bin sizes imply larger neighborhoods, and thus more boid-boid checks. Performance is generally better with a lower bin size, but smaller bins mean a smaller level of awareness of the boids, which can sometimes lead to inaccurate behavior. This tradeoff may be acceptable in some cases, but generally, a bin size of 600 appears to be the best choice.

Of course, the best way to examine the results is to view the program in action, or to at least see some screen shots.

Boids turning towards the new goal. Note the slight variance in angles, due to the random force.

Boids moving towards a goal together. Note the overlay (overlay not used in other shots for simplicity).

Two separate flocks converging on a common goal. In this way, even if boids separate, they still can occasionally rejoin.

A group of boids "splitting off". A goal has occurred directly behind them, and so they veer off in whichever direction is closer.

This was taken while in boid cam mode. It is interesting to watch the simulation from the perspective of a boid.

An obstacle blocks a goal, and the boids swell around it. Note that it caused a slight split of the flock, also.

Circling another obstacle.

Here, a goal is purposefully placed inside an obstacle. The boids then swirl around the obstacle, making interesting patterns.

A shot with lighting enabled. It does not look much different, so it is simply an optional feature.

Without repulsion forces, boids clump together without regard to their neighbor's proximity.

With repulsion forces, they keep a respectable distance from their peers.

A graphical representation of the bins (bins containing boids are drawn in dark red).

GL/GLUT files - (141kb) - Will be needed to run/compile (if not already present on system).