Check out Flock!

A year ago I attended a 3 week college-like event called Missouri Scholar’s Academy. I showed several of my peers there some of the different demos I had here on bluethen.com, and they seemed to like it.

The teacher suggested that I should try and simulate a flock of birds. I told him that there were several implementations out there already, but I gave it a go anyways.

I wrote and based the algorithm off of a blog post by Harry Brundage. The original simulation could handle about 200 birds or “boids” before the frame rate drops noticeably.

In the past week I’ve returned to the flocking algorithm and did a few improvements. Right now it can handle about 1000 boids, and, with the OpenGL renderer, it can handle 1500 and up.

Flocking basics

Harry gives a pretty good explanation to the basic mechanics of flocking algorithms. Each bird looks at other birds within a certain radius of itself, and makes a decision on where to accelerate. It factors in 3 different properties: cohesion, alignment, and separation.

For cohesion, each bird takes the average position of all surrounding birds within a radius of itself. The bird would then move towards that position.

Separation works exactly like cohesion, except the bird avoids that averaged position. For cohesion and separation to not just cancel out, you can have separation work at a smaller distance than cohesion. Birds, this way, will move towards towards a certain range from others.

Alignment involves velocity. The speed and direction of surrounding birds are averaged out, and then added to the speed and velocity to the central bird. To keep birds from accelerating to the speed of light, it’s a good idea to place a limit on how fast each bird can go.

My algorithm involved a few other checks and balances in order to keep things stable. Here is a basic pseudo-code of what happens for each boid

update (elapsedTime) {
     Vector cohere, separate, align
     int count, separationCount
     for (boid from nearbyBoids) {
          if (boid and this are close enough to interact) {
               count += 1
               cohere += boid.position
               align += boid.velocity
               if (boids are too close!) {
                    separate += boid.position
                    separationCount += 1
                    if (boids are REALLY too close!) {
                         separation += boid.position * 12
                         separationCount += 12
                    } // end really close check
               } // end too close check
          } // end close enough check
     } // end loop

     cohere /= count
     align /= count
     separation /= separationCount

     Vector desired = cohere - position
     Vector avoid = separation - position

     if (count > 10 && cohereConstant > 0) // too many too close
          desired *= -0.25

     velocity += desired * cohereConstant
     velocity += align * alignConstant
     velocity -= avoid * avoidConstant

     velocity.limit(80)

     position += velocity * elapsedTime
}

Optimization

Grid

One of the biggest bottlenecks in the original code was the huge number of distance checking being done.

For a boid to find out if another is close enough to interact with, they need to loop through every other boid and find the distance between themselves before deciding whether they should interact. In a simulation with 1500 objects, that would involve 2,247,001 checks per timestep!

for (boid from boids)
     for (otherBoid from boids)
          if (boid and otherBoid are close enough)
               do stuff

You can avoid a huge amount of unnecessary distance checking by only calculating the distance between boids that are potentially close.

I used Spatial Partitioning, the same algorithm in Balls, to separate all of the boids into a grid. Each cell is the width and height of the maximum amount of distance needed for two boids to interact. Whenever the distance check needs to be done, the Grid looks inside the cell the boid is in, and the cells adjacent to it, and returns their contained boids.

for (boid from boids)
     nearbyBoids = list of boids from adjacent grid cells
     for (otherBoid from nearbyBoids)
          distance check

For an algorithm involving circle collisions, you can expect at most n * 8 (or 12000 for 1500 balls) collision checks. It’ll be a bit more for Flock, since the boids will be packing together inside cells.

Sqrt()

After reducing the amount of checks needed, we can now save on calculation time. One of the biggest bottlenecks in physics engines and simulators is sqrt().

Because it has to be approximated in most cases, sqrt() can be expensive to compute. It can be especially costly when you’re using it thousands of times per frame. If possible, we should try to avoid sqrt().

Consider distance checking again. If we want to see if two boids are close enough, use the distance formula:

if (sqrt((x1 - x2)^2 + (y1 - y2)^2) <= influence)
     do stuff

With some algebra, you can remove sqrt() by squaring both sides of our condition:

if ((x1 - x2)^2 + (y1 - y2)^2 <= influence^2)
     sqrt() the squared distance if needed
     do stuff

Already our algorithm is a lot more efficient. Sqrt will only be calculated once we know two boids are close enough.

I’ve also made many changes to the original algorithm used by Harry. You’ll notice in his algorithm, sqrt() is used quite a few times (again, including normalize(), limit(), or dist()).

Take a look and compare our algorithms for cohering:

Harry’s:

     avgPos = average position of surrounding birds within a distance
     currentPos = current boid’s position
     desired = avgPos - currentPos
     dist = desired.mag()
     desired.normalize()
     desired = desired * MAX_SPEED * (dist/maxDist)
     velocity -= desired

Mine:

     avgPos = average position of surrounding birds within a distance
     currentPos = current boid’s position
     desired = currentPos - avgPos 
     desired *= cohesionProperty
     velocity -= desired

They’re very much similar, however a significant difference is the lack of desired.mag() and desired.normalize() in my algorithm. Both mag() and normalize() require sqrt() to compute and can slow things down quite a bit.

These changes also mean that the boids in mine and his will behave differently. However, with flocking, there’s really no “correct” way for boids to interact. As long as they move and behave like a flock of birds/worms/whatever, it’s good in my books.

I made similar changes to the alignment and separation algorithms.

Timestep

Traditionally, one would find the elapsed amount of time between the current and previous frame and then plug it into the update function. Velocity is multiplied by the elapsed time, and added to the position of each boid every frame.

// In Main loop:
elapsedTime = currentTime - timeLastFrame
for (boid from Boids)
     boid.update(elapsedTime)

// Inside Boid:
update (elapsedTime) {
     position += velocity * elapsedTime
}

Called Euler Method (or Euler Integration), this is the simplest way to solve for the physics of boids/particles/pointmasses.

Euler Integration is very prone to jitteriness. If your simulation were to freeze for a second, then things will accelerate way more than intended.

An excellent thing about Flock is that it only needs to be stable, not accurate. All we need to do is regulate elapsedTime.

I used Processing’s frameRate in order to smoothen elapsedTime, and then placed a simple min/max constraint on it to keep things from moving too slow or fast.

Processing’s frameRate will return the average fps your applet is running over the last several frames. It’s great because it won’t change too rapidly, and it gives a rough estimate for how fast the applet is going.

To calculate elapsedTime, I use

elapsedTime = constrain(1f/frameRate, 16f/1000f, 32f/1000f)

1/frameRate will return how many seconds have passed on average since the last frame. I limit it to the range of 16/1000 (16ms per frame at ~60fps) and 32/1000 (32ms per frame at ~30fps) to keep the boids from moving too fast or too slow.

Source

I commented the source to the best of my ability. I encourage you to take a look at it and see how it works, and maybe find some of my errors. You can view Flock’s code at OpenProcessing or Hawkee.

Links

Boids – The original flocking algorithm by Craig Reynolds
Neat Algorthims – Flocking – A great starting point for flocking algorithms. Has several JS examples that illustrates the different parts