Welcome to my boids page. Boids are computer generated fish, birds, or insects that exhibit the flocking behavior and show that the phenomenom of flocking is a decentralized activity. With that said, be sure to read my paper on boids that I wrote for a school science project.

Abstract

Paper - CAN THE PHENOMENOM OF FLOCKING BE EXPLAINED AS A DECENTRALIZED ACTIVITY?

Introduction

Methods and Materials Results

Discussion and Conclusions

Appendix A - The Algorithm in Java

Appendix B - Parameters Used in the Experiment and Their Affect on the Program

Bibliography

The Boid Applet

ABSTRACT

The purpose of this experiment was to simulate the flocking behavior of birds. The hypothesis is that if a computer simulation is created using three simple rules, then the complex flocking behavior of birds will emerge. This hypothesis was tested by a computer simulation written in the programming language Java.

The simulation used three simple rules to show that birds flock based on localized behavior: flock centering, velocity matching, and collision avoidance. A similar simulation without the use of the three simple rules was used as a comparative control. The computer simulation without the three rules did not show the flocking behavior successfully. With this known, it was concluded that the flocking behavior of birds could be modeled as local behavior, and the hypothesis was accepted. This information is important because it applies to any animal that travels in a flock or herd, and can be applied to some human behaviors as well.

CAN THE PHENOMENOM OF FLOCKING BE EXPLAINED
AS A DECENTRALIZED ACTIVITY?

INTRODUCTION:

The flocking behavior of birds is a result of their individual behaviors and knowledge. This is the main scientific principle associated with the experimenter's project. The article "Flocks, Herds, and Schools: A Distributed Behavioral Model", appeared in the magazine Computer Graphics (Volume 21, Issue 4, 1987). It was written by Craig Reynolds and pioneered the concept that the flocking behavior displayed by birds is a completely decentralized activity. Reynolds' work in the area of using simple rules to create complex behaviors is the basis of this experiment. Reynolds called the flocking birds "boids" because the name "boid" applies both to flocking birds and schooling fish. Fish also exhibit a behavior similar to flocking, known as schooling.

This experiment is a simulation of the flocking behavior. Microsoft Bookshelf 1995 defines a simulation as a "Representation of the operation or features of one process or system through the use of another." The simulation was written using the computer programming language Java. Simulations are used to demonstrate the plausibility of a natural mechanism, such as flocking. The experimenter used a computer program to simulate the flocking behavior of birds.

Many other definitions were associated with this project. The following definitions were taken from The Java Tutorial by Mary Campione and Kathy Walrath, Teach Yourself Java in 21 Days by Laura Lemay and Charles Perkins, and Microsoft Bookshelf 1995. A computer is a programmable device that computes or otherwise processes information. A computer program is a set of instructions for solving a problem or processing data. A programming language is a structured way of providing instructions for a computer that is usually textual. Java is an object-oriented programming language created by Sun Microsystems that was modeled after C++ and was designed to be small, portable across operating systems, and simple. Object-oriented is a software technology using objects. An object is a software collection of variables and related methods. A class is a blueprint or prototype that defines the variables and methods common to all objects of a certain kind. A method is an orderly arrangement of parts or steps to accomplish an end. In the Java programming language the parts are statements in the programming language. Data is numerical or other information represented in a form suitable for processing by a computer. A parameter is a value that varies in an equation. In Java, implement means to provide the steps for a method by writing the statements. In Java the interface describes the methods of a class. A user interface is that part of the computer program that provides for user interaction. A constructor is a special method that is used to implement create and initialize a new object of that class.

The exact statement of the problem was "Can the phenomenon of flocking be explained as a decentralized activity?". The hypothesis of the experiment was that if a computer simulation is created using three simple decentralized rules, then the complex flocking behavior of birds will emerge.

