Refactoring Boids

Boids, by Daniel Shiffman is a Processing example of the flocking algorithm developed by Craig Reynolds using simple rules for individual “boids” to simulate the behaviour seen in flocks of real birds.

As a challenge from a colleague I wanted to see how I could refactor the code from a single file into smaller chunks so it’s more readable and understandable.

Original

original

Here’s the original code from the processing website:


Flock flock;

void setup() {
  size(640, 360);
  flock = new Flock();
  // Add an initial set of boids into the system
  for (int i = 0; i < 150; i++) {
    flock.addBoid(new Boid(width/2,height/2));
  }
}

void draw() {
  background(50);
  flock.run();
}

// Add a new boid into the System
void mousePressed() {
  flock.addBoid(new Boid(mouseX,mouseY));
}



// The Flock (a list of Boid objects)

class Flock {
  ArrayList<Boid> boids; // An ArrayList for all the boids

  Flock() {
    boids = new ArrayList<Boid>(); // Initialize the ArrayList
  }

  void run() {
    for (Boid b : boids) {
      b.run(boids);  // Passing the entire list of boids to each boid individually
    }
  }

  void addBoid(Boid b) {
    boids.add(b);
  }

}




// The Boid class

class Boid {

  PVector position;
  PVector velocity;
  PVector acceleration;
  float r;
  float maxforce;    // Maximum steering force
  float maxspeed;    // Maximum speed

    Boid(float x, float y) {
    acceleration = new PVector(0, 0);

    // This is a new PVector method not yet implemented in JS
    // velocity = PVector.random2D();

    // Leaving the code temporarily this way so that this example runs in JS
    float angle = random(TWO_PI);
    velocity = new PVector(cos(angle), sin(angle));

    position = new PVector(x, y);
    r = 2.0;
    maxspeed = 2;
    maxforce = 0.03;
  }

  void run(ArrayList<Boid> boids) {
    flock(boids);
    update();
    borders();
    render();
  }

  void applyForce(PVector force) {
    // We could add mass here if we want A = F / M
    acceleration.add(force);
  }

  // We accumulate a new acceleration each time based on three rules
  void flock(ArrayList<Boid> boids) {
    PVector sep = separate(boids);   // Separation
    PVector ali = align(boids);      // Alignment
    PVector coh = cohesion(boids);   // Cohesion
    // Arbitrarily weight these forces
    sep.mult(1.5);
    ali.mult(1.0);
    coh.mult(1.0);
    // Add the force vectors to acceleration
    applyForce(sep);
    applyForce(ali);
    applyForce(coh);
  }

  // Method to update position
  void update() {
    // Update velocity
    velocity.add(acceleration);
    // Limit speed
    velocity.limit(maxspeed);
    position.add(velocity);
    // Reset accelertion to 0 each cycle
    acceleration.mult(0);
  }

  // A method that calculates and applies a steering force towards a target
  // STEER = DESIRED MINUS VELOCITY
  PVector seek(PVector target) {
    PVector desired = PVector.sub(target, position);  // A vector pointing from the position to the target
    // Scale to maximum speed
    desired.normalize();
    desired.mult(maxspeed);

    // Above two lines of code below could be condensed with new PVector setMag() method
    // Not using this method until Processing.js catches up
    // desired.setMag(maxspeed);

    // Steering = Desired minus Velocity
    PVector steer = PVector.sub(desired, velocity);
    steer.limit(maxforce);  // Limit to maximum steering force
    return steer;
  }

  void render() {
    // Draw a triangle rotated in the direction of velocity
    float theta = velocity.heading2D() + radians(90);
    // heading2D() above is now heading() but leaving old syntax until Processing.js catches up
    
    fill(200, 100);
    stroke(255);
    pushMatrix();
    translate(position.x, position.y);
    rotate(theta);
    beginShape(TRIANGLES);
    vertex(0, -r*2);
    vertex(-r, r*2);
    vertex(r, r*2);
    endShape();
    popMatrix();
  }

  // Wraparound
  void borders() {
    if (position.x < -r) position.x = width+r;
    if (position.y < -r) position.y = height+r;
    if (position.x > width+r) position.x = -r;
    if (position.y > height+r) position.y = -r;
  }

  // Separation
  // Method checks for nearby boids and steers away
  PVector separate (ArrayList<Boid> boids) {
    float desiredseparation = 25.0f;
    PVector steer = new PVector(0, 0, 0);
    int count = 0;
    // For every boid in the system, check if it's too close
    for (Boid other : boids) {
      float d = PVector.dist(position, other.position);
      // If the distance is greater than 0 and less than an arbitrary amount (0 when you are yourself)
      if ((d > 0) && (d < desiredseparation)) {
        // Calculate vector pointing away from neighbor
        PVector diff = PVector.sub(position, other.position);
        diff.normalize();
        diff.div(d);        // Weight by distance
        steer.add(diff);
        count++;            // Keep track of how many
      }
    }
    // Average -- divide by how many
    if (count > 0) {
      steer.div((float)count);
    }

    // As long as the vector is greater than 0
    if (steer.mag() > 0) {
      // First two lines of code below could be condensed with new PVector setMag() method
      // Not using this method until Processing.js catches up
      // steer.setMag(maxspeed);

      // Implement Reynolds: Steering = Desired - Velocity
      steer.normalize();
      steer.mult(maxspeed);
      steer.sub(velocity);
      steer.limit(maxforce);
    }
    return steer;
  }

