Collision Detection with MANY objects

问题:

I mainly focused on the Graphics aspects to create a little 2DGame. I've watched/looked at several tutorials but none of them were that pleasing. I already have a player(a square) moving and colliding with other squares on the screen. Gravity etc. Are also done.

If there are only that much objects as seen on the screen (30*20), everything works perfectly fine. But if I increase it to let's say 300*300 the program starts to run very slow since it has to check for so many objects.

I really don't get how games like Minecraft can work with ALL THOSE blocks and my program already gives up on 300*300 blocks.

I already tried to ONLY check for collisions when the objects are visible, but that leads to the program checking every single object for it's visibility leading to the same problem. What am I doing wrong? Help appreciated.

I'll post some code on how I handle the collisions.

player.collision(player, wall);

public void collision(Tile object1, Tile[] object2){
    collisionCheckUp(object1, object2);
    collisionCheckDown(object1, object2);
    collisionCheckLeft(object1, object2);
    collisionCheckRight(object1, object2);  
}

public void collisionCheckDown(Tile object1, Tile[] object2){

    for (int i = 0; i < Map.tileAmount; i++){
        if(object2[i] != null && object2[i].visible)
        {
            if(object1.isCollidingDown(object2[i])){
                object1.collisionDown = true;
                return;
            }

        }
    }       
    object1.collisionDown = false;
}

public void compileHullDown(){

     collisionHull = new Rectangle((int)x+3, (int)y+3, width-6, height);
}

int wallCount = 0;
    for (int x=0;x<Map.WIDTH;x++) {
        for (int y=0;y<Map.HEIGHT;y++) {

            if (Map.data[x][y] == Map.BLOCKED) {
                wall[wallCount] = new Tile(x * Map.TILE_SIZE, y *  Map.TILE_SIZE);
                wallCount++;
            }
        }
    }

回答1:

The usual approach to optimize collision detection is to use a space partition to classify/manage your objects.

The general idea of the approach is that you build a tree representing the space and put your objects into that tree, according to their positions. When you calculate the collisions, you traverse the tree. This way, you will have to perform significantly less calculations than using the brute force approach, because you will be ignoring all objects in branches other than the one you're traversing. Minecraft and similar probably use octrees for collision (and maybe for rendering too).

The most common space partition structures are BSP-Trees, kd-Trees (a special type of BSP-trees). The simpler approach would be to use a uniform space partition for the start - split your space in axis-aligned halves.

The best resource on collision that I have discovered is this book. It should clarify all your questions on the topic.

That's if you wanted to do it right. If you want to do it quick, you could just sample the color buffer around your character, or only in the movement direction to determine if an obstacle is close.

回答2:

As Kostja mentioned, it will be useful for you to partition your space. However, you will need to use QuadTrees instead of Octrees as you are only in 2D not 3D. Here are is a nice article to get you started on QuadTrees.

回答3:

You can cut your overhead by a factor of 4 by, instead of calculating collisions for up/down/left/right, calculating collisions once and using the relative positions of the two objects to find out if you hit a floor, wall, or ceiling. Another good idea is to only pay attention to the objects that are nearby - maybe once every 0.25 seconds make a list of all objects that are probably close enough to collide with in the next 0.25 seconds?