The code base for any given modern video game is a huge, complicated beast. There are countless code paths, and many actions are deferred, so the code that acts on a piece of data may well be far removed, both in space and time, from the code which created the data.

So, we’re not going to be creating a game engine, at least not today. Instead, I decided to start with something smaller, and simpler, upon which we can more easily add new features, the sorts of features that a modern game engine will need.

With that, I’d like to introduce you to Bayts, an implementation of flocking behavior. The name was suggested as a joke by my good friend Matthew. A joke it may have been, but it stuck.

If you aren’t already familiar with flocking behavior, take a look at Boids, the earliest known implementation. There are also articles about it in Game Programming Gems and Game Programming Gems 2. You should really have a look at least at the Boids page, because I am not going to go into any detail about what flocking behaviors are or how they work, at least not in this post.

The implementation we’re going to be working on is influenced pretty heavily by the one in Game Programming Gems. In many ways, though, it’s simpler. For example, the camera is fixed, and the bayts are represented by AAB’s, rather than arrows pointing in the direction of movement. This is intentional; I wanted the code to be as simple as possible, while still being flexible.

ANN aside, or more Other People’s Code

One of the problems that must be solved for implementing flocking behavior is a nearest neighbor search. Most example implementations of flocking behaviors that I’ve seen use a brute-force search, simply iterating over every single member of the flock, calculating its distance from the current member, and keeping track of the closest one(s). This works fine for small flocks, but very quickly gets bogged down when the number of members increases. There are alternative algorithms available for the nearest neighbor search, such as KD-trees, but these algorithms tend to be complex enough that they overshadow the actual flocking behavior algorithms. Which is, I suspect, why most flocking example code you find just sticks with the brute-force search.

Well, to be perfectly honest, I wasn’t terribly happy with that situation. I wanted our flock to have hundreds, maybe even thousands of members. But I also didn’t want to be overwhelmed trying to implement a better nearest neighbor algorithm. So I did what I always recommend - I got lazy. I searched around a bit, and found ANN: A Library for Approximate Nearest Neighbor Searching.

ANN is a C++ library for performing exact and approximate nearest neighbor searches, and is released under the LGPL. The library supports a few different data structures and algorithms for performing the nearest neighbor search, including KD-trees and box-decomposition trees. The interface is pretty straightforward. All of this makes it pretty much a perfect match for what I was looking for.

Bayts also depends on a couple other open source libraries:

• TMV, which I’ve discussed before. I’ve modified the version in the source repository so that it can be built with Visual C++ 2005. I’ve sent the patch to the original author, and he’s planning to include it in the next release.
• freeglut, an open source implementation of GLUT. (Not used on Mac OS X).

All of the dependent libraries are already in the source repository, so you will not have to go and get them individually.

Get It

I’m not really going to discuss Bayts any more in this post, as it’s already gone on long enough, but it will form the basis of several discussions going forward. If you want to get Bayts and try it out, you should follow these directions:

• Mac OS X
• Windows
• Linux

The directions are somewhat general, since they will be basically the same for future Programmicon projects, but since this is the first time I’m presenting code in this way, all of the examples in the instructions are for Bayts. If you follow the instructions, you should end up with a working Bayts executable.

Comments