The three simple rules were 1) flock centering to keep the birds together in the flock, 2) velocity matching so the birds would flock at a similar speed, and 3) collision avoidance so the birds would not be constantly bumping into each other. The experimenter sought to support the theory that birds flock based on local knowledge and behaviors, and not on global, overall knowledge or behaviors.

Two different simulations were developed in the experiment. One simulation used the rules and the other was a random simulation that had the three rules disabled. The simulation without the rules represented the belief that birds flock based on random behavior and served as the control of the experiment. The three rules were the independent variables of the experiment. The dependent variable was how well the birds appear to be flocking. In the experiment the constants were the number of simulated birds and the size of the viewing area of the simulation.

The experimenter chose this topic for many different reasons. Computers and the ability to create life like objects using the computer has always fascinated the experimenter. Alfred Hitchcock's The Birds made the experimenter wonder how birds flocked, and, also, if birds really do attack people. Finally, having been exposed to computer programming in Java, the experimenter was anxious to try it in a problem solving endeavor.

METHODS AND MATERIALS:

The first thing the experimenter had to do was to learn the basics of the Java programming language. This was done with the guidance of the experimenter's mentor, senior C++ programmer David Leserman, who gave the experimenter homework every week. This homework included changing the code to make the boids fly in different directions and reading parts of a Java programming language book, The Java Tutorial written by Mary Campione and Kathy Walrath. As the formulas in the program code got increasingly complicated, up to high school Trigonometry, the experimenter received more homework on changing the parameters in the experiment to produce the best representation of flocking. This allowed the experimenter to keep learning the Java language, without being lost in the complicated formulas and functions. The experimenter's mentor would sometimes explain methods from the experiment to keep the experimenter somewhat up to date in the latest version of the program.

The simulation used in this experiment was written in the programming language Java by senior programmer David Leserman. Three main classes made up the simulation. These classes were an ObservationField class, a Boid class, and a BoidThatFlocks subclass. All programming was done using Symantec Café Version 1.51 and Microsoft Visual J++ Version 1.0 .

The ObservationField class contains some important methods. These methods are GetParameter, init, start, stop, run, and paint. The GetParameter method was created to tell the program the values of the parameters to be used in the simulation. The init method imported the parameters, initialized the panels used to change the parameters while the applet was running, and prepared for the actual running of the simulation in a web browser or applet viewer. The start method actually began the running of the applet. The stop method stopped and froze the applet after the applet window was closed. The run method initialized the flock parameters for the actual running of the applet, painted the boids on the screen, and repainted the boids after each move. The paint method called up the dimensions and colors of the boid and drew them into the applet window. Many other methods are contained in the ObservationField class. Most of the other methods draw the panels and slide bars used to set the parameters in the actual applet, tell the applet whether or not to use the three rules, or tell the applet what to do if it is frozen or running. Most of the parametric data used in the applet is stored in the ObservationField class.

The Boid class contains most of the information to draw the birds using their coordinates, set the colors of the boids, move the boids to the next step in their simulated flight, and import the parameter values used by the birds. The important methods in the Boid class are Boid (the constructor), initializeVertices, moveNext, paint, and rotate. The constructor creates the Boid object, setting initial data values and creating a link to the singleton ObservationField object. The initializeVertices method defines the coordinates of the boid and sets the number of points. The moveNext method is just the generic interface for the moveNext in the subclass. The paint method connects the points defined by initializeVertices to form polygons and paints the polygons in different colors. The rotate method lets a boid change the direction it is facing within the viewing area.

BoidThatFlocks is a subclass of Boid. In BoidThatFlocks, the moveNext method incorporates calls to the methods that implement the three simulation rules: matchVelocity, centerInFlock, and avoidCollisions. The method matchVelocity returns a vector quantity consisting of heading and speed that tells the boids how to match their heading and speed to other surrounding boids. The centerInFlock method dictates what the boids do when they have nearby flockmates. The avoidCollisions method makes the boids steer away from imminent impact.

