Boids Simulation: Part 1

In the 1980s an animator named Craig Reynolds was interested in animating groups of animals, such as flocks of birds. He wanted to avoid having to individually determine each bird’s movement, and he suspected that their behaviour could be captured by an algorithm wherein each bird followed simple rules relating to its surroundings. His work showed that he was right, and he produced a now famous simulation called boids that demonstrated flocking behaviour based on three simple principles: stay close to other boids, head in the same direction as them, but avoid hitting them.

Occoids

Boids is famous for several reasons: it emulates animal group behaviour quite simply, it demonstrates emergent behaviour, and so on. I’m going to use it as an example application for two reasons: it looks good, and it’s a nice, fairly small example of a physical simulation. So this is the first in a series of posts on implementing boids using the CHP library, based on an existing example in another message-passing concurrency language: occam. That version, occoids, can be seen in videos from the CoSMoS project.

We will start with the framework for visualisation, then build up the simulation. All the code in this guide is held in a chp-boids repository on patch-tag — each sample will have an accompanying darcs command to get the code associated with that point in the guide. Oh, and you will need the latest version of CHP to work with these examples (1.3.0, currently), which you can get by issuing “cabal update ; cabal install chp”. So without further ado, here’s the first piece of code for boids in CHP:

mainCHP :: CHP ()
mainCHP = do
  boidStartPos <- liftIO $ liftM2 zip (replicateM 150 randomIO) (replicateM 150 randomIO)

  let displayIO = do startFrame
                     mapM_ drawBoid boidStartPos
                     endFrame

  liftIO $ do setup
              displayCallback $= glRunAs2D displayIO
              mainLoop
  where...

main :: IO ()
main = runCHP_ mainCHP

darcs get --tag p1b http://patch-tag.com/r/twistedsquare/chp-boids chp-boids-p1b

I’ve omitted some irrelevant bits that can be seen in the full code. displayIO is the callback for the display — currently it’s starting and ending a frame, and drawing some stationary boids. You can see the general structure of a CHP program — the top-level command uses runCHP_ to run the main function (in the CHP monad). Currently the body of mainCHP just uses liftIO to do some OpenGL/GLUT bits, but that will change in due course. The program currently runs and displays some stationary boids until you close it. So far, so good — now it’s time to add some concurrency.

We are going to turn each of our boids into a concurrent process (recall that we aim to add as much concurrency as we can find). For now, our boid processes will simply continually offer to send their unchanging position on a channel. So here’s our starting boid:

boid :: Chanout (Float, Float) -> (Float, Float) -> CHP ()
boid out pos = forever $ writeChannel out pos

Our boid is fairly self-explanatory — it just repeatedly writes its position on the channel (we will come to the reading shortly). It is important to understand that the boid will not sit there filling up some internal buffer until it overflows:

CHP channels are synchronous, which means the writer only sends the data when the reader is ready to recieve it. There is no buffering in the channels.

So although our boid is continually offering to send its position on the channel, the communication will only occur when the reader asks for it. Now we can look at how the rest of our code has changed to use this boid process:

mainCHP :: CHP ()
mainCHP = do
  boidStartPos <- liftIO $ liftM2 zip (replicateM 150 randomIO) (replicateM 150 randomIO)
  -- Allocate channels for boids:
  boidChannels <- replicateM (length boidStartPos) oneToOneChannel

  let (*$*) = zipWith ($) -- apply a list of functions to a list of arguments
      boids = repeat boid *$* writers boidChannels *$* boidStartPos

  displayIO <- embedCHP_ $
                  do boidPos <- mapM readChannel (readers boidChannels)
                     liftIO $ do startFrame
                                 mapM_ drawBoid boidPos
                                 endFrame

  runParallel_ boids
    <||> liftIO (do setup
                    displayCallback $= glRunAs2D displayIO
                    mainLoop)
  return ()
  where...

darcs get --tag p1c http://patch-tag.com/r/twistedsquare/chp-boids chp-boids-p1c

Early on, we now allocate a list of channels that the boids will use to send their position. There is then a little bit of Haskell that forms the boid processes from the list of channels and list of start positions. The displayIO callback has to be in the IO monad rather than the CHP monad so we use a helper function supplied by the CHP library (embedCHP) that pushes a CHP process back down into the IO monad. The displayIO callback can then use CHP functions — here it uses readChannel to collect positions from all the boids.

Finally, the boids are run in parallel with each other (using the runParallel_ function) and also in parallel (this time via the <||> operator) with the main loop of the program. What this gives us is a concurrent program with 151 processes: 150 boids, and one main loop.

The wiring and interface with OpenGL/GLUT is likely to be one of the ugliest parts of our simulation, so it should get better from here. In the next part of the guide I will show how to get the boids moving.