Collision-checking optimizations

If I'm working in a 2D environment and have hundreds of objects, brute force collision-checking would be out of the question, but would my method below work?

For example, let's say I have a

std::vector objectsVector

to hold all objects and a

std::multimap objectsMap

(basically a map which takes a 2D point representing a GameObject's coordinate as a key and the object itself as a value)

to get any object associated with a point. If I want to do collision-checking for an object, I could use a function that looks like this:

void World::checkForCollisions()
{
    for (int i = 0; i getX() - (int)currObject->getWidth(); 
                x getX() + 2*currObj->getWidth();
                x++
            ) 
        {
            for (
                    int y = (int)currObj->getY() - (int)currObject->getHeight(); 
                    y getY() + 2*currObj->getHeight();
                    y++
                ) 
            {
                pair::iterator, multimap > \
                  range = objectsMap.equal_range(Point2D(x, y));
                for (
                        multimap::iterator it=range.first; 
                        it!=range.second; 
                        ++it
                    ) 
                {
                    if (checkCollision(currObj, it->second)) 
                        currObj->handleCollision(it->second);
                }
            }
        }
    }
}

Is this even remotely efficient? Because it doesn't seem to be. It basically just scrolls through the vector and checks to see if it collides with nearby objects. Problem is, I have to use 2 containers AND when things move, I have to pretty much reinitialize the entire map, because the keys would be invalid! Is there any way to improve this collision-checking function, or should I scrap the whole thing altogether and use spatial hashes or a quad-tree? Any suggestions would be helpful.

If I'm understanding things correctly, (x,y) is an anchor point of your object (say, bottom left), and you're iterating over every single point that could be an anchor point for an object that it's in collision with, then checking if it's an actual anchor point of an existing object.

My suggestion (assuming that your shapes are small and circle/box-like) would be to check for exclusion rather than inclusion. If you consider that each obj has a bounding rectangle around it, then do the following checks:

curr-x > test-x + test-width
curr-x + curr-width  test-y + test-height
curr-y + curr-height <= test-y

If any of these are true, then you're no longer interested.

So your function then becomes something like:

typedef std::multimap ObjectSpace;
void World::checkForCollisions()
{
    for (int i = 0; i second;
            if ( test == currObj ) continue;
            if ( outsideBoundingRectangle( currObj, test ) ) continue;
            if ( checkCollision( currObj, test ) ) {
                    currObj->handleCollision( test );
            }
        }
    }
}

This may be enough for a reasonable speed.

StackExchange Code Review Q#13556, answer score: 2