Convert tiles to rectangles

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Convert tiles to rectangles

Post by darkfrei »

Hi all!

The problem comes from another topic: viewtopic.php?f=4&t=94150

We have a map of tiles, for example:

Code: Select all

map = {
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,1,0,0,0,1},
	{1,1,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,1,0,1},
	{1,0,1,1,0,1,0,1,0,1},
	{1,0,0,1,0,1,0,1,0,1},
	{1,0,1,1,0,1,0,1,0,1},
	{1,0,0,1,0,1,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1},
}
We are need to convert it to the smallest amount of rectangles, for example:
2023-01-06.png
2023-01-06.png (18.09 KiB) Viewed 2554 times
How to do that?


I have a code to convert the map to the list of horizontal/vertical rectangles, but how to optimize the amount of rectangles?

Code: Select all

map = {
	{1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1, },
	{1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0, 1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0, },
	{1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0, 1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0, },
	{0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0, 0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0, },
	{1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1, 1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1, },
	{0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0, 0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0, },
	{1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1, 1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1, },
	{1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0, 1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0, },
	{1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0, 1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0, },
	{0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0, 0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0, },
	{1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0, 1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0, },
	{0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0, 0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0, },
	{1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1, 1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1, },
	{1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0, 1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0, },
	{1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1, },
	{0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0, },
	{1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1, 1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1, },
	{0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0, 0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0, },
	{1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0, 1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0, },
	{1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0, 1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0, },
	
	{1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1, },
	{1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0, 1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0, },
	{1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0, 1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0, },
	{0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0, 0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0, },
	{1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1, 1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1, },
	{0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0, 0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0, },
	{1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1, 1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1, },
	{1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0, 1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0, },
	{1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0, 1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0, },
	{0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0, 0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0, },
	{1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0, 1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0, },
	{0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0, 0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0, },
	{1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1, 1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1, },
	{1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0, 1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0, },
	{1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1, },
	{0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0, },
	{1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1, 1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1, },
	{0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0, 0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0, },
	{1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0, 1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0, },
	{1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0, 1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0, },
}

Code: Select all

rectangles = {}
local firstX, lastX = 1, #map[1]
local firstY, lastY = 1, #map
for y = firstY, lastY do
--	local r = {x=firstX,y=y,w=1,h=1}
	local r
	for x = firstX, lastX do
		if map[y][x] == 1 and (x == lastX) then -- lastwall
			if r then
				r.w=r.w+1
			else
				r = {x=x,y=y,w=1,h=1}
			end
			table.insert (rectangles, r)
		elseif map[y][x] == 1 then -- wall
			if r then
				r.w=r.w+1
			else
				r = {x=x,y=y,w=1,h=1}
			end
		elseif r then -- not wall, save existing rectangle
			table.insert (rectangles, r)
			r = nil
		end
	end
