Quadtree demonstration

I’ve been working on different approaches to speed up the collision detection stage for some while now (mainly for the motor engine and some games). This includes a Quadtree which I started working on last year, but just recently got around to pick it up again. I’m still fine-tuning the code, so I can’t share it at the moment. But, because I added some visualization stuff to help fix some bugs, I thought I could put together a little demo showing the Quadtree in action :).

I’m also thinking of creating another package (like the data structures) which would include some highly optimized broadphase collision detection algorithms, but this depends how much spare time I have – which is very limited at the moment.

But what exactly is a Quadtree ? Generally speaking, it’s a tree structure using a principle called ‘spatial locality’ to speed up the process of finding all possible collisions. Because objects can only hit things close to them, testing against distant objects should be avoided.

The easiest way to quickly compute a collisions set is to divide the collision space (e.g. your game area) into a uniform grid and register each object with all intersecting grid cells. That’s also called spatial hashing. One disadvantage is that it doesn’t cope well with objects of varying sizes. If the grid cells are too big, many unnecessary collision checks are done, and if they are too small, you end up searching many registered cells containing the same object.

The quad tree tries to overcome this weakness by recursively splitting the collision space into smaller subregions, similar to the RDC algorithm, with the difference that every region is divided exactly into 4 smaller regions of the same size, so you end up having multiple grids with different resolutions, where the number of cells in a region goes go up by a power of two every time the resolution is increased. So every object resides in the cell (called quad node or quadrant) with the highest (finest) possible resolution. A search is made by starting at the object’s node and ‘bubbling’ up to the root node. Wikipedia has a nice explanation, and there exist many variations.

The quad tree in the demo contains 1000 objects. I’m not sure if the quad tree is faster than a regular grid, but I’ll compare both versions soon. And don’t be afraid of the memory usage, it needs tons of memory because I’m storing all tree nodes for drawing them on the screen.

A Quadtree containing 1000 objects. (9 levels, leaf size 8x8px)

Collision detection with Recursive Dimensional Clustering

Brute force comparison

Collision detection can be done in many ways. The most straightforward and simplest way is to just test every object against all other objects. Because every object has to test only for others after it in the list of objects, and testing an object with itself is useless, we arrive at the well known brute force comparison algorithm:

for (i = 0; i <  n; i++)
    a = obj[i];

    for (j = i + 1; j <  n; j++)
        b = obj[j];
        collide(a, b)

This double nested loop has a time complexity (n is the number of objects to check) of:
brute force time complexity
It can be immediately seen that this suffers from a big problem: exponential growth. An excellent article by Dave Roberts describes this problem in more detail and also covers several alternative approaches to collision detection.

Space partitioning

The algorithm represented here uses space partitioning, which means it subdivides the screen into smaller regions. Each region then obviously contains a fewer number of objects. The collision checks for all the entities in the region (space garbage, alien spaceships, orks, whatever) are then performed by the brute force comparison - which is very efficient for a small number of objects.

Two other common spatial partitioning schemes are Binary Space Partitioning (BSP) and Quadtree/Octree Partitioning. All have in common that they recursively subdivide the space into smaller pieces. RDC however, does not construct a tree based structure and must be recomputed every frame. BSP and Quad trees on the other side are best used when precomputed since they are expensive to modify.

So first, we limit the number of collision checks by using spatial partitioning and second, we wrap each object in a bounding shape (e.g. bounding sphere) to quickly eliminate objects that aren't colliding.

RDC has an average time complexity of:
RDC time complexity
While the number of tests using brute-force alone explodes, RDC method increases approximately linearly.

The algorithm

RDC was described by Steve Rabin, in the book Game Programming Gems II: "Recursive Dimensional Clustering: A Fast Algorithm for Collision Detection". Without going into the depth as much, I'll try to recap the basic principles, followed by an working implementation which you can download and try for yourself.

The steps involved in the RDC algorithm are as follows:

Step1: Iterate trough all objects and store the intervals for a given axis in a list data structure. e.g. for the x-axis we store the minimum (open) and maximum (close) x position of the object boundary. An easy way to do this is using displayObjectInstance.getBounds(). The same is done for the y-axis (and of course for the z-axis, if you are in 3D space). Each boundary has to also remember what entity it belongs to and if its a 'open' or 'close' type:

