Original post

Lately, I’ve been revisiting concepts and algorithms that I got stuck on when I was learning to code. One of them is the boids flocking simulation.

We’ll look at how this program can be written in and delivered via WebAssembly. You can find all the source code for this article, as well as the demo, on healeycodes/boids.

A flock of dark colored boids swimming around a white area

A boid is a simulated bird-like object, a bird-oid. Each boid looks at their local flockmates and uses three rules to respond to their behavior — separation, alignment, and cohesion.

This artificial life program was first developed by Craig Reynolds. In Flocks, Herds, and Schools: A Distributed Behavioral Model he describes it:

The simulated flock is an elaboration of a particle system, with the simulated birds being the particles. The aggregate motion of the simulated flock is created by a distributed behavioral model much like that at work in a natural flock; the birds choose their own course.

Ebiten “A dead simple 2D game library for Go”

Ebiten is well documented and has a lively community (#ebiten channel in Gophers Slack). I started learning it by extending the example programs to get used to the API.

Let’s look at the overall structure of our program.

When you build a game with Ebiten, you must implement the ebiten.Game interface. We define a Game struct to store our flock of boids as well as the methods required by Ebiten to run our game. Update is called every tick to handle the game logic, Draw is called every frame to draw the screen, and Layout is used to define the game’s screen size (which can be ‘stretched’ to fit the window).

type Game struct {
    flock  Flock
    inited bool
}


func (g *Game) init() {}


func (g *Game) Update(screen *ebiten.Image) error {}


func (g *Game) Draw(screen *ebiten.Image) {}


func (g *Game) Layout(outsideWidth, outsideHeight int) (int, int) {}



func main() {}

Game Loops

Almost every game that you’ve played uses a pattern called a Game Loop.

A game loop runs continuously during gameplay. Each turn of the loop, it processes user input without blocking, updates the game state, and renders the game. It tracks the passage of time to control the rate of gameplay.

The frequency of a game loop is sometimes referred to as the tick rate of a game. A single iteration of the loop is a tick.

Simulation Logic

In our program, a boid has the following properties:

  • Position — the coordinates of the boid in the world
  • Velocity — how fast and in what direction the boid is moving
  • Acceleration — we change the velocity by this value during the next tick
type Boid struct {
    imageWidth   int
    imageHeight  int
    position     Vector2D 
    velocity     Vector2D
    acceleration Vector2D
}

Every tick, we need to handle three things for every boid in our flock:

  • Check edges — check if the boid has gone off the edge of the screen
  • Apply rules — using the three rules, set every boid’s acceleration
  • Apply movement — apply acceleration to the boid’s velocity
type Flock struct {
    boids []*Boid
}

func (flock *Flock) Logic() {
    for _, boid := range flock.boids {
        boid.ApplyEdges()
        boid.ApplyRules(flock.boids)
        boid.ApplyMovement()
    }
}

To handle boids hitting the edge of the screen, we wrap them around by swapping their position to the opposite side. Their velocity means they keep flying in the same relative direction.

After we’ve figured out the boid’s acceleration by applying the three rules, we need to update its position and velocity, and reset acceleration.

func (boid *Boid) ApplyMovement() {
    boid.position.Add(boid.velocity)
    boid.velocity.Add(boid.acceleration)
    boid.velocity.Limit(maxSpeed)
    boid.acceleration.Multiply(0.0)
}

By adding acceleration to the boid’s existing velocity, and then limiting it by a maximum speed, we get smooth movement that tends towards the desired direction and speed. Velocity can be thought of as momentum and acceleration as steering.

The Three Rules

In the following code excerpts, you may notice that the logic is not very optimized. This is to make it easier to understand. On every tick, every boid considers the position of every other boid. We would say that the asymptotic complexity is O(n^2).

Different rules use different ‘inclusion’ zones. Whether another boid is local to another boid depends on which rule we are applying.

maxForce             = 1.0
maxSpeed             = 4.0
alignPerception      = 75.0
cohesionPerception   = 100.0
separationPerception = 50.0

The last three values are really fun to play with and greatly affect the shape and contortions of a flock of boids. maxForce limits the steering of a boid and maxSpeed is the ultimate speed limit.

I’ve expanded some of Craig Reynolds’ low-resolution diagrams to help explain the three rules that define a boid’s behavior.

Separation

Steer to avoid crowding local flockmates.

The closer another boid is to us, the more motivated we are to move away from it. The white circle represents separationPerception. Boids outside of this area are not considered. This rule encourages boids to move into free space.

A boid looking at its local area and deciding to move away from the average position of other boids

(In the canonical version of the Boid program, a boid doesn’t consider other boids behind itself by applying a field of view restriction.)

separationSteering := Vector2D{}
separationTotal := 0

for _, other := range restOfFlock {
    d := boid.position.Distance(other.position)

    
    if boid != other {

        
        if d < separationPerception {
            separationTotal++

            
            
            diff := boid.position
            diff.Subtract(other.position)
            diff.Divide(d)
            separationSteering.Add(diff)
        }
    }
}


if separationTotal > 0 {
    separationSteering.Divide(float64(separationTotal))
    separationSteering.SetMagnitude(maxSpeed)
    separationSteering.Subtract(boid.velocity)
    separationSteering.SetMagnitude(maxForce * 1.2)
}



boid.acceleration.Add(separationSteering)

Alignment

Steer towards the average heading of local flockmates.

We know the direction of a boid by looking at the velocity. We sum and take the average of other nearby boids within the alignPerception area. This rule encourages boids to travel together.

A group of boids with lines indicating their heading, the boid in question is about to adjust to this

alignSteering := Vector2D{}
alignTotal := 0

for _, other := range restOfFlock {
    d := boid.position.Distance(other.position)
    if boid != other {
        if d < alignPerception {
            alignTotal++
            alignSteering.Add(other.velocity)
        }
    }
}

if alignTotal > 0 {
    alignSteering.Divide(float64(alignTotal))
    alignSteering.SetMagnitude(maxSpeed)
    alignSteering.Subtract(boid.velocity)
    alignSteering.Limit(maxForce)
}

boid.acceleration.Add(alignSteering)

Cohesion

Steer to move toward the average position of local flockmates

To be a cohesive boid, one must head towards the center of the clump. This may seem at odds with separation but these two rules work together to let boids arrange themselves equally within a space. Although, the reality of this arranging can look quite chaotic!

Our boid has a red arrow pointing to a green point in space. There are lines from the other boids that lead to this average center.

cohesionSteering := Vector2D{}
cohesionTotal := 0

for _, other := range restOfFlock {
    d := boid.position.Distance(other.position)
    if boid != other {
        if d < cohesionPerception {
            cohesionTotal++
            cohesionSteering.Add(other.position)
        }
    }
}

if cohesionTotal > 0 {
    cohesionSteering.Divide(float64(cohesionTotal))
    cohesionSteering.Subtract(boid.position)
    cohesionSteering.SetMagnitude(maxSpeed)
    cohesionSteering.Subtract(boid.velocity)
    cohesionSteering.SetMagnitude(maxForce * 0.9)
}

boid.acceleration.Add(cohesionSteering)

Each rule should be considered equally, so after summing the rules together, we divide by three to find the average.

boid.acceleration.Divide(3)

Building And Deploying

It’s time to get this simulation in front of users! Lucky for us, Ebiten supports many platforms. (The Nintendo Switch is even on the roadmap.)

The current release (v1.11.4), supports:

We will be compiling to WebAssembly. With WebAssembly as a compilation target, we can deliver our Go program to anyone running a modern browser. I’m currently hosting it on GitHub Pages.

What are the benefits of WebAssembly? In brief:

  • Fast, efficient, and portable
  • Executes at ‘near-native’ speed
  • Runs in a secure sandbox

To get our Boid program ready for users, I wrote a build script. (I nearly set up a GitHub Action to automate this on push but it felt like I was procrastinating from writing this!)

GOOS=js GOARCH= go build -o dist/boids.wasm github.com/healeycodes/boids
gzip -9 -v -c dist/boids.wasm > dist/boids.wasm.gz

We set the program’s target operating system to js as well as setting the architecture to wasm. After that, gzip is used to deflate the file. This shrinks it from 8MB to 2MB.

This means an additional step is required for clients (they must inflate the gzipped file) but this is quicker than downloading an extra 6MB. I chose the pako library to handle the gzipped file client-side after reading David Stoikovitch’s post about Go + WASM. (Minified, pako is 44KB.)

If you’re setting this up from scratch, you’ll need a copy of wasm_exec.js from the Go source — you can copy it locally from your machine or get it from GitHub.

Our index.html page looks like this:

<script src="dist/pako.min.js"></script>
<script src="dist/wasm_exec.js"></script>
<script>
  ;(async function () {
    
    const file = window.pako.ungzip(
      await (await fetch("dist/boids.wasm.gz")).arrayBuffer()
    )
    const go = new Go()
    
    
    WebAssembly.instantiate(file, go.importObject).then((result) => {
      
      document.querySelector("#loading").remove()
      go.run(result.instance)
    })
  })()
</script>

It loads and runs in ~1sec on my machine.

Where to go from here?

We looked at how to create an Ebiten game, the emergent behavior of the Boid program, and delivering a Go program via WebAssembly. But there’s still more to explore!

Expand this solution with:

  • Field of vision support (boids shouldn’t look behind 👀)
  • QuadTree optimization
  • Different maxSpeed/maxForce for each boid
  • Graphical interface for live-editing of values

Or use a different language:

I’d love to see what you come up with!


Reynolds, C. W. (1987) Flocks, Herds, and Schools: A Distributed Behavioral Model, in Computer Graphics, 21(4) (SIGGRAPH ‘87 Conference Proceedings) pages 25-34.

Nystrom, R. (2020) Game Programming Patterns/Sequencing Patterns