Quadtree vs Red-Black tree for a game in C++?

Question

I have been looking for a quadtree/quadtree node implementation on the net for ages. There is some basic stuff but nothing that I would be able to really use it a game.

My purpose is to store objects in a game for processing things such as collision detection. I am not 100% certain that a quadtree is the best data structure to use, but from what I have read it is. I have already coded a Red-Black tree, but I don't really know if the performance would be good enough for my game (which will be an adventure 3rd person game like Ankh).

How would I write a basic but complete quadtree class (or octree) in C++? How would you use the quad tree for collisions?

Answer 1

Quadtrees are used when you only need to store things that are effectively on a plane. Like units in a classic RTS where they are all on the ground or just a little bit above it. Essentially each node has links to 4 children that divide the node's space up into evenly distributed quarters.

Octrees do the same but in all three dimensions rather than just two, and thus they have 8 child nodes and partition the space up into eights. They should be used when the game entities are distributed more evenly among all three dimensions.

If you are looking for a binary tree - like a red-black tree - then you want to use a data structure called a binary space partitioning tree (BSP tree) or a version of it called the KD Tree. These partition space into halves using a plane, in the KD tree the planes are orthogonal (on the XZ, XY, ZY axes) so sometimes it works better in a 3D scene. BSP trees divide the scene up using planes in any orientation, but they can be quite useful, and they were used as far back as Doom.

Now because you've partitioned the game space you now don't have to test every game entity against every other game entity to see if they collide, which is an O(n^2) algorithm at best. Instead you query the data structure to return the game entities within a sub-region of the game space, and only perform collision detection for those nodes against each other.

This means that collision detection for all game entities should be n O(nlogn) operation (at worst).

A couple of extra things to watch out for:

• Make sure you test game entities from adjacent nodes, not just the ones in the current node, since they could still collide.
• Rebalance the data structure after the entities have moved since you may have empty nodes in the data structure now, or ones that contain too many entities for good performance (also the degenerate case of all entities being in the same node).

Answer 2

A red-black tree is not a spatial index; it can only sort on a single ordinal key. A quadtree is (for two dimensions) a spatial index that allows fast lookup and elimination of points. An Octree does the same thing for three dimensions.