daniel shiffman

Examples

download zipped archive of all examples

 

seek and arrive

wander

path following

flow field

flocking

crowd path following

 

Reading

Steering

In the late 80s, Craig Reynolds developed algorithmic steering behaviors for animated characters. These behaviors allowed individual elements to navigate their digital environments in a “life-like” manner with strategies for seeking, fleeing, wandering, arriving, pursuing, evading, path following, obstacle avoiding, etc. Used in the case of a single autonomous agent, these behaviors are fairly simple to understand and implement. In addition, by building a system of multiple characters, each steering according to simple locally-based rules, surprising levels of complexity emerge, the most famous example being Reynolds’ “boids” model for “flocking” / “swarming” behavior.

We can’t get anywhere, however, without first understanding the concept of a steering vector. In the above examples, we have a “Boid” class (similar to our earlier Particle class). This new object has additional variables, such as a maximum speed and maximum steering force. It also has a method to compute a steering vector towards a given target location.

Steering Vector = “Desired Vector” minus “Velocity”
where “desired vector” is defined as the vector pointing from the object’s location directly towards the target

Our method receives a location vector (“target”) and returns a force vector (“steer”) as below:

// A method that calculates a steering vector towards a target
PVector steer(PVector target) {
  PVector steer;  // The steering vector
  PVector desired = PVector.sub(target,loc);  // A vector pointing from the location to the target
  float d = desired.mag(); // Distance from the target is the magnitude of the vector
  // If the distance is greater than 0, calc steering (otherwise return zero vector)
  if (d > 0) {
    // Normalize desired and give it magnitude determined by maxspeed
    desired.normalize();
    desired.mult(maxspeed);
    // Steering = Desired minus Velocity
    steer = PVector.sub(desired,vel);
    steer.limit(maxforce);  // Limit to maximum steering force
  } else {
    steer = new PVector(0,0);
  }
  return steer;
}

Seeking — with the above method, we can now have a Boid object seek a given location. We calculate the steering vector and store it in the object’s acceleration. Reynolds’ seeking example: http://www.red3d.com/cwr/steer/SeekFlee.html.

void seek(PVector target) {
  acc = steer(target);
}

In our examples, however, we accumulate various steering forces (instead of simply setting acceleration equal to one given steering vector.) Remember, when we do this, we must reset acceleration to a zero vector at the end of each cycle.

void update() {
  vel.add(acc);
  vel.limit(maxspeed);
  loc.add(vel);
  acc.setXYZ(0,0,0);
}

void seek(PVector target) {
  acc.add(steer(target));
}

Arrival — Arrival can be achieved in an identical fashion as seeking, only instead of pursuing a target at maximum velocity, the object slows down as it approaches the destination. One solution for implementing this behavior is to modify the steering vector calculation as follows (note in the above examples for this week, the steering method receives a true or false flag to indicate whether it should apply the distance based damping or not). Here, the magnitude of the “desired” vector shrinks as the object approaches the destination. For a full explanation of “arrival”, visit: http://www.red3d.com/cwr/steer/Arrival.html.

// A method that calculates a steering vector towards a target
// Takes a second argument, if true, it slows down as it approaches the target
PVector steer(PVector target, boolean slowdown) {
  PVector steer;  // The steering vector
  PVector desired = PVector.sub(target,loc);  // A vector pointing from the location to the target
  float d = desired.mag(); // Distance from the target is the magnitude of the vector
  // If the distance is greater than 0, calc steering (otherwise return zero vector)
  if (d > 0) {
    // Normalize desired
    desired.normalize();
    // Two options for desired vector magnitude (1 -- based on distance, 2 -- maxspeed)
    if ((slowdown) && (d < 100.0f)) desired.mult(maxspeed*(d/100.0f)); // This damping is somewhat arbitrary
    else desired.mult(maxspeed);
    // Steering = Desired minus Velocity
    steer = PVector.sub(desired,vel);
    steer.limit(maxforce);  // Limit to maximum steering force
  } else {
    steer = new PVector(0,0);
  }
  return steer;
}
  }

