Chapter 5. Autonomous Agents

“This is an exercise in fictional science, or science fiction, if you like that better.”

— Valentino Braitenberg

Believe it or not, there is a purpose. Well, at least there’s a purpose to the first five chapters of this book. I could stop right here; after all, I’ve covered several different ways of modeling motion and simulating physics. Angry Birds, here we come!

Still, let’s think for a moment. Why are you here? The nature of code, right? What have I been demonstrating so far? Inanimate objects. Lifeless shapes sitting in canvas that flop around when affected by forces in their environment. What if you could breathe life into those shapes? What if those shapes could live by their own rules? Can shapes have hopes and dreams and fears? This is what I am here in this chapter to do—develop autonomous agents.

5.1 Forces from Within

The term autonomous agent generally refers to an entity that makes its own choices about how to act in its environment without any influence from a leader or global plan. For the context here, “acting” will mean moving. This addition is a significant conceptual leap. Instead of a box sitting on a boundary waiting to be pushed by another falling box, I would like to now design a box that has the ability and “desire” to leap out of the way of that other falling box, if it so chooses. While the concept of forces that come from within is a major shift in design thinking, the code base will barely change, as these desires and actions are simply that—forces.

Here are three key components of autonomous agents that I’ll want to keep in mind as I build the examples.

• An autonomous agent has a limited ability to perceive environment. It makes sense that a living, breathing being should have an awareness of its environment. What does this mean, however? Throughout all the examples in this chapter, I will point out programming techniques for objects to store references to other objects and therefore “perceive” their environment. It’s also crucial to consider the word limited here. Are you designing an all-knowing rectangle that flies around a p5 window, aware of everything else in that window? Or are you creating a shape that can only examine any other object within fifteen pixels of itself? Of course, there is no right answer to this question; it all depends. I’ll explore several possibilities throughout this chapter. For a simulation to feel more “natural,” however, limitations are a good thing. An insect, for example, may only be aware of the sights and smells that immediately surround it. For a real-world creature, you could study the exact science of these limitations. Luckily, I can just make stuff up and try it out.
• An autonomous agent processes the information from its environment and calculates an action. This will be the easy part, as the action is a force. The environment might tell the agent that there’s a big scary-looking shark swimming right at it, and the action will be a powerful force in the opposite direction.
• An autonomous agent has no leader. This third principle is something I care a little less about for the context here. After all, if you are designing a system where it makes sense to have a leader barking commands at various entities, then that’s what you’ll want to implement. Nevertheless, many of these examples will have no leader for an important reason. Towards the end of this chapter, I'll examine group behaviors and look at designing collections of autonomous agents that exhibit the properties of complex systems— intelligent and structured group dynamics that emerge not from a leader, but from the local interactions of the elements themselves.

In the late 1980s, computer scientist Craig Reynolds developed algorithmic steering behaviors for animated characters. These behaviors allowed individual elements to navigate their digital environments in a “lifelike” manner with strategies for fleeing, wandering, arriving, pursuing, evading, and more. 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 that steer themselves according to simple, locally based rules, surprising levels of complexity emerge. The most famous example is Reynolds’s “boids” model for “flocking/swarming” behavior.

5.2 Vehicles and Steering

Now that I‘ve discussed the core concepts behind autonomous agents, it‘s time to begin writing the code. There are many places where I could start. Artificial simulations of ant and termite colonies are fantastic demonstrations of systems of autonomous agents. (For more on this topic, I encourage you to read Turtles, Termites, and Traffic Jams by Mitchel Resnick.) However, I want to begin by examining agent behaviors that build on the work in the first five chapters of this book: modeling motion with vectors and forces. And so it’s time to once again rename the Mover class that became the Particle class. This time I am going to call it Vehicle.

class Vehicle {

  constructor(){
    this.position = createVector();
    this.velocity = createVector();
    this.acceleration = createVector();
  }

In his 1999 paper “Steering Behaviors for Autonomous Characters,” Reynolds uses the word “vehicle” to describe his autonomous agents, so I will follow suit.

Reynolds describes the motion of idealized vehicles (idealized because he was not concerned with the actual engineering of such vehicles, but rather started with the assumption that they work and respond to the rules defined) as a series of three layers—Action Selection, Steering, and Locomotion.

1. Action Selection. A vehicle has a goal (or goals) and can select an action (or a combination of actions) based on that goal. This is essentially where I left off the discussion of autonomous agents. The vehicle takes a look at its environment and calculates an action based on a desire: “I see a zombie marching towards me. Since I don’t want my brains to be eaten, I’m going to flee from the zombie.” The goal is to keep one’s brains and the action is to flee. Reynolds’s paper describes many goals and associated actions such as: seek a target, avoid an obstacle, and follow a path. In a moment, I’ll start building these examples out with p5.js code.
2. Steering. Once an action has been selected, the vehicle has to calculate its next move. That next move will be a force; more specifically, a steering force. Luckily, Reynolds has developed a simple steering force formula that I’ll use throughout the examples in this chapter: steering force = desired velocity - current velocity. I’ll get into the details of this formula and why it works so effectively in the next section.
3. Locomotion. For the most part, I’m going to ignore this third layer. In the case of fleeing zombies, the locomotion could be described as “left foot, right foot, left foot, right foot, as fast as you can.” In a p5 canvas, however, a rectangle or circle or triangle’s actual movement across a window is irrelevant given that it’s all an illusion in the first place. Nevertheless, this isn’t to say that you should ignore locomotion entirely. You will find great value in thinking about the locomotive design of your vehicle and how you choose to animate it. The examples in this chapter will remain visually bare, and a good exercise would be to elaborate on the animation style —could you add spinning wheels or oscillating paddles or shuffling legs?

Ultimately, the most important layer for you to consider is #1—Action Selection. What are the elements of your system and what are their goals? In this chapter, I am going to cover a series of steering behaviors (i.e. actions): seek, flee, follow a path, follow a flow field, flock with your neighbors, etc. It’s important to realize, however, that the point of understanding how to write the code for these behaviors is not because you should use them in all of your projects. Rather, these are a set of building blocks, a foundation from which you can design and develop vehicles with creative goals and new and exciting behaviors. And even though the examples will be highly literal in this chapter (follow that pixel!), you should allow yourself to think more abstractly (like Braitenberg). What would it mean for your vehicle to have “love” or “fear” as its goal, its driving force? Finally (and I’ll address this later in the chapter), you won’t get very far by developing simulations with only one action. Yes, the first example will be “seek a target.” But for you to be creative—to make these steering behaviors your own—it will all come down to mixing and matching multiple actions within the same vehicle. So view these examples not as singular behaviors to be emulated, but as pieces of a larger puzzle that you will eventually assemble.

5.3 The Steering Force

I could entertain you by discussing the theoretical principles behind autonomous agents and steering as much as you like, but we won’t get anywhere without first understanding the concept of a steering force. Consider the following scenario: a vehicle moving with velocity desires to seek a target.

Its goal and subsequent action is to seek the target in Figure 5.1. If you think back to Chapter 2, you might begin by making the target an attractor and apply a gravitational force that pulls the vehicle to the target. This would be a perfectly reasonable solution, but conceptually it’s not what I’m looking for here. I don’t want to simply calculate a force that pushes the vehicle towards its target; rather, I would like to ask the vehicle to make an intelligent decision to steer towards the target based on its perception of its state and environment (i.e. how fast and in what direction is it currently moving). The vehicle should look at how it desires to move (a vector pointing to the target), compare that goal with how it is currently moving (its velocity), and apply a force accordingly.

steering force = desired velocity - current velocity

Or as you might write in p5:

let steer = p5.Vector.sub(desired, velocity);

In the above formula, velocity is not a problem. After all, there is already a variable for that. However, the desired velocity is something that has to be calculated. Take a look at Figure 5.2. If the vehicle’s goal is defined as “seeking the target,” then its desired velocity is a vector that points from its current position to the target position.

Assuming a p5.Vector target, I then have:

let desired = p5.Vector.sub(target, position);

But this there is more to the story here. What if the canvas is high-resolution and the target is thousands of pixels away? Sure, the vehicle might desire to teleport itself instantly to the target position with a massive velocity, but this won’t make for an effective animation. I’ll restate the desire as follows:

The vehicle desires to move towards the target at maximum speed.

In other words, the vector should point from position to target with a magnitude equal to maximum speed (i.e. the fastest the vehicle can go). So first, I’ll need to make sure to add a property to the Vehicle class for maximum speed itself.

class Vehicle {

