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