Space-efficient data structures for broad-phase collision detection
- by Marian Ivanov
As far as I know, these are three types of data structures that can be used for collision detection broadphase:
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);
};
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
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?
