Array-based tilemaps and bounding box (aabb?), how to do efficient tile collisions?

Question

At one point in my game I had every tile as it's own object, so that I could use standard AABB collision testing easily. I later realized this was horrible for performance and simply made my tiles be an array of numbers denoting which 16x16 segment to use.

However, this also means that I can no longer use standard AABB collision testing for tilemaps, since tiles don't have their own AABBs anymore. The first method I've tried is using hotspot collisions (per-pixel, see this page), but I'd really like to instead use some kind of bounding-box based collision testing instead of manually placing hotspots. The only methods I can think of are horrible for performance; using separate AABBs for tiles (already tried) and checking every singe pixel inside a bounding box / AABB for collision with a tile (likely even worse for performance).

What is a way that I can detect collisions using my character's bounding box while keeping my tiles simply an array of numbers, and not having a large performance impact?

Answer 1

The reason there isn't a standard AABB or partition strategy for tile-based maps is that it's already easier to detect collisions against it than using AABBs.

static int TILE_WIDTH=16, TILE_HEIGHT=16;
Tile[,] map;

class Character { 
   int width, height;
   int x, y;
   bool isColliding () { 
       for(var i = this.x; i < this.x + this.width; i += TILE_WIDTH)
       for(var j = this.y; j < this.y + this.height; j += TILE_HEIGHT) {
           if (map[x / TILES_PER_UNIT, y/TILES_PER_UNIT] != Tile.Empty) {
               return true;
           }
       }
       return false;
   }
}

Answer 2

I don´t see a problem having an AABB for your Tiles (if you don´t want to have 1 AABB for each Tile in your game you can use Flyweight pattern to minimize the memory usage(but only if you want to have the tiles of the same size)- Flyweight pattern describtion). But I think keeping an AABB for every tile is not a big memory hurt these days.

To minimize the number of the collision checks I would suggest you some kind of spatial partition (there are many ways to implement it) - Spatial partition explanation. Basically this drastically helps to improve the performance because instead of checking collisions between all the objects you check the collision only between the objects in the same grid.

Answer 3

I know of a program called Tiled that allows you to easily create a tile map. The program features object layers, which can allow you to customize bounding boxes. You can use these to create a shape around an entire group of tiles, so that instead of checking for each individual tile, you can collide with the entire group as a whole. You'll need to figure out how to load TMX files, but they are in XML format so it's really not that hard.

Link here