# How can I determine which tiles in a tilemap an oriented bounding box (OBB) overlaps?

I need to detect collisions between an oriented bounding box and a static tile map. My tile map class looks something like this:

function Tilemap(width, height, tiles) {
this.width = width;        // Width of the map in tiles
this.height = height;      // Height of the map in tiles
this.tiles = tiles;        // 1D array containing tiles, grouped by row
}

Tilemap.prototype.getTile = function (x, y) {
return this.tiles[y * this.width + x];
};

Tilemap.prototype.setTile = function (x, y, value) {
this.tiles[y * this.width + x] = value;
};


My question is this: How can I determine which tiles an OBB, represented as an array of vertices, overlaps?

(I am writing in JavaScript but answers for any language would be appreciated.)

• How is the array or vertices represented? If it's an arbitrarily rotated box then the solution could cover any kind of convex polygon. – Jay Dec 20 '17 at 0:37

You can approach this as a polygon rasterization problem.

Take the four lines that make up the edges of your bounding box and rasterize them to your tile grid using a line drawing algorithm like eg. DDA.

For each row of tiles marked this way, keep track of the leftmost and rightmost tile in that row that any of your lines touch. Then you can fill the box by including all tiles between these left & right extremes.

I guess you could do something like this:

var x_min = Math.floor(v[0] / this.width),
y_min = Math.floor(v[1] / this.height),
x_max = Math.ceil(v[2] / this.width),
y_max = Math.ceil(v[3] / this.height);


In this case, the tiles are all the ones from getTile(x, y) where x is between x_min and x_max and v is your selection box.

• Maybe I'm missing something but wouldn't this only work if the box was axis-aligned? – Jack Dec 19 '17 at 17:03
• Yes, I guess an oriented box is different to an AABB which I thought you were asking about. – Jay Dec 20 '17 at 0:35