http://lab.polygonal.de/articles/recursive-dimensional-clustering/
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:
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:
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:
All objects are happily separated, no groups are found.
The open/close boundaries of object a and b overlap -
thus both are put into a group.
Even though the intervals of object a and b overlap along the
x-axis, they are still separated along the y-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!
Mike