Simulating crowds and animal swarms

If you've ever looked at an ant farm I'm sure you were surprised by how organised they were. But the truth is they all follow a very simple logic which “magically” adds up to a large scale organised colony. How do they do that?

Swarm behaviour is not really observable on one entity but very visible on the large scale. Interestingly it works with us, humans as well: we don't know how we board a train or plain but a simulated environment can predict very well will we move and how efficient the crowd movement will be.

Boids

Studying the crowd movement is not new by any means: Craig Reynolds in 1986 came up with three simple rules that can describe the large swarm movement quite accurately. He named the rules as “boids” after birds (it supposed to be the New York accent style bird?).

The three rules are:
- separation: the entities prefer to keep some distance from each other
- alignment: try to go the same way as the group or the local flock-mates
- cohesion: try to go closer to the centre of the crowd

Implementation

In my case I just wanted to write up something quickly to validate how much fine-tuning would be required. To my surprise t was very reasonable for the first version! The simulated crowd moved moved in a very reasonable pattern, nothing like robots. For instance when directed to a remote point the head of the group got a bit away from the rest, just like you would expect from a larger human group.

Boids are just having rest and staying together with some random movement.

Boids are chasing a target point – the rest of the group is trying to catch up with the first ones.

The code was written is Javascript and I haven't really used any optimisation – for a couple of hundred members even the O(n^2) algorithm did just fine. The movement was calculated at every 100ms and to smooth out the movement I just used CSS animations.

.boid{  
        position: absolute;
        height: 10px;
        width: 10px;
        transition: margin 0.1s;
}

The main loop looks like this:

function StepBoids(boids, destination, blocks){
        for(var i = 0, b; b = boids[i]; i++){
                var dCenter = StepBoidCenter(b, boids); // Get a vector to center.
                var dDest = StepBoidDestination(b, destination); // Get a vector to destination.
                var dAway = StepBoidAway(b, boids); // Get a vector away from others.
                var x = dAway.x + dCenter.x + dDest.x;
                var y = dAway.y + dCenter.y + dDest.y;
                var length = Math.sqrt(x*x + y*y);
                if(length){
                        x = x * Boid.speed / length; // Normalise speed.
                        y = y * Boid.speed / length;
                }

                var blocked = false;
                for(var j = 0, block; block = blocks[j]; j++){
                        if(block.inBlock(b.x + x, b.y + y)){
                                blocked = true; // Simple 'wall' detection.
                                break;
                        }
                }
                if(!blocked){
                        b.x += x;
                        b.y += y;
                }
        }
}

Navigating around an object

As the algorithm didn't have any routing defined, my expectation was that any object in their way would just simply block them and every member would get stuck. However, something much more interesting happened:

Boids moving around an object and finding their way to the destination

Of course! The first couple of boids get stuck but the rest stay away from those, eventually pushing each other around the obstacle. Again, there is no code to avoid any obstacles – it's just a side effect of the group behaviour.

Further steps – why train boarding is so slow

To put this into something more useful, you can simulate how much the boids would sow down if you had a few of them standing around the train doors while the rest is trying to get out. Seeing that maybe next time we would want to give a bit more space to the ones getting off the train so we can get on much faster.

You can grab the full source code from here.