Improving Boid Flocking

I’m working right now on adapting Shiffman’s flocking example (https://www.processing.org/examples/flocking.html) for openFrameworks. So far, the flocking itself works great, but I know there are ways to make the flocking much more efficient, but I’m not sure if I’m going about this correctly.

My idea right now is to create a flock grid system, in which a boid in the flock is only concerned about the location of nearby boids. Because a boid might inhabit a spot right next to the grid boundary, it will continue to look at all adjacent grid areas, but exclude distant ones. This will at least reduce the number of boids that each boid will need to check the location of.

My confusion, and possibly where I might be mislead, is how I’m doing this within vectors. Essentially, I’m creating a vector< vector >, with the first dimension being the grid id (for which I have a working formula for assigning an id), and the second for the individual boid. Will all of my efforts to reduce the number of checks actually increase the number of calculations? Every boid will now have to constantly tell the flock structure if it has or hasn’t left it’s grid location.

Does anyone have some advice on how I might approach this?

This is a great idea for increasing the efficiency of your flocking system. You could approach this two different ways:

  1. Search for neighbors in a fixed distance around each boid. For each boid, your algorithm would find all the boids in its grid cell and the adjacent grid cells and then discard all of the boids that are further than a certain distance.

  2. Search for the k-nearest neighbors around each boid. For each boid, your algorithm would find all the boids in its grid cell. If the count of neighbor boids was < k, your algorithm would find all of the boids in the adjacent grid cells. Your algorithm would continue working outwards until it has found at least k neighboring boids, and then it would discard the furthest ones until you have just the k-nearest boids.

The short answer is no, it should not.

The longer answer —

This is a question of computational complexity. The flocking algorithm in the Processing example you provided is O(n^2). Say we have 10 boids. For each of those 10 boids we need to compute the distance to 10 boids — 10 X 10 = 100 distance operations. Not bad, but say we have 100 boids. For each of those 1,000 boids we need to compute the distance to 100 boids — 100 X 100 = 10,000. Yikes — increasing the number of boids by a factor of 10 (or, n) increased the number of operations we need to do by 100 (or, n^2).

The algorithm that you’re proposing is much more efficient. Yes, you’d have to write some additional code to keep track of the grid cell each boid belongs to, but because that calculation helps you get away from looping over every boid in the flock for every boid in the flock, you’ll end up with net savings. Especially when you have a big flock! See: Flocking — Algorithmic Complexity (Wikipedia).

More code doesn’t always mean less efficient! Until you have an intuitive grasp of algorithmic complexity, the best way to find out is to code it up and see what happens!