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.
First version
-- map_width and map_height are the dimensions of the map
-- is_wall_f checks if a tile is a wall
local function tilesMerging (grid, tileSize, is_wall_f) -- tilesMerging_v1
local function newRect (start_x, start_y, end_x, end_y)
local new_rect = {
start_x = start_x,
start_y = start_y,
end_x = end_x,
end_y = end_y,
}
return new_rect
end
local sortStart_y = function (a, b)
return a.start_y < b.start_y
end
local function rectOverlaps (r, x, start_y, end_y)
return r.end_x == x - 1
and start_y <= r.start_y
and end_y >= r.end_y
end
local map_width = #grid[1]
local map_height = #grid
local rectangles = {}
for x = 0, map_width - 1 do
local start_y
local end_y
for y = 0, map_height - 1 do
if is_wall_f(grid, 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 rectOverlaps (r, x, start_y, end_y) then
table.insert(overlaps, r)
end
end
table.sort(overlaps, sortStart_y)
for _, r in ipairs(overlaps) do
if start_y < r.start_y then
local new_rect = newRect (x, start_y, x, 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 or (y == map_height - 1) then
local new_rect = newRect (x, start_y, x, end_y)
table.insert(rectangles, new_rect)
start_y = nil
end
end
end
if start_y then
local new_rect = newRect (x, start_y, x, end_y)
table.insert(rectangles, new_rect)
end
end
-- resize rectangles
for _, r in ipairs(rectangles) do
r.x = r.start_x * tileSize
r.y = r.start_y * tileSize
r.w = (r.end_x - r.start_x + 1) * tileSize
r.h = (r.end_y - r.start_y + 1) * tileSize
end
return rectangles
end
Example:
local grid = {
{1,1,1,1,1,1,1,1,1},
{1,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,0,1},
{1,1,1,0,1,0,1,1,1},
{1,1,1,1,0,1,1,1,1},
{1,1,1,0,1,0,1,1,1},
{1,0,1,1,1,1,1,0,1},
{1,0,0,1,1,1,0,0,1},
{1,1,1,1,1,1,1,1,1},
}
local tileSize = 30
local function is_wall_f(grid, x, y)
if grid[y+1] and grid[y+1][x+1] then
if grid[y+1][x+1] == 1 then
return true -- wall
else
return false -- not wall
end
else
return false -- out of map, also wall
end
end
local rectangles = tilesMerging (grid, tileSize, is_wall_f)
print ('amount rectangles:', #rectangles)
function love.draw ()
love.graphics.translate (5,5)
for i, r in ipairs (rectangles) do
love.graphics.setColor (0.8,0.8,0.8,0.8)
love.graphics.rectangle ('fill', r.x, r.y, r.w, r.h)
love.graphics.setColor (1,1,1)
love.graphics.rectangle ('line', r.x, r.y, r.w, r.h)
end
end
It gives 20 following rectangles:
Second version
local function tilesMerging (grid, tileSize, is_wall_f) -- v2
local function isRectangle(hashMap, x0, y0, w, h)
for y = y0, y0 + h - 1 do
for x = x0, x0 + w - 1 do
if not (hashMap[y] and hashMap[y][x]) then
return false
end
end
end
return true
end
local function newRectangle(hashMap, start_x, start_y)
local w, h = 1, 1
local end_x, end_y = start_x, start_y
while true do
-- print ('x, y, w, h', start_x, start_y, w, h)
local right = isRectangle(hashMap, start_x + w, start_y, 1, h)
local rightT = isRectangle(hashMap, start_x + w, start_y - 1, 1, h + 2)
local down = isRectangle(hashMap, start_x, start_y + h, w, 1)
local downT = isRectangle(hashMap, start_x - 1, start_y + h, w + 2, 1)
local canDiag = right and down and hashMap[start_y + w] and hashMap[start_x + w][start_y + h]
if canDiag then
w, h = w + 1, h + 1
elseif right and not rightT then
w = w + 1
elseif down and not downT then
h = h + 1
else
for y0 = start_y, start_y + h - 1 do
for x0 = start_x, start_x + w - 1 do
hashMap[y0][x0] = false
end
end
start_x = start_x-1
start_y = start_y-1
local end_x = start_x+w-1
local end_y = start_y+h-1
-- print (start_x, start_y, end_x, end_y)
return { start_x = start_x, start_y = start_y, end_x = end_x, end_y = end_y}
end
end
end
-- create hash of booleans
local hashMap = {}
for y = 1, #grid do
hashMap[y] = {}
for x = 1, #grid[y] do
hashMap[y][x] = is_wall_f(grid, x-1, y-1) -- true by 1
end
end
-- main loop
local map_width = #grid[1]
local map_height = #grid
local rectangles = {}
for y = 1, map_height do
for x = 1, map_width do
if hashMap[y][x] then
local rectangle = newRectangle(hashMap, x, y)
table.insert(rectangles, rectangle)
end
end
end
-- resize rectangles
for _, r in ipairs(rectangles) do
r.x = r.start_x * tileSize
r.y = r.start_y * tileSize
r.w = (r.end_x - r.start_x + 1) * tileSize
r.h = (r.end_y - r.start_y + 1) * tileSize
end
return rectangles
end
And it gives 16 rectangles:
Adding physics
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
Other Languages
Dansk –
Deutsch –
English –
Español –
Français –
Indonesia –
Italiano –
Lietuviškai –
Magyar –
Nederlands –
Polski –
Português –
Română –
Slovenský –
Suomi –
Svenska –
Türkçe –
Česky –
Ελληνικά –
Български –
Русский –
Српски –
Українська –
עברית –
ไทย –
日本語 –
正體中文 –
简体中文 –
Tiếng Việt –
한국어
More info