During the last lesson of complex systems course, prof. Vizzari showed a
crowd simulation based on
BOIDS, an
intriguing model invented by Craig Reynolds in 1986 that simulates
bird flocks, fish schools and all that kind of
self-organizing masses of living stuff. The basic model is based on three simple assumptions:
- each boid moves toward the other flockmates (cohesion)
- each boid moves away from crowded situations (separation)
- each boid follows the direction of the rest of the flock (alignment)
Even in its simplest formulation the model works very well, and gives a pleasant feeling of viability. I turned the model from 3D to 2D, by putting all boids on the y=0 plane, and here we go: we have a simple crowd simulator.
There exist
several approaches to crowd simulation (like cellular automata or multi-agent systems) but I do think that BOIDS have many interesting capabilities.
In fact, one of the open issues in crowd simulations is the
sponteneous formation of groups because of common goals, shared costumes, socio-political aspects, familiar relationships and so on. BOIDS leave a
lot of space for embedding this wide spectrum of behaviours, whilst the model itself mantains the
proxemic distances between people and let them
gather peacefully, by the rules decribed above.
The video I embed shows my model in a simple scenario made of four groups (yellow, red, green and blue). Green people have their own goal to follow; red and blue have a shared one. Yellow people just walk around the space, with no specific purpose. In the middle of the screen there's a strong repulsor which keeps boids away. The dynamic works as I expect: there's the formation of clusters, boids belonging to the same group tend to aggregate and find their way even in overcrowded situations. What's fascinating is the
emerging, unexpected behaviour of yellow ones: some of them hold still, some dodge the crowd, many other enter the moving groups and follow them wherever they go, conditioned by the first rule.Very nice.
 |
Hajj - the annual pilgrimage to Mecca - is
one the most interesting scenario to simulate |
Still, there's a lot of work to do that I'll share with my brilliant coursemate Michele. For instance, we'll try to identify the
correct parameters that fit the experimental results, incorporating Elias Canetti's proxemic dynamics as well. We also could find a way to introduce different kind of
non-penetrable contraints (walls, doors, and such). There's the problem of instructing
complex goals (like finding a way to an exit in non-straight situations or following a leader), with an eye to
stability and realism. Finally, there's lot of
optimization to do: I wrote the code as general classes and new rules can be easily introduced by pushing a new function pointer to a "rules" vector. That's very flessible, allows a very rapid prototyping but it's very inefficient: the naive algorithm is O(n²), because every boid's position needs to be compared with the rest of the flock, and every rule is computed on its own, adding a costant factor.
Too slow for serious business like sport events, concerts, and religious pilgrimages, just to name a few of the typical simulations that require
millions of individuals at once.
