Collision detection between many objects

Question

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, lets 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?

Answer 1

It seems that you didn't try the 'brute' force approach yet. Try checking for all objects in a O(n²) algorithm, it may solve your issue.

These techniques that you are mentioning, like a Sweep and Prune, in their worst case, will check all the objects too. Before going to this complex trees way, I suggest you to use a simple grid to se if you get any improvement (be sure to do the most simple way first for comparisons).

In this algorithm you are proposing, you're making hops of one unit from x to x+width (same thing for y), then checking if there's any object on all this points. You're checking more then necessary, but I'm not sure if i quite understood your idea. You should make a better use of your objects geometry to make few calls to checkCollision(currObj, it->second).

Real Time Collision Detection as mentioned by raigan, can help you a lot on this task.

Answer 2

I wanted to post this as a comment to Vandell's answer, but I don't have the privilege to comment yet I guess.

As he said, you probably didn't try the brute force approach yet. I'm using it in my game, and on a Intel i5-750 @2.67GHz, it is running smoothly with no problem with around 300-400 entities. (Might be able to support even more, didn't test it.)

If your target platform is a mobile device, then I don't know how well it will run however.

This is my code:

public void detectCollision(float tmpx, float tmpy) {

Rectangle tmpRect = this.getRectangle(tmpx, tmpy);

if (tmpRect == null) //If the entity doesn't have a bound box
    return;

for (int i = 0; i < MainGameState.objectList.size(); i++) {
    if (!this.equals(MainGameState.objectList.get(i)))
      if (tmpRect.intersects(MainGameState.objectList.get(i).getRectangle())) {
            MainGameState.objectList.get(i).doCollision(this);
            return;
       }

}

if ((tmpx > 0 && tmpx < 3600) && (tmpy > 0 && tmpy < 3000)) { //Within map bounds
     this.setX(tmpx);
     this.setY(tmpy);
     jumpSpeed += CConstants.GRAVITY * weight;
     return;
}

I think your problem, which is the same one I had before I fixed it, is that you are recalculating the bound box every iteration? I'm too rusty with pointers and it's kinda late here.

Try you're using an AABB bound box (if you aren't), in which case you just need to create it one time at the game initialization, and then just update its center coordinates to that of the bound object, like this for example:

public void init(GameContainer gc) throws SlickException {
    rectangle = new Rectangle(this.getX(), this.getY(), currentAnimation.getCurrentFrame().getWidth(), currentAnimation.getCurrentFrame().getHeight()); //Assumes that all the animation frames will be the same size.

}

public Rectangle getRectangle() {

    rectangle.setX(x);
    rectangle.setY(y);
    return rectangle;
}

public Rectangle getRectangle(float tmpx, float tmpy) {

   rectangle.setX(tmpx);
   rectangle.setY(tmpy);

return rectangle;
}

My game is still in the pretty early stages in development, as so I can't guarantee the scalability of the code when more things are being done, but as I said I'm getting 60fps with Vsync, and around 200-300fps without it.

Feel free to look at my source code in github. But be warned, it's horrible code. :P

Answer 3

Christer Ericson's "Real-Time Collision Detection" is probably the best game-programming-related book I've found; read the chapter on grids/spatial hashing and you'll have several options and ideas for how to approach broad-phase collision detection.

Answer 4

Something I have wondered about but I have not tested. It's O(n) but an expensive constant:

Maintain a separate copy of the screen. When you move an object on the real screen it moves on the other screen also. It's just the other screen draws only collidable objects and draws them in color # (object number). If you try to draw on anything but a black pixel you collided with object # (pixel color).