# How can I implement fast, accurate 2D collision detection?

I'm well aware of how to detect if two or more 2D objects collide but I'm interested in how to decide whether to check for a collision. In previous projects, I just had every object check against every other object (I know, O(n^2) level of stupidity) and it created a less than fluid gameplay.

Various forums hail the greatness of Quadtrees, B-Trees, and any other kind of tree or structure you can think of.

What is the most efficient structure for determining whether a collision should be checked?

• One thing you may want to consider is only checking collisions for objects that have moved, and the only the objects that are close to you. My current system works well (hundreds of thousands of objects)- and that's all I'm doing. – ultifinitus Oct 7 '11 at 20:31
• I think gamedev.stackexchange.com/questions/14369/… could help you alot. it was originally meant for and algorithm for parallel processing but I think the same algorithm could also improve single threaded applications. – Ali1S232 Oct 7 '11 at 20:57
• @ultifinitus That's essentially what I'm asking about. How do I determine which objects are nearby without iterating through every object and checking it's position? – Mike Cluck Oct 7 '11 at 22:24
• Mike, you can email me for some specific code that I used, it's in c++- or I can give you the basic structure, though it may get rather ambiguous and complicated because of that. – ultifinitus Oct 8 '11 at 6:38
• It's not a duplicate because I was asking what kind of structure is best suited for determining whether we should bother checking for a collision. That other question was asking about transparent vs. non-transparent collisions. Not to mention, this question was asked about a year before the one you linked to. – Mike Cluck Jan 26 '14 at 21:30

## 3 Answers

For a 2d game, unless the 2D objects have a very heavy distribution to one side of your map, a uniform grid is almost always the way to go. The memory complexity is straight forward, (proportional to the dimensions of your map), and with a reasonable distribution, has O(1) look-up time and an average of log(numberOfObjects / (rows * columns)) ^ 2 intersection tests done per cell. You might decide to only check cells which have had an object move in them, which makes static geometry much more efficient. It's easy to modify a uniform grid on the fly, (much less of a pain than in tree based solutions), and it is simpler to implement. The only time I would say not to use it in a 2D game is when the memory requirements of a uniform grid become too large, (say a space sim where the levels are sparse but enormous).

• How does this solution deal with objects that border 2 or 4 grid cells? – ashes999 Jan 10 '12 at 23:18
• Any cell the object overlaps, it is considered to be in, so an object can be in multiple cells. Most spatial data structures will deal with the issue of overlaps in a similar way. – Darcy Rayner Jan 10 '12 at 23:27
• Wow, that's preetty smart. +1 Cheers dude. – ashes999 Jan 11 '12 at 14:31

2D Physics engines such as Box2D and Chipmunk, make heavy use of a spatial Hash Map

see http://chipmunk-physics.net/release/ChipmunkLatest-Docs/#CollisionDetection for reference. The chipmunk demos include a really good spatial hash visualizer which makes it really clear how they technique works.

If your world has one very "long" dimension (call it X), compared to others, you can keep the objects in an ordered-list which you can re-sort as they move, and then collision detection means only checking for objects which overlap in the X axis.

Another possibilty is to keep active/passive lists of objects, and don't bother with the passive objects (which aren't moving at all).

If they are all medium-sized objects which are visible to the player on the screen, everything vs everything is probably not too bad.

Other than that, I'm with Darcy, a uniform grid is good.