Tuesday 28 July 2009

Flocking about with Clojure

Emergent behaviour describe the way complex behaviours emerge from simple rules.

Conway's Game of Life is a good example. Just a handful of simple rules about how to behave in the presence of neighbours result in really complicated behaviours. Visualizing Conway's Game of Life has some great examples.

Nature provides even better examples such as flocks of birds or shoals of fish. How do these behaviours emerge? Computer simulations can simulate a similar effect by just following a few simple rules. The classical paper was written by Craig Reynolds who presented at SIGGRAPH three simples rules to allow flocking behaviour to emerge:

  1. Collision Avoidance - members of the flock don't like flying/swimming into each other!
  2. Velocity Matching - members of the flock tend to fly together at the same speed
  3. Flock Centering - stay close to members of the flock

Modeling this in Clojure gives me a chance to get a bit more familiar with agents. Agents provide a way to get independent asynchronous access to state. An agent is bound to some state (e.g. a Clojure data structure). Data is manipulated by sending messages (functions) to the agent.

To get some flocking behaviour, we'll model each member of the flock (a boid, after the paper) as an agent. Each agent has some state (a position and a velocity). Messages will be sent to the agents corresponding to the rules above. A single agent will be used to manage the animation thread.

Screen shot of Flocking Behaviour

(I realize an animation would be much better, but all the desktop recording software I tried, gtk-recordmydesktop, didn't get a high enough frame rate to make it worth recording!)

The code for the behaviours is shown below (it's missing a few helper methods here and there, but see Clojure Projects for the full version).

The behaviours are as simple as they can be. Big thanks to kfish for a nice lucid explanation of how to implement this!

The animation loop is an agent with no state whose only job is to make the other boids behave, by sending them the appropriate message. This is all rendered within a subclass of JPanel which has a custom paint method.

The code is nice and simple, and easy to play with and extend. The behaviours can be mixed and matched to show all sorts of crazy effects (for example, with just cantering and separation behaviours the flock tends to go into a crazy implode/explode cycle!). Further extensions could be:

  • Have separate flocks (they avoid each other, but follow the same rules within each other)
  • Three dimensions (more or less exactly the same maths)
  • Sphere of Influence (at the moment each boid affects every other, perhaps it should only be within a certain area)

It makes a good example of the power of agents and STM. There's no threading problems whatsoever, all I need to do is take a consistent view of the boids each time I go to draw them (and STM provides that for free).