  constructor(){
    this.position = createVector();
    this.velocity = createVector();
    this.acceleration = createVector();

    this.maxspeed = ????;
  }
  

Then, in the desired velocity calculation, I’ll scale according to maximum speed.

let desired = p5.Vector.sub(target, this.position);
desired.normalize();
desired.mult(this.maxspeed);

Putting this all together, I can now write a function called seek() that receives a p5.Vector target and calculates a steering force towards that target.

  seek(target) {
    let desired = p5.Vector.sub(target,this.position);
    desired.normalize();

    desired.mult(this.maxspeed);

    let steer = p5.Vector.sub(desired, this.velocity);

    this.applyForce(steer);

  }

Note how in the above function I finish by passing the steering force into applyForce(). This assumes that the the code is built on top of the foundation built in Chapter 2. However, you could just as easily use the steering force with Box2D’s applyForce() function or toxiclibs’ addForce() function.

So why does this all work so well? Let’s see what the steering force looks like relative to the vehicle and target positions.

Again, notice how this is not at all the same force as gravitational attraction. Remember one of the principles of autonomous agents: An autonomous agent has a limited ability to perceive its environment. Here is that ability, subtly embedded into Reynolds’s steering formula. If the vehicle weren’t moving at all (zero velocity), desired minus velocity would be equal to desired. But this is not the case. The vehicle is aware of its own velocity and its steering force compensates accordingly. This creates a more active simulation, as the way in which the vehicle moves towards the targets depends on the way it is moving in the first place.

In all of this excitement, however, I’ve missed one last step. What sort of vehicle is this? Is it a super sleek race car with amazing handling? Or a large city bus that needs a lot of advance notice to turn? A graceful panda, or a lumbering elephant? The example code, as it stands, has no feature to account for this variability in steering ability. Steering ability can be controlled by limiting the magnitude of the steering force. Let’s call that limit the “maximum force” (or maxforce for short). And so finally:

class Vehicle {

  constructor(){
    this.position = createVector();
    this.velocity = createVector();
    this.acceleration = createVector();

    this.maxspeed = ????;

    this.maxforce = ????;
  }
  

followed by:

  seek(target) {
    let desired = p5.Vector.sub(target, this.position);
    desired.normalize();
    desired.mult(this.maxspeed);
    let steer = p5.Vector.sub(desired, this.velocity);

    steer.limit(this.maxforce);

    this.applyForce(steer);
  }

Limiting the steering force brings up an important point. Remember, it’s not actually the goal here to get the vehicle to the target as fast as possible. If that were the case, I would just say “position equals target” and there the vehicle would be. The goal, as Reynolds puts it, is to move the vehicle in a “lifelike and improvisational manner.” I’m trying to make it appear as if the vehicle is steering its way to the target, and so it’s up to me to play with the forces and variables of the system to simulate a given behavior. For example, a large maximum steering force would result in a very different path than a small one. One is not inherently better or worse than the other; it depends on the desired effect. (And of course, these values need not be fixed and could change based on other conditions. Perhaps a vehicle has health: the higher the health, the better it can steer.)

Here is the full Vehicle class, incorporating the rest of the elements from the Chapter 2 Mover object.

Example 5.1: Seeking a target

class Vehicle {
  constructor(x, y){
    this.acceleration = createVector(0, 0);
    this.velocity = createVector(0, 0);
    this.position = createVector(x,y);

    this.r = 3.0;

    this.maxforce = 4;
    this.maxspeed = 0.1;

  }

  update() {
    this.velocity.add(this.acceleration);
    this.velocity.limit(this.maxspeed);
    this.position.add(this.velocity);
    this.acceleration.mult(0);
  }

  applyForce(force) {
    this.acceleration.add(force);
  }

  seek(target) {
    let desired = p5.Vector.sub(target, this.position);
    desired.normalize();
    desired.mult(this.maxspeed);
    const steer = p5.Vector.sub(desired, this.velocity);
    steer.limit(this.maxforce);
    this.applyForce(steer);
  }

  display() {

    let theta = this.velocity.heading() + PI/2;

    fill(175);
    stroke(0);
    push();
    translate(this.position.x, this.position.y);
    rotate(theta);
    beginShape();
    vertex(0, -this.r * 2);
    vertex(-this.r, this.r * 2);
    vertex(this.r, this.r * 2);
    endShape(CLOSE);
    pop();
  }
}

5.4 Arriving Behavior

After working for a bit with the seeking behavior, you probably are asking yourself, “What if I want my vehicle to slow down as it approaches the target?” Before I can even begin to answer this question, I should look at the reasons behind why the seek behavior causes the vehicle to fly past the target so that it has to turn around and go back. Let’s consider the brain of a seeking vehicle. What is it thinking?

• Frame 1: I want to go as fast as possible towards the target
• Frame 2: I want to go as fast as possible towards the target
• Frame 3: I want to go as fast as possible towards the target
• Frame 4: I want to go as fast as possible towards the target
• Frame 5: I want to go as fast as possible towards the target
• etc.

The vehicle is so gosh darn excited about getting to the target that it doesn’t bother to make any intelligent decisions about its speed relative to the target’s proximity. Whether it’s far away or very close, it always wants to go as fast as possible.

In some cases, this is the desired behavior (if a missile is flying at a target, it should always travel at maximum speed.) However, in many other cases (a car pulling into a parking spot, a bee landing on a flower), the vehicle’s thought process needs to consider its speed relative to the distance from its target. For example:

Frame 1: I’m very far away. I want to go as fast as possible towards the target

Frame 2: I’m very far away. I want to go as fast as possible towards the target

Frame 3: I’m somewhat far away. I want to go as fast as possible towards the target

Frame 4: I’m getting close. I want to go more slowly towards the target

Frame 5: I’m almost there. I want to go very slowly towards the target

Frame 6: I’m there. I want to stop!

How can you implement this “arriving” behavior in code? Let’s return to the seek() function and find the line of code which sets the magnitude of the desired velocity.

   let desired = p5.Vector.sub(target, this.position);
   desired.setMag(this.maxspeed);

In Example 5.1, the magnitude of the desired vector is always “maximum speed.”

What if instead the desired velocity's magnitude were equal to half the distance?

   let desired = p5.Vector.sub(target, this.position);
   desired.div(2);

While this nicely demonstrates the goal of a desired speed tied to the distance from the target, it’s not a particularly good solution. After all, 10 pixels away is rather close and a desired speed of 5 is rather large. Something like a desired velocity with a magnitude of 5% of the distance might work much better.

  let desired = p5.Vector.sub(target, this.position);
  desired.mult(0.05);

Reynolds describes an even more sophisticated approach. Imagine a circle around the target with a given radius. If the vehicle is within that circle, it slows down—at the edge of the circle, its desired speed is maximum speed, and at the target itself, its desired speed is 0.

In other words, if the distance from the target is less than r, the desired speed is between 0 and maximum speed mapped according to that distance.

Example 5.2: Arrive steering behavior

  arrive(target) {
    let desired = p5.Vector.sub(target, this.position);

    let d = desired.mag();

    if (d < 100) {

      let m = map(d, 0, 100, 0, this.maxspeed);
      desired.setMag(m);

    } else {

      desired.setMag(this.maxspeed);

    }

    let steer = p5.Vector.sub(desired, this.velocity);

    steer.limit(this.maxforce);
    this.applyForce(steer);
  }

The arrive behavior is a great demonstration of the magic of “desired minus velocity.” Let’s examine this model again relative to how forces were calculated in Chapter 2. In the “gravitational attraction” example, the force always pointed directly from the object to the target (the exact direction of the desired velocity).

The steering function, however, says: “I have the ability to perceive the environment.” The force isn’t based on just the desired velocity, but on the desired velocity relative to the current velocity. Only things that are alive can know their current velocity. A box falling off a table doesn’t know it’s falling. A cheetah chasing its prey, however, knows it is chasing.

The steering force, therefore, is essentially a manifestation of the current velocity’s error: "I’m supposed to be going this fast in this direction, but I’m actually going this fast in another direction. My error is the difference between where I want to go and where I am currently going." Taking that error and applying it as a steering force results in more dynamic, lifelike simulations. With gravitational attraction, you would never have a force pointing away from the target, no matter how close. But with arriving via steering, if you are moving too fast towards the target, the error would actually tell you to slow down!

5.5 Your Own Desires: Desired Velocity

The first two examples I’ve covered—seek and arrive—boil down to calculating a single vector for each behavior: the desired velocity. And in fact, every single one of Reynolds’s steering behaviors follows this same pattern. In this chapter, I’m going to walk through several more of Reynolds’s behaviors—flow field, path-following, flocking. First, however, I want to emphasize again that these are examples—demonstrations of common steering behaviors that are useful in procedural animation. They are not the be-all and end-all of what you can do. As long as you can come up with a vector that describes a vehicle’s desired velocity, then you have created your own steering behavior.

Let’s see how Reynolds defines the desired velocity for his wandering behavior.

“Wandering is a type of random steering which has some long term order: the steering direction on one frame is related to the steering direction on the next frame. This produces more interesting motion than, for example, simply generating a random steering direction each frame.”

—Craig Reynolds

For Reynolds, the goal of wandering is not simply random motion, but rather a sense of moving in one direction for a little while, wandering off to the next for a little bit, and so on and so forth. So how does Reynolds calculate a desired vector to achieve such an effect?

Figure 5.12 illustrates how the vehicle predicts its future position as a fixed distance in front of it (in the direction of its velocity), draws a circle with radius r at that position, and picks a random point along the circumference of the circle. That point moves randomly around the circle in each frame of animation. And that point is the vehicle’s target, its desired velocity pointing in that direction.

Sounds a bit absurd, right? Or, at the very least, rather arbitrary. In fact, this is a very clever and thoughtful solution—it uses randomness to drive a vehicle’s steering, but constrains that randomness along the path of a circle to keep the vehicle’s movement from appearing jittery, and, well, totally random.

But the seemingly random and arbitrary nature of this solution should drive home the point I’m trying to make—these are made-up behaviors inspired by real-life motion. You can just as easily concoct some elaborate scenario to compute a desired velocity yourself. And you should.

Exercise 5.4

Write the code for Reynolds’s wandering behavior. Use polar coordinates to calculate the vehicle’s target along a circular path.

Let’s say I wanted to create a steering behavior called “stay within walls.” I’ll define the desired velocity as:

If a vehicle comes within a distance d of a wall, it desires to move at maximum speed in the opposite direction of the wall.

If I define the walls of the space as the edges of a p5.js canvas and the distance d as 25, I can write the code for this with a series of if statements.

Example 5.3: “Stay within walls” steering behavior

if (this.position.x > 25) {

  let desired = createVector(this.maxspeed, this.velocity.y);

  let steer = p5.Vector.sub(desired, this.velocity);
  steer.limit(this.maxforce);
  this.applyForce(steer);
}

5.6 Flow Fields

Now back to the task at hand. Let’s examine a couple more of Reynolds’s steering behaviors. First, flow field following. What is a flow field? Think of your canvas as a grid. In each cell of the grid lives an arrow pointing in some direction—you know, a vector. As a vehicle moves around the canvas, it asks, “Hey, what arrow is beneath me? That’s my desired velocity!”

Reynolds’s flow field following example has the vehicle predicting its future position and following the vector at that spot, but for simplicity’s sake, I’ll have the vehicle simply look to the vector at its current position.

Before I can write the additional code for the Vehicle class, I’ll need to build a class that describes the flow field itself, the grid of vectors. A two-dimensional array is a convenient data structure in which to store a grid of information. If you are not familiar with 2D arrays, I suggest reviewing this video: 2D Arrays in JavaScript - p5.js Tutorial. The 2D array is convenient because I can reference each element with two indices, and think of these as columns and rows.

class FlowField {

  constructor(){

    this.resolution = ????;

    this.cols = ????;
    this.rows = ????;
    this.resolution = ????;

    this.field = [];
  }
  

Notice how we are defining a third variable called resolution above. What is this variable? Let’s say I have a p5.js canvas that is 200 pixels wide by 200 pixels high. I could make a flow field that has a vector for every single pixel, or 40,000 vectors (200 * 200). This isn’t terribly unreasonable, but in this context, it’s overkill. I don’t need a vector for every single pixel; I can achieve the same effect by having, say, one every ten pixels (20 * 20 = 400). I’ll use this resolution to define the number of columns and rows based on the size of the canvas divided by resolution:

  constructor(){
    this.resolution = 10;

    this.cols = width / this.resolution;

    this.rows = height / this.resolution;

    this.resolution = ????;

    this.field = [];
    for (let i = 0; i < this.cols; i++) {
      this.field[i] = [];
    }
  }
  

Now that I’ve set up the flow field’s data structures, it’s time to compute the vectors in the flow field itself. How do you do that? However you feel like it! Perhaps you want to have every vector in the flow field pointing to the right.

for (let i = 0; i < this.cols; i++) {
  for (let j = 0; j < this.rows; j++) {

    this.field[i][j] = createVector(1, 0);

  }
}

Or perhaps you want the vectors to point in random directions.

for (let i = 0; i < this.cols; i++) {
  for (let j = 0; j < this.rows; j++) {

    this.field[i][j] = p5.Vector.random2D();

  }
}

What if you use 2D Perlin noise (mapped to an angle)?

let xoff = 0;
for (let i = 0; i < this.cols; i++) {
  let yoff = 0;
  for (let j = 0; j < this.rows; j++) {

    let angle = map(noise(xoff, yoff), 0, 1, 0, TWO_PI);

    this.field[i][j] = p5.Vector.fromAngle(angle);
    yoff += 0.1;
  }
  xoff += 0.1;
}

Now I’m getting somewhere. Flow fields can be used for simulating various effects, such as an irregular gust of wind or the meandering path of a river. Calculating the direction of vectors using Perlin noise is one way to achieve such an effect. Of course, there’s no “correct” way to calculate the vectors of a flow field; it’s really up to you to decide what you’re looking to simulate.

Exercise 5.6

Write the code to calculate a p5.Vector at every position in the flow field that points towards the center of a window. 

const v = createVector(____________,____________);
v.______________();
this.field[i][j] = v;

Now that I have a two-dimensional array storing all of the flow field vectors, I need a way for a vehicle to look up its desired velocity in the flow field. Let’s say there is a vehicle that lives at a p5.Vector: its position. I first need to divide that position by the resolution of the grid. For example, if the resolution is 10 and the vehicle is at (100, 50), I’ll want to look up column 10 and row 5.

let column = floor(this.position.x / this.resolution);
let row = floor(this.position.y / this.resolution);

Because a vehicle could theoretically wander off the p5 canvas, it’s also useful to employ the constrain() function to make sure I don’t look outside the bounds of flow field array. Here is a function I’ll call lookup(), part of the FlowField class, that receives a vector (presumably the position of the vehicle) and returns the corresponding flow field vector for that position.

  lookup(lookup) {

    let column = constrain(floor(lookup.x / this.resolution), 0, this.cols - 1));
    let row    = constrain(floor(lookup.y / this.resolution), 0, this.rows - 1));

    return this.field[column][row].copy();

  }

Before I move on to the Vehicle class, let’s take a look at the FlowField class all together.

class FlowField {

  constructor(r) {
    this.resolution = r;

    this.cols = width / this.resolution;
    this.rows = height / this.resolution;

    this.field = make2Darray(this.cols, this.row);

    init();
  }

  init() {

    noiseSeed(random(10000));
    let xoff = 0;
    for (let i = 0; i < this.cols; i++) {
      let yoff = 0;
      for (let j = 0; j < this.rows; j++) {

        let angle = map(noise(xoff, yoff), 0, 1, 0, TWO_PI);
        this.field[i][j] = p5.Vector.fromAngle(angle);
        yoff += 0.1;
      }
      xoff += 0.1;
    }
  }

  lookup(lookup) {
    let column = constrain(floor(lookup.x / this.resolution), 0, this.cols - 1));
    let row = constrain(floor(lookup.y / this.resolution), 0, this.rows - 1));
    return this.field[column][row].copy();
  }

}