Wandering — Reynolds’ method for wandering is a bit more complex. It involves steering towards a random point on a circle projected at a given length in front of the the object. Normally, we think of wandering as applying a random steering vector each frame of animation. Reynolds solution is more sophisticated as it implements an ordered wandering where the steering at one moment is related to the previous one (note the conceptual similarity here to what perlin noise achieves for us). For a full explanation, visit: http://www.red3d.com/cwr/steer/Wander.html.

Here is our implementation of the wander algorithm:

void wander() {
  float wanderR = 16.0f;         // Radius for our "wander circle"
  float wanderD = 60.0f;         // Distance for our "wander circle"
  float change = 0.25f;
  wandertheta += random(-change,change);     // Randomly change wander theta

  // Now we have to calculate the new location to steer towards on the wander circle
  PVector circleloc = vel.copy();  // Start with velocity
  circleloc.normalize();            // Normalize to get heading
  circleloc.mult(wanderD);          // Multiply by distance
  circleloc.add(loc);               // Make it relative to boid's location

  PVector circleOffSet = new PVector(wanderR*cos(wandertheta),wanderR*sin(wandertheta));
  PVector target = PVector.add(circleloc,circleOffSet);
  acc.add(steer(target,false));  // Steer towards it

  // Render wandering circle, etc.
  if (drawwandercircle) drawWanderStuff(loc,circleloc,target,wanderR);

}  

Group Behaviors

Once we’ve mastered control over a single object navigating its environment, we can begin to experiment with a group of autonomous agents, each steering according to the relative positions and velocities of its neighbors. One of the most famous examples is Reynolds’ rules for flocking Boids which incorporates the following three rules:

 
In order to implement this, we can revise the Particle system class to manage an ArrayList of boids (note we could build these classes using inhertiance, but to simplify the examples, we’ll leave them as stand-alone classes). The difference here is that each boid not only needs to know about its own properties (location, velocity, etc.), but it needs to know about all the other boids as well. We can accomplish this by passing the ArrayList as an argument to an individual boids’ “run” method, i.e.

class Flock {
  ArrayList boids; // An arraylist for all the boids

  Flock() {
    boids = new ArrayList(); // Initialize the arraylist
  }

  void run() {
    for (int i = 0; i < boids.size(); i++) {
      Boid b = (Boid) boids.get(i);
      b.run(boids);  // Passing the entire list of boids to each boid individually
    }
  }

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

}

Once each individual boid / particle knows about the whole list of boids it can perform calculations based on it, such as compute the average velocity of all particles, center of all particles, check for its neighbors, etc. For example, consider this method built into the boid class itself:

// Cohesion
// For the average location (i.e. center) of all nearby boids, calculate steering vector towards that location
PVector cohesion (ArrayList boids) {
  float neighbordist = 50.0f;
  PVector sum = new PVector(0,0,0);   // Start with empty vector to accumulate all locations
  int count = 0;
  for (int i = 0 ; i < boids.size(); i++) {
    Boid other = (Boid) boids.get(i);
    float d = PVector.distance(loc,other.loc);
    if ((d > 0) && (d < neighbordist)) {
      sum.add(other.loc); // Add location
      count++;
    }
  }
  if (count > 0) {
    sum.div((float)count);
    return steer(sum,false);  // Steer towards the location
  }
  return sum;
}

In the above we code, we peform the following algorithm:

 
With the above method, along with two more similar ones for separation and alignment, we now have all the elements for flocking, i.e. take the results of the three rules, weight them appropriately, and accumulate them together in the object’s acceleration.

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

OpenSteer

C++ implementation of the above autonomous steering behaviors and more can be found in the OpenSteer library: http://opensteer.sourceforge.net/