COS 226 Programming Assignment

Flocks and Boids


Flocking boids. Boids (short for bird-oids) are an artificial life simulation created in 1986 by Craig Reynolds. The boids act as individual members of a simulated flock of birds. Although the flock seems to move as one entity, each individual reacts based solely on observations of its nearest neighbors. This is a classic example of emergent behavior, a complex behavior emerging from many simple interactions. The simulation framework you will create controls the boids with Reynolds' original three simple rules:

  1. Boids attempt to match the average direction of their neighboring boids.

  2. Boids attempt to move towards the center of mass of their neighboring boids.

  3. When boids become too close, they repel each other to avoid collision and provide spacing in the flock.
While the first three rules are sufficient to create nice flocking behavior, we include one extra rule to make the simulation more practical.

  1. When approaching the walls the boids will be inclined to change course to avoid collision. (Without this rule, the flock will soon fly out of view.)

Boid data type. Write a data type Boid.java to model a boid, implementing the following API. Each Boid is characterized by its position, velocity, and an image filename. Note that the position and velocity values are provided as Vector.java objects.

public class Boid {

    // Create a new boid with the given position and velocity
    public Boid(Vector position, Vector velocity, String filename)

    // Return the distance between this boid and that boid
    public double distanceTo(Boid that)

    // Move this boid according to its current velocity
    public void move()

    // Adjust the velocity by the given vector
    public void accelerate(Vector a)

    // Return the current velocity
    public Vector velocity()

    // Return the current position
    public Vector position()

    // Display the boid as its image in its current position facing the direction of its velocity
    public void draw()
}

Brute force implementation. Create a program Brute.java that implements the simulation using brute force.

public class Brute {
    public Brute(Boid[] boids, int k)   // initialize 
    public void step()                  // simulate one step
    public void draw()                  // display the boids using standard draw

    // read input file in format described below and simulate system
    public static void main(String[] args) {
        int k = StdIn.readInt();
        int N = StdIn.readInt();
        Boid[] boids = new Boid[N];
        for (int i = 0; i < N; i++) {
           double rx = StdIn.readDouble(), ry = StdIn.readDouble();
           double vx = StdIn.readDouble(), vy = StdIn.readDouble();
           Vector position = new Vector(rx, ry);
           Vector velocity = new Vector(vx, vy);
           String filename = StdIn.readString();
           boids[i] = new Boid(position, velocity, filename);
        }
        Brute brute = new Brute(boids, k);
        while (true) {
            brute.step();
            brute.draw();
            StdDraw.show(100);
        }
    }
    
}
To implement step(), calculate the accelerate vector affecting each boid by adding up the four components. After computing the acceleration for each boid, update the velocity of each boid, and move each boid to its new location.

Input format. The input format consists for an integer K (number of nearest neighbors), followed by an integer N (number of boids), followed by N lines, where each lines consists of the initial position of the boid (rx and ry), the initial velocity (vx and vy), and the image filename.

% more input1.txt
K
Number of Boids 
X_position Y_position  X_velocity  Y_velocity ImageFileName
Etc.

kD-tree implementation. The bottleneck in the brute-force implementation is finding all of the nearest neighbors. Your more efficient version of the simulation will use a 2D-tree to speed the nearest neighbor search. Write your 2D-tree in KDTree.java with this API:

public class KDTree {
      //Construct an empty KDTree
    public KDTree()
   
    //Insert a Boid into the structure
    public void insert(Boid b)
  
    //Displays the structure of the tree     
    public void display()               
 
    //Returns set of the closest K neighbors     
    public Iterable findNeighbors(Boid b, int K)
}
Each inserted boid should result in a new cutoff line in the tree. The orientation of the lines should alternate between vertical and horizontal. For simplest debugging, it is recommended that you implement the display function early, so that you can visually verify that your tree structure has been built correctly.

Fast implementation. Write a program Fast.java that has the same API as Brute.java, but uses a kd-tree to find the nearest neighbors instead of brute force. To get a probabilistic guarantee of a balanced tree, the boids should be inserted in random order every time. public class Fast { // Construct a Fast object public Fast(Boid[] boids, int K) // Adjust the simulation by one step public void step() // Display the boids in the simulation. public void draw() }

Analysis.  Analyze your approach to this problem giving estimates of its time and space requirements. Also, critically explore the effectiveness of this technique for this task.

Submission.  Submit Boid.java, Brute.java, Fast.java, KDTree.java andany other files needed by your program (excluding those in stdlib.jar and adt.jar). Finally, submit a readme.txt file and answer the questions.

This assignment was developed by Jacob Lewellen and Kevin Wayne.