class Boundary
    public var type:String;
    public var position:Number;
    public var object:Object;

Step2: Sort the collected list of boundary objects in ascending order from lowest to highest position:

var boundaries:Array = getIntervals(objects, axis)
boundaries.sortOn("position", Array.NUMERIC);

Step3: Iterate trough the sorted boundary list and store objects with overlapping intervals into groups:

var group:Array = [];
var groupCollection:Array;
var count:int = 0;

for (var i:int = 0; i <  boundaries.length; i++)
    var object:Boundary = boundaries[i];
    if (object.type == "open")
        if (count == 0)
            group = [];

If you are dealing just with one dimension (which would be a strange game...) you would be done.
For this to work in higher dimensions, you have to also subdivide the group along the other axis (y in 2d, y and z in 3d), and then re-analyze those groups along every other axis as well. For the 2d case, this means:

1. subdivide along the x-axis
2. subdivide the result along the y-axis.
3. re-subdivide the result along the x-axis.

Those steps are repeated until the recursion depth is reached. This is best shown with some pictures:

x-axis no intersection
All objects are happily separated, no groups are found.

x-axis intersection
The open/close boundaries of object a and b overlap -
thus both are put into a group.

y-axis no intersection
Even though the intervals of object a and b overlap along the
x-axis, they are still separated along the y-axis.

y-axis reanalyze x-axis
Subdividing along the x-axis results in one group [A, B, C].
Second pass along y-axis splits the group into [B], [A, C].
Subdividing along the x-axis again splits [A,C], so finally we
get the correct result: [A], [B], [C].

Interactive demo

This should give you a better idea what RDC does. The value in the input field defines how many objects a group must have to stop recursion. By lowering the number, you actually increase the recursion depth (slower computation). So you tell the algorithm: "try to make smaller groups by subdividing further!". If you set this value to 1, only one object is allowed per group. If you set the value too high (faster computation) you get bigger groups. This can also be seen as a blending factor between brute force comparison and RDC. Usually you have to find a value in between, so that perhaps each group contains 5-10 object to make this algorithm efficient.

The 's' key toggles snap on/off. This is to show a potential problem that arises when the boundaries of two object share the same position. The sorting algorithm then arbitrary puts both object in a group (e.g. if the open boundary of object is stored before the close boundary of object b in the list), although they aren't colliding, but just touching.
You can resolve the issue in the sorting function, but as we want the algorithm to be as fast as possible, this is not a good idea. Instead, it's best to use a tiny threshold value, which is accumulated to the interval. If the threshold value is positive, the boundaries are 'puffed' in, and object touching each other are not counted as colliding. If the value is negative, touching objects are grouped together and checked for collision later.

'+/-' keys simple increase/decrease the number of objects, and 'd' key toggles drawing of the boundaries, which gets very messy on large number of objects. Green rectangles denote the final computed groups, whereas gray groups are temporary groups formed by the recursive nature of the algorithm and are further subdivided.

Drag the circles around, begin with a small number of object (3-4) and watch what the algo does.

Full screen demo: interactive, animated (Flash Player 9)


- recursive dimensional clustering is most efficient if the objects are distributed evenly across the screen and not in collision.

- it is great for static objects since you can precompute the groups and use them as bounding boxes for dynamic objects.


- the worst case is when all objects are in contact with each other and the recursion depth is very high - the algorithm cannot isolate groups and is just wasting valuable processing time.

- because of the recursive nature the algorithm is easy to grasp, but tricky to implement.

the AVM2 is very fast, so unless you use expensive collision tests or have a large number of objects, a simple brute force comparison with a bounding sphere distance check is still faster than RDC.

Download, implementation and usage

Download the source code here. Please note that it is coded for clarity, not speed.
Usage is very simple. You create an instance of the RDC class and pass a reference to a collision function to the constructor. The function is called with both objects as arguments if a collision is detected. A more elegant solution would use event handlers.

function collide(a:*, b:*)
     // do something meaningful

var rdc:RDC = new RDC(collide);

    // start with x-axis (0), followed by y-axis (1)
    rdc.recursiveClustering([object0, object1, ...], 0, 1);

Have fun!