Doug Kavendek - Portfolio

 

Flocking
Title Flocking simulation
Date 2004
Platforms Windows
Created For Graphics II class
Source source (42 kb)
Executable Win32 (66kb)
More Info Flocking final report
01.png
Boids flying about, avoiding large yellow obstacles and tracking blue goals

Given the option to implement a graphics topic we had covered during the semester, I eagerly jumped into creating a 'boid' simulator, where I would model the behavior of flocks. I chose to base it in three dimensions, and model the flight of birds. I still was not too steady with OpenGL, so I focused entirely on the behavior of the birds, without even attempting to realistically represent the birds themselves or their surroundings, so everything is just triangles and spheres. Regardless, the behavior of the birds is pleasant, and through the various controls, the user can tweak how they act.

Very simply, the movement of the birds (or 'boids', since they are bird-oid) is entirely governed by various forces. There are forces that encourage them to try to find the blue goals, there are forces that attempt to divert them from a collision with the yellow obstacles, and various other forces deal with their neighboring birds, from attractive forces between birds to encourage flocks, to repulsion forces to keep them from bunching up and colliding with each other. In addition to this, the velocity and turning abilities of the birds are adjustable, as forces only encourage the bird to turn in the appropriate direction, while the turning tolerance limits the sharpness of such turns.

05.png
More graceful avoidance of obstacles

In order to improve performance, I implemented a binning system, which organized the birds by location, so that adding more birds would not exponentially degrade performance. For spatial comparisons (for attractive/repulsive calculations), birds could reference their own and neighboring bins, in order to get nearby birds. This required quite a bit of overhead, but limited the performance hit to an almost linear growth, rather than an n-squared growth by performing comparison calculations against every other bird in the environment.

Static screens do not adequately convey the motion of the birds -- when they are in motion the subtle adjustments of individual birds blends fluidly with the overall motion of the flock, provided that the various settings are consistent. If the user turns some force variables too high or too low, key behaviors can be destroyed, causing ugly bunches of birds or ridiculous collisions. Generally, the default settings work well, but adjustments should only be made incrementally. With minor adjustments of key variables, like the turning tolerance or the goal-seeking force, the behavior can be changed drastically while still maintaining a pleasing appearance. For example, by adjusting the local forces (like collision avoidance) to be higher than the goal seeking forces, and increasing the turning tolerance, the behavior begins to mimic a swarm of bees rather than a flock of birds.

09.png
With boid avoidance turned down too far, boids make a jumbled mess

As this program stands, it does not have too much use except as a prototype. However, I have integrated the flocking behavior into the enemy behavior in my game, Captain Awesome, and have expanded upon this topic in a later flocking project.


04.png
Obstacles can split boids into smaller flocks
12.png
Graphically showing active bins; brighter red indicates higher density
06.png
Having a goal inside an obstacle creates some confusion
08.png
With common goals, small flocks can rejoin and create larger flocks