In this post I’ll explain and demonstrate an algorithm that simulates a group of entities grouping together, illustrating something called “flocking”. I think it’s quite neat because the flock exhibits some complex collective intelligence when just a few simple governing rules are applied to each entity.

The original flocking algorithm was developed by Craig Reynolds in 1986, and has some super cool real world applications:

• Computer animation. Batman Returns (1992) is widely quoted as having been nominated for an Oscar for its bat swarms which were procedurally generated using algorithms similar to these.
• Social network simulation and modeling opinion flow. After choosing humans as the entities in the flock, the overall direction of the flock can be estimated using the rules that apply to the simple flock model, and people’s future opinions can be predicted. See Gamasutra’s stupendous article on the subject.
• Aerospace engineering. By sending UAVs on missions in flocks they are able to more effectively complete their missions and react to enemy events. See one paper and another on the subject.
• Distributed systems analysis, search, and optimization. By modeling things like spacial data, network traffic, or solutions to an optimization problem as entities, the direction of the flock can be used to find clusters, where to push traffic, or optimal solutions.

Here’s the full algorithm in action:

You can also turn on a legend and a magnified view of one boid: Decorate

How it Works

Each entity on the map, which we’ll now refer to as a “boid”, moves around while being governed by a few simple rules. Each boid starts out at the center of the map with a random velocity, and for each frame of the simulation, a new velocity is calculated using the flocking algorithm. For each boid, the algorithm uses the boid’s current velocity, its neighbours' velocities, and its position relative to its neighbours to calculate this new velocity. There are three components to it: the alignment, the cohesion, and the separation, which when used in combination display the full blown flocking behaviour.

About this page

At any time you can click on any of the demos to stop or start the boid’s movement. The lower ones also have buttons allowing you to control the speed at which the boids move. When the movement is stopped you can hover your mouse over a boid to inspect the components of its velocity, as generated by the flocking algorithm. The boids also have an elephantine weakness: they are afraid of mice. Feel free to perturb the flock using your mouse while the boids are moving, and watch them try and regroup.

All the demos are running the same algorithm, just with random start positions and random start velocities. The code running the demos as well as the example code on the page is done in Coffeescript. If you haven’t seen it before, it shouldn’t be too hard to pick up, but visit that page if you want a quick primer on the syntax. Also, the example code on this page is the distilled version of the running code, algorithmically complete but missing a lot of the boring nuances arising from actual implementation, such as a lot of the code to render the boids, wrap them around the edges of the map, and display the indicators. The code running the actual demos can be found here, and isn’t really all that interesting.

The code & components

Heres the essence of the Coffeescript class modeling the boid. Each boid has a location and a velocity, which are represented as Vector objects (source). Each frame calls the step method on each boid, which calculates an acceleration based on the 3 components. This acceleration is added to the velocity, which is then limited to a maxmium magnitude so the boid can’t go too fast. The new velocity is added to the location to translate the boid on the map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# Ported almost directly from http://processingjs.org/learning/topic/flocking
# thanks a whole lot to Craig Reynolds and Daniel Shiffman

class Boid
  location: false
  velocity: false

  constructor: (loc, processing) ->
    @velocity = new Vector(Math.random()*2-1,Math.random()*2-1)
    @location = loc.copy()
    @p = processing

  # Called every frame. Calculates the acceleration using the flock method,
  # and moves the boid based on it.
  step: (neighbours) ->
    acceleration = this.flock(neighbours)
    # Limit the maximum speed at which a boid can go
    @velocity.add(acceleration).limit(MAX_SPEED)
    @location.add(@velocity)
    this._wrapIfNeeded()

  # Implements the flocking algorthim by collecting the three components
  # and returning a weighted sum.
  flock: (neighbours) ->
    separation = this.separate(neighbours).multiply(SEPARATION_WEIGHT)
    alignment = this.align(neighbours).multiply(ALIGNMENT_WEIGHT)
    cohesion = this.cohere(neighbours).multiply(COHESION_WEIGHT)
    return separation.add(alignment).add(cohesion)

Next up is the three components which generate the acceleration.

