In 1986 Craig Reynolds developed a simulation of flocking behavior of creatures that he called boids. As is typical of good ideas, this one is simple to describe: even when many individuals each behave according to a small set of very simple rules, the resulting collective behavior of the group can be very interesting and complex. For example, consider a flock of birds, or a school of fish, or an army of orcs (that’s right, orcs), or cars on a freeway.
In the case of boids, Reynolds originally used just three simple rules: separation, alignment, and cohesion. Separation means don’t run into any other boids. Alignment means head where everyone else is heading. And cohesion means stick with the group. Just these three rules can yield interesting and realistic flocking behavior among a large number of boids that all follow those same rules.
I have VPython to blame for spending enough time on this to warrant posting about the subject. In the process of experimenting with VPython and putting together a few example programs for students, I wrote the following boids simulation. It’s a little quick and dirty, but I think it provides pretty convincing evidence for Python’s advertisement as “pseudo-code that runs.” Cool flocking behavior in less than a page of code. Each rule determines a small change in velocity of a boid as a function of its neighbors. Note that I added a fourth rule, bounding, so that the boids tend to stay within a fixed volume of space, so that they don’t fly “off camera.” Here is the code:
#!/usr/bin/env python from visual import * seterr(all='ignore') num_boids = 30 fps = 24 dt = 1.0 / fps boids = [arrow(pos=20 * (v - 0.5), axis=norm(v - 0.5)) for v in random.rand(num_boids,3)] def separation(boid): center = mean([b.pos for b in boids if b != boid and abs(b.pos - boid.pos) < 5], 0) if isscalar(center): center = boid.pos return norm(boid.pos - center) * 0.05 def alignment(boid): heading = mean([b.axis for b in boids if b != boid and abs(b.pos - boid.pos) < 10], 0) if isscalar(heading): heading = boid.axis return (norm(heading) - boid.axis) * 0.1 def cohesion(boid): center = mean([b.pos for b in boids if b != boid and abs(b.pos - boid.pos) < 10], 0) if isscalar(center): center = boid.pos return norm(center - boid.pos) * 0.01 def bounding(boid): if abs(boid.pos) > 30: return -norm(boid.pos) * 0.25 else: return vector(0, 0, 0) rules = [separation, alignment, cohesion, bounding] while True: rate(fps) for boid in boids: boid.axis = norm(boid.axis + sum([dv(boid) for dv in rules], 0)) boid.pos = boid.pos + boid.axis * 10 * dt
The filtered list comprehensions and vectorized mathematical operations provided by Numpy (included with VPython) certainly contribute to the readability.
This sort of simulated “emergent” complexity of behavior has several interesting applications. Hollywood has put it to good use: computer-generated bats and penguins simulated using algorithms similar to boids were first used in the movie Batman Returns. (Okay, so maybe that’s not very good use.) And the idea has taken off from there; Massive Software has a pretty cool gallery on their site showing, among other things, the many movies and games where similar technology has been used.