Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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:

Hash grid, or just plain grid

Sort and sweep (sweep and prune)

Hope that helps!

share|improve this answer
2  
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
2  
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. –  Byte56 Nov 30 '12 at 16:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.