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
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)
No comments:
Post a Comment