So let’s assume there is a FlowField object called “flow”. Using the lookup() function above, a vehicle can then retrieve a desired velocity from the flow field and use Reynolds’s rules (steering = desired - velocity) to calculate a steering force.

Example 5.4: Flow field following 

class Vehicle {

  follow(flow) {

    let desired = flow.lookup(this.position);
    desired.setMag(this.maxspeed);

    let steer = p5.Vector.sub(desired, this.velocity);
    steer.limit(this.maxforce);
    this.applyForce(steer);

  }

5.7 The Dot Product

In a moment, I’m going to work through the algorithm (along with accompanying mathematics) and code for another of Craig Reynolds’s steering behaviors: Path Following. Before I can do this, however, I would like to spend some time discussing another piece of vector math that I skipped over in Chapter 1—the dot product. I haven’t needed it yet, but it’s likely going to prove quite useful for you (beyond just this path-following example).

Remember all the basic vector math covered in Chapter 1? Add, subtract, multiply, and divide?

Notice how in the above diagram, vector multiplication involves multiplying a vector by a scalar value? This makes sense; when you want a vector to be twice as large (but facing the same direction), multiply it by 2. When you want it to be half the size, multiply it by 0.5.

However, there are several other multiplication-like operations with vectors that are useful in certain scenarios—the dot product, the cross product, and something called a Hadamard product. For now I’m going to focus on the dot product, defined as follows. Assume vectors $\vec{A}$ and $\vec{B}$:

THE DOT PRODUCT: $\vec{A}\cdot\vec{B}=a_x\times b_x + a_y\times b_y$

For example, assuming the following two vectors:

Notice that the result of the dot product is a scalar value (a single number) and not a vector.

In p5.js, this would translate to:

const a = createVector(-3, 5);
const b = createVector(10, 1);

const n = a.dot(b);

And if you were to look in the guts of the p5.Vector source, you’d find a pretty simple implementation of this function:

function dot(v) {
  return this.x * v.x + this.y * v.y + this.z * v.z;
}

This is simple enough, but why do you need the dot product, and when is it useful in coding?

One of the more common uses of the dot product is to find the angle between two vectors. The dot product can also be be expressed as:

In other words, A dot B is equal to the magnitude of A times magnitude of B times cosine of theta (with theta defined as the angle between the two vectors A and B).

The two formulas for dot product can be derived from one another with trigonometry, but for the context here I am happy to simply operate on the assumption that:

and therefore:

Now, let’s start with the following problem. Assuming, again, the vectors A and B:

I now have a situation in which I know everything except for the angle between—theta. I know the components of the vector and can calculate the magnitude of each vector. Therefore I can solve for cosine of theta:

To solve for theta, I can then take the inverse cosine (often expressed as cosine or arccosine).

Doing the math now with actual numbers:

Therefore:

The p5.js version of this would be:

let a = createVector(10, 2);
let b = createVector(4, -3);
let theta = acos(a.dot(b) / (a.mag() * b.mag()));

And, again, if you were to dig into the guts of the p5.js source code, you would see a function that implements this exact algorithm.

  function angleBetween(v1, v2) {
    let dot = v1.dot(v2);
    let theta = Math.acos(dot / (v1.mag() * v2.mag()));
    return theta;
  }

Exercise 5.9

Create a sketch that displays the angle between two vectors.

A couple things to note here:

1. If two vectors ($\vec{A}$ and $\vec{B}$) are orthogonal (i.e. perpendicular), the dot product ($\vec{A}\cdot\vec{B}$) is equal to 0.
2. If two vectors are unit vectors, then the dot product is simply equal to cosine of the angle between them, i.e. $\vec{A}\cdot\vec{B}=\cos(\theta)$ if $\vec{A}$ and $\vec{B}$ are of length 1.

5.8 Path Following

Now that I’ve covered the fundamentals of the dot product, I’d like to return to a discussion of Craig Reynolds’s path-following algorithm. Let’s quickly clarify something. I am talking about path following, not path finding. Pathfinding refers to an algorithm (commonly studied in artificial intelligence) that involves solving for the shortest distance between two points, often in a maze. With path following, the path already exists and the vehicle just tries to follow it.

Before we work out the individual pieces, however, let’s take a look at the overall algorithm for path following, as defined by Reynolds.

I’ll start by defining what I mean by a path. There are many ways you could implement a path, but one simple way is to define a path as a series of connected points:

The simplest version of this path would be a line between two points.

I’m also going to consider a path to have a radius. Thinking of the path as a road, the radius determines the road’s width. With a smaller radius, the vehicles will have to follow the path more closely; a wider radius will allow them to stray a bit more.

Putting this into a class :

class Path {

  constructor() {

    this.radius = 20;
    this.start = createVector(0, height / 3);

    this.end = createVector(width, 2 * height / 3);
  }

