Boids

The Boids algorithm was an artificial life program developed by Craig Reynolds in 1986 to model flocking behavior of birds. Complicated behaviors emerge from these three basic rules:

1. Separation: steer to avoid crowding local flock-mates

2. Alignment: steer towards the average heading of local flock-mates

3. Cohesion: steer to move toward the average position (center of mass) of local flock-mates

Basically, each boid considers all other boids within a set distance to be part of its flock, adjusting its own velocity to both match that of flock members in its cone of vision and attempting to avoid collisions.

I’ve implemented the algorithm in just a few lines of code and uploaded the sketch file to OpenProcessing, i.e. jsfiddle for Processing. Fork it and try enforcing different rules and see what emerges.

The source code is under 200 lines:

class Boid {
  float x;
  float y;
  float vx;
  float vy;
  color c;

  Boid(float x, float y, float vx, float vy, color c){
    this.x=x;
    this.y=y;
    this.vx=vx;
    this.vy=vy;
    this.c=c;
  }
}

int worldSize = 550;
int boidCount = 100;
int boidHeight = 10;
int boidWidth = 3;
float boidStartingSpeed = .1;
float boidMaxSpeed = 2;
float boidDetectionMaxAngle = 0.1*TWO_PI;
int boidDetectionRange = 50;
int boidCollisionRange = 7;
float boidCollisionPower = 0.42;
float boidFlockingPower = 0.69;
float boidCenterPower = 0.2;
int offscreenOffset = 30;
ArrayList<Boid> boids = new ArrayList<Boid>(); 

Boid makeBoid(){ 
   float x = random(worldSize/3,2*worldSize/3);
   float y = random(worldSize/3,2*worldSize/3);
   float theta = random(TWO_PI);
   color c = color(random(255),random(255),random(255));
   Boid b = new Boid(x, y, boidStartingSpeed*cos(theta),
                                   boidStartingSpeed*sin(theta), c);
   return b;
}


float angleBetween(Boid b1, Boid b2){ 
  PVector v1 = new PVector(b1.vx, b1.vy);
  PVector v2 = new PVector(b2.vx, b2.vy);
  return PVector.angleBetween(v1, v2);
}

float distanceBetweenSq(Boid b1, Boid b2){  
   return pow(dist(b1.x, b1.y, b2.x, b2.y),2);
}

Boid updateBoid(Boid b){
  ArrayList<Boid> closeEnough = new ArrayList<Boid>();
  ArrayList<Boid> colliding = new ArrayList<Boid>();
  ArrayList<Boid> detected = new ArrayList<Boid>();
  float newVelx = b.vx;
  float newVely = b.vy;
  float newPosx = 0;
  float newPosy = 0;
  float dr = pow(boidDetectionRange,2);
  float cr = pow(boidCollisionRange,2);
  float sumy = 0;
  float sumx = 0;
  
  for(Boid i : boids){
   if(distanceBetweenSq(b, i) < dr){
     closeEnough.add(i);
     closeEnough.add(i);
   }
  }
  
  for(Boid i : boids){
   if(distanceBetweenSq(b, i) < cr){
     colliding.add(i);
   }
  }
 
  if(closeEnough.size() > 0){
    for(Boid i : closeEnough){
       if(angleBetween(b, i) < boidDetectionMaxAngle){
         detected.add(i);
       }
    }
    if(detected.size()>0){
       for(Boid i : detected){
         sumx += i.vx;
         sumy += i.vy;
       }
       float avgVelx = sumx / detected.size();
       float avgVely = sumy / detected.size();
       newVelx += boidFlockingPower*avgVelx;
       newVely += boidFlockingPower*avgVely;
    }
    sumx=0;sumy=0;
    for(Boid i : closeEnough){
      sumx += i.x;  
      sumy += i.y;
    }
    float meanPosx = sumx / closeEnough.size();
    float meanPosy = sumy / closeEnough.size(); 
    PVector v = new PVector(meanPosx - b.x, meanPosy - b.y);
    v.normalize();
    newVelx += boidCenterPower*v.x;
    newVely += boidCenterPower*v.y;
  }
  
  sumx=0;sumy=0;
  if(colliding.size() > 0){
    for(Boid i : colliding){
      sumx += -(i.x-b.x);  
      sumy += -(i.y-b.y);
    }    
    newVelx += boidCollisionPower*sumx;
    newVely += boidCollisionPower*sumy;
  }  
  
  PVector p = new PVector(newVelx, newVely);
  if(p.mag() > boidMaxSpeed){
    p.normalize();
    newVelx = boidMaxSpeed*p.x;
    newVely = boidMaxSpeed*p.y;
  }  
  
  newPosx = b.x + newVelx;
  newPosy = b.y + newVely;
  
  if(newPosx>worldSize){
    newPosx=0;
  }
  if(newPosx<0){
    newPosx=worldSize;
  }
  if(newPosy>worldSize){
    newPosy=0;
  }
  if(newPosy<0){
    newPosy=worldSize;
  }
  Boid n = new Boid(newPosx, newPosy, newVelx, newVely, b.c);
  
  return n;
  
}


void drawBoid(Boid b) {
  float x = b.x;
  float y = b.y;
  float vy = b.vy;
  float vx = b.vx;
  color c = b.c;
   
  float theta = atan(vy/vx);
  if (vx < 0) {  
    theta += PI;
  }
  
  float h = boidHeight/2.;
  float w = boidWidth/2.;
  
  pushMatrix();
  beginShape();
  fill(c);
  vertex(-h,w);
  vertex(-h,-w);
  vertex(h,0);
  translate(x, y);
  rotate(theta);
  endShape(CLOSE);
  popMatrix();
}

void setup() {
  size(550, 550);
  background(0);
  noStroke();
  smooth();
  for (int i = 0; i < boidCount; i = i+1) {
    boids.add(makeBoid());
  } 
}

void draw() {
  background(#000000);
  for (Boid b : boids) {
    drawBoid(b);
  }
  ArrayList<Boid> newBoids = new ArrayList<Boid>(); 
  for (Boid b : boids) {
    newBoids.add(updateBoid(b));
  } 
  boids = newBoids;
}