The principles behind flocking behaviors were first demonstrated in a computer simulation in 1986 by Craig Reynolds. Flocking is an example of emergent behavior, which I touched on briefly in an ealier post about Conway’s Game of Life.
Flocking behaviors are a lot of fun to play with, but simulating them can be fairly processor intensive. In an earlier post, I talked about using proximity grids to increase performance in this type of simulation. In the demo at the bottom of this post, I have employed a proximity grid and an implementation of verlet integration to control the particle dynamics.
One of the problems I ran into when combining flocking behaviors with proximity grids is that flocking tends to subvert the ways in which proximity grids optimize. A proximity grid reduces processing by making it easy to skip any inter-agent reactions on agents which are far apart. Flocking on the other hand tends to take agents and clump them together into small areas, thereby thwarting some of the benefit of a proximity grid. This is not to say that the proximity grid doesn’t help, because it does, but a proximity grid is more effective in cases where particles are scattered somewhat evenly across an area. I was unable to simulate as many particles in this demo as I did in the proximity grid demo partly because of the clumping nature of flocks, but mostly because of the need to examine the direction in which a particle is heading (a costly operation).
Figure 1. Agents react to near neighbors according to the basic priniciples of flocking. The length of an agent’s tail is based on its current velocity.
The core principles of flocking are alignment, separation and cohesion. Each individual agent (e.g., particle, sprite) operates autonomously by following these 3 basic rules. Each agent can only “see” agents near them (their neighbors). Agents will avoid close contact with neighbors (separation), they will attempt to travel in the same direction as their neighbors (alignment), and they will attempt to navigate towards the average position of their neighbors (cohesion). By employing these 3 basic rules, a wide variety of complex group behaviors emerge.
I’ve built a simple demonstration of flocking in Actionscript which you can view at the bottom of this post. This demo requires Flash Player 9 or later.
Figure 2. Holding the mouse button down will attract the agents, releasing the mouse button returns them to their regular behavior.
dave says:
this looks great, an chance of any hints or tips on how to code this?
daniel says:
“any hints or tips on how to code this?” um yes, right here: http://www.red3d.com/cwr/boids/
I was building a bit of a flocking behaviour for some fish some time ago an Id the boids were a great place to start. I wasn’t smart enough to apply different paradigms and the ability to switch between them. This paper “Context-Dependent Adaptability in Crowd Behavior Simulation” (http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4018492), however, does a pretty good job of explaining how to take this a bit further. (and make it context dependent)
The thing that I found the most useful, was the use of excitation values and the way they were calculated.
Noel says:
@dave – Flocking behaviors are not particularly difficult to implement, but if you have no experience with vector math and switching between polar and Cartesian coordinates, you might not have the foundation to work upon. I would highly recommend researching those topics first, as adding flocking behavior to a 2d motion system is relatively easy. One important concept to keep in mind is that you can use the dot product of vectors to figure out the angle between them. This is important when determining what direction to steer your agents in.
Steven Baughman says:
I am such a sucker for this stuff. Very cool.
Mike says:
Very cool emergent behavior example.
In your “alignment” algorithm, is there account taken for the magnitude of the neighboring particle velocities? I notice that when in “flock” mode, the sprites tend to fly off in extreme directions when encountering a cluster of neighboring sprites.
Doesn’t happen when the particles are all traveling in the same direction (towards a target), but when they all get to the target, they begin to exhibit more and more separatist behavior. Could this because particles are accounting for the direction but -not- magnitude of their neighbors? I wonder how the simulation might change if you allowed particles to know how fast their neighbors were traveling…