Optimized Boids I

Posted on October 27, 2010

1


As i mentioned in my previous post, I’m developing a little game based on Flocking simulations devised by Craig Reynolds. There’s more than enough ink been spilled describing these so I won’ t bother to explain here.

What I would like to talk about is optimization. Many articles about boids in games mention that it would be easy to optimize them through various methods… and then leave it at that. What has been frustrating for me, as I wanted hundreds, even thousands of boids in my game and traditional algorithms are O(n^2) which is obviously pretty terrible.

There are many ways to cure this, but the first and simplest step is to hold the boids in a more advanced data structure than a simple array. This is because each boid is normally passed every other boid, checks that its distances is less than a given cutof, gets its position and velocity relative to the current boid, and changes the current boid’s velocity based on that.
So a lot of time is spent checking boids which are beyond the cuttoff range, when in fact if we keep a minimum separation between boids there can never be more than a few boids inside the cutoff range.

The solution to this is a spacially ordered data structure, where information about the boids’ position is contained in the very way its stored. The structure is set up so that returning objects within a given area is very efficient.

In 2D quad-trees are often mentioned – a look on wikipedia should help explain how these work. Unfortunately while returning an objects inside a given rectangle is very easy with a quad tree, inserting an object generally requires it to be pushed through every “level” of the tree. Since for quickly moving objects this well be done many times a second it seemed to me to be not such a good solution.

In the end I came across a very simple solution – a simple grid. Each cell (Leaf) of the grid is a linked list that can contain any number of boids. Adding the boid to the right place in the table is trivial using this:

int I = (int) Math.floor(x / leafWidth);
int J = (int) Math.floor(y / leafWidth);

where I and J are the position of the leaf in the grid. The whole grid can be rebuilt many times a second with just two mathematical operations per boid.
The leaf width is set to be smaller than the boid influence range, so that if the boid is at the edge of a leaf/grid cell its influence radius extends into the adjacent cell but not further.
When running the simulation the “close” boids are found by simply returning the contents of the boids’ current cell and the 8 neighboring cells (Moore neighborhood for cellular automata fans).
|_|_|_|
|_|B|_|
|_|_|_|
Larger objects in the game can simply return the contents of more cells:
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|B|_|_|
|_|_|_|_|_|
|_|_|_|_|_|

As you can see this method will become cumbersome for large objects/areas of interest, which is not the case with Quad trees which can happily accommodate objects on a large range of scales. On the other hand the insertion process with the table set-up is trivial, and I’ve successfully run 1500 boids using Pulpcore on a 2010 macbook at smooth-ish framerate. (note that I also only process the boids 10 times a second even if they are rendered more often).

I was originally planning to combine this with the advantages of a Quad Tree by adding a set of tree nodes with my table as the bottom level of nodes, however there’s been no need an I don’t think there will be.

I will be posting the java code for this at some point, however at the moment my code is a huge mess and I want to strip it down to just the boid stuff to post (otherwise it’ll just be confusing).

Posted in: Computers