Bird Flocking Simulation

6-11-2009

By Katherine Blizard ~ Zoe Wood's CPE 471 ~ Spring 2009

Overview

Distributed Behavorial Models are a way to give a simple artifical intelligence to a 'particle' in order for it to move about a world. Specific behaviors can be defined for a certain type of moving particle that it will follow. Simulating a few schooling behaviors that are shown in birds, fish and herds, and replacing the particle with a fearsome DragonBatBird (Dragatird?) in a world can create a simulation of flocking.

The Flocking algorithm linked from at the bottom of this page has several levels of complexity. The most basic eventauly gathers a flock heading in a general direction while flock members avoid colliding with each other. More complex ones entail flock members avoiding other objects in the world, and further complixities include avoiding or chasing predators and prey, following a designated path, following a leader and other AI upgrades. I planned to start with a simple implementation and add complexity as I have time.

This is the lastest version of my final project I am satisfied with. The source code contains hours of commented out code of me trying to implement a more sophisticated version of the flocking algorithm. it is more buggy (as in uselessly broken) than the simpler version, even though the simpler version gets rather boring after all the Dragons decide on a direction to travel. In the newer version the dragons would organize themselves in a flock like formation but they would hover close to the ground and then stop, and that's it. So you're not missing out on much.

Simulation Elements:

• Basic AI defining three behaviors: collision avoidance with other flockmates, velocity matching, and neighbor seeking
• Camera controls: looking around in the world with the mouse
• texture-mapped desert floor and sky.
• Random placement of birds and direction of travel at simulation start.
• Flapping Animation done in "traditional" animation style (No Tweens)
• "Punishment" for leaving the skybox: teleportation to the opposite end of the box.
• Heirarcical models of Dragatirds using two materials.
• Teapot marking the origin

Flocking Algorithm:

The CPU needs to move each Dragatird by a certain amount in each frame. Basically it runs in an O(n^2) running time. Each Dragatird calculates each of the directions each of its behaviors dictate, in priority order. It stops calculating the lower priority movements if higher priority demands are needed. Each flock member has it's own position vector and it's own lookAt vector, so most mathmatics are vector calculations.

• First, it checks if it is about to collide with its nearest neighbor, making a high priority movement if it is.
• Next, it check if it is getting near the skybox boundries, and heading towards it
• Then it checks if it is too far from it's nearest neighbor and moves closer.
• Finally, it adjusts it's velocity to be average of its nearest 4 neighbors and adjusts it's position to be in the center of the 4 of them.

Key Commands:

• W = moves forward
• S = step back
• A = side step
• D = side step
• + = moves the sun out of the setting
• - = moves the sun into the setting
• Mouse drag = moves the camera to look at things

Screenshots:

Resources:

• Flocks, Herds, and Schools: A Distributed Behavioral Model by Craig W. Reynolds -- the general outline of the flocking algorithm, submitted to SIGGRAPH
• Containment steering behavior Information on Collision Avoidance
• Boids -- further information and a different, java implementation of flocking