Skip to content

Flocking and Swarming

by Stephen on June 17th, 2010

Flocking algorithms are a very interesting subset of n-body simulations that allow for the modeling of fairly complex behaviour (such as the swarming of moths around a light) using a very simple set of base rules. Chris Reynolds developed the first computer simulation back in 1986, outlining the 3 basic rules that govern the behaviour of individual “Biods” .

During the last winter semester at school I was developing a graphical demo to showcase some research I had done for a directed studies, and stumbled across Reynolds’ work while I was looking for a way to create a swarm of fireflies. Thanks to the very simple nature of biod interaction, (you can think of Reynolds’ three rules as being the basic instincts for flies) implementation only took a couple of days. While my graphical demo ended up going in a different direction, meaning I didn’t get to use the flocking code I’d written, I did manage to put together a fun little java demo.

Basic Implementation

Each biod is an autonomous object that gets simulated independently (think of a particle in a standard n-body simulator). Updates are done in 2 passes – the first pass applies Reynolds’ three rules:

  1. Separation: Biods will steer to avoid one-another.
  2. Alignment: Biods will steer to match the same general heading as their neighbors.
  3. Cohesion: Biods will steer to move towards the center position of their neighbors.

Implementation of the first pass is pretty straight forward. First, each biod scans each other biod in the simulation and builds a list of neighbours (those biods which are both within a certain “visibility” range, and fit within a front-facing cone that mimics field-of-view). Next a vector is calculated for each of the three rules, with separation modeled like a spring so as to scale with distance to surrounding elements. Finally the three vectors are summed and normalized, providing a new heading for that biod.

The second pass iterates through each biod and advances them forward along the heading vector that was calculated in the first pass.

Repulsers and Attractors

Having a bunch of biods swarm about aimlessly in a cloud is kind of cool, but in order to make things more visually exciting I decided to give my biods some direction. I extended them to incorporate a fourth force, an “outside influence” force if you will, that simply gets added in during normalization with the other three forces. Prior to running the update passes on the biods, I iterate through each attractor/repulser, having each apply an exponential force to all biods based on distance (think the force of gravity between two entities), which is accumulated in the new fourth force vector of each biod. For fun, I added several different kinds of methods to model the interaction between attractors/repulsers, such as linear, logarithmic, and sinusoidal (weird eh? Creates a very cool pulsing-wave effect). For kicks I also threw in support for walls, so I could force my flock through a maze.

Predators

Finally, to wrap everything up, I added one final feature. Predators. No point in having a heard of gazelle without a lion to hunt them, eh? Predators are just repulsers that tend to move towards the center position of all visible biods. This creates a nice chasing effect as the predator moves in towards the bulk of the flock, and the flock disperses to avoid the predator.

Improvements

For the most part I figure my flocking simulation is pretty complete – it has all the basics implemented, looks pretty cool, and even has an extra feature or two. However it is highly unoptimized (about 4000 biods is the maximum my poor MacbookPro can handle) – everything is done in a single thread, I’m using the basic built-in Java drawing routines, and there’s a nasty Thread.sleep() in the main loop to maintain a semi-constant framerate. If I end up getting back to this and improving it any, I think I’d like to take a look at jCuda (Java bindings for Nvidia’s CUDA library) and see what kind of a benefit massively-parallelizing the simulation on the GPU brings.

No comments yet

Leave a Reply

Note: XHTML is allowed. Your email address will never be published.

Subscribe to this comment feed via RSS