Ever wondered at the flowing patterns generated when birds flock together in great numbers? It can be quite hypnotizing, as shown in the video clip below.
For some time I had wanted to make a model and simulate the flocking of large numbers of birds. Such models have created visual effects for movies and computer games for a couple of decades already. So, to avoid reinventing the wheel I chose to base my simulations on the most well known model out there.
Enter The Boids
In an attempt to describe the flocking of animals Craig Reynolds proposed his boids model in 1986. The word boid is short for “bird-oid”, a bird-like object. The model is one way to show self-organisation and emergence in a system. This means that an entity can show behaviors or have properties that its individual parts do not. But it is the individuals that are in charge, they react to simple rules that govern the interaction with their neighbors. Therefore, individual boid reactions is what generates the emergent behavior. In principle, a single boid could cause the group to change direction.
The Boids Rules
The boid is a kind of simulation creature that moves in space, and reacts to other boids following three rules:
- Attraction: steer towards the average position of nearby neighbors. Mimics the instinct to join a group when separated, and results in tendency to centre oneself within the group.
- Alignment: steer towards the average velocity direction of nearby neighbors. Mimics an instinct to avoid separation and collisions.
- Avoidance: steer away from the average position of nearby neighbors. Mimics an instinct to avoid collisions, and avoids too dense congregations.
Each rule is characterized by an acceleration and a perception radius, within which neighboring boids are reacted to. Typically, attraction acts over longer distances and avoidance over shorter distances, with alignment in between. This is illustrated in the figure below.
There are many simulations using this model out there, often applying the three rules mutually exclusive, meaning only one applies at any one time. Also, avoidance usually takes highest priority and attraction lowest. The idea behind this is that boids do everything to avoid collisions. While this makes sense, the very sharp distinction at different radii feels a bit unnatural to me.
My Boids Model
The boids movement model I use is pretty standard, see my blog post objects in motion for the main ideas. Position updates are calculated using Beeman’s algorithm. All three boid rules apply simultaneously, with avoidance acceleration larger than the other accelerations to prevent collisions.
To prevent boids from accelerating to ridiculous speeds some limit must be enforced. This is often done by imposing a maximum speed that the boids cannot exceed. I prefer a more physically realistic method and use a velocity dependent air friction to do the job. The larger the speed, the larger the breaking force. At high enough speed the friction will simply prevent further increase.
Birds in real life obviously move in three dimensions, but for my simulations here i use only two. This makes the simulation faster, which is useful during development. Also, visualizing on screen is inherently two dimensional. I may try three dimensions in the future, but for now two will do.
Craig Reynold’s boids model also includes an angular limited perception. This means boids cannot see all the way behind them. I will test this in future simulations, but for now boids have full 360° perception.
Some More Simulation Details
I use Python to program the simulations. It is versatile but, being an interpreted language, unfortunately slow. In pure python I could simulate a collection of maybe a few tens of boids before the simulation became unbearably slow.
Now, I usually use the Python package numpy and related ones for scientific programming. This allows more efficient data structures and the use of C and Fortran code. Using numpy speeds up the simulation so that a few thousand boids can be simulated in a similar time.
As a partial goal for this simulation work I wanted to learn how to use my graphics card for parallel computations. This should allow for even faster simulation speeds. For this I used PyCUDA, which is a Python wrapper around CUDA. This required learning some C-like CUDA programming, but I am pretty happy with the results. In the end I could run simulations of about a hundred thousand boids in a similar time.
Force strength relations between attraction, aligment and avoidance in the simulations shown below is 3:5:-8, where the minus sign indicates a repelling force. The videos below show simulations of different number of boids. The perception ranges for attraction, alignment and avoidance are visualized as green, blue and red discs (same as figure above) centered around one of the boids.
The first video shows 3 boids with randomized starting positions and velocities. It illustrates how they first attract and align and then start moving back and forth across the border of the avoidance disc.
The second video shows 20 boids with randomized starting positions and velocities. It illustrates how after attracting and aligning all boids, they move as a unit group. Individual boids now drift between the inner and outer region of the group. This becomes clear when following the highlighted boid.
The last movie below shows a simulation of 110367 boids with arranged starting positions but randomized velocities. It took about 15 minutes to simulate the 600 frames on my computer. The resulting patterns do resemble actual bird flocking to some extent. Actually this large number comes out a bit too dense with this frame size. A more eye pleasing result may follow using a few tens of thousands instead. We’ll see, I will continue to play with the simulation framework I have developed.
Boids will continue…