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))
fork
dimensionsO(n^1.5)
for 2d andO(n^1.67)
for 3d andO(n)
space.Assuming the space is 2D and
sortedArray
is sorted so that if the object begins insortedArray[i]
and another object ends atsortedArray[i-1]
; they don't collideHeaps 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, butO(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?