Simulating how birds form flocks

This article is about using a computer to simulate how birds form into flocks.  This probably also applies to fish forming shoals and dinosaurs moving and grouping together like they apparently did.  There’s a static snapshot of this simulation below, and clicking on the picture will take you to a live version where you can vary the parameters that control the simulation.

I was browsing the web, and came across a nice explanation of some maths, which used a toolkit called MathBox to do 3D graphics.  That made me think of arrows flying around like birds in the sky, which reminded me of a Smarter Every Day video on simulating bird flocking, using something called the boids algorithm.  The implementation used in the video was lovely, but was 2D.  I wondered if I could extend the 2D simulation into 3D, and this article describes the result.

If you haven’t already seen it, I really recommend that you watch the Smarter Every Day video.  It has some gorgeous footage of big flocks of birds swirling around the sky (and other good stuff).  In the rest of this article I will use the terms bird and flock rather than e.g. fish and shoal etc, but the principles apply to all bird-like (or boid) objects.  The video also features Ben Eater, and it’s Ben’s code that is the basis of the code you can play with below.

Boids algorithm

The interesting thing about the boids algorithm is that it doesn’t include anything about flocks.  It has no concept of flocks, has no rules about how to form them and keep them together etc.  All it does is tell each bird how to move itself.  When all the birds in a region of space follow the same rules, even if they start off in random positions heading in random directions at random speeds, eventually flocks will form.  Over time, flocks merge with other flocks, until all the birds are in one flock.

Flocks are an emergent behaviour from the algorithm’s rules – they aren’t explicitly and deliberately created and maintained, but grow up out of a lower-level set of behaviour.

Due to practical limitations of screens and eyesight, and to stop you having to scroll around chasing the birds as they fly off the screen, I have added to the boids algorithm a rule that says to turn around as you get near the edge of the screen.  This is a bit artificial, but it’s also similar to natural behaviour.  Instead of wanting to stay within a particular region of space, I think that birds will want to stay near something like a particular tree.  So, as they get too far away from it, they will start to turn around.

The rules

Apart from the rule about not flying off the edge of the screen, there are three main rules:

1. If you get too near another bird, steer away from it;
2. Try to fly towards the centre of the birds around you;
3. Try to match the speed and direction of the birds around you.

The first two are in tension – birds are attracted towards each other, but at close ranges repel each other.  The third rule is because it’s not enough for the birds to be in the right arrangement in space at one moment in time, they need to travel alongside each other too.

The last two rules have an implicit concept of visual range – how far can you see around you?  If you run the algorithm, the birds don’t immediately form into one big flock.  Instead they clump together with the birds already near them into small flocks – i.e. they clump together with the birds that they can see.  These flocks fly around and come near each other.  This lets the flocks merge with each other more and more, and it can take a little while for the flocks to completely merge into one.  If you increase the visual range, the birds more quickly form into one big flock.

It’s interesting to notice the one-way nature of this clumping together.  Once a flock of any size has formed, the rules will tend to keep it together.  The only change it will make (other than to its location and speed) is to merge with another flock.

One more practical consideration is a rule to impose a speed limit on birds as they can’t fly arbitrarily fast.

Playing with it

Click on the image above to go to the live version of the code.  While you can just about use it on a small screen such as a phone, it’s much better on a bigger screen.

There are controls to let you vary the parameters that the rules use, so you can make each rule apply more or less by changing the parameters.  You can also reset the parameters back to a set of default values, and also restart the birds with random positions and speeds but the current values of the parameters.

You can zoom in or out, by using the wheel on your mouse if you’re using one, or by pinching / stretching on a touch screen in the normal way.  You can also rotate the camera position by clicking / tapping and then dragging it around.

If you set the maximum speed high enough, the birds won’t always turn around before they hit the ground.  They fly through the ground unharmed and eventually come back up again! Also, increasing the maximum speed won’t immediately make the birds go faster. Instead, they will tend to reach the higher speed limit gradually and then stay that fast.

