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?
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
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.