how about using sectors to further reduce the number of checks? if two cubes are not in neighboring sectors, its impossible for them to collide (assuming your sectors are larger then a cube can move per frame). of course you need to sort the cubes first. but once they are initially sorted you never have to do it again since when a cube crosses a sector, you just pop it from the previous sector and push it to the new sector. straddling cubes might be slightly tricky, but some research will solve things pretty well.

hello_there: why dont you ust do some research and try it out?

Just wanted to point out that the number of checks would actually be 850 "combination" 2, which is 850!/2!(850 - 2)! , or 360825 checks. That's using the fact that A to B = B to A. Gotta love statistics

[edited by - Zipster on May 6, 2002 7:15:53 PM]

Assuming that the cubes are all of the same size, a simple distance check could allow you to avoid checking for a collision all together. This wouldnt change the big-O, but would drastically reduce the calculating. Plus, there are a million other things you could do to cut down on extra processing. Thats my two cents.