Home > Boids, Guides > Boids Simulation: Part 1

Boids Simulation: Part 1

boids-logo

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

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.

About these ads
Categories: Boids, Guides
  1. Jeremy
    September 10, 2009 at 11:48 pm

    I’m getting this when I try to install:

    $ cabal update
    Downloading the latest package list from hackage.haskell.org
    cabal install chp
    $ cabal install chp
    Resolving dependencies…
    Configuring chp-1.3.0…
    Preprocessing library chp-1.3.0…
    Building chp-1.3.0…

    Control/Concurrent/CHP/Console.hs:38:17:
    Could not find module `Control.OldException':
    it is a member of the hidden package `base’
    Use -v to see a list of the files searched for.
    cabal: Error: some packages failed to install:
    chp-1.3.0 failed during the building phase. The exception was:
    exit: ExitFailure 1

    I’m using Fedora 11 with current ghc+haskell platform packages installed.

    Any clues?

    • September 11, 2009 at 9:41 am

      Hi Jeremy,

      This is to do with the reorganisation of the base package that occurred between GHC 6.8 and 6.10. I think you must have a configuration that I haven’t tested. Can you post the output of “ghc –version” and “ghc-pkg list | grep base”, and I’ll try to roll a 1.3.1 version to fix the problem.

      Thanks.

    • September 11, 2009 at 3:56 pm

      For now (assuming you have a version of cabal that supports this feature), a work-around is to use:

      cabal install chp –preference=’base >= 4′

      (Try changing ‘base >= 4′ to ‘base < 4' if that doesn't work). That works on my machine where I have now replicated your problem. I'm working on a better solution, though.

      • Jeremy
        September 11, 2009 at 7:57 pm

        Yes, someone on IRC suggested that to me so I got to the next step of fighting with the new version of HOpenGL not accepting Float as a VertexComponent any more (it insists on GLfloat, which is a low-level C type). I worked around that by converting Float to GLfloat in drawBoid, but ultimately I reverted to the Fedora packaged OpenGL which still works as expected (Float is an instance of VertexComponent).

        $ ghc –version
        The Glorious Glasgow Haskell Compilation System, version 6.10.3
        $ ghc-pkg list | grep base
        OpenGL-2.2.1.1, QuickCheck-1.2.0.0, array-0.2.0.0, base-3.0.3.1,
        base-4.1.0.0, bytestring-0.9.1.4, cairo-0.10.1, containers-0.2.0.1,
        directory-1.0.0.3, (dph-base-0.3), (dph-par-0.3),
        random-1.0.0.1, regex-base-0.72.0.2, regex-compat-0.71.0.1,

  1. September 10, 2009 at 3:02 pm
  2. September 12, 2009 at 5:31 pm
  3. September 14, 2009 at 1:32 pm
  4. September 16, 2009 at 3:47 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: