Thursday, April 10, 2008

E Terra Tree / Term Project Roundup

I already discussed some about my AI class term project: a language identifier. In this post I'll describe my other two term projects some.

In game programming class, we are making a tower defense game. This was decided by vote. We're still pretty early into development (still discussing gameplay design), so there isn't much to tell right now. It will be 2.5D, meaning that the gameplay will be two-dimensional, but the graphics will be three-dimensional. We decided to write it in C#/XNA, because XNA is a very nice self-contained platform for amateur game development (if you're looking to make a small-scale game, I'd definitely recommend XNA), and most of us have used it before in the introduction to game programming class.

In graphics programming class, I'm going to be making a commercial-grade space-partitioning tree for E Terra. Games have to do a lot involving spatial searches. Collision detection, range-finding, path-finding, and view frustum culling (only drawing objects that are actually visible on screen) are some of the things E Terra needs to do.

In the very beginning, I used a simple set to hold all objects on the playing field. This was just a temporary method, to allow me to work on other stuff before creating a space-partitioning structure. This worked okay when there were only a couple dozen things on the map, but as spatial search for anything in the set is O(n), obviously this would become a bottleneck as the number of units on the map increases. That was expected, and happened after not too long.

As I still didn't want to take the time to make a commercial-grade structure, I came up with something else that was much faster, yet still didn't take very long to code: a spatial hash table. The X and Y coordinates of each object on the map were quantized, and the objects were put into buckets corresponding to regular, fixed-size squares of the map. While this was still O(n), the actual time was much smaller, as the space which was searched in each case was much smaller than the entire map (with the maps I was using, things like collision detection were quite a few orders of magnitude faster). The problem is that this structure is only optimal if objects on the map are evenly distributed, which is extremely unlikely in a game (or anything, for that matter).

I'm still not certain which type of structure I'm going to use in the end, although I have it down to two: a kd-tree and a quadtree. Both are trees that partition space, but they do not partition space in fixed-size regions like my spatial hash table does. This allows them to maintain a roughly even distribution of objects per partition even when there isn't an even distribution of objects on the map, by creating more, smaller partitions in areas where there is a high object density. Search for the object nearest a given point/object is O(log n) for both; other algorithms are harder to give a definite complexity of.

A quadtree (diagram) is the simpler of the two. It's a two-dimensional space partitioning structure that separates a given region into four equal-sized squares, which may further be split. Thus it partitions the space by recursively splitting it in both dimensions at once. Partitions that have few units can be left large, while partitions that contain many objects can be further split into smaller partitions. The three-dimensional version of a quadtree is an octree, which partitions each region into eight equal-sized cubes.

A kd-tree (diagram from here) is a binary space-partitioning (BSP) tree. It also recursively divides the space in a region (this time into two parts), but the two partitions need not be equal in size. Furthermore, each partition may be along any axis (a kd-tree is a general structure that may represent spaces of any numbers of dimensions, and the logic is the same for any number of dimensions). The standard way of building a kd-tree is to partition each region such that half of the objects in it fall in one of the sub-partitions, and half in the other, producing uniform object density.

A quadtree has the benefit of using fixed-size partitions, making it very fast to add or remove partitions on the fly; this is beneficial for a game because objects often move frequently. As well, for maximum benefit of a kd-tree, the entire set of objects must be known in advance, to produce optimal partitioning. However, there is a fairly easy solution to these issues: for kd-trees that hold a dynamic set of objects, the tree behaves similar to a quad/octree, splitting each region in half as needed. Note also that because I require support for changes to the tree, I would use a kd-trie (diagram), rather than a true kd-tree (diagram; though I've been mostly using the terms interchangeably).

I'm actually leaning toward the kd-tree for several reasons. First, the same code can be used in any number of dimensions, making it highly reusable. Second, only minor modifications are necessary to make the kd-tree implementation work optimally for a non-changing set of objects yet still perform well for sets that change frequently (about as well as a quad/octree). Of course, a kd-tree will be more complicated to code, but I don't see that as a major deterrent.