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?

Answer

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).