  // Alignment
  // For every nearby boid in the system, calculate the average velocity
  PVector align (ArrayList<Boid> boids) {
    float neighbordist = 50;
    PVector sum = new PVector(0, 0);
    int count = 0;
    for (Boid other : boids) {
      float d = PVector.dist(position, other.position);
      if ((d > 0) && (d < neighbordist)) {
        sum.add(other.velocity);
        count++;
      }
    }
    if (count > 0) {
      sum.div((float)count);
      // First two lines of code below could be condensed with new PVector setMag() method
      // Not using this method until Processing.js catches up
      // sum.setMag(maxspeed);

      // Implement Reynolds: Steering = Desired - Velocity
      sum.normalize();
      sum.mult(maxspeed);
      PVector steer = PVector.sub(sum, velocity);
      steer.limit(maxforce);
      return steer;
    } 
    else {
      return new PVector(0, 0);
    }
  }

  // Cohesion
  // For the average position (i.e. center) of all nearby boids, calculate steering vector towards that position
  PVector cohesion (ArrayList<Boid> boids) {
    float neighbordist = 50;
    PVector sum = new PVector(0, 0);   // Start with empty vector to accumulate all positions
    int count = 0;
    for (Boid other : boids) {
      float d = PVector.dist(position, other.position);
      if ((d > 0) && (d < neighbordist)) {
        sum.add(other.position); // Add position
        count++;
      }
    }
    if (count > 0) {
      sum.div(count);
      return seek(sum);  // Steer towards the position
    } 
    else {
      return new PVector(0, 0);
    }
  }
}


Python

To make things more interesting, I thought I would refactor or rework in Python.

Split

First off, we have three distinct classes - the main game class, the flock (a container for the boids) and the boid class itself. In processing, we can add two extra tabs and reference those from the main file.

One important thing to note when dealing with multi-tab projects in Processing, pay special attention to which tabs are currently saved because they aren’t by default and you can be editing one version of the code but running the last saved version which can be a bit confusing. The modified indicator in processing isn’t very noticeable.

Game

In setup(), we set full screen, then create our initial flock (and we let the flock itself decide how big it’s going to be).


from Boid import Boid 
from Flock import *

def setup():
  fullScreen()
  global flock
  flock = Flock()

def draw():
  background(50)
  global flock
  flock.fly(width, height)

def mousePressed():
  global flock
  flock.add(Boid(mouseX, mouseY))

  if (mouseButton == RIGHT):
    saveFrame("flock-####.png")

In draw(), we have to let the flock move itself and I much prefer the function to be fly() rather than run(). Flying birds aren’t usually that great at running :). When a mouse button is pressed, we add a new member to the flock at the current mouse position. That seems to work fine. Let’s move onto the Flock itself.

Flock

As mentioned above, I have chosen to describe the flock in terms of it’s members - adding, flying - rather than talking about running, drawing and addingBoid from the original version.


class Flock(object):
    
  def __init__(self):
    self.members = list()
    
  def fly(self, width, height):
    for member in self.members:
      member.fly(self.members, width, height)
            
  def add(self, newMember):
    self.members.append(newMember)


Boid

To get started, I have opted for a super simple version of the boid implementation. It records where it was created and never moves but just draws a black line from the original to its position to show itself.


class Boid(object):
    
  def __init__(self, x, y):
    self.x = x
    self.y = y

  def fly(self, members):
    stroke(255)
    point(self.x, self.y)


Debug

At this point, it’s very useful to use the print() function to output what’s happening to the console. Also for debugging purposes, I’m using the right mouse button to trigger a screenshot.

initial flock

Boids

Now that we have something like a manageable split between the three concerns, game, flock and individual boid, it’s time to look at the implementation of the boid itself and the rules it uses to interact with the flock-mates.

Here’s a pretty straight rewrite of the original code from Java to Python and by far the biggest bit of the rewrite before the actual refactor:


