Boids Simulation: Part 4

After part 1, part 2 and part 3 of this guide, we now have boids moving around and doing some very basic flocking. In this part of the guide I will implement the full flocking rules, finishing with a video.

Aside: After the previous parts of the guide, I decided that the architecture for the boids was not quite right. Each boid was doing its own clamping (which had a small bug — now fixed) and was dealing with its absolute position. But a boid doesn’t care about its absolute position, only about the relative position of the other boids. So I have refactored the design so that a boid keeps track of its own velocity, and is sent information about its neighbours’ relative positions (and absolute velocities). The cell keeps track of each boid’s absolute position, and is changed to send the boid the appropriate information. That change on its own can be seen with this command:

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

The remainder of this part of the guide implements the full flocking rules, and is more interesting for how the boids work than for the concurrency (more concurrency next time!). I have implemented the rules in pure Haskell for now to try to make them understandable. First, we will define some helper functions:

    (*+*) (a, b) (a', b') = (a + a', b + b')
    (*/) (a, b) c = (a / c, b / c)

    average xs
      | null xs = 0
      | otherwise = sum xs / fromIntegral (length xs)

    sq x = x * x

    within ps d = filter ((< sq d) . hyp2) ps
      where
        hyp2 n = sq (relX n) + sq (relY n)

The *+* operator adds together two pairs, and the */ operator divides both elements of the left-hand pair by the right-hand side. The average function is as expected, and returns zero if the list is empty. sq is a short-hand for squaring something, and within filters down a list of (X,Y) pairs to all those within the given distance of the origin. For relative positions of boids, this will filter a list down to all the boids within a certain range. But enough boring helper functions — here is the first rule, where the boid tries to match its neighbours’ velocities:

    -- An acceleration to allow us to match the mean velocity (i.e. speed and direction)
    -- of the boids nearby
    meanVelocityAcc neighbours cur
      = (average (map (velX . neighbourVel) neighbours) - velX cur
        ,average (map (velY . neighbourVel) neighbours) - velY cur)

All the rules are given in terms of acceleration — i.e. a desired change in our velocity. This rule is very simple, and just says that we should accelerate to match the average of our neighbours’ velocity (by producing that average, and working out the change needed from our current velocity). The second rule tries to make sure that we don’t bump into our neighbours:

    -- An acceleration to stop us hitting nearby boids
    repulsionAcc neighbours
      = foldl (*+*) (0, 0) $ map ((negate . relX) &&& (negate . relY)) veryClose
      where
        veryClose = neighbours `within` 0.02

The rule first filters the neighbours list to a small distance. Then it works out the velocity away from the neighbour (by negating their relation position) and adds up all these velocities to produce a total (not an average). The &&& is an Arrow function — a habit I picked up from Neil Mitchell (I think his HLint suggests it). Here it applies the two functions to a single input and produces a pair of the results. The third rule is to make us stay close to the other nearby boids:

    -- An acceleration to keep us quite close to nearby boids (stick with the flock!)
    keepCloseAcc neighbours
      = (average $ map relX neighbours
        ,average $ map relY neighbours)

Very straightforward — head towards the average centre of the nearby boids. Obviously there will be tension between the second rule (avoid hitting boids) and the third rule (stay near them). You will see boids jostling around a bit in the flock because of this. There is a fourth rule that I have taken from the occoids example — a slowly changing bias angle to make the flocks head roughly in the same direction. This involves some state-passing and thus I have incorporated it with the definition of the boid:

boid :: Chanout BoidVel -> Chanin [BoidNeighbour] -> BoidVel -> CHP ()
boid out input = boid' (0, 0)
  where
    boid' (biasCount, biasAngle) cur
      = do writeChannel out cur
           possibleNeighbours <- readChannel input
           let neighbours = possibleNeighbours `within` 0.05
               -- Every 100 frames, tweak the bias:
               (biasCount', biasAngle')
                 | biasCount == 100 = (0, biasAngle + 0.5)
                 | otherwise = (succ biasCount, biasAngle)
               (idealAccX, idealAccY)
                 = (meanVelocityAcc neighbours cur */ 8 )
                     *+* (repulsionAcc neighbours */ 4)
                     *+* (keepCloseAcc neighbours */ 30)
                     *+* ((cos biasAngle, sin biasAngle) */ 10000)
               new = limit $ BoidVel {velX = velX cur + (idealAccX/5)
                                     ,velY = velY cur + (idealAccY/5)
                                     }
           boid' (biasCount', biasAngle') new

The definition for idealAccX and idealAccY combines all the rules together. The seemingly magic numbers in the weighting (and throughout these rules) are tweaked parameters that I have taken directly from the occoids source. The limit function crudely limits the boid’s velocity:

    speedLimit = 0.007

    -- Stop the boids from speeding up crazily by limiting their maximum speed:
    limit v@(BoidVel vx vy)
      | sq vx + sq vy > speedLimit * speedLimit
        = let slowdown = (speedLimit * speedLimit) / (sq vx + sq vy)
          in BoidVel (slowdown * vx) (slowdown * vy)
      | otherwise = v

That’s all we need to implement our boids. You can get all this source with the command:

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

If you compile and run the program, you’ll be able to see the boids flocking together from random start positions. Close the window and re-run to see it happen again from different start positions. I quickly recorded a short video of one instance of the flocking:

Choose from WMV format (suitable for Windows) or MPEG format (suitable for Linux, etc).

David A. Wheeler’s sloccount says that we have written 142 lines of Haskell code to implement the boids concurrently, which is not too bad. It works — but you may wonder if it gets faster should you have multiple cores available. I aim to find out in the next part of the guide.