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.)

  • \$\begingroup\$ How is the array or vertices represented? If it's an arbitrarily rotated box then the solution could cover any kind of convex polygon. \$\endgroup\$ – 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.

| improve this answer | |

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.