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

3 comments
thanks for the javascript and html code bro, this will help me LOL
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
Fixed, has no effect