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:
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.
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.