end
print('#rectangles', #rectangles)

rectangles2 = {} 
for x = firstX, lastX do
	local r
	for y = firstY, lastY do
		if map[y][x] == 1 and (y == lastY) then -- lastwall
			if r then
				r.h=r.h+1
			else
				r = {x=x,y=y,w=1,h=1}
			end
			table.insert (rectangles2, r)
		elseif map[y][x] == 1 then -- wall
			if r then
				r.h=r.h+1
			else
				r = {x=x,y=y,w=1,h=1}
			end
		elseif r then -- not wall, save existing rectangle
			table.insert (rectangles2, r)
			r = nil
		end
	end
end
print('#rectangles2', #rectangles2)

function love.draw()
	love.graphics.scale(16)
	love.graphics.setLineWidth(1/8)
	
	for i, r in ipairs (rectangles2) do
		love.graphics.rectangle('line', r.x-1, r.y-1, r.w, r.h)
	end
end
2023-01-06T14_38_36-Untitled.png
2023-01-06T14_38_36-Untitled.png (97.02 KiB) Viewed 2554 times
2023-01-06T14_38_52-Untitled.png
2023-01-06T14_38_52-Untitled.png (127.5 KiB) Viewed 2554 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
Sasha264
Party member
Posts: 131
Joined: Mon Sep 08, 2014 7:57 am

Re: Convert tiles to rectangles

Post by Sasha264 »

Maybe it will be enough to just group tiles horizontally then group remaining tiles vertically =)

------

But if you want ultimate minimum of rectangles then I can think of some king of genetic algorithm:
  1. For each tile assign random boolean: will it be grouped vertically or horizontally.
  2. Shuffle tiles in random order.
  3. Iterate through tiles in that order and to each of them group it with all free (not yet grouped) neighbors (and neighbors neighbors, and so on, as you do in your example) accordingly to that core-tile direction. That will be one rectangle. Mark all grouped tiles as already grouped.
  4. Count result number of rectangles.
Then repeat these 4 steps, but not with random directions and random order: leave them as it was on the previous iteration + slightly modify it randomly. For example change orientation of 5% of tiles and reshuffle 5% of tiles. And see, if it lead to smaller rectangles count. If not — revert that slight modification.

After some steps you will not get any farther improvements. This will be resulting group order. This can be called "a population". Then you can run different populations if you want farther improvement, each with independent start conditions. That way you will find a "local minimum" with help of each population. Choosing minimum from several local minimums will get you something very close to absolute minimum.

------

Another way: let the rectangles intersect. Leave your vertically grouped rectangles plus your horizontally grouped rectangles and remove single-tile-rectangles. And adapt the algorithm to not fail when 1 tile is grouped in 2 rectangles. That way you can get smaller total rectangle count that is possible without intersection. Of course it depends on the maze topology, if it have a lot of + or a lot of T...
User avatar
Sasha264
Party member
Posts: 131
Joined: Mon Sep 08, 2014 7:57 am

Re: Convert tiles to rectangles

Post by Sasha264 »

An idea: that can be turned into a puzzle game, where player on some small grid with mouse somehow changes single tile grouping in an attempt to reach minimum rectangle number. For some special handpicked topology with a lot of + and with cycles it can be pretty interesting task :P
RNavega
Party member
Posts: 235
Joined: Sun Aug 16, 2020 1:28 pm

Re: Convert tiles to rectangles

Post by RNavega »

Since this will be used with 2D shadows, I think it'd be even better if you just found the boundary polygon of all walls, as if you merged all the tiles together.

In this polygon, the corners (the red dots) form lines that can be used to make 2D shadows, if those corner lines are visible to the player.
temp.jpg
temp.jpg (32.15 KiB) Viewed 2367 times
(Actually in hindsight, that square external wall isn't necessary, just the walls inside.)
User avatar
knorke
Party member
Posts: 237
Joined: Wed Jul 14, 2010 7:06 pm
Contact:

Re: Convert tiles to rectangles

Post by knorke »

I stumbled across this snippet: https://love2d.org/wiki/TileMerging
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Convert tiles to rectangles

Post by darkfrei »

knorke wrote: Fri Feb 03, 2023 2:57 pm I stumbled across this snippet: https://love2d.org/wiki/TileMerging
It makes just vertical rectangles, vertical or wide rectangles are not possible.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Convert tiles to rectangles

Post by darkfrei »

Can you please check it?

Code: Select all

-- map tiles to rectangles

local function isRectangle (hashMap, x0, y0, w, h)
	for y = y0, y0+h-1 do
		for x = x0, x0+w-1 do
			if hashMap[y] then
				if not hashMap[y][x] then
					return false
				end
			else
				return false
			end
		end
	end
	return true
end

local function newRectangle (hashMap, x, y)
	local w, h = 1, 1
	while true do
		local right = isRectangle (hashMap, x+w, y, 1, h)
		local rightT = isRectangle (hashMap, x+w, y-1, 1, h+2)
		local down = isRectangle (hashMap, x, y+h, w, 1)
		local downT = isRectangle (hashMap, x-1, y+h, w+2, 1)
		local canDiag = right and down and hashMap[y+w][x+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 = y, y+h-1 do
				for x0 = x, x+w-1 do
					hashMap[y0][x0] = false
				end
			end
			return {x=x, y=y, w=w, h=h}
		end
	end
end

local function getRectanglesFromMap (map)
	local hashMap = {}
	for y = 1, #map do
		hashMap[y] = {}
		for x = 1, #map[y] do
			hashMap[y][x] = (map[y][x] == 1) -- true by 1
		end
	end
	
	local rectangles = {}
	for y = 1, #hashMap do
		for x = 1, #hashMap[y] do
			if hashMap[y][x] then
				local rectangle = newRectangle (hashMap, x, y)
				table.insert (rectangles, rectangle)
			end
		end
	end
	return rectangles
end
My example:

Code: Select all

local map = {
	{0,1,1,1,0},
	{1,0,1,0,1},
	{1,1,0,1,1},
	{1,0,1,0,1},
	{0,1,1,1,0},
}

local rectangles = getRectanglesFromMap (map)
for i, r in ipairs (rectangles) do
	print (i, r.x, r.y, r.w, r.h)
end
Result (right: no way to make it with less than 8 rectangles):

Code: Select all

1	2	1	3	1
2	1	2	1	3
3	3	2	1	1
4	5	2	1	3
5	2	3	1	1
6	4	3	1	1
7	3	4	1	1
8	2	5	3	1
Screenshot 2023-03-17 230633.png
Screenshot 2023-03-17 230633.png (9.21 KiB) Viewed 1375 times
Screenshot 2023-03-17 231615.png
Screenshot 2023-03-17 231615.png (9.52 KiB) Viewed 1371 times
Attachments
tiles-to-rectangles-10.love
CC0 - no license
(1.22 KiB) Downloaded 25 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
knorke
Party member
Posts: 237
Joined: Wed Jul 14, 2010 7:06 pm
Contact:

Re: Convert tiles to rectangles

Post by knorke »

That image has at least two places where it could use less rectangles.
At right edge, lower third, is a 2x2 on top of a 2x1: It could be one 2x6.
With the neighbouring 3x2 and 2x2 it would be possible to do a 7x2 with a 2x1 on top. So 2 rects instead of 4.

Similar situation around the 3x3 near center.
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

Re: Convert tiles to rectangles

Post by pgimeno »

Asking for a minimal partition is asking too much. The fastest known algorithm takes time in the order of n^1.5 log n and is behind a paywall. darkfrei has achieved a decently small partition, even if not optimal.

There are better algorithms for polygons without holes though, which are also useful in games. See for example https://ir.nctu.edu.tw/bitstream/11536/ ... 300004.pdf or https://www.cise.ufl.edu/~sahni/papers/part.pdf
Post Reply

Who is online

Users browsing this forum: Bing [Bot] and 18 guests