Other classes are contained in the simulation. DesignatedInsetPanel, ObservationFieldView, and SliderControl are helpers for the user interface. FloatPair and TwoDVector are helpers for data storage and computation. The rules part of the Java simulation is contained in Appendix A in a font and size appropriate for viewing programming code.

RESULTS:

As part of the experiment, the parameters needed to be adjusted for optimal performance. The mentor left this job up to the experimenter. In the experiment, some parameters were held and some were varied. The parameters held constant were the minimum distance per move and the delay between moves. Also, all three rules remained on throughout all the trials. The parameters that varied were the number of boids, the maximum distance to nearby flockmates, and the maximum direction change. In the simulation appearing most life-like the parameter values were the same of trial number twenty in shown in Appendix B. Contained in Appendix B is a table showing the different parameters used and their effect on the representation of flocking in the program. Appendix C contains pictures of the boids flocking after different amounts of time. Every three seconds, or twelve steps, a picture of the Java applet was copied to the clipboard by using the Print Screen-Alt command. These pictures show how well the boids in the two simulations were flocking. In the first picture of the simulation using the three rules, the boids first appeared. In picture two the boids moved twelve steps and began to move into a flocking formation. Picture three shows the boids moving at a similar speed to the upper right corner without bumping into each other. Picture four shows the boids after they had flown off one corner of the screen and were moving back up the other side of the screen still in a flocking formation. In the second set of pictures which represented the random simulation, no recognizable flocking behavior emerged. In picture one the boids appeared. In the next three pictures the boids ran into each other, did not keep a similar velocity, and did not attempt to center into the middle of the flock.

DISCUSSIONS AND CONCLUSIONS:

The experiment verified the hypothesis that it is plausible that the flocking behavior of birds is a decentralized activity. This was concluded because the boids in the simulation with the three simple rules appeared to be flocking, while in the simulation without the three rules did not show flocking behavior. This means that when birds flock they stay in that flock because of their surroundings and knowledge, and not by a group knowledge or behavior. Thus, the hypothesis was accepted.

In the real world, the principle that simple rules produce complex behaviors is widely used. For example, in the magazine Colorado Business, an article in 1995 reported about the use of simple rules and goals applied in a business environment to yield complex results, such as more income and better moral. Also, an article in PC Magazine Online in 1996 discussed the use of simple rules to make complex behaviors emerge, such as crowds moving swiftly without the people in them bumping into each other.

If the experimenter were to redo this project, many factors would be changed. The experimenter would write the Java program by himself. This was impossible in this experiment because a beginner to programming cannot write a complex simulation. It takes experience to master a programming language. Also, the experimenter would have liked the flocking of the boids to look more realistic. Watching nature shows and observing flocks of birds would have helped the experimenter to better understand the flocking behavior.

The experimenter would like to see more research on using the principle that simple rules yield complex behaviors. This research would help scientists to better understand the flocking behavior. Also, the research could be used in the field of avionics to help guide planes, in stadiums to help crowd control, and in many other fields.

APPENDIX A

The Algorithm in Java

public class BoidThatFlocks extends Boid {
    // ...
    // The three rules to simulate flocking, most important first, are:
    // 1. collision avoidance,
    // 2. velocity matching, and
    // 3. flock centering.

    // Collision Avoidance: Avoid collisions with nearby boids.
    // Steer away from imminent impact. This is based on the
    // relative position of each boid and ignores velocity.
    private TwoDVector avoidCollisions() {
        // Not yet implemented.
        return new TwoDVector();
    }

