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.