Aug. 4, 2008
Recursive Dimensional Clustering is a fast algorithm for finding collisions and clusters in sets of data. It scales well from one dimension upwards, making it appropriate for high dimensional scientific applications as well as the obvious application in 2d and 3d games. The algorithm first appeared in the book Game Programming Gems 2 in an entry by Steve Rabin. There is a lot more info and an interactive Flash implementation on this page.
I took the code from Polygonal Laboratory and ported it to Javascript, and then later I took that implementation and ported it to Python. I like to think that my implementation is quite clean, and scalable up to many dimensions with very little effort. It's also fast, as you will see from the demo, detecting about 26 collisions amongst 100 objects per frame at 90 frames per second on my sub-2Ghz dual core machine.
To use it, the programmer needs to inherit the main RDCEntity class and supply 'axis function' methods which return the min and max bounds of the entity in each dimension or axis. The resulting class will have the 'Collide' method called whenever it collides with another entity, and the 'SetGroup' method called when it is detected to be part of a group; see the Polygonal Labs post for more info about what these terms relate to. Note that this does simple axis-aligned bounding-box collisions. If you want more complicated collisions you could use RDC to narrow down which polys are potentially colliding, and then use a poly-poly collision function to see if they're actually colliding. Another approach is to use RDC with multiple bounding boxes per entity. Put the three Python classes below into a file called 'RDC.py' to use them.
The first class represents a 'Boundary' which is what the RDC algorithm uses to determine if things are overlapping in a particular dimension or not. Boundaries are either 'open' (leading edge) or 'closed' (trailing edge).
class Boundary:
def __init__(self, type, position, obj):
self.type = type
self.position = position
self.obj = obj
The next class is the RDCEntity class which the programmer needs to inherit from in order to run the RDC algorithm on their own game entities.
class RDCEntity:
"""
Base class you should override to make things which are RDC collideable.
axisFns is a list of dimension bounding axis conditions.
These must be methods which return the values of each bound on a particular axis for this entity.
"""
axisFns = [["GetLeft", "GetRight"], ["GetTop", "GetBottom"]]
def Collide(self, who):
"""
'who' is the other entity who we collided with.
"""
def SetGroup(self, group, friends):
"""
Set the group identifier number that we are part of.
group is the integer ID.
friends is a list of friends in my collision group.
"""
##################
# Axis functions #
##################
def GetLeft(self):
"""
Example axis function which returns the left bound on the x axis.
"""
The next class makes up the bulk of the actual algorithm. It finds collisions and groups amongst entities. Call it with the DoRDC() method.
class RDC:
def __init__(self, entityClass):
# Array of functions that contain the sort and position functions for each axis
self.axisFns = entityClass.axisFns
# which axis we are currently checking on in this pass
self.idx = 0
# test if there has been a division or not
self.divided = True
def DoSort(self, clusters, axis):
# we're going to replace all clusters with new found ones
newclusters = []
# assume that we won't divide any further
self.divided = False
# for every sub cluster in our group of clusters
for c in clusters:
boundaries = []
count = 0
group = []
# store the intervals for a given axis in a list data structure
for obj in c:
boundaries.append(Boundary('o', getattr(obj, axis[0])(), obj))
boundaries.append(Boundary('c', getattr(obj, axis[1])(), obj))
# sort our list of all boundaries on position
boundaries.sort(lambda a, b: cmp(a.position, b.position))
# finally, make new chunks out of our existing collection
for i in xrange(len(boundaries)):
b = boundaries[i]
# if we find a leading edge, increment our count
# and push it onto our stack of the current group
if b.type == "o":
count += 1
group.append(b.obj)
elif b.type == "c":
count -= 1
# if we have finished finding a group
# push this group onto the stack on new clusters
# empty out our group
if count == 0:
newclusters.append(group)
group = []
# if we're not at the very end of our array then we've just made a new subdivision
if i != len(boundaries) - 1:
self.divided = True
return newclusters
def FindGroups(self, group):
clusters = [group]
while (self.divided):
# find the new clusters
clusters = self.DoSort(clusters, self.axisFns[self.idx])
# select the next axis for subdivision
self.idx = (self.idx + 1) % len(self.axisFns)
return clusters
def DoRDC(self, entities):
groups = self.FindGroups(entities)
for g in xrange(len(groups)):
# Do collision callbacks - test each entity against others in their group
self.BruteForceRectangles(groups[g])
# set which group each entity belongs to
# pass in group friends
[d.SetGroup(g, groups[g]) for d in groups[g]]
def BruteForceRectangles(self, group):
"""
Bruteforce collision detection.
Pass in an array of objects, and an array that looks like this:
[[leading1, trailing1], [leading2, trailing2], [leading3, trailing3]...]
leading1 is the function that returns the leading edge of an axis bounding box.
trailing1 is the function that returns the trailing edge of an axis bounding box.
"""
for i in xrange(len(group)):
for j in xrange(i + 1, len(group)):
collided = True
for a in self.axisFns:
if (getattr(group[i], a[0])() > getattr(group[j], a[1])()):
collided = False
if (getattr(group[j], a[0])() > getattr(group[i], a[1])()):
collided = False
if collided:
group[i].Collide(group[j])
group[j].Collide(group[i])
I tried running the same code without the 'getattr' function, which gets called many times each frame, but I didn't notice any particular speedup so I think it's fine to leave that in there as it makes the code cleaner and more flexible.
Finally here is some test code that uses pygame to showcase the RDC code above. You can save it in a file called testRDC.py for example, and then run it. You will see it processing collisions between 100 random squares as fast as possible. You can click on the window to pause the simulation and examine an example frame; squares of the same colour are in a group/cluster together, whilst squares with a red border are actually colliding.
from random import random, randint
from time import time
from sys import argv, exit
from os import environ
import pygame
from RDC import *
SCREENSIZE = (640, 480)
collisions = 0
class Square(RDCEntity):
def __init__(self):
self.color = [100, 100, 100]
self.border = [0, 0, 0]
self.width = 20
self.height = 20
self.left = random() * (SCREENSIZE[0] - self.width)
self.top = random() * (SCREENSIZE[1] - self.height)
# if we collide with someone
def Collide(self, who):
self.border = [255, 0, 0]
global collisions
collisions += 1
def SetGroup(self, g, friends):
self.color = [(g * 10) % 255, ((g - 50) * 35) % 255, (g * -15) % 255]
# functions for returning bounding box sides
def GetLeft(self):
return self.left
def GetRight(self):
return self.left + self.width
def GetTop(self):
return self.top
def GetBottom(self):
return self.top + self.height
environ['SDL_VIDEO_CENTERED'] = '1'
pygame.init()
screen = pygame.display.set_mode(SCREENSIZE)
pygame.font.init()
fnt = pygame.font.SysFont("Arial", 12)
many = len(argv) > 1 and int(argv[1]) or 100
pause = False
frames = 0
total = 0
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT or event.type == pygame.KEYDOWN:
exit()
if event.type == pygame.MOUSEBUTTONDOWN:
pause = not pause
if not pause:
squares = [Square() for s in range(many)]
start = time()
rdc = RDC(RDCEntity).DoRDC(squares)
elapse = int(1 / (time() - start))
total += elapse
frames += 1
txt = fnt.render(str("%d objects collided an average of %d times at %d fps" % (many, collisions / frames / 2, total / frames)), 1, (0, 0, 0))
screen.fill([255, 255, 255])
[pygame.draw.rect(screen, s.color, (s.left, s.top, s.width, s.height), 0) for s in squares]
[pygame.draw.rect(screen, s.border, (s.left, s.top, s.width, s.height), 1) for s in squares]
screen.blit(txt, (10, 10))
pygame.display.flip()
For interest's sake, below is my earlier Javascript implementation of the same code. Email me for a test HTML file that uses this code:
/*
Recursive dimensional clustering
Pass in an array that looks like this:
[[leading1, trailing1], [leading2, trailing2], [leading3, trailing3]...]
leading1 is the function that returns the leading edge of an axis bounding box.
trailing1 is the function that returns the trailing edge of an axis bounding box.
*/
PodSix.RDC = function(axisFunctions)
{
// Array of functions that contain the sort and position functions for each axis
this.axisFns = axisFunctions;
// which axis we are currently checking on in this pass
this.idx = 0;
// test if there has been a division or not
this.divided = true;
var Boundary = function(type, position, obj)
{
this.type = type;
this.position = position;
this.obj = obj;
}
this.DoSort = function(clusters, axis)
{
// we're going to replace all clusters with new found ones
var newclusters = [];
// assume that we won't divide any further
this.divided = false;
// for every sub cluster in our group of clusters
for (c in clusters)
{
var boundaries = [];
var count = 0;
var group = [];
// store the intervals for a given axis in a list data structure
for (i in clusters[c])
{
obj = clusters[c][i];
boundaries.push(new Boundary('o', obj[axis[0]](), obj));
boundaries.push(new Boundary('c', obj[axis[1]](), obj));
debug.innerHTML += obj[axis[0]]() +"," + obj[axis[1]]() + "</br>";
}
// sort our list of all boundaries on position
boundaries.sort(function(a, b) { return a.position - b.position });
// finally, make new chunks out of our existing collection
for (i = 0; i < boundaries.length; i++)
{
b = boundaries[i];
// if we find a leading edge, increment our count
// and push it onto our stack of the current group
if (b.type == "o")
{
count++;
group.push(b.obj);
}
else if (b.type == "c")
{
count--;
// if we have finished finding a group
// push this group onto the stack on new clusters
// empty out our group
if (count == 0)
{
newclusters.push(group);
group = [];
// if we're not at the very end of our array then we've just made a new subdivision
if (i != boundaries.length - 1)
{
this.divided = true;
}
}
}
}
}
return newclusters;
}
this.FindGroups = function(group)
{
var clusters = [group];
while (this.divided)
{
// find the new clusters
clusters = this.DoSort(clusters, this.axisFns[this.idx]);
// select the next axis for subdivision
this.idx = (this.idx + 1) % this.axisFns.length;
}
return clusters;
}
}
/*
Bruteforce collision detection.
Pass in an array of objects, and an array that looks like this:
[[leading1, trailing1], [leading2, trailing2], [leading3, trailing3]...]
leading1 is the function that returns the leading edge of an axis bounding box.
trailing1 is the function that returns the trailing edge of an axis bounding box.
*/
PodSix.BruteForceRectangles = function(group, axisFns)
{
for (var i = 0; i < group.length; i++)
{
for (var j = i + 1; j < group.length; j++)
{
collided = true;
for (a in axisFns)
{
if (group[i][axisFns[a][0]]() > group[j][axisFns[a][1]]()) collided = false;
if (group[j][axisFns[a][0]]() > group[i][axisFns[a][1]]()) collided = false;
}
if (collided)
{
group[i].Collide(group[j]);
group[j].Collide(group[i]);
}
}
}
}