Cohesion

A flock is defined as a group of boids all staying close to each together, and the cohesion component of the algorithm is mainly responsible for the togetherness aspect of this. Every frame, each boid looks at the position of each other boid to see if it is within a specified NEIGHBOUR_RADIUS, that is, it checks to see which other boids are close enough to be considered flockmates. The positions of the qualifying neighbours are averaged and the boid steers to towards that position. This way, each boid is trying to steer towards the center of the flock, resulting in them all staying close together.

The example on the right shows how the cohesion component of the algorithm works. The pink boid’s NEIGHBOUR_RADIUS is drawn as the green circle around it, and boids inside it (neighbours) are drawn as green instead of blue when they are inside it. Their locations (the dark purple vectors) are summed up to find the center of the flock. The light pink vector points to this center point which the pink boid is trying to reach. The blue vector shows the path by which the boid steers towards this center point. This steering vector looks a tad odd, but have a look at the code to see why it is necessary.

Also note that if a boid has only one neighbour, the center of its neighbouring flock is exactly its neighbour’s location. In this case the dark purple vector has a zero magnitude (it starts and ends at the same point), and the light purple vector points to the position of that neighbour.

Code

The cohesion component is calculated by averaging the location of all the neighbours within the NEIGHBOUR_RADIUS. Note that the returned value is the result of calling steer_to on the average position. The steer_to method implements some basic easing towards a target so the boids turn towards fellow flock members at reasonable speeds instead of instantly switching direction. You can also see this as an implementation of friction and reaction speeds.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Boid

  # Called to get the cohesion component of the acceleration
  cohere: (neighbours) ->
    sum = new Vector
    count = 0
    for boid in neighbours
      d = @location.distance(boid.location)
      if d > 0 and d < NEIGHBOUR_RADIUS
        sum.add(boid.location)
        count++

    if count > 0
      return this.steer_to sum.divide(count)
    else
      return sum # Empty vector contributes nothing

  steer_to: (target) ->
    # A vector pointing from the location to the target
    desired = Vector.subtract(target, @location)
    # Distance from the target is the magnitude of the vector
    d = desired.magnitude()

    # If the distance is greater than 0, calc steering
    # (otherwise return zero vector)
    if d > 0
      desired.normalize()

      # Two options for desired vector magnitude
      # (1 -- based on distance, 2 -- maxspeed)
      if d < 100.0
        # This damping is arbitrary
        desired.multiply(MAX_SPEED*(d/100.0))
      else
        desired.multiply(MAX_SPEED)

      # Steering = Desired minus Velocity
      steer = desired.subtract(@velocity)
      # Limit to maximum steering force
      steer.limit(MAX_FORCE)
    else
      steer = new Vector(0,0)

    return steer

Alignment

Each boid in a flock tries to head in the same direction as the rest of the flock, which is the responsibility of the alignment portion of the algorithm. Each frame, each boid looks at the heading in which it is travelling in comparison to the headings of all its neighbours, and realigns itself to match their heading. The velocity vectors of each boid within the NEIGHBOUR_RADIUS are averaged and the resulting vector points in the average direction of the flock, which the boid then tried to head in.

In the example on the left, the neighbouring boids are highlighted in green, and their velocities are shown in light green. Each of those velocities is averaged to find the average heading the pink boid should head in. This new heading is shown as the bright green vector coming from the pink boid. You can also see the pink boid’s velocity as the black vector, and notice how if the angle between the current velocity in black and the average alignment of the neighbours in bright green is large, it gradually decreases as the boid adopts the new heading.

Code

The alignment is calculated by averaging the velocities of the neighbours within the NEIGHBOUR_RADIUS. The return value is also limited to exert no more than the maximum force. This is so that the alignment component can’t overpower the others, which can happen if there is a big difference between the current boid and its neighbours' velocities.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Boid
  # Alignment component for the frame's acceleration
  align: (neighbours) ->
    mean = new Vector
    count = 0
    for boid in neighbours
      d = @location.distance(boid.location)
      if d > 0 and d < NEIGHBOUR_RADIUS
        mean.add(boid.velocity)
        count++

    mean.divide(count) if count > 0
    mean.limit(MAX_FORCE)
    return mean

Separation

While in a flock, each boid tries not to run into each other one in the flock. They try to remain separate by keeping a specified amount of space in between themselves. Each boid checks all the other boids on the map to see if the distance between them is too small, and if so, adds an inversely proportional amount to its velocity in the opposite direction.

In the example on the right you can see the red circle which indicates the desired separation around the pink boid. If a boid enters this radius, the pink boid tries to navigate away. Boids which violate the pink boid’s desired separation are also highlighted in red. The red arrow pointing out of the pink boid is the separation component of the algorithm, pointing away from any boids that are too close. Note that right at the start, all the boids are too close to the pink one, so they are all highlighted in red.

Code

The code loops through the neighbours as the other methods do while checking each neighbour to see if the distance to it is less than the DESIRED_SEPARATION. If it is, the vector going between the two boids is found such that it is pointing away from the uncomfortably close boid. This vector is normalized, and then scaled up proportionally to how close the boid is. If the foreign boid is closer, the vector is larger, and the current boid will move away faster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Boid

  # Separation component for the frame's acceleration
  separate: (neighbours) ->
    mean = new Vector
    count = 0
    for boid in neighbours
      d = @location.distance(boid.location)
      if d > 0 and d < DESIRED_SEPARATION
        # Normalized, weighted by distance vector pointing away from the neighbour
        mean.add Vector.subtract(@location,boid.location).normalize().divide(d)
        count++

    mean.divide(count) if count > 0
    mean

Bringing it all together

Once the component accelerations have been calculated, the weighted sum can be taken, and the final acceleration can be applied to the boid’s velocity, as is shown at the beginning of the post. A small script like the one below is needed to manage each boid and step each one in sequence. To render this whole thing, I used Processing.js, which was an absolute joy. The code (which has nothing to do with the flocking algorithm) to render the boid is below. For more on the Processing part of this page, I encourage you to check out the source for this page on Github.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Boid
  r: 2 # "radius" of the triangle
  render: () ->
    # Draw a triangle rotated in the direction of velocity
    theta = @velocity.heading() + @p.radians(90)
    @p.fill(70)
    @p.stroke(255,255,0)
    @p.pushMatrix()
    @p.translate(@location.x,@location.y)
    @p.rotate(theta)
    @p.beginShape(@p.TRIANGLES)
    @p.vertex(0, -1 * @r *2)
    @p.vertex(-1 * @r, @r * 2)
    @p.vertex(@r, @r * 2)
    @p.endShape()
    @p.popMatrix()

# flock function, passed the Processing instance by Processing itself
flock = (processing) ->
  start = new Vector(processing.width/2,processing.height/2)

  # Instantiate 100 boids who start in the middle of the map, have a maxmimum
  # speed of 2, maximum force of 0.05, and give them a reference to the
  # processing instance so they can render themselves.
  boids = for i in [0..100]
    new Boid(start, 2, 0.05, processing)

  processing.draw = ->
    processing.background(255)
    for boid in boids
      boid.step(boids)
      boid.render()
    true

canvas = $('<canvas width="550" height="550"></canvas>').appendTo($('#flockingDemo'))[0]
processingInstance = new Processing(canvas, flock)

That’s it! You can now stir up your own flocks of tiny little dudes to watch and herd about.

Wrap Up

I hope you found this informative! If you have any questions, comments, corrections, or know of any neat uses of flocking algorithms in the wild (baha!), please leave them below. Also, thanks again to Craig Reynolds for publishing his code in the first place and Daniel Shiffman for creating a basic Processing version of it.

Thanks

Thanks to Craig Reynolds for coming up with the algorithm and Daniel Shiffman for the initial port to Processing. Daniel is working on a new, free book called “The Nature of Code”, exploring what properties of nature we can find and use while coding. He’s publishing the draft chapters for anyone who helps fund the project on Kickstarter, so if you like this kind of thing you could help contribute to it on Kickstarter.

Also, thanks to Mo for helping edit.