A nice effect happens when you set the visual range up really high (which makes the birds clump together a lot), and then make it really low – the birds spread out like an exploding firework.

MathBox

As I mentioned in the introduction, I’ve implemented it in MathBox.  MathBox is a JavaScript toolkit that uses WebGL to turn data into graphics.  It’s similar to other toolkits like D3, except it’s more geared towards maths-related things.  It makes it simple to generate points, lines, surfaces and vectors.  I found the documentation hard to follow – the latest version is 0.0.5 and I think documentation is one of the things that would be improved to take it to version 1.0.

The basic concept is a view, which is the top-level container.  You add data to the view, such as an array of numbers.  You then add a display thing to the view, such as point or line, and it automatically creates a point or line for each element in the array.  I.e. you don’t loop over the array saying what to do with each member.

It has the concept of time, which lets you animate things (as I’ve done here).  It also lets you create your data indirectly, via a function that generates it.  I.e. when you add data to the view, you don’t add the values directly, instead you pass in a function that MathBox will call to generate each item of data.

As one of the arguments to the generator function can be time, you can use that inside the generator function to return data that changes over time.  MathBox will call the function once per item in the array, once per frame of animation.  It will then handle all the tricky stuff of removing the corresponding point or line from its previous position and replacing it with one in the right position for the new value of the data.

One of the slightly annoying aspects of MathBox is that it takes over the whole screen – it creates a canvas element and makes it take up the whole screen.  To make space for some controls, I have written some JavaScript to find the canvas and then resize it and move it down.

I’m using MathBox’s vector thing to represent each bird, which looks like a rod sticking out of a cone.  I wanted to give some sense of the direction each bird’s travelling in, which wouldn’t be as obvious if I used a point.  Ideally I’d use a set of polygons, to make the bird be more like an arrow head (specifically, a broad head arrow head).

The important bit, that a vector doesn’t show but something like an arrow head would, is the way in which birds are more or less visible to you depending on which direction they’re pointing.  If you look at a flying bird straight on (from the front or rear) there’s not much bird visible.  If the bird turns side-on, there’s much more bird visible.  The effect of this in a real flock is flashes of lightening or darkening as the flock turns in the air.  Unfortunately this would take more time than I was prepared to spend.

For all its rough edges, I was very impressed by how smoothly MathBox animates things, and how many moving objects it can cope with while still staying smooth.

Custom JavaScript

I have implemented the boids algorithm as a series of JavaScript functions as you might expect.  The only thing that might not be immediately obvious is that there are two frames’ worth of data – the previous frame is used to create the next frame’s.  Once that’s drawn, the previous frame is discarded, the next frame shuffles along to be the new previous frame, and a new next frame is created.  I implement this as a circular buffer two elements long.

Ben Eater’s code doesn’t have two frames’ worth of data, so why did I bother?  It shouldn’t matter too much, but I think it will produce more correct results.  To produce the next version of the speed for a bird, you need to read the previous version of the location and speed of all other birds.  If you’ve already updated some of those other birds, the updates to the current bird will have skipped one frame’s version of its source data.

By having two frames’ worth of data, all birds can read an unchanged version of all other birds, even though all birds are in the process of changing.  The changed version of each bird is written elsewhere (to the other frame’s slot in the buffer) rather than updating data in place.

I treat each bird as a single point in space during the calculations.  At the end of the calculations, each bird has a new position and new speed.  The speed is in three dimensions i.e. it’s a vector (it has size and direction).  I treat the location I already have as the blunt end of the bird’s vector on screen, and use the speed vector to say which direction the pointy end of the on-screen vector should be relative to that.

Summing up

I hope that you enjoy playing with it, and if you’re old enough to remember such things maybe it will remind you of a 1980s-era screensaver.  It’s weird and lovely how flocks emerge out of rules applied separately to each bird.  Part of the reason why I did this is because my mum likes murmurations of starlings, and while this isn’t as good as the real thing, I hope it’s still nice.