LÖVE


https://www.love2d.org/forums/

Convert tiles to rectangles

https://www.love2d.org/forums/viewtopic.php?t=94154

Page 1 of 1

Convert tiles to rectangles

Posted: Fri Jan 06, 2023 1:41 pm
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 3036 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 3036 times
2023-01-06T14_38_52-Untitled.png
2023-01-06T14_38_52-Untitled.png (127.5 KiB) Viewed 3036 times

Re: Convert tiles to rectangles

Posted: Sat Jan 07, 2023 9:27 am
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...

Re: Convert tiles to rectangles

Posted: Sun Jan 08, 2023 8:39 am
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

Re: Convert tiles to rectangles

Posted: Tue Jan 10, 2023 4:59 pm
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 2849 times
(Actually in hindsight, that square external wall isn't necessary, just the walls inside.)

Re: Convert tiles to rectangles

Posted: Fri Feb 03, 2023 2:57 pm
by knorke
I stumbled across this snippet: https://love2d.org/wiki/TileMerging

Re: Convert tiles to rectangles

Posted: Mon Feb 06, 2023 12:06 pm
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.

Re: Convert tiles to rectangles

Posted: Fri Mar 17, 2023 9:58 pm
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 1857 times
Screenshot 2023-03-17 231615.png
Screenshot 2023-03-17 231615.png (9.52 KiB) Viewed 1853 times

Re: Convert tiles to rectangles

Posted: Fri Mar 17, 2023 10:33 pm
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.

Re: Convert tiles to rectangles

Posted: Sat Mar 18, 2023 1:15 pm
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
All times are UTC
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited