An optimized Boids implementation

Posted on January 2, 2011

0


[Update: there is now a python version of this script which might be easier to follow]
Better late than never…

After first completely breaking my program while trying to improve it (the best being the enemy of the good) and having generally got fed up with the whole thing for a while I’ve finally come back and fixed everything. What you will find linked at the bottom of the page is the source code for my optimized implementation of Craid Reynolds Boids flocking system. It’s built in Java with the Pulpcore game engine, though it wouldn’t take much work to separate the flocking system from the game engine. There’s just the source code for now, since I’ve been working in eclipse and can’t be bothered figuring out Ant to produce a neatly packaged build.

The motivation for this was to build a game based on flocking (though the game hasn’t come very far). The computation needed for naive implementation of the flocking algorithm grow with the square of the number of boids i.e. O(n^2) which obviously is pretty problematic for a game. The reason is that in the naive implementation each boid checks the position of every other boid to see if it is within its “line of sight” – since the behavior of each boid in the flock is only affected by its neighbors.

The simplest optimization is to avoid having to check every boid for distance by putting them in a spacial data structure where information about the position is contained in the position of the boid in the data structure. Quad trees are often used but usually require each element to be pushed down all the levels of the tree on insertion. Since the boids’ position is updated every frame the data structure must be rebuilt and so all the boids re-inserted. So I used a simple grid – each grid square (called Leaf) contains the boids within it. Since the Leafs are integer indexed it is very fast to find the correct leaf to add the boid to. Finding neighbor boids is a question of return the contents of the boids current leaf and the 8 surrounding leafs. This is also very fast thanks to the use of linked lists which can be trivially concatenated.

Anyway, here are the files. You need Pulpcore (I set it up in Eclipse). I found I had to put the unit graphic (unit.png) in the “build” directory.

Java source files

Unit image (copyrighted Musings of an Idle Mind)

Advertisements
Posted in: Computers