    // Match Velocity: Velocity is a vector quantity consisting of
    // heading and speed.
    private TwoDVector matchVelocity() {
        TwoDVector newVelocity = new TwoDVector();
        Vector nearbyBoids = obsField.nearbyFlockmates(this);
        float magnitudeSum = 0;
        float directionSum = 0;
        float deltaDirectionSum = 0;
        float myDirection = 
            TwoDVector.normalizedDirection(this.prevVelocity.direction);
        int nearbyBoidCount = nearbyBoids.size();
        for (int i = 0; i < nearbyBoidCount; i++) {
            Boid nearbyBoid = (Boid) nearbyBoids.elementAt(i);
            magnitudeSum += nearbyBoid.prevVelocity.magnitude;
            float neighborDirection = nearbyBoid.prevVelocity.direction;
            float deltaDirection = neighborDirection - myDirection;
            deltaDirectionSum += deltaDirection;
            if (nearbyBoidCount != 0) {
                float deltaDirection = deltaDirectionSum / nearbyBoidCount;
                newVelocity.direction =        
                        TwoDVector.normalizedDirection(deltaDirection);
            } else {
                TwoDVector randomVel = randomlyAltered(this.velocity);
                newVelocity.direction = this.velocity.direction;
                newVelocity.magnitude = randomVel.magnitude / 2;
            }
        }
        return newVelocity;
    }

    // Flock Centering: Stay close to nearby flockmates.
    private TwoDVector centerInFlock() {
        TwoDVector newVelocity = new TwoDVector();
        FloatPair nearbyBoidsCentroid = new FloatPair();
        Vector nearbyBoids = obsField.nearbyFlockmates(this);
        int nearbyBoidCount = nearbyBoids.size();
        for (int i = 0; i < nearbyBoidCount; i++) {
            Boid nearbyBoid = (Boid) nearbyBoids.elementAt(i);
            nearbyBoidsCentroid.x += nearbyBoid.prevLocation.x;
            nearbyBoidsCentroid.y += nearbyBoid.prevLocation.y;
        }
        if (nearbyBoidCount != 0) {
            float nearbyBoidsCentroidX = nearbyBoidsCentroid.x / 
                                        nearbyBoidCount;
            float nearbyBoidsCentroidY = nearbyBoidsCentroid.y / 
                                         nearbyBoidCount;
            float deltaX = this.prevLocation.x - nearbyBoidsCentroidX;
            float deltaY = this.prevLocation.y - nearbyBoidsCentroidY;
            newVelocity.direction = (float) Math.atan(deltaY/deltaX);
            newVelocity.magnitude = nearbyBoidCount * randomNumber();
        } else {
            TwoDVector randomVel = randomlyAltered(this.velocity);
            newVelocity.direction = this.velocity.direction;
            newVelocity.magnitude = 1;
        }
        return newVelocity.normalized();
    }

    public void moveNext() {
        super.moveNext();

        TwoDVector acceleration = new TwoDVector();
        if (useVelocityMatching) acceleration = matchVelocity();
        else acceleration = randomlyAltered(acceleration);

        if (useFlockCentering)
            acceleration = acceleration.plus(centerInFlock());

        //if (useCollisionAvoidance)
        //    newVelocity = newVelocity.plus(avoidCollisions());

        float directionChange = 
                TwoDVector.normalizedDirection(acceleration.direction);
        if (directionChange > PI) directionChange -= (float) 2.0*PI;

        if (directionChange > maxDirectionChangePerMove) 
            directionChange = maxDirectionChangePerMove;
        else if (directionChange < -maxDirectionChangePerMove)
            directionChange = -maxDirectionChangePerMove;
         
        velocity.direction = 
               TwoDVector.normalizedDirection(velocity.direction 
                                               += directionChange);

        float magnitude = acceleration.magnitude;
        if (magnitude > maxDistancePerMove) 
            magnitude = maxDistancePerMove;
        else if (magnitude < minDistancePerMove)
            magnitude = minDistancePerMove;
        velocity.magnitude = magnitude;

        float xDistance = velocity.magnitude * 
                           (float) Math.cos(velocity.direction + PI/2);
        float yDistance = velocity.magnitude * 
                           (float) Math.sin(velocity.direction + PI/2);

        location.x += xDistance;
        location.y += yDistance;
    }
}

APPENDIX B

Parameters Used in the Experiment and Their Affect on the Program

BIBLIOGRAPHY