# TileMerging

This algorithm is for 2D tile maps. The algorithm generates a (hopefully) minimum set of rectangles that cover all tiles of a certain type.

This is useful for physics where you can generate rectangles to cover all wall tiles. You use the rectangles to create physics bodies that can cover multiple wall tiles, instead of create a physics body for every single tile.

```-- map_width and map_height are the dimensions of the map
-- is_wall_f checks if a tile is a wall

local rectangles = {} -- Each rectangle covers a grid of wall tiles

for x = 0, map_width - 1 do
local start_y
local end_y

for y = 0, map_height - 1 do
if is_wall_f(x, y) then
if not start_y then
start_y = y
end
end_y = y
elseif start_y then
local overlaps = {}
for _, r in ipairs(rectangles) do
if (r.end_x == x - 1)
and (start_y <= r.start_y)
and (end_y >= r.end_y) then
table.insert(overlaps, r)
end
end
table.sort(
overlaps,
function (a, b)
return a.start_y < b.start_y
end
)

for _, r in ipairs(overlaps) do
if start_y < r.start_y then
local new_rect = {
start_x = x,
start_y = start_y,
end_x = x,
end_y = r.start_y - 1
}
table.insert(rectangles, new_rect)
start_y = r.start_y
end

if start_y == r.start_y then
r.end_x = r.end_x + 1

if end_y == r.end_y then
start_y = nil
end_y = nil
elseif end_y > r.end_y then
start_y = r.end_y + 1
end
end
end

if start_y then
local new_rect = {
start_x = x,
start_y = start_y,
end_x = x,
end_y = end_y
}
table.insert(rectangles, new_rect)

start_y = nil
end_y = nil
end
end
end

if start_y then
local new_rect = {
start_x = x,
start_y = start_y,
end_x = x,
end_y = end_y
}
table.insert(rectangles, new_rect)

start_y = nil
end_y = nil
end
end
```

Here's how the rectangles would be used for physics.

```-- Use contents of rectangles to create physics bodies
-- phys_world is the world, wall_rects is the list of...
-- wall rectangles

for _, r in ipairs(rectangles) do
local start_x = r.start_x * TILE_SIZE
local start_y = r.start_y * TILE_SIZE
local width = (r.end_x - r.start_x + 1) * TILE_SIZE
local height = (r.end_y - r.start_y + 1) * TILE_SIZE

local x = start_x + (width / 2)
local y = start_y + (height / 2)

local body = love.physics.newBody(phys_world, x, y, 0, 0)
local shape = love.physics.newRectangleShape(body, 0, 0,
width, height)

shape:setFriction(0)

table.insert(wall_rects, {body = body, shape = shape})
end
```