Fast 2D collision detection in an unbounded space

Question

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!!

Answer 1

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

• optimizing-collision-engine-bottleneck

Answer 2

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)