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")
    {
        count++;
        group.push(object);
    }
    else
    {
        count--;
        if (count == 0)
        {
            groupCollection.push(group);
            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)

pro's

- 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.

con's

- 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);

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

Have fun!
Michael

A flash BitVector class

What’s a BitVector ?

BitVector is composed of two words, bit and vector:

A bit refers to a digit in the binary numeral system (base 2). It’s like a switch, it can be either on (1 or true) or off (0 or false), which is a boolean value.

When referring to a vector, you might think of a vector used in linear algebra which has both magnitude and direction, but in this case it defines a structure which is basically a resizable array. With this little background information we can say that a BitVector is meant to pack bit values (or booleans) as close as possible into an array so that no space is wasted.

Most compilers and flash use a larger data type (e.g. an integer) in place of a boolean. This is done because it is more efficient to send a fixed amount of data at a time through the memory and to the processor (e.g. x86 machines can only send data in packs of 32bits). Thus storing a boolean always waists some memory.

We can overcome this limitation by using bitwise operators in flash to modify the bits in a number. Since flash internally represents a number by an 32bit signed integer (double word) we can store up to 31 boolean values (0..31) in it.

How this works

The class uses a native array to store integers in it, whereas each integer will hold the bit values. The important details are found inside the setBit() and getBit() function.

Both functions need the array index for the integer and the position of the bit inside the number. The array index is computed by dividing the bit index by the data size:

arrayIndex = int(bitIndex / dataSize)

For example, if we want to set a bit at index 42 in the BitVector, we get arrayIndex = int(42 / 31) = 1. To determine the bit position we modulo the bit index by the data size, which simply wraps the bit index into the range of the data size.

bitPos = bitIndex % dataSize

Referring to the example above: bitPos = 42 % 31 = 11.

Now the bitwise part:

To set a bit shift a 1 into the bit position giving a 1 at the same position as the bit to write. Assuming the bit position is 4, the result would be:

1 << bit = 1 << 4 = 1*2*2*2*2 = 1* 2^3 = 10000 (binary).

Then logically or (|) it with the integer, which only returns 0 when both operands have a zero at the same position:

1 << bitPos 10000
integer     00110
result |    10110

To get a bit shift up a 1 bit position, which gives a 1 at the same position as the bit to retrieve. Then binary and (&) it with the integer and shift the number back down bit positions to get a one or a zero. The binary & operator returns 1 only if both the operands have a 1 in the same position.

1 << bitPos 10000
integer	    10110
result &    10000

result >> bitPos = 1

Finally to clear a bit without affecting all the other bits, the bit to get cleared must be 0, and every other bits need to be 1. So again shift a 1 into the bit position to clear, but this time apply the binary not operator (~) to reverse every bit. Then the binary& operator clears the bit.

 1 << bitPos   10000
(1 << bitPos)~ 01111
integer	       10110
result	&      00110

Why should this be useful ?

If storing thousands of values, the BitVector is more size efficient and thus reduces memory consumption. I admit it's hard to reach the limit now, but with AS3 we will see much more complex applications. You also get less traffic and therefore a faster response when sending bit packed values over the network.

Setting and getting a bit involves one division (to get the correct array index), one modulo (to get the correct bit position), and finally two bit operations, to modify the bits. So it's not as fast as an native flash array.

The BitVector class

public function BitVector(size:Number)

The constructor in my implementation takes only one parameter: the total number of bits.
For efficiency's sake you have to manually resize the BitVector with the resize() function, which automatically expands or truncates the BitVector.

The syntax to get/set a boolean value:

myBitVector.setBit(4, true); // set bit at index 4
trace(myBitVector.getBit(4)); // outputs 1

myBitVector.setBit(4, false); // clear bit at index 4
trace(myBitVector.getBit(4)); // outputs 0

You can also clear or set all bits in one step by using the clearAll() or setAll() function.
Here you can download (right click & save as) my BitVector class.

That's it !
Have fun, Michael