# Space-efficient data structures for broad-phase collision detection

As far as I know, these are three types of data structures that can be used for collision detection broadphase:

1. Unsorted arrays: Check every object againist every object - O(n^2) time; O(log n) space. It's so slow, it's useless if n isn't really small.

for (i=1;i<objects;i++){
for(j=0;j<i;j++) narrowPhase(i,j);
};

2. Sorted arrays: Sort the objects, so that you get O(n^(2-1/k)) for k dimensions O(n^1.5) for 2d and O(n^1.67) for 3d and O(n) space.

Assuming the space is 2D and sortedArray is sorted so that if the object begins in sortedArray[i] and another object ends at sortedArray[i-1]; they don't collide

3. Heaps of stacks: Divide the objects between a heap of stacks, so that you only have to check the bucket, its children and its parents - O(n log n) time, but O(n^2) space.

This is probably the most frequently used approach.

Is there a way of having O(n log n) time with less space? When is it more efficient to use sorted arrays over heaps and vice versa?

• How can an algorithm use O(n^2) space but only O(n log(n)) time? That makes no sense. – Mikola Dec 14 '14 at 15:38

If you want a memory efficient data structure then don't forget the almighty hash table for maintaining an implicit grid for spatial partitioning!

Simply put, you place a grid over your simulation space and implicitly maintain it in a hash table. The table will only contain active sectors (sectors with one or more colliders in it) with their keys corresponding to their grid index using whatever hash function that works for the grid dimensions. This can save a lot of memory depending on your grid size since you don't have a tree or array of empty sectors. So each update, you perform broad phase collision detection by simply clearing the hash table and iterating through each collider and placing it into it's corresponding sector. If it's a uniform grid you can derive the sector's index that it belongs to using the collider's coordinates and sector dimensions. Then for inner phase collision detection simply iterate through the hash table's sectors and check all the colliders in each sector and it's neighbors for collisions.

I just wanted to say your first example is slightly incorrect in that it will check i against j and j against i as well. You really want to check pairs only once:

for (i=0; i<objects-1; i++)
{
for (j=i+1; j<objects; j++)
{
narrowPhase(i,j);
}
}


This is then O( (n-1) n / 2 ).

As for your main question, there are a number of ways to handle broadphase, the most popular two are:

• For the first - constants don't change big O, and I'm only checking for i in 1 to length, and j for 0 to i. – Marian Ivanov Nov 30 '12 at 14:00
• My apologies, I didn't see that j<i for some reason :) – wildbunny Nov 30 '12 at 15:04
• This answer (without the incorrect correction) is just two links, without much explaination. "Just links" answers are poor because if the link were to change, this answer would be useless. – MichaelHouse Nov 30 '12 at 16:17