/* ****************************************************************************** * Compilation: javac-algs4 Boid * Execution: none * Dependencies: none * * Implementation of a boid (birdoid). Each boid uses five rules to * decide where to go next. These are: * * avoidCollision(nearest neighbors) * avoidCollision(hawk) * matchVelocity(nearest neighbors) * plungeDeeper(nearest neighbors) * returnToWorld(nearest neighbors) * * plungeDeeper models a Boid's desire to be deeper inside the flock. * * returnToWorld is a hack so that the Boids will eventually return to * the origin, since that's where the camera is pointed. * * More details in the code below. * **************************************************************************** */ import edu.princeton.cs.algs4.Point2D; import edu.princeton.cs.algs4.StdDraw; import edu.princeton.cs.algs4.Vector; public class Boid { // Weights of a Boid's desires. Modify these and see what happens. private static final double BOID_AVOIDANCE_WEIGHT = 0.01; private static final double HAWK_AVOIDANCE_WEIGHT = 0.01; private static final double VELOCITY_MATCH_WEIGHT = 1; private static final double PLUNGE_DEEPER_WEIGHT = 1; private static final double RETURN_TO_ORIGIN_WEIGHT = 0.05; // Agiility of a Boid is given by this value. Increase and they can react // more quickly (and also have a higher max velocity, due to simplicity // of physics model). private static final double THRUST_FACTOR = 0.0001; // x,y stored as a Point2D // In the context of the Boid simulator, this is a little bit of // an awkward way to structure the code, since we map from Point2D // to Boid -- i.e. they key is stored both in the symbol table // and in the value mapped to by the symbol table. // Despite this awkardness, this seems to be the best solution. private Point2D position; private Vector velocity; // create a boid at (x, y) with zero velocity public Boid(double x, double y) { position = new Point2D(x, y); velocity = new Vector(2); } public Boid(double x, double y, double xvel, double yvel) { position = new Point2D(x, y); velocity = new Vector(xvel, yvel); } public Point2D position() { return position; } public double x() { return position.x(); } public double y() { return position.y(); } // Each Boid tries to avoid collisions with its neighbors. This method // provides a thrust vector to achieve that goal. public Vector avoidCollision(Iterable neighbors) { Vector requestedVector = new Vector(2); Vector myPosition = new Vector(x(), y()); // Sum the difference in position between this boid and its nearest // neighbors. Scale each vector so that closer boids are given more // weight. for (Boid b : neighbors) { Vector neighborPosition = new Vector(b.x(), b.y()); double distanceTo = myPosition.distanceTo(neighborPosition); // don't count self if (distanceTo == 0.0) break; Vector avoidanceVector = myPosition.minus(neighborPosition); Vector scaledAvoidanceVector = avoidanceVector.scale(1.0 / distanceTo); requestedVector = requestedVector.plus(scaledAvoidanceVector); } return requestedVector; } // Return a thrust vector to avoid a collision with the Hawk. public Vector avoidCollision(Hawk hawk) { Vector myPosition = new Vector(x(), y()); Vector hawkPosition = new Vector(hawk.x(), hawk.y()); double distanceTo = myPosition.distanceTo(hawkPosition); Vector avoidanceVector = myPosition.minus(hawkPosition); Vector scaledAvoidanceVector = avoidanceVector.scale(1.0 / distanceTo); return scaledAvoidanceVector; } // Return a thrust vector to match velocities with neighbors. public Vector matchVelocity(Iterable neighbors) { Vector requestedVector = new Vector(2); for (Boid b : neighbors) { Vector neighborVelocity = b.getVelocity(); Vector matchingVector = neighborVelocity.minus(velocity); requestedVector = requestedVector.plus(matchingVector); } return requestedVector; } // Return a thrust vector towards the center of the nearest neighbors. public Vector plungeDeeper(Iterable neighbors) { Vector centroid = new Vector(2); double neighborCnt = 0; for (Boid b : neighbors) { Vector neighborPosition = new Vector(b.x(), b.y()); centroid = centroid.plus(neighborPosition); neighborCnt++; } centroid = centroid.scale(1.0 / neighborCnt); // Boid centroidPoint = new Boid(centroid.cartesian(0), centroid.cartesian(1)); Vector myPosition = new Vector(x(), y()); return centroid.minus(myPosition); } // Return a thrust vector towards the origin: 0.5, 0.5; public Vector returnToWorld() { Vector center = new Vector(0.5, 0.5); Vector myPosition = new Vector(x(), y()); return center.minus(myPosition); } // Combines all thrust vectors into a single vector. // Each is weighted by arbitrary hard coded weights. public Vector desiredAcceleration(Iterable neighbors, Hawk hawk) { Vector avoidanceVector = avoidCollision(neighbors).scale(BOID_AVOIDANCE_WEIGHT); Vector hawkAvoidanceVector = avoidCollision(hawk).scale(HAWK_AVOIDANCE_WEIGHT); Vector matchingVector = matchVelocity(neighbors).scale(VELOCITY_MATCH_WEIGHT); Vector plungingVector = plungeDeeper(neighbors).scale(PLUNGE_DEEPER_WEIGHT); Vector returnVector = returnToWorld().scale(RETURN_TO_ORIGIN_WEIGHT); Vector desired = new Vector(2); desired = desired.plus(avoidanceVector); desired = desired.plus(hawkAvoidanceVector); desired = desired.plus(matchingVector); desired = desired.plus(plungingVector); desired = desired.plus(returnVector); if (desired.magnitude() == 0.0) return desired; return desired.direction().scale(THRUST_FACTOR); } public void draw() { StdDraw.setPenColor(StdDraw.BLACK); StdDraw.point(x(), y()); } public Vector getVelocity() { return velocity; } public String toString() { return "" + x() + " " + y() + " " + " " + velocity; } // Updates position and velocity using rules given above. public void updatePositionAndVelocity(Iterable neighbors, Hawk hawk) { double x = x() + velocity.cartesian(0); double y = y() + velocity.cartesian(1); position = new Point2D(x, y); Vector desire = desiredAcceleration(neighbors, hawk); velocity = velocity.plus(desire); } }