Z-sections with T-crossings

[darkfrei]

Hi all!

I was very impressed by the code doodle of Trystan viewtopic.php?p=257660#p257660

But I think that it will be nice to insert not straight lines, but Z-shaped lines as:

z-sections.jpg (100.74 KiB) Viewed 1833 times

Can you please help me to start? Now I don't see any way to solve it. This examples above was brutforced on the paper.

Rules are:
1. Create Z-line, only first one can be connected to the border with both sides;
2. Don't allow X-crossings, just T-crossings;
3. Don't allow spots with area 2x2 or bigger.

[pgimeno]

The idea is quite interesting, but I'm not convinced that all possible rectangles are solvable. It's easy to come up with a dead end. For example, I took your fourth example and after the second stage, I placed the next Z on the left differently, and then one more on the right, and came up with this:

Dead_end.png (675 Bytes) Viewed 1806 times

I don't think you can add any more Z's to that 5-square block on the bottom right corner, following the rules.

I guess you can always backtrack when you get to a dead end to change something, but I'm not sure how slow that would be, or even if every rectangle will have a solution, as I've mentioned.

[darkfrei]

I am pretty sure that not every rectangle can be solved, but there is a smallest rectangle, that can have n such Z-splitters (or n+1 block).

But big map without third rule makes just nice city map. Maybe some X-crossings will be also OK.

Also this blocks are nice to make a puzzle with not typical tiling.

[darkfrei]

First working version, the Z must make the shortest section more often, not random as now.

Code: Select all

-- Z-sections with T-crossings

love.window.setTitle ('Z-sections with T-crossings; press SPACE for one or X-C-V-B to make alot; Q to new')

function insertZ (x1,y1, x2,y2, x3,y3, x4,y4)
	local xmin, ymin, xmax, ymax = math.min(x1, x2),math.min(y1, y2), math.max(x1, x2),math.max(y1, y2)
	table.insert (lines, {xmin, ymin, xmax, ymax})
	xmin, ymin, xmax, ymax = math.min(x2, x3),math.min(y2, y3), math.max(x2, x3),math.max(y2, y3)
	table.insert (lines, {xmin, ymin, xmax, ymax})
	xmin, ymin, xmax, ymax = math.min(x3, x4),math.min(y3, y4), math.max(x3, x4),math.max(y3, y4)
	table.insert (lines, {xmin, ymin, xmax, ymax})
end


function createFirstZ ()
	if h > w then
		-- two horizontal
		local x = math.random (1,w-1)
		local y1 = math.random (1,h-2)
		local y2 = math.random (2,h-1)
		print (y1, y2)
		if y1 == y2 then
			y2 = y1+1
		end
		if math.random () > 0.5 then
			insertZ (0,y1, x,y1, x, y2, w,y2)
		else
			insertZ (0,y2, x,y2, x, y1, w,y1)
		end
	else
		local x1 = math.random (1,w-2)
		local x2 = math.random (2,w-1)
		local y = math.random (1,h-2)
		if x1 == x2 then
			x2 = x1+1
		end
		if math.random () > 0.5 then
			insertZ (x1,0, x1,y, x2, y, x2,h)
		else
			insertZ (x1,0, x1,y, x2, y, x2,h)
		end
	end
end

function isPointFree (x, y)
	for i, line in ipairs (lines) do
		if x >= line[1] and x <= line[3] and y >= line[2] and y <= line[4] then
			return false
		end
	end
	return true
end

function isPointEnd (x, y)
	for i, line in ipairs (lines) do
		if (x == line[1] and y == line[2]) or (x == line[3] and y == line[4]) then
			return true
		end
	end
	return false
end

function getCrossingH (x, y, side)
	local x1 = x
	while true do
		x1 = x1+side
		if x1 == 0 then return 0, false end
		if x1 == w then return w, false end
		local pointFree = isPointFree (x1, y)
		local isEnd = isPointEnd (x1, y)
		if not pointFree then
			if isEnd then
				return nil
			else
				return x1, true -- position
			end
		end
	end
end

function getCrossingV (x, y, side)
	local y1 = y
	while true do
		y1 = y1+side
		if y1 == 0 then return 0, false end
		if y1 == h then return h, false end
		local pointFree = isPointFree (x, y1)
		local isEnd = isPointEnd (x, y1)
		if not pointFree then
			if isEnd then
				return nil
			else
				return y1, true -- position
			end
		end
	end
end

function getRandomFreeY (x, y)
	local list = {}
	local y1 = y
	while true do
		y1 = y1 + 1
		if y1 == h then break end
		if not isPointFree (x, y1) then break end
		table.insert (list, y1)
	end
	y1 = y
	while true do
		y1 = y1 - 1
		if y1 == 0 then break end
		if not isPointFree (x, y1) then break end
		table.insert (list, y1)
	end
	if #list > 0 then
		return list[math.random(#list)]
	end
end

function getRandomFreeX (x, y)
	local list = {}
	local x1 = x
	while true do
		x1 = x1 + 1
		if x1 == w then break end
		if not isPointFree (x1, y) then break end
		table.insert (list, x1)
	end
	x1 = x
	while true do
		x1 = x1 - 1
		if x1 == 0 then break end
		if not isPointFree (x1, y) then break end
		table.insert (list, x1)
	end
	if #list > 0 then
		return list[math.random(#list)]
	end
end



function tryCreateNewZ ()
	local x = math.random (1,w-1)
	local y = math.random (1,h-1)
	if isPointFree (x, y) then
		if math.random () < 0.5 then
			-- two horizontal
			local x1, onLineA = getCrossingH (x, y, -1)
			if x1 then
				local y1 = getRandomFreeY (x, y)
				if y1 then
					local x2, onLineB = getCrossingH (x, y1, 1)
					if x2 and (onLineA or onLineB) then
						insertZ (x1,y, x,y, x, y1, x2,y1)
					end
				end
			end
		else
			-- two vertical
			local y1, onLineA = getCrossingV (x, y, -1)
			if y1 then
				local x1 = getRandomFreeX (x, y)
				if x1 then
					local y2, onLineB = getCrossingV (x1, y, 1)
					if y2 and (onLineA or onLineB) then
						insertZ (x,y1, x,y, x1, y, x1,y2)
					end
				end
			end
		end
	end
end

function love.load ()
	w, h = 79, 59
	lines = {}
	createFirstZ ()
end


function love.draw ()
	local gridSize = 10
	love.graphics.translate (5,5)
	love.graphics.scale (gridSize)
	love.graphics.setLineWidth (2/gridSize)
	love.graphics.rectangle ('line', 0,0, w,h)
	for i, line in ipairs (lines) do
		love.graphics.line (line)
	end
end



function love.keypressed (key, scancode, isrepeat)
	if key == 'escape' then love.event.quit () end
	if key == 'space' then
		tryCreateNewZ ()
	elseif scancode == 'x' then
		for i = 1, 10 do
			tryCreateNewZ ()
		end
	elseif scancode == 'c' then
		for i = 1, 100 do
			tryCreateNewZ ()
		end
	elseif scancode == 'v' then
		for i = 1, 1000 do
			tryCreateNewZ ()
		end
	elseif scancode == 'b' then
		for i = 1, 10000 do
			tryCreateNewZ ()
		end
	elseif scancode == 'q' then
		lines = {}
		createFirstZ ()
	end

end

[Trystan]

I don't really have anything to add to the topic but wanted to say that these look amazing.