Collision Detection in Box2D

Question

So I'm using Box2D for collision detection in a game. I have a tilemap that contains information on the terrain: for now it's just a char[][] that has either road or grass. Now, at the start of each level I wanted to create rectangles to describe the different terrains, but I wanted these rectangles to be optimized and apparently that takes quite an algorithm.

My first approach was to create an individual terrain for EVERY tile in the map at the start of the level. The FPS was reduced to 5.

My second idea was to simply create the different rectangles for terrains as the player moved along the map, deleting the rectangles that were out of view. Although it would still be a lot of rectangles, it would be considerably less.

I haven't attempted the second method yet, but I want to know: is there any easy way for me to efficiently perform collision detection against terrain with a large tilemap?

Thanks.

Answer 1

Try combining tiles. For example, if you have 16 rectangular collision volumes for 16 tiles like so...

* * * *
* * * *
* * * *
* * * *

You can obviously combine these tiles into one large rectangle.

Now, things get more difficult if you have tiles in a weird arrangement, maybe like this...

**---
****-
*--**
-*-*-

I just recently solved this problem in my game using a quad tree and sweep and prune. (Sweep and prune isn't strictly necessary, its an optimization.)

Quad tree partitions your square tiles into bigger rectangles, then you iterate over the rectangles the quad tree produces, and combine them if they have the same width, then iterate over them again and combine them by similar heights. Repeat until you can't combine them anymore, then generate your collision volumes.

Here's a link to a question I asked about a more optimal reduction. I probably won't implement this as it sounds difficult, and my current approach is working well.

Some code:

do {
    lastCompressSize = currentOutput;
    this.runHorizontalCompression(this.output1, this.output2);
    this.output1.clear();
    this.runVerticalCompression(this.output2, this.output1);
    this.output2.clear();
    currentOutput = this.output1.size;
    iterations += 1;
}while (lastCompressSize > currentOutput);

public void runHorizontalCompression(Array<SimpleRect> input,
        Array<SimpleRect> output) {
    input.sort(this.xAxisSort);
    int x2 = -1;
    final SimpleRect newRect = this.rectCache.retreive();
    for (int i = 0; i < input.size; i++) {
        SimpleRect r1 = input.get(i);
        newRect.set(r1);
        x2 = newRect.x + newRect.width;
        for (int j = i + 1; j < input.size; j++) {
            SimpleRect r2 = input.get(j);
            if (x2 == r2.x && r2.y == newRect.y
                    && r2.height == newRect.height) {
                newRect.width += r2.width;
                x2 = newRect.x + newRect.width;
                input.removeIndex(j);
                j -= 1;
            } else if (x2 < r2.x)
                break;
        }
        SimpleRect temp = this.rectCache.retreive().set(newRect);
        output.add(temp);
    }
}

public void runVerticalCompression(Array<SimpleRect> input,
        Array<SimpleRect> output) {
    input.sort(this.yAxisSort);
    int y2 = -1;
    final SimpleRect newRect = this.rectCache.retreive();
    for (int i = 0; i < input.size; i++) {
        SimpleRect r1 = input.get(i);
        newRect.set(r1);
        y2 = newRect.y + newRect.height;
        for (int j = i + 1; j < input.size; j++) {
            SimpleRect r2 = input.get(j);
            if (y2 == r2.y && r2.x == newRect.x
                    && r2.width == newRect.width) {
                newRect.height += r2.height;
                y2 = newRect.y + newRect.height;
                input.removeIndex(j);
                j -= 1;
            } else if (y2 < r2.y)
                break;
        }
        SimpleRect temp = this.rectCache.retreive().set(newRect);
        output.add(temp);
    }
}