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<GameObj*> objectsVector

to hold all objects and a

std::multimap<Point2D, GameObj*> 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 < objectsVector; ++i) {
GameObj* currObj = objectsVector[i];
for (
int x = (int)currObj->getX() - (int)currObject->getWidth();
x < currObj->getX() + 2*currObj->getWidth();
x++
)
{
for (
int y = (int)currObj->getY() - (int)currObject->getHeight();
y < currObj->getY() + 2*currObj->getHeight();
y++
)
{
pair< multimap<Point2D, GameObj*>::iterator, multimap<Point2D, GameObj*> > \
range = objectsMap.equal_range(Point2D(x, y));
for (
multimap<Point2D, GameObj*>::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-x
curr-y > 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<Point2D, GameObj*> ObjectSpace;
void World::checkForCollisions()
{
for (int i = 0; i < objectsVector; ++i) {
GameObj* currObj = objectsVector[i];
for ( ObjectSpace::iterator ito = objectsmap.begin(); ito != objectsMap.end(); ito++ ) {
const GameObj* test = it->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.

• So the outsideBoundingBox() function replaces the 2 for() loops right? And is there a way around re-initializing the map in order to update the keys (the Point2D's), meaning, can keys be updated in an std::multimap WITHOUT creating a new object? – rcplusplus Jul 12 '12 at 18:06
• If the only purpose of the map is to do your spatial collision detection, then you can do without it altogether - just replace it with something like a list. Otherwise, I think you're out of luck (those keys are const for a good reason!), unless most of the objects aren't moving, in which case you can try erasing/re-inserting elements from the existing map without creating a new one. – Glenn Rogers Jul 13 '12 at 8:57
• yeah but then to check collisions, I have to iterate through every single item! Is there really no way to update keys or something? – rcplusplus Jul 13 '12 at 18:17
• Is it a real problem, or a problem that you think might exist (otherwise known as Beware of Premature Optimisation)? If your objects are 50x50, with 250 that you're checking against, you've just reduced your searchspace by 10x. Get it working the simplest way first, then optimise if required. – Glenn Rogers Jul 14 '12 at 6:32