Scripting HelpersARCHIVE
A little piece of Roblox history. Preserved for everyone, one question at a time.Read about the archive →
✓ ANSWER ACCEPTED

Problems with maze generator ported from JS to Lua?

A while back, I made a maze generator in JavaScript using a popular algorithm. It never fails to produce a solvable maze. I thought it would be interesting if I could port it to Lua, so I started working. This is what I came up with:

local function genMaze()
    local tilesDone = 1
    local tilesGoal = width * height
    local stack = {{
    	pos = {math.random(0, width - 1), math.random(0, height - 1)}, 
    	open = {false, false, false, false}
    }}
    maze = {}
    maze[stack[1].pos[2] * width + stack[1].pos[1]] = stack[1]
    while tilesDone < tilesGoal do
        local currentNode = stack[#stack]
        local path = randPath(currentNode);
        while path == -1 do
            -- if tilesDone < tilesGoal, stack.length will never be 0
            table.remove(stack, #stack)
            currentNode = stack[#stack]
            path = randPath(currentNode)
        end
        currentNode.open[path] = true
        
        local pos, open = nil, {false, false, false, false}
        open[(path + 2) % 4] = true
        if tonumber(path) == 1 then
    		pos = {currentNode.pos[1], currentNode.pos[2] - 1}
    	elseif tonumber(path) == 2 then
    		pos = {currentNode.pos[1] + 1, currentNode.pos[2]}
    	elseif tonumber(path) == 3 then
    		pos = {currentNode.pos[1], currentNode.pos[2] + 1}
    	elseif tonumber(path) == 4 then
			pos = {currentNode.pos[1] - 1, currentNode.pos[2]}
    	end
        local node = { pos = pos, open = open }
        maze[pos[2] * width + pos[1]] = node
        table.insert(stack, node)
        tilesDone = tilesDone + 1
    end
end

I rewrote the script line by line. Lua's 1-based indexing was a problem, but I got the mistakes ironed out... or so I thought. This version rarely produces a solvable maze. Isolated cells are made frequently, and large chunks of the map are often cut off. No errors are produced. What am I doing wrong?

Javascript version

Full script:

local width, height = 10, 10
local function mapRange(v, x1, y1, x2, y2)
	return (v - x1) * (y2 - x2) / (y1 - x1) + x2
end
local function line(v1, v2)
	local angle = math.atan2(v2.Y - v1.Y, v2.X - v1.X)
	local frame = Instance.new("Frame", script.Parent.Puzzle)
	frame.Name = "Line"
	frame.BackgroundColor3 = Color3.new(0, 0, 0)
	frame.BorderSizePixel = 0
	frame.Size = UDim2.new(
		mapRange(
			(v1 - v2).Magnitude, 
			0, 
			script.Parent.AbsoluteSize.X, 
			0, 
			1
		), 
		0, 
		0, 
		1
	)
	local center = v1:Lerp(v2, 0.5)
	frame.Position = UDim2.new(
		mapRange(
			center.x, 
			0,
			script.Parent.AbsoluteSize.X, 
			0, 
			1
		), 
		0, 
		mapRange(
			center.y, 
			0,
			script.Parent.AbsoluteSize.Y, 
			0, 
			1
		), 
		0
	)
	frame.Rotation = math.deg(angle)
	frame.AnchorPoint = Vector2.new(0.5, 0.5)
end

local maze = {}
local function tileInDir(node, dirA)
	local dir = tonumber(dirA)
	if dir == 1 then
		return (node.pos[2] == 0) or maze[width * (node.pos[2] - 1) + node.pos[1]]
	elseif dir == 2 then
		return (node.pos[1] == width - 1) or maze[width * node.pos[2] + node.pos[1] + 1]
	elseif dir == 3 then
		return (node.pos[2] == height - 1) or maze[width * (node.pos[2] + 1) + node.pos[1]]
	elseif dir == 4 then
		return (node.pos[1] == 0) or maze[width * node.pos[2] + node.pos[1] - 1]
	else
		print("Failed to find tileInDir with dir " .. dirA)
	end
end

local function randPath(node)
    local open, bias = {}, {}
    for i in ipairs(node.open) do
    	if node.open[i] then
    		if not tileInDir(node, (i + 3) % 4 + 1) then table.insert(bias, (i + 3) % 4 + 1) end
    		if not tileInDir(node, (i + 1) % 4 + 1) then table.insert(bias, (i + 1) % 4 + 1) end
    	end
        if not (node.open[i] or tileInDir(node, i)) then table.insert(open, tonumber(i)) end
    end
    if #open < 1 then return -1 end
    -- 50% chance to ignore paths that would make straight lines
    if #bias > 0 and math.random() > 0.5 then return bias[math.random(1, #bias)] end
    return open[math.random(1, #open)];
end

local function genMaze()
    local tilesDone = 1
    local tilesGoal = width * height
    local stack = {{
    	pos = {math.random(0, width - 1), math.random(0, height - 1)}, 
    	open = {false, false, false, false}
    }}
    maze = {}
    maze[stack[1].pos[2] * width + stack[1].pos[1]] = stack[1]
    while tilesDone < tilesGoal do
        local currentNode = stack[#stack]
        local path = randPath(currentNode);
        while path == -1 do
            -- if tilesDone < tilesGoal, stack.length will never be 0
            table.remove(stack, #stack)
            currentNode = stack[#stack]
            path = randPath(currentNode)
        end
        currentNode.open[path] = true
        
        local pos, open = nil, {false, false, false, false}
        open[(path + 2) % 4] = true
        if tonumber(path) == 1 then
    		pos = {currentNode.pos[1], currentNode.pos[2] - 1}
    	elseif tonumber(path) == 2 then
    		pos = {currentNode.pos[1] + 1, currentNode.pos[2]}
    	elseif tonumber(path) == 3 then
    		pos = {currentNode.pos[1], currentNode.pos[2] + 1}
    	elseif tonumber(path) == 4 then
			pos = {currentNode.pos[1] - 1, currentNode.pos[2]}
    	end
        local node = { pos = pos, open = open }
        maze[pos[2] * width + pos[1]] = node
        table.insert(stack, node)
        tilesDone = tilesDone + 1
    end
end

local function drawMaze()
	for _, v in pairs(script.Parent.Puzzle:GetChildren()) do
		if v.Name == "Line" then
			v:Destroy()
		end
	end
	local tileHeight, tileWidth = script.Parent.AbsoluteSize.Y / height, script.Parent.AbsoluteSize.X / width
	for i, v in ipairs(maze) do
		local tilePosition = {maze[i].pos[1] * tileWidth, maze[i].pos[2] * tileHeight}
		if not maze[i].open[1] then
			line(
				Vector2.new(tilePosition[1], tilePosition[2]),
				Vector2.new(tilePosition[1] + tileWidth, tilePosition[2])
			)
		end
		if not maze[i].open[2] then
			line(
				Vector2.new(tilePosition[1] + tileWidth, tilePosition[2]),
				Vector2.new(tilePosition[1] + tileWidth, tilePosition[2] + tileHeight)
			)
		end
		if not maze[i].open[3] then
			line(
				Vector2.new(tilePosition[1], tilePosition[2] + tileHeight),
				Vector2.new(tilePosition[1] + tileWidth, tilePosition[2] + tileHeight)
			)
		end
		if not maze[i].open[4] then
			line(
				Vector2.new(tilePosition[1], tilePosition[2]),
				Vector2.new(tilePosition[1], tilePosition[2] + tileHeight)
			)
		end
	end
end
while wait(5) do
	genMaze()
	for _, v in pairs(maze) do
		if not v.open[1] and not v.open[2] and not v.open[3] and not v.open[4] then
			print("Isolated cell")
		end
	end
	drawMaze()
end

3 comments

1

thanks for the javascript and html code bro, this will help me LOL

1

I don't have a lot of time to look at it, but I noticed on line 22 you are indexing the open table with a value between 0 and 3 instead of 1 and 4. Will let you know if I find anything else

0

Fixed, has no effect

1 answer

✓ Accepted answer

I found your problem. Change line 22 to:

open[((path-1)+2)%4+1] = true

or more succinctly:

open[(path+1)%4+1] = true

With just this line changed in the above code everything works like it should.

2 comments

0

Thanks for your answer! I'll test it soon and accept it if it works

0

It works! tysm

This discussion is preserved as it was. New answers, comments, and votes are closed.