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.

I'm trying to do collision detection on a large number of entities of greatly varying size in an unbounded space. The entities are circles, so it's relatively easy to check if two are colliding. However, with a large number of entities the simulations slows down a lot when I code it to check every entity against every other (for n entities, I believe it is n*(n-1)/2 checks, way too many!) Here's my though process so far:

First, I considered using a grid of some sort, like described in steps 1-2 of the answer here: Fast, accurate 2d collision

There are, however, a few problems with this:

1) It is an unbounded space. Where do I start and end the grid? How do I determine the size of each square in the grid in a world where some objects are literally tens of millions times larger the other objects?

2) Even if I somehow manage to adjust the size of the grid every frame without using too much processing power, so that it adjust to fit the most distant objects, (unlikely that I could do this efficiently) this is still not a solution. If tons of objects are clustered in a 10,000x10,000 space, and one object goes shooting off into space 100 billion units of distance away, the grid would "zoom out", leaving all of the objects in the smaller 10,000x10,000 space in one square, which would defeat the purpose of making a grid in the first place.

For these reasons, I'm thinking that a simple grid is not the best idea...

I looked at BSP's, and I admit that I don't fully understand the concept, but it seems like it does not apply well to my situation (especially since I am using circles and BSP seems better suited to a more complicated polygonal world).

Quad trees seem promising (something like this perhaps: http://www.youtube.com/watch?v=qJJnzSLrC1E) but I foresee at least two potential issues:

1) I can calculate the "farthest away objects" each frame to give calculate GreatestXValue, LeastXValue, GreatestYValue, and LeastYValue, for each frame. From that I have a rectangle to work with that contains all entities. However, I will have to redo this each frame, which means that I have recreate the the entire quadtree each frame: no shortcuts on calculations done in previous frames. Is this a problem or do most game/simulation programmers have to completely recreate the quadtree each frame anyway?

2) (Probably the bigger problem) How do I handle a massive object in the vincinity of many small objects? Think about many circles with radius 5 being very close to, resting against, or colliding with a circle with radius 100,000. That massive object will be in many, many grid squares, and it seems to me that the situation would force the creation of a tree that is far too broad and deep.

Am I on the right track with my thought process? Where do I go from here? Thank you very much for your time and help!!

share|improve this question
    
Binary space partitioning DOES apply to circles perfectly well, and it is the only way to reduce your collision detection's complexity below O(n^2) to O(log(n)). If you do not fully understand them, study more. Note that quad trees are simply another form of BSP. –  Seth Battin Jul 28 '13 at 17:00
    
I was debating this with a friend last night. How to do collision like that. My idea would be to let the entities report to an event system when two of them collide so you don't check for entity collision every frame for every object that way. I don't know if this would be effective or not though. –  Vipar Jul 28 '13 at 17:08
    
@SethBattin I will go back and study BSP more. I definitely see the similarity between BSP and quad trees. Are you recommending that I use BSP over quad trees in my situation? (Despite their similarities, they definitely are two different concepts). When you said BSP was the only way to achieve that lesser complexity did you mean that I could achieve that low level of complexity with quad trees too or did you mean that would BSP be faster than quad trees? Which method do you recommend that I go with in my situation? I really appreciate your help! –  MindSeeker Jul 28 '13 at 20:34

2 Answers 2

You are on the right track, but you didn't reach your goal, well let me explain

Spartial schemes

Fixed grid with Hashtable

The solution to your first problem is a spartial hashing scheme, you divide your world space into a grid but you save the content of the grid elements in a hashtable. The index for the hashtable is calculated from the address of the grid element.

For example

Index = xOffset + 5*yOffset

(note the prime, its important)

You also need to check non empty grid elements against their neightbors.

A way to reduce the calculation time for the collision detection phase is to check only against neightborcells in one direction, a image says more than thousand words:

unoptimized detection scheme:

 | C | C | C
 +---+---+---
 | C | X | C
 +---+---+---
 | C | C | C

Optimized detection scheme:

 |   |   |
 +---+---+---
 |   | X | C
 +---+---+---
 |   | C | C

X : grid element against which to check collisions with...

C : collision grid element

So you save more than half of the checks. This works also in 3 dimensions.


To use the Fixed grid with Hashtable scheme with very large/very small objects you basically do have two choices:

  1. make the grid element size as large as the biggest object
  2. use a space division scheme for the grid elements which are stored in the hashtable, i illustrate it with a picture:

    |       |   |   |        |
    |       +---+---+        |
    |       |   |   |        |
    +-------+---+---+--------+
    |       |       |        |
    |       |       |        |
    |       |       |        |
    

    the cells with large elements are not subdivided and the cells with small elements are subdivided.

    This is actually a combination of the hashing scheme and the spartial subdivision scheme and combines the advantages (and disadvantages).

For more information of collision detection algorithms you can also check out these questions

share|improve this answer
up vote 0 down vote accepted

Sorry it's been so long; I forgot to come back and answer the question. Fixed grid with hashtable was a really good explanation, and I really appreciate the time and help, but it doesn't work as well for a world where the bounds are changing. (keyword here is fixed, this is an unbounded space so it is incompatible unless if I misunderstood the concept).

I ended up going with quadtrees. To answer my concerns above:

1) You pretty much have to recalculate the whole tree anyway on each timestep.

2) A large object does NOT go into many small squares. Instead, it resides in the smallest higher node (i.e. bigger square) that it can completely fit into. You wouldn't want to have to create thousands of small nodes just because you have one massive object!

Once the tree is created, for collision, when you are looking at object X, you check X not only against other objects in it's node, but against all objects in all nodes "below" it (i.e. all objects in smaller squares that are contained by X's larger square). (You can also check up the tree instead of down of course, I just chose to check down rather than up)

share|improve this answer

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.