class Boid(object):
    
  def __init__(self, x, y):
    self.acceleration = PVector(0, 0)

    angle = random(TWO_PI)
    self.velocity = PVector(cos(angle), sin(angle))
    self.position = PVector(x, y)
    
    # these may stand to be better described later.
    self.r = 2.0
    self.maxspeed = 2
    self.maxforce = 0.03
    
  def fly(self, members, width, height):
    self.flock(members)
    self.update()
    self.borders(width, height)
    self.render()

  def applyForce(self, force):
    # We could add mass here if we want A = F / M
    self.acceleration.add(force)

  def flock(self, members):
    separationForce = self.separate(members) # Separation
    alignmentForce = self.align(members)       # Alignment
    cohesiveForce = PVector(0,0) #self.cohesion(members)    # Cohesion
    # Arbitrarily weight these forces
    separationForce.mult(1.5)
    alignmentForce.mult(1.0)
    cohesiveForce.mult(1.0)
    # Add the force vectors to acceleration
    self.applyForce(separationForce)
    self.applyForce(alignmentForce)
    self.applyForce(cohesiveForce)

  def update(self):
    # Update velocity
    self.velocity.add(self.acceleration)
    # Limit speed
    self.velocity.limit(self.maxspeed)
    self.position.add(self.velocity)
    # Reset accelertion to 0 each cycle
    self.acceleration.mult(0)

  # Ensure boids wrap around the edges of the screen
  def borders(self, width, height):
    if self.position.x < -self.r: self.position.x = width + self.r
    if self.position.y < -self.r: self.position.y = height + self.r
    if self.position.x > width + self.r: self.position.x = -self.r
    if self.position.y > height + self.r: self.position.y = -self.r 

  def render(self):
    # Draw a triangle rotated in the direction of velocity
    theta = self.velocity.heading2D() + radians(90)
    # heading2D() above is now heading() but leaving old syntax until Processing.js catches up
    
    fill(200, 100)
    stroke(255)
    pushMatrix()
    translate(self.position.x, self.position.y)
    rotate(theta)
    beginShape(TRIANGLES)
    vertex(0, -self.r*2)
    vertex(-self.r, self.r*2)
    vertex(self.r, self.r*2)
    endShape()
    popMatrix()

  #
  # Rules for boid movement
  #     
  # A method that calculates and applies a steering force towards a target
  # STEER = DESIRED MINUS VELOCITY
  def seek(self, target):
    desired = PVector.sub(target, self.position);  # A vector pointing from the position to the target
    # Scale to maximum speed
    desired.normalize()
    desired.mult(self.maxspeed)

    # Above two lines of code below could be condensed with new PVector setMag() method
    # Not using this method until Processing.js catches up
    # desired.setMag(maxspeed);

    # Steering = Desired minus Velocity
    steer = PVector.sub(desired, self.velocity)
    steer.limit(self.maxforce)  # Limit to maximum steering force
    
    return steer
  

  # Separation
  # Method checks for nearby boids and steers away
  def separate(self, members):
    desiredseparation = 25.0
    steer = PVector(0, 0, 0)
    
    count = 0
    # For every boid in the system, check if it's too close
    for other in members:
      d = PVector.dist(self.position, other.position)
      # If the distance is greater than 0 and less than an arbitrary amount (0 when you are yourself)
      if d > 0  and d < desiredseparation:
        # Calculate vector pointing away from neighbor
        diff = PVector.sub(self.position, other.position)
        diff.normalize()
        diff.div(d)        # Weight by distance
        steer.add(diff)
        count += 1         # Keep track of how many

    # Average -- divide by how many
    if count > 0:
      steer.div(float(count))

    # As long as the vector is greater than 0
    if steer.mag() > 0:
      # First two lines of code below could be condensed with new PVector setMag() method
      # Not using this method until Processing.js catches up
      # steer.setMag(maxspeed);

      # Implement Reynolds: Steering = Desired - Velocity
      steer.normalize()
      steer.mult(self.maxspeed)
      steer.sub(self.velocity)
      steer.limit(self.maxforce)

    return steer

    # Alignment
    # For every nearby boid in the system, calculate the average velocity
  def align(self, members):
    neighbordist = 50
    sum = PVector(0, 0)
    
    count = 0
    
    for other in members:
      d = PVector.dist(self.position, other.position)

      if d > 0 and d < neighbordist:
        sum.add(other.velocity)
        count += 1

    if count > 0:      
      sum.div(float(count))
      
      # First two lines of code below could be condensed with new PVector setMag() method
      # Not using this method until Processing.js catches up
      # sum.setMag(maxspeed);

      # Implement Reynolds: Steering = Desired - Velocity
      sum.normalize()
      sum.mult(self.maxspeed)
      steer = PVector.sub(sum, self.velocity)
      steer.limit(self.maxforce)
            
      return steer
      
    return PVector(0, 0)

    # Cohesion
    # For the average position (i.e. center) of all nearby boids, calculate steering vector towards that position
    def cohesion(self, members):
      neighbordist = 50
      sum = PVector(0, 0)    # Start with empty vector to accumulate all positions
        
      count = 0
      for other in members:
        d = PVector.dist(self.position, other.position)
        if d > 0 and d < neighbordist:
          sum.add(other.position); # Add position
          count += 1
        
      if count > 0:
        sum.div(count)
        return self.seek(sum)  # Steer towards the position

      return PVector(0, 0)


One consequence of splitting the code up into separate modules is not having access to width and height properties inside the flock or the boid class. We need those values so we can implement the border behaviour where a boid flying off one side of the screen wraps around and flies in from the opposite side.

Refactor

So, what opportunities do we have to refactor (code and functionality)?

  • Lots of maths which is a bit difficult to understand
  • Hard coded creation policy
  • No flexibility in drawing
  • All boids behave in pretty much the same way.