  display() {
    strokeWeight(this.radius * 2);
    stroke(0, 100);
    line(this.start.x, this.start.y, this.end.x, this.end.y);
    strokeWeight(1);
    stroke(0);
    line(this.start.x, this.start.y, this.end.x, this.end.y);

  }
}

Now, let’s assume there is a vehicle (as depicted below) outside of the path’s radius, moving with a velocity.

The first thing I want to do is predict (assuming a constant velocity) where that vehicle will be in the future.

let predict = vel.copy();

predict.normalize();
predict.mult(25);

let predictLoc = p5.Vector.add(this.position, predict);

Once I have that position, it’s then time to determine the distance from that predicted position to the path. If it’s very far away, well, then, it’s strayed from the path and needs to steer back towards it. If it’s close, then all is well and the vehicle can continue following the path nicely.

So, how do I calculate the distance between a point and a line? This concept is key. The distance between a point and a line is defined as the length of the normal between that point and line. The normal is a vector that extends from that point and is perpendicular to the line.

Let’s figure out what I do know. I know I have a vector (call it $\vec{A}$) that extends from the path’s starting point to the vehicle’s predicted position.

let a = p5.Vector.sub(predictLoc, path.start);

I also know that I can define a vector (call it $\vec{B}$) that points from the start of the path to the end.

let b = p5.Vector.sub(path.end, path.start);

Now, with trigonometry, I can calculate the distance from the path’s start to the normal point: $|A| * cos(theta)$.

If only I knew theta, I could easily define that normal point as follows:

let d = a.mag() * cos(theta);

b.normalize();

b.mult(d);

let normalPoint = p5.Vector.add(path.start, b);

And if the dot product has taught me anything, it’s that given two vectors, I can get theta, the angle between those vectors!

let theta = p5.Vector.angleBetween(a, b);
b.normalize();
b.mult(a.mag() * cos(theta));
let normalPoint = p5.Vector.add(path.start, b);

While the above code will work, there’s one more simplification I can make. Looking again, you’ll see the desired magnitude for vector $\vec{B}$ is:

which is the code translation of:

And if you recall:

Now, what if vector {vectorb} is a unit vector, i.e. length 1? Then:

or

And what am I doing in my code? Normalizing b!

b.normalize();

Because of this fact, I can simplify the code to:

const theta = p5.Vector.angleBetween(a, b);

b.normalize();

b.mult(a.dot(b));

let normalPoint = p5.Vector.add(path.start, b);

This process is commonly known as “scalar projection.” |A| cos(θ) is the scalar projection of A onto B.

Once I have the normal point along the path, the next step is to decide whether the vehicle should steer towards the path and how. Reynolds’s algorithm states that the vehicle should only steer towards the path if it strays beyond the path (i.e., if the distance between the normal point and the predicted future position is greater than the path radius).

let distance = p5.Vector.dist(predictLoc, normalPoint);

if (distance > path.radius) {

  this.seek(target);

}

But what is the target?

Reynolds’s algorithm involves picking a point ahead of the normal on the path (see step #3 above). But for simplicity, I could just say that the target is the normal itself. This works “good enough”:

let distance = p5.Vector.dist(predictLoc, normalPoint);
if (distance > path.radius) {

  this.seek(normalPoint);

}

However, since I know the vector that defines the path (I’m calling it “B”), I can implement Reynolds’s “point ahead on the path” without too much trouble.

let distance = p5.Vector.dist(predictLoc, normalPoint);
if (distance > path.radius) {

  b.normalize();
  b.mult(25);

  const target = p5.Vector.add(normalPoint, b);

  this.seek(target);
}

Putting it all together, here is the steering function in the Vehicle class.

Example 5.5: Simple path following

  follow(p) {

    let predict = this.velocity.copy();
    predict.normalize();
    predict.mult(25);
    let predictLoc = p5.Vector.add(loc, predict);

    let a = p.start;
    let b = p.end;
    let normalPoint = this.getNormalPoint(predictLoc, a, b);

    let dir = p5.Vector.sub(b, a);
    dir.normalize();
    dir.mult(10);
    let target = p5.Vector.add(normalPoint, dir);

    let distance = p5.Vector.dist(normalPoint, predictLoc);
    if (distance > p.radius) {
      this.seek(target);
    }
  }

Now, you may notice above that instead of using all that dot product/scalar projection code to find the normal point, I instead call a function: getNormalPoint(). In cases like this, it’s useful to break out the code that performs a specific task (finding a normal point) into a function that can be called when required. The function takes three vector arguments: the first defines a point in Cartesian space and the second and third define a line segment between two points.

  getNormalPoint(p, a, b) {

    let ap = p5.Vector.sub(p, a);

    let ab = p5.Vector.sub(b, a);

    ab.normalize();
    ab.mult(ap.dot(ab));

    let normalPoint = p5.Vector.add(a, ab);

    return normalPoint;
  }

What do I have so far? I have a Path class that defines a path as a line between two points. I have a Vehicle class that defines a vehicle that can follow the path (using a steering behavior to seek a target along the path). What is missing?

Take a deep breath. You’re almost there.

5.9 Path Following with Multiple Segments

I’ve built a decent example so far, yes, but it’s pretty darn limiting. After all, what if you want a path to be something that looks more like:

While it’s true that I could investigate algorithms for following a curved path, I’m much less likely to end up needing a cool compress on my forehead if I stick with line segments. Here again, I can employ the same technique I used with Box2D—I can draw whatever fancy curved path I want and approximate it behind the scenes with simplified geometric forms.

So, what’s the problem? If I made path following work with one line segment, how do I make it work with a series of connected line segments? Let’s take a look again at the vehicle driving along the canvas. Say it arrives at Step 3.

Step 3: Find a target point on the path.

To find the target, I need to find the normal to the line segment. But now that there is a series of line segments, there is also a series of normal points (see above)! Which one does the vehicle choose? The solution I’ll employ is to pick the normal point that is (a) closest and (b) on the path itself.

If you have a point and an infinitely long line, you’ll always have a normal. But, as in the path-following example, if you have a point and a line segment, you won’t necessarily find a normal that is on the line segment itself. So if this happens for any of the segments, I can disqualify those normals. Once I am left with normals that are on the path itself (only two in the above diagram), I simply pick the one that is closest to the vehicle’s position.

In order to write the code for this, I’ll have to expand the Path class to have an Array of points (rather than just two, a start and an end).

 class Path {

  constructor() {
    this.radius = 20;

    this.points = [];

  }

  addPoint(x, y) {
    let point = createVector(x, y);
    this.points.add(point);
  }

  display() {
    stroke(0);
    noFill();
    beginShape();
    for (let v of this.points) {
      vertex(v.x, v.y);
    }
    endShape();
  }

}

Now that the Path class is defined, it’s the vehicle’s turn to deal with multiple line segments. All it did before was find the normal for one line segment. Using a loop, it can find the normals for all the line segments.

for (int i = 0; i < p.points.length - 1; i++) {
  let a = p.points[i];
  let b = p.points[i+1];

  let normalPoint = this.getNormalPoint(predictLoc, a, b);

Then I should make sure the normal point is actually between points a and b. Since I know the path goes from left to right in this example, I can test if the x component of normalPoint is outside the x components of a and b.

   if (normalPoint.x < a.x || normalPoint.x > b.x) {

      normalPoint = b.copy();

   }

As a little trick, I’ll say that if it’s not within the line segment, let’s just pretend the end point of that line segment is the normal. This will ensure that the vehicle always stays on the path, even if it strays out of the bounds of the line segments themselves.

Finally, I’ll need to find the normal point that is closest to the vehicle. To accomplish this, I can start with a very high “world record” distance and iterate through each normal point to see if it beats the record (i.e. is less than). Each time a normal point beats the record, the world record is updated and the winning point is stored in a variable named target. At the end of the loop, that variable will store the closest normal point.

Example 5.6: Path following

let target = null;

let worldRecord = Infinity;

for (int i = 0; i < p.points.length-1; i++) {
  let a = p.points[i];
  let b = p.points[i+1];
  let normalPoint = this.getNormalPoint(predictLoc, a, b);

  if (normalPoint.x < a.x || normalPoint.x > b.x) {
    normalPoint = b.copy();
  }

  let distance = p5.Vector.dist(predictLoc, normalPoint);

  if (distance < worldRecord) {
    worldRecord = distance;
    target = normalPoint.copy();
  }

}

if (normalPoint.x < ____(____,____) || normalPoint.x > ____(____,____)) {
  normalPoint = b.copy();
}

5.10 Complex Systems

Remember your purpose? To breathe life into the things that move around p5 canvases? By learning to write the code for an autonomous agent and building a series of examples of individual behaviors, hopefully your soul feel a little more full. But this is no place to stop and rest on your laurels. I’m just getting started. After all, there is a deeper purpose at work here. Yes, a vehicle is a simulated being that makes decisions about how to seek and flow and follow. But what is a life led alone, without the love and support of others? The purpose here is not only to build individual behaviors for these vehicles, but to put these vehicles into systems of many vehicles and allow those vehicles to interact with each other.

Let’s think about a tiny, crawling ant—one single ant. An ant is an autonomous agent; it can perceive its environment (using antennae to gather information about the direction and strength of chemical signals) and make decisions about how to move based on those signals. But can a single ant acting alone build a nest, gather food, defend its queen? An ant is a simple unit and can only perceive its immediate environment. A colony of ants, however, is a sophisticated complex system, a “superorganism” in which the components work together to accomplish difficult and complicated goals.

I want to take what I’ve developed during the process of building autonomous agents in p5.js into simulations that involve many agents operating in parallel—agents that have an ability to perceive not only their physical environment but also the actions of their fellow agents, and then act accordingly. I want to create complex systems with p5.js.

What is a complex system? A complex system is typically defined as a system that is “more than the sum of its parts.” While the individual elements of the system may be incredibly simple and easily understood, the behavior of the system as a whole can be highly complex, intelligent, and difficult to predict. Here are three key principles of complex systems.

• Simple units with short-range relationships. This is what I’ve been building all along: vehicles that have a limited perception of their environment.
• Simple units operate in parallel. This is what is needed to simulate in code. For every cycle through p5.js’s draw() loop, each unit will decide how to move (to create the appearance of them all working in parallel).
• System as a whole exhibits emergent phenomena. Out of the interactions between these simple units emerges complex behavior, patterns, and intelligence. Here I’m talking about the result I am hoping for in the sketches. Yes, this happens in nature (ant colonies, termites, migration patterns, earthquakes, snowflakes, etc.), but can I achieve the same result in a p5.js sketch?

Following are three additional features of complex systems that will help frame the discussion, as well as provide guidelines for features to include in a software simulation. It’s important to acknowledge that this is a fuzzy set of characteristics and not all complex systems have all of them.

• Non-linearity. This aspect of complex systems is often casually referred to as “the butterfly effect,” coined by mathematician and meteorologist Edward Norton Lorenz, a pioneer in the study of chaos theory. In 1961, Lorenz was running a computer weather simulation for the second time and, perhaps to save a little time, typed in a starting value of 0.506 instead of 0.506127. The end result was completely different from the first result of the simulation. In other words, the theory is that a single butterfly flapping its wings on the other side of the world could cause a massive weather shift and ruin your weekend at the beach. It‘s called “non-linear” because there isn’t a linear relationship between a change in initial conditions and a change in outcome. A small change in initial conditions can have a massive effect on the outcome. Non-linear systems are a superset of chaotic systems. In the next chapter, you’ll see how even in a system of many zeros and ones, if you change just one bit, the result will be completely different.

• Competition and cooperation. One of the things that often makes a complex system tick is the presence of both competition and cooperation between the elements. In the upcoming flocking system, there will be three rules—alignment, cohesion, and separation. Alignment and cohesion will ask the elements to “cooperate”—i.e. work together to stay together and move together. Separation, however, will ask the elements to “compete” for space. When the time comes, try taking out the cooperation or the competition and you’ll see how you are left without complexity. Competition and cooperation are found in living complex systems, but not in non-living complex systems like the weather.

• Feedback. Complex systems often include a feedback loop where the output of the system is fed back into the system to influence its behavior in a positive or negative direction. Let’s say you drive to work each day because the price of gas is low. In fact, everyone drives to work. The price of gas goes up as demand begins to exceed supply. You, and everyone else, decide to take the train to work because driving is too expensive. And the price of gas declines as the demand declines. The price of gas is both the input of the system (determining whether you choose to drive or ride the train) and the output (the demand that results from your choice). I should note that economic models (like supply/demand, the stock market) are one example of a human complex system. Others include fads and trends, elections, crowds, and traffic flow.

Complexity will serve as a theme for the remaining content in this book. In this chapter, I’ll begin by adding one more feature to the Vehicle class: an ability to look at neighboring vehicles.

5.11 Group Behaviors (or: Let’s not run into each other)

A group is certainly not a new concept. You’ve seen this before—in Chapter 4, where I developed a framework for managing collections of particles in a ParticleSystem class. There, a list of particles was stored in an Array. I’ll do the same thing here: store a bunch of Vehicle objects in an Array.

let vehicles;

function setup() {

  vehicles = [];
  for (let i = 0; i < 100; i++) {
    vehicles.push(new Vehicle(random(width), random(height)));

  }
}

Now when it comes time to deal with all the vehicles in draw(), I can loop through all of them and call the necessary functions.

function draw(){
  for (let v of vehicles) {
    v.update();
    v.display();
  }
}

OK, so maybe you want to add a behavior, a force to be applied to all the vehicles. This could be seeking the mouse.

    v.seek(mouseX, mouseY);

But that’s an individual behavior. I’ve already spent thirty-odd pages worrying about individual behaviors. You’re here because you want to apply a group behavior. I’ll begin with separation, a behavior that commands, “Avoid colliding with your neighbors!”

    v.separate();

Is that right? It sounds good, but it’s not. What’s missing? In the case of seek, I said, “Seek mouseX and mouseY.” In the case of separate, I’m saying “separate from everyone else.” Who is everyone else? It’s the list of all the other vehicles.

    v.separate(vehicles);

This is the big leap beyond what you saw before with particle systems. Instead of having each element (particle or vehicle) operate on its own, I’m now saying, “Hey you, the vehicle! When it comes time for you to operate, you need to operate with an awareness of everyone else. So I’m going to go ahead and pass you the Array of everyone else.”

Following is an example of setup() and draw() that deals with a group behavior.

let vehicles;

function setup() {
  createCanvas(320, 240);
  vehicles = [];
  for (let i = 0; i < 100; i++) {
    vehicles.push(new Vehicle(random(width), random(height)));
  }
}

function draw() {
  background(255);

  for (let v of vehicles) {

    v.separate(vehicles);

    v.update();
    v.display();
  }
}

Of course, this is just the beginning. The real work happens inside the separate() function itself. Let’s figure out how to define separation. Reynolds states: “Steer to avoid crowding.” In other words, if a given vehicle is too close to you, steer away from that vehicle. Sound familiar? Remember the seek behavior where a vehicle steers towards a target? Reverse that force and you have the flee behavior.

But what if more than one vehicle is too close? In this case, I’ll define separation as the average of all the vectors pointing away from any close vehicles.

Let’s begin to write the code. Remember, I’m writing a function called separate() that receives an Array of Vehicle objects as an argument.

separate (vehicles) {

}

Inside this function, I will loop through all of the vehicles and see if any are too close.

  let desiredseparation = 20;

  for (let other of vehicles) {

    let d = p5.Vector.dist(this.position, other.position);

    if ((d > 0) && (d < desiredseparation)) {

    }
  }

Notice how in the above code, we are not only checking if the distance is less than a desired separation (i.e. too close!), but also if the distance is greater than zero. This is a little trick that makes sure I don’t ask a vehicle to separate from itself. Remember, all the vehicles are in the array, so if you aren’t careful you’ll be comparing each vehicle to itself!

If two vehicles are too close, I then need to create a vector that points away from the offending vehicle.

    if ((d > 0) && (d < desiredseparation)) {

      let diff = p5.Vector.sub(this.position, other.position);
      diff.normalize();

    }

This is not enough. I have that vector now, but I need to make sure to calculate the average of all vectors pointing away from close vehicles. How do you compute average? Add up all the vectors and divide by the total.

  let sum = createVector();

  let count = 0;

  for (let other of vehicles) {

    const d = p5.Vector.dist(this.position, other.position);
    if ((d > 0) && (d < desiredseparation)) {

      let diff = p5.Vector.sub(this.position, other.position);

      diff.normalize();

      sum.add(diff);

      count++;
    }
  }

  if (count > 0) {

    sum.div(count);
  }

Once I have the average vector (stored in the vector object “sum”), that vector can be scaled to maximum speed and become the desired velocity—the vehicle desires to move in that direction at maximum speed! (In fact, I really don't have to divide by count anymore since the magnitude is set manually.) And once I have the desired velocity, it’s the same old Reynolds story: steering equals desired minus velocity.

  if (count > 0) {

    sum.setMag(this.maxspeed);

    const steer = p5.Vector.sub(sum, vel);

    steer.limit(this.maxforce);

    this.applyForce(steer);

  }

Let’s see the function in its entirety. There are two additional improvements, noted in the code comments.

Example 5.7: Group behavior: Separation

  separate (vehicles) {

    let desiredseparation = this.r * 2;

    let sum = createVector();
    let count = 0;
    for (let other of vehicles) {
      const d = p5.Vector.dist(this.position, other.position);
      if ((d > 0) && (d < desiredseparation)) {
        let diff = p5.Vector.sub(this.position, other.position);
        diff.normalize();

        diff.div(d);

        sum.add(diff);
        count++;

      }
    }
    if (count > 0) {
      sum.setMag(this.maxspeed);
      let steer = p5.Vector.sub(sum, vel);
      steer.limit(this.maxforce);
      this.applyForce(steer);
    }

  }

Exercise 5.13

Add the separation force to path following to create a simulation of Reynolds’s “Crowd Path Following.”

5.12 Combinations

The previous two exercises hint at what is perhaps the most important aspect of this chapter. After all, what is a p5.js sketch with one steering force compared to many? How could I even begin to simulate emergence in a sketch with only one rule? The most exciting and intriguing behaviors will come from mixing and matching multiple steering forces, and I’ll need a mechanism for doing so.

You may be thinking, “This is nothing new. We do this all the time.” You would be right. In fact, this technique appeared as early as Chapter 2.

  const wind = createVector(0.001, 0);
  const gravity = createVector(0, 0.1);
  mover.applyForce(wind);
  mover.applyForce(gravity);

Here there is a mover that responds to two forces. This all works nicely because of the way the Mover class was designed to accumulate the force vectors into its acceleration vector. In this chapter, however, the forces stem from internal desires of the movers (now called vehicles). And those desires can be weighted. Let’s consider a sketch where all vehicles have two desires:

• Seek the mouse position.
• Separate from any vehicles that are too close.

I might begin by adding a function to the Vehicle class that manages all of the behaviors. I’ll call it applyBehaviors().

applyBehaviors(vehicles) {
  this.separate(vehicles);
  this.seek(createVector(mouseX, mouseY));
}

Here a single function takes care of calling the other functions that apply the forces—separate() and seek(). I could start mucking around with those functions and adjust the strength of the forces they are calculating. But it might be easier to ask those functions to return the forces so that I can adjust their strength before applying them to the vehicle’s acceleration.

  applyBehaviors(vehicles) {
    let separate = this.separate(vehicles);
    let seek = this.seek(createVector(mouseX, mouseY));

    this.applyForce(separate);
    this.applyForce(seek);

  }

Let’s look at how the seek function changed.

  seek(target) {
    let desired = p5.Vector.sub(target, loc);
    desired.normalize();
    desired.mult(this.maxspeed);
    const steer = p5.Vector.sub(desired, vel);
    steer.limit(this.maxforce);

    this.applyForce(steer);

    return steer;

  }

This is a subtle change, but incredibly important: it allows the strength of these forces to be weighted all in one place.

Example 5.8: Combining steering behaviors: Seek and separate

applyBehaviors(vehicles) {
  let separate = this.separate(vehicles);
  let seek = this.seek(createVector(mouseX, mouseY));

  separate.mult(1.5);
  seek.mult(0.5);

  this.applyForce(separate);
  this.applyForce(seek);
}

5.13 Flocking

Flocking is a group animal behavior that is characteristic of many living creatures, such as birds, fish, and insects. In 1986, Craig Reynolds created a computer simulation of flocking behavior and documented the algorithm in his paper, “Flocks, Herds, and Schools: A Distributed Behavioral Model.” Recreating this simulation in p5.js will bring together all the concepts in this chapter.

1. I will use the steering force formula (steer = desired - velocity) to implement the rules of flocking.
2. These steering forces are be group behaviors and will require each vehicle to look at all the other vehicles.
3. I will combine and weight multiple forces.
4. The result will be a complex system—intelligent group behavior will emerge from the simple rules of flocking without the presence of a centralized system or leader.

The good news is, I’ve already done items 1 through 3 in this chapter, so this section can be just about putting it all together and seeing the result.

Before I begin, I should mention that I’m going to change the name of the Vehicle class (yet again). Reynolds uses the term “boid” (a made-up word that refers to a bird-like object) to describe the elements of a flocking system and I will do the same.

Here’s an overview of the three rules of flocking.

1. Separation (also known as “avoidance”): Steer to avoid colliding with your neighbors.
2. Alignment (also known as “copy”): Steer in the same direction as your neighbors.
3. Cohesion (also known as “center”): Steer towards the center of your neighbors (stay with the group).

Just as with the separate and seek example, I’ll want the Boid objects to have a single function that manages all the above behaviors. I’ll call this function flock().

  flock(boids) {

    let sep = this.separate(boids);
    let ali = this.align(boids);
    let coh = this.cohesion(boids);

    sep.mult(1.5);
    ali.mult(1.0);
    coh.mult(1.0);

    this.applyForce(sep);
    this.applyForce(ali);
    this.applyForce(coh);

  }

Now, it’s just a matter of implementing the three rules. I did separation before; it’s identical to the previous example. Let’s take a look at alignment, or steering in the same direction as your neighbors. As with all of the steering behaviors, I’ve got to boil down this concept into a desire: the boid’s desired velocity is the average velocity of its neighbors.

So the algorithm is to calculate the average velocity of all the other boids and set that to desired.

  align (boids) {

    let sum = createVector(0, 0);
    for (let other of boids) {
      sum.add(other.velocity);
    }
    sum.div(boids.length);

    sum.setMag(this.maxspeed);

    let steer = p5.Vector.sub(sum,velocity);
    steer.limit(this.maxforce);
    return steer;

  }

The above is pretty good, but it’s missing one rather crucial detail. One of the key principles behind complex systems like flocking is that the elements (in this case, boids) have short-range relationships. Thinking about ants again, it’s pretty easy to imagine an ant being able to sense its immediate environment, but less so an ant having an awareness of what another ant is doing hundreds of feet away. The fact that the ants can perform such complex collective behavior from only these neighboring relationships is what makes them so exciting in the first place.

In the alignment function, I’m taking the average velocity of all the boids, whereas I should really only be looking at the boids within a certain distance. That distance threshold can be variable, of course. You could design boids that can see only twenty pixels away or boids that can see a hundred pixels away.

The solution is much like what I did with separation (calculating a force for others within a certain distance), I’ll want to apply the same logic to alignment (and cohesion).

  align (boids) {

    let neighbordist = 50;

    let sum = createVector(0, 0);
    let count = 0;
    for (let other of boids) {
      let d = p5.Vector.dist(this.position, other.position);
      if ((d > 0) && (d < neighbordist)) {
        sum.add(other.velocity);

        count++;

      }
    }
    if (count > 0) {
      sum.setMag(this.maxspeed);
      let steer = p5.Vector.sub(sum, this.velocity);
      steer.limit(this.maxforce);
      return steer;

    } else {
      return createVector(0, 0);
    }

  }

Exercise 5.15

Can you write the above code so that boids only see other boids that are actually within their “peripheral” vision (as if they had eyes)?

Finally, I am ready for cohesion. Here the code is virtually identical to that for alignment—only instead of calculating the average velocity of the boid’s neighbors, I want to calculate the average position of the boid’s neighbors (and use that as a target to seek).

  cohesion(boids) {
    let neighbordist = 50;
    let sum = createVector(0, 0);
    let count = 0;
    for (let other of boids) {
      let d = p5.Vector.dist(this.position, other.position);
      if ((d > 0) && (d < neighbordist)) {

        sum.add(other.position);
        count++;

      }
    }
    if (count > 0) {
      sum.div(count);

      return this.seek(sum);

    } else {
      return createVector(0, 0);
    }
  }

It’s also worth taking the time to write a class called Flock, which will be virtually identical to the ParticleSystem class in Chapter 4 with only one tiny change: When I call run() on each Boid object (as I did to each Particle object), I’ll pass in a reference to the entire array of boids.

Flock {

  constructor() {
    this.boids = [];
  }

  run() {
    for (let boid of this.boids) {

      boid.run(this.boids);

    }
  }

  addBoid(boid) {
    this.boids.push(boid);
  }
}

And setup()> and draw() will look like:

Example 5.9: Flocking

let flock;

function setup() {
  createCanvas(300, 200);
  flock = new Flock();
  for (let i = 0; i < 100; i++) {
    let boid = new Boid(width / 2, height / 2);

    flock.addBoid(boid);

  }
}

function draw() {
  background(255);
  flock.run();
}

Exercise 5.17

In his book The Computational Beauty of Nature (MIT Press, 2000), Gary Flake describes a fourth rule for flocking: “View: move laterally away from any boid that blocks the view.” Have your boids follow this rule.

5.14 Algorithmic Efficiency (or: Why does my sketch run so slowly?)

I would like to hide the dark truth behind what I’ve just done, because I would like you to be happy and live a fulfilling and meaningful life. But I also would like to be able to sleep at night without worrying about you so much. So it is with a heavy heart that I must bring up this topic. yes, group behaviors are wonderful. But they can be slow, and the more elements in the group, the slower they can be. Usually, when I talk about p5.js sketches running slowly, it’s because drawing to the canvas can be slow—the more you draw, the slower your sketch runs. This is actually a case, however, where the slowness derives from the algorithm itself. Let’s discuss.

Computer scientists classify algorithms with something called “Big O notation,” which describes the efficiency of an algorithm: how many computational cycles does e it require to complete? Let’s consider a simple analog search problem. You have a basket containing one hundred chocolate treats, only one of which is pure dark chocolate. That’s the one you want to eat. To find it, you pick the chocolates out of the basket one by one. Sure, you might be lucky and find it on the first try, but in the worst-case scenario you have to check all one hundred before you find the dark chocolate. To find one thing in one hundred, you have to check one hundred things (or to find one thing in N things, you have to check N times.) Your Big O Notation is N. This, incidentally, is the Big O Notation that describes the simple particle system. If you have N particles, you have to run and display those particles N times.

Now, let’s think about a group behavior (such as flocking). For every Boid object, you have to check every other Boid object (for its velocity and position). Let’s say you have one hundred boids. For boid #1, you need to check one hundred boids; for boid #2, you need to check one hundred boids, and so on and so forth. For one hundred boids, you need to perform one hundred times one hundred checks, or ten thousand. No problem: computers are fast and can do things ten thousand times pretty easily. Let’s try one thousand.

1,000 x 1,000 = 1,000,000 cycles.

OK, this is rather slow, but still somewhat manageable. Let’s try 10,000 elements:

10,000 x 10,000 elements = 100,000,000 cycles.

Now, things are really getting slow. Really, really, really slow.

Notice something? As the number of elements increases by a factor of 10, the number of required cycles increases by a factor of 100. Or as the number of elements increases by a factor of N, the cycles increase by a factor of N times N. This is known as Big O Notation N-Squared.

I know what you are thinking. You are thinking: “No problem; with flocking, I only need to consider the boids that are close to other boids. So even if I have 1,000 boids, I can just look at, say, the 5 closest boids and then I only have 5,000 cycles.” You pause for a moment, and then start thinking: “So for each boid I just need to check all the boids and find the five closest ones and I’m good!” See the catch-22? Even if you only want to look at the close ones, the only way to know what the close ones are would be to check all of them.

Or is there another way?

Let’s take a number that you might actually want to use, but would still run too slowly: 2,000 (4,000,000 cycles required).

What if you could divide the screen into a grid? You would take all 2,000 boids and assign each boid to a cell within that grid. You would then be able to look at each boid and compare it to its neighbors within that cell at any given moment. Imagine a 10 x 10 grid. In a system of 2,000 elements, on average, approximately 20 elements would be found in each cell (20 x 10 x 10 = 2,000). Each cell would then require 20 x 20 = 400 cycles. With 100 cells, we’d have 100 x 400 = 40,000 cycles, a massive savings over 4,000,000.

This technique is known as “bin-lattice spatial subdivision” and is outlined in more detail in (surprise, surprise) Reynolds’s 2000 paper, “Interaction with Groups of Autonomous Characters”. How do you implement such an algorithm in p5.js? The sollution I’ll describe below uses multiple arrays. One array to track of all the boids, just like in the flocking example.

let boids = [];

In addition to that array, I’ll store an additional reference to each Boid object in a two-dimensional array (repurposing the make2DArray function from Example X.X: Flow Field Following). For each cell in the grid, an additional array tracks the objects in that particular cell.

let grid = make2Darray(this.cols, this.rows);

In the draw(), each Boid object then registers itself in the appropriate cell according to its position.

let column = floor(boid.x) / this.resolution;
let row    = floor(boid.y) / this.resolution;
grid[column][row] = boid;

Then when it comes time to have the boids check for neighbors, they can look at only those in their particular cell (in truth, I also need to check neighboring cells to deal with border cases).

let column = floor(boid.x) / this.resolution;
let row    = floor(boid.y) / this.resolution;

boid.flock(grid[column][row]);

I’re only covering the basics here; for the full code, check the book’s website.

Now, there are certainly flaws with this system. What if all the boids congregate in the corner and live in the same cell? Then don’t we have to check all 2,000 against all 2,000?

The good news is that this need for optimization is a common one and there are a wide variety of similar techniques out there. For us, it’s likely that a basic approach will be good enough (in most cases, you won’t need one at all.) I cover another, more sophisticated approach, in my [tutorial series about building a QuadTree](https://thecodingtrain.com/CodingChallenges/098.1-quadtree.html) in p5.js. A QuadTree employs the exact same methodology as bin-lattice spatial subdivison, only the cells themselves are not sized equally but rather according to the distribution density of the elements themselves. TODO: QUAD TREE DIAGRAM https://github.com/nature-of-code/noc-book-2/issues/101 The accompanying [QuadTree p5.js library](https://github.com/CodingTrain/QuadTree) also includes a flocking example. .

5.15 A Few Last Notes: Optimization Tricks

This is something of a momentous occasion. The end of Chapter 5 marks the end of the story of motion (in the context of this book, that is). I started with the concept of a vector, moved on to forces, designed systems of many elements, examined physics libraries, built entities with hopes and dreams and fears, and simulated emergence. The story doesn’t end here, but it does take a bit of a turn. The next two chapters won’t focus on moving bodies, but rather on systems of rules. Before you get there, I have a few quick items I’d like to mention that are important when working with the examples in Chapters 1 through 5. They also relate to optimizing your code, which fits in with the previous section.

1) Magnitude squared (or sometimes distance squared)

What is magnitude squared and when should you use it? Let’s revisit how the magnitude of a vector is calculated.

function mag() {
  return sqrt(x * x + y * y);
}

Magnitude requires the square root operation. And it should. After all, if you want the magnitude of a vector, then you’ve got to look up the Pythagorean theorem and compute it (we did this in Chapter 1). However, if you could somehow skip using the square root, your code would run faster. Let’s consider a situation where you just want to know the relative magnitude of a vector. For example, is the magnitude greater than ten? (Assume a vector v.)

if (v.mag() > 10) {

}

Well, this is equivalent to saying:

if (v.magSq() > 100) {

}

And how is magnitude squared calculated?

function magSq() {
  return x * x + y * y;
}

Same as magnitude, but without the square root. In the case of a single vector, this will never make a significant difference on a p5.js sketch. However, if you are computing the magnitude of thousands of vectors each time through draw(), using magSq() instead of mag() could help your code run a wee bit faster.

2) Sine and cosine lookup tables

There’s a pattern here. What kinds of functions are slow to compute? Square root. Sine. Cosine. Tangent. Again, if you just need a sine or cosine value here or there in your code, you are never going to run into a problem. But what if you had something like this?

function draw() {
  for (let i = 0; i < 10000; i++) {
    print(sin(PI));
  }
}

Sure, this is a totally ridiculous code snippet that you would never write. But it illustrates a certain point. If you are calculating the sine of pi ten thousand times, why not just calculate it once, save that value, and refer to it whenever necessary? This is the principle behind sine and cosine lookup tables. Instead of calling the sine and cosine functions in your code whenever you need them, you can build an array that stores the results of sine and cosine at angles between 0 and TWO_PI and just look up the values when you need them. For example, here are two arrays that store the sine and cosine values for every angle, 0 to 359 degrees. I’ll use angleMode(DEGREES) here to simplify the discussion but the same technique can be applied with radians.

angleMode(DEGREES);
let sinvalues = [];
let cosvalues = [];
for (let i = 0; i < 360; i++) {
  sinvalues[i] = sin(i);
  cosvalues[i] = cos(i);
}

Now, what if you need the value of sine of pi (or 180 degrees)?

let angle = 180;
let answer = sinvalues[angle];

A full example using this technique can be found TODO: https://github.com/nature-of-code/noc-book-2/issues/102.

3) Making gajillions of unnecessary p5.Vector objects

I have to admit, I am perhaps the biggest culprit of this last note. In fact, in the interest of writing clear and understandable examples, I often choose to make extra p5.Vector objects when I absolutely do not need to. For the most part, this is not a problem at all. But sometimes, it can be. Let’s take a look at an example.

function draw() {
  for (let v of vehicles) {
   let mouse = createVector(mouseX, mouseY);
   v.seek(mouse);
  }
}

Let’s say the of vehicles has one thousand vehicles in it. We just made one thousand new p5.Vector objects every single time through draw(). Now, on any ol’ laptop or desktop computer you’ve purchased in recent times, your sketch will likely not register a complaint, run slowly, or have any problems. After all, you’ve got tons of RAM, and JavaScript will be able to handle making a thousand or so temporary objects and dispose of them without much of a problem.

If your numbers grow larger (and they easily could) you will almost certainly run into a problem. In cases like this you want to look for ways to reduce the number of p5.Vector objects you make. An obvious fix for the above code is:

function draw() {
  let mouse = createVector(mouseX, mouseY);
  for (let v of vehicles) {
   v.seek(mouse);
  }
}

Now you’ve made just one vector instead of one thousand. Even better, you could turn the vector into a global variable and just assign the x and y value:

let mouse;

function setup() {
  mouse = createVector();
}

function draw() {
  mouse.x = mouseX;
  mouse.y = mouseY;
  for (let v of vehicles) {
   v.seek(mouse);
  }
}

Now you never make a new p5.Vector object; you use just one over the length of your sketch!

Throughout the book’s examples, you can find lots of opportunities to reduce the number of temporary objects. Let’s look at one more. Here is a snippet from the seek() function.

    let desired = p5.Vector.sub(target, this.position);
    desired.normalize();
    desired.mult(this.maxspeed);

    let steer = p5.Vector.sub(desired,this.velocity);

    steer.limit(this.maxforce);
    return steer;

See how I’ve made two vector objects? First, I calculate the desired vector, then the steering force. Notice how you could rewrite this to create only one vector!

    let desired = p5.Vector.sub(target, this.position);
    desired.normalize();
    desired.mult(this.maxspeed);

    desired.sub(this.velocity);
    desired.limit(this.maxforce);
    return desired;

I don’t actually need a second vector called steer. I could just re-use the desired vector object and turn it into the steering force by subtracting velocity. I didn’t do this in my example because it is more confusing to read. But in some cases, it may improve efficiency.