Boids and Flocks

As stated before, immersion in an interactive medium is dependent on the realism of the movement of the objects in the environment. One area where I was having problems with this in my previous experimentation was with the interaction between the birds. One way I could incorporated some kind of collision detection would be with a physics library, such as Box 2D for Processing. However the kind of physics that this library provides, such as balls rebounding off each other or boxes breaking, is not exactly the way birds would react in real life.

murmuration
A Starling murmuraton

In the real world, birds create flocks to travel in large numbers. As researched in his paper for SIGGRAPH, Craig Reynolds (1987) described the physical laws that dictate the formation of flocks.

flockingforces
Image by Daniel Shiffman

To build a simulated flock, we start with a boid model that supports geometric flight. We add behaviors that correspond to the opposing forces of collision avoidance and the urge to join the flock. Stated briefly as rules, and in order of decreasing precedence, the behaviors that lead to simulated flocking are:

Collision Avoidance: avoid collisions with nearby flockmates
Velocity Matching: attempt to match velocity with nearby flockmates
Flock Centering: attempt to stay close to nearby flockmates

(Reynolds, 1987)

With the rules, simulated objects named boids in his simulation react similarly as real world flocks would do. By staying close but avoiding colliding with other flockmates the boids form a cohesive group.

Here’s an early version of the bird’s flocking behavior. To create the flocking phenomenon I added three functions to the birds object. Each of the functions returns a PVector called steer which is processed using a steer function which I used before.

  // Separation
  // Method checks for nearby boids and steers away
  //Takes Array List of Boids as argument
  PVector separate (ArrayList<Boid> boids) {
    float desiredseparation = 25.0f;
    //PVector that is returneed
    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(location,other.location);
      // If the distance is greater than 0 and less than an arbitrary amount
      if ((d > 0) && (d < desiredseparation)) {
        // Calculate vector pointing away from neighbor
        PVector diff = PVector.sub(location,other.location);
        //normalise
        diff.normalize();
        //make relative to how far the other boid is
        diff.div(d);        
        steer.add(diff);
        count++;            
      }
    }
    // Divide by the number of boids gives average
    //needed to seperate from them all
    if (count > 0) {
      steer.div((float)count);
    }

 
    if (steer.mag() > 0) {
      // make the steering a "seeking" vector not an absolute
      steer.normalize();
      steer.mult(maxspeed);
      steer.sub(velocity);
      steer.limit(maxforce);
    }
    return steer;
  }

The separate function takes the whole list of birds and if they are in a certain distance, steers away from them, but this steering is dictated by the number of birds in a flock. Like the “seeking” function, it is not absolute and works on a “desired location” basis.

 // Alignment
  // For every nearby boid in the system, calculate the average velocity
  PVector align (ArrayList<Boid> boids) {
    float neighbordist = 100;
    PVector sum = new PVector(0,0);
    int count = 0;
    for (Boid other : boids) {
      float d = PVector.dist(location,other.location);
      if ((d > 0) && (d < neighbordist)) {
        //adds the other boids velocity to the sum
        sum.add(other.velocity);
        count++;
      }
    }
    if (count > 0) {
      sum.div((float)count);
      sum.normalize();
      sum.mult(maxspeed);
      //steer is based off subtracting the velocity from the sum
      PVector steer = PVector.sub(sum,velocity);
      steer.limit(maxforce);
      return steer;
    } else {
      return new PVector(0,0);
    }
  }

The alignment function is similar in that it works by taking the boids within a selected circle and subtracts the sum of velocity of all of the boids from the current boid’s steering.

  // Cohesion
  // Calculate steering vector towards average location of nearby boids
  PVector cohesion (ArrayList<Boid> boids) {
    float neighbordist = 50;
    //locations will get accumulated to this vector
    PVector sum = new PVector(0,0);   
    int count = 0;
    for (Boid other : boids) {
      float d = PVector.dist(location,other.location);
      if ((d > 0) && (d < neighbordist)) {
        //add boids location to sum
        sum.add(other.location);
        count++;
      }
    }
    if (count > 0) {
      //Devide by nearby boids to get average
      sum.div(count);
      //Steer towards that location
      return seek(sum);  
    } else {
      return new PVector(0,0);
    }
  }
}

The cohesion function finds the average location of all nearby boids and uses the seek function created earlier to create a steering force towards that loaction.

 void flock(ArrayList<Vehicle> Vehicles) {
    PVector sep = separate(Vehicles);   // Separation
    PVector ali = align(Vehicles);      // Alignment
    PVector coh = cohesion(Vehicles);   // 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);
  }

The flocking function then brings this all together by weighting and applying the PVectors from the other three functions to the birds’ velocity by using the old applyForce method to add the vectors on.

Next was to add interactivity to the flocking behavior. The easiest way to test this was to use the seek function I had created before with a PVector created from the mouse’s location.

Overall I think this works very well. The birds move quite realistically through the sketch and react well to the movements of the mouse. However I do need add a left-facing “sprite” to the birds so that they don’t fly backwards. Next I need to incorporate this testing and techniques with my previous camera work in order to begin work on the final piece.

Shiffman, D., 2015. Box 2D for Processing [online] Availble from:https://github.com/shiffman/Box2D-for-Processing [Accessed 02.02.2015]

Reynolds, C., 1987. Flocks, Herds and Schools. A Distributed Behavioural Model. In SIGGRAPH July 1987. California: ACM Press, 25-34.

Shiffman, D., 2012. The Nature of Code [online] Mountain View: Creative Commons.