# Tile map optimization algorithm

I've read this artical on tilemap optimization https://www.scirra.com/blog/ashley/3/tech-blog-tilemap-tidbits and wondering what algorithm is used to achieve something like this.

I'm wondering how they convert an array of tiles into simplified rectangles that use the same texture. To optimize rendering

• Have you messaged the creator? And what aspect of it are you referring to? – Savlon Mar 17 '15 at 11:15
• This is a valid route to try, but note that if your case looks similar to this reference then you may be solving the wrong problem. Modern GPUs won't blink at the tiny amount of geometry in a typical tile-based game, so it's really draw calls you want to minimize. The linked method reduces the calls to 22, but you could put all of these tiles into a single sprite sheet and draw the whole map in one call. In this case, you'd keep one quad per tile (skipping the optimization you're asking about) and use texture coordinates to control which part of the sprite sheet is used in each square – DMGregory Mar 17 '15 at 15:44

From that picture it looks like the method to put tiles into regions like that is to check left as far as you can go for sameness, and then check for sameness below as far as you can go without a mismatch. Regions would be defined by their top left and bottom right tiles. You'd just do that, line by line, and have something in place to indicate certain tiles are already part of a region. That could just be another temporary array the same size as the tile map filled with booleans that you set when you add a tile to a region.

for ( int y = 0; y < tilemap.height; ++y){
for ( int x = 0; x < tilemap.width; ++x){
if (taken_tiles[x,y]){
continue;
} else {
Region* rc = region_container.add(x, y, tilemap[x,y].tile_type);
taken_tiles[x,y] = true;
for ( int x2 = 0; x2 < tilemap.width - x; ++x2){
if (tilemap[x+x2,y].tile_type == tilemap[x,y].tile_type
&& !taken_tiles[x + x2,y]){
rc->last_tile(x + x2, y);
} else {
for ( int y2 = 0; y2 < tilemap.height - y; ++y){
//check then row below the previously added row
//from rc->first_tile.x to rc->last_tile.x on the
// y + y2 line. If all are same then make each
// of them taken and make the y + y2 as rc->last_tile.y
// if there's a difference then break
}
break;
}    }    }    }    }

• Nice algorithm, but do you know the its name? I'm looking it because I want to learn more about it. – Macabeus May 12 '19 at 21:05