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.
To implement step(), calculate the accelerate vector affecting each boid by adding up the four components.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); } } }
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:
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.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 IterablefindNeighbors(Boid b, int K) }
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.