Problems with maze generator ported from JS to Lua?

Asked by

5 years ago

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:

01local function genMaze()
02    local tilesDone = 1
03    local tilesGoal = width * height
04    local stack = {{
05        pos = {math.random(0, width - 1), math.random(0, height - 1)}, 
06        open = {false, false, false, false}
07    }}
08    maze = {}
09    maze[stack[1].pos[2] * width + stack[1].pos[1]] = stack[1]
10    while tilesDone < tilesGoal do
11        local currentNode = stack[#stack]
12        local path = randPath(currentNode);
13        while path == -1 do
14            -- if tilesDone < tilesGoal, stack.length will never be 0
15            table.remove(stack, #stack)
16            currentNode = stack[#stack]
17            path = randPath(currentNode)
18        end
19        currentNode.open[path] = true
20 
21        local pos, open = nil, {false, false, false, false}
22        open[(path + 2) % 4] = true
23        if tonumber(path) == 1 then
24            pos = {currentNode.pos[1], currentNode.pos[2] - 1}
25        elseif tonumber(path) == 2 then
26            pos = {currentNode.pos[1] + 1, currentNode.pos[2]}
27        elseif tonumber(path) == 3 then
28            pos = {currentNode.pos[1], currentNode.pos[2] + 1}
29        elseif tonumber(path) == 4 then
30            pos = {currentNode.pos[1] - 1, currentNode.pos[2]}
31        end
32        local node = { pos = pos, open = open }
33        maze[pos[2] * width + pos[1]] = node
34        table.insert(stack, node)
35        tilesDone = tilesDone + 1
36    end
37end
 View all 37 lines...

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:

001local width, height = 10, 10
002local function mapRange(v, x1, y1, x2, y2)
003    return (v - x1) * (y2 - x2) / (y1 - x1) + x2
004end
005local function line(v1, v2)
006    local angle = math.atan2(v2.Y - v1.Y, v2.X - v1.X)
007    local frame = Instance.new("Frame", script.Parent.Puzzle)
008    frame.Name = "Line"
009    frame.BackgroundColor3 = Color3.new(0, 0, 0)
010    frame.BorderSizePixel = 0
011    frame.Size = UDim2.new(
012        mapRange(
013            (v1 - v2).Magnitude, 
014            0, 
015            script.Parent.AbsoluteSize.X, 
016            0, 
017            1
018        ), 
019        0, 
020        0, 
021        1
022    )
023    local center = v1:Lerp(v2, 0.5)
024    frame.Position = UDim2.new(
025        mapRange(
026            center.x, 
027            0,
028            script.Parent.AbsoluteSize.X, 
029            0, 
030            1
031        ), 
032        0, 
033        mapRange(
034            center.y, 
035            0,
036            script.Parent.AbsoluteSize.Y, 
037            0, 
038            1
039        ), 
040        0
041    )
042    frame.Rotation = math.deg(angle)
043    frame.AnchorPoint = Vector2.new(0.5, 0.5)
044end
045 
046local maze = {}
047local function tileInDir(node, dirA)
048    local dir = tonumber(dirA)
049    if dir == 1 then
050        return (node.pos[2] == 0) or maze[width * (node.pos[2] - 1) + node.pos[1]]
051    elseif dir == 2 then
052        return (node.pos[1] == width - 1) or maze[width * node.pos[2] + node.pos[1] + 1]
053    elseif dir == 3 then
054        return (node.pos[2] == height - 1) or maze[width * (node.pos[2] + 1) + node.pos[1]]
055    elseif dir == 4 then
056        return (node.pos[1] == 0) or maze[width * node.pos[2] + node.pos[1] - 1]
057    else
058        print("Failed to find tileInDir with dir " .. dirA)
059    end
060end
061 
062local function randPath(node)
063    local open, bias = {}, {}
064    for i in ipairs(node.open) do
065        if node.open[i] then
066            if not tileInDir(node, (i + 3) % 4 + 1) then table.insert(bias, (i + 3) % 4 + 1) end
067            if not tileInDir(node, (i + 1) % 4 + 1) then table.insert(bias, (i + 1) % 4 + 1) end
068        end
069        if not (node.open[i] or tileInDir(node, i)) then table.insert(open, tonumber(i)) end
070    end
071    if #open < 1 then return -1 end
072    -- 50% chance to ignore paths that would make straight lines
073    if #bias > 0 and math.random() > 0.5 then return bias[math.random(1, #bias)] end
074    return open[math.random(1, #open)];
075end
076 
077local function genMaze()
078    local tilesDone = 1
079    local tilesGoal = width * height
080    local stack = {{
081        pos = {math.random(0, width - 1), math.random(0, height - 1)}, 
082        open = {false, false, false, false}
083    }}
084    maze = {}
085    maze[stack[1].pos[2] * width + stack[1].pos[1]] = stack[1]
086    while tilesDone < tilesGoal do
087        local currentNode = stack[#stack]
088        local path = randPath(currentNode);
089        while path == -1 do
090            -- if tilesDone < tilesGoal, stack.length will never be 0
091            table.remove(stack, #stack)
092            currentNode = stack[#stack]
093            path = randPath(currentNode)
094        end
095        currentNode.open[path] = true
096 
097        local pos, open = nil, {false, false, false, false}
098        open[(path + 2) % 4] = true
099        if tonumber(path) == 1 then
100            pos = {currentNode.pos[1], currentNode.pos[2] - 1}
101        elseif tonumber(path) == 2 then
102            pos = {currentNode.pos[1] + 1, currentNode.pos[2]}
103        elseif tonumber(path) == 3 then
104            pos = {currentNode.pos[1], currentNode.pos[2] + 1}
105        elseif tonumber(path) == 4 then
106            pos = {currentNode.pos[1] - 1, currentNode.pos[2]}
107        end
108        local node = { pos = pos, open = open }
109        maze[pos[2] * width + pos[1]] = node
110        table.insert(stack, node)
111        tilesDone = tilesDone + 1
112    end
113end
114 
115local function drawMaze()
116    for _, v in pairs(script.Parent.Puzzle:GetChildren()) do
117        if v.Name == "Line" then
118            v:Destroy()
119        end
120    end
121    local tileHeight, tileWidth = script.Parent.AbsoluteSize.Y / height, script.Parent.AbsoluteSize.X / width
122    for i, v in ipairs(maze) do
123        local tilePosition = {maze[i].pos[1] * tileWidth, maze[i].pos[2] * tileHeight}
124        if not maze[i].open[1] then
125            line(
126                Vector2.new(tilePosition[1], tilePosition[2]),
127                Vector2.new(tilePosition[1] + tileWidth, tilePosition[2])
128            )
129        end
130        if not maze[i].open[2] then
131            line(
132                Vector2.new(tilePosition[1] + tileWidth, tilePosition[2]),
133                Vector2.new(tilePosition[1] + tileWidth, tilePosition[2] + tileHeight)
134            )
135        end
136        if not maze[i].open[3] then
137            line(
138                Vector2.new(tilePosition[1], tilePosition[2] + tileHeight),
139                Vector2.new(tilePosition[1] + tileWidth, tilePosition[2] + tileHeight)
140            )
141        end
142        if not maze[i].open[4] then
143            line(
144                Vector2.new(tilePosition[1], tilePosition[2]),
145                Vector2.new(tilePosition[1], tilePosition[2] + tileHeight)
146            )
147        end
148    end
149end
150while wait(5) do
151    genMaze()
152    for _, v in pairs(maze) do
153        if not v.open[1] and not v.open[2] and not v.open[3] and not v.open[4] then
154            print("Isolated cell")
155        end
156    end
157    drawMaze()
158end
 View all 158 lines...

thanks for the javascript and html code bro, this will help me LOL greatneil80 2647 — 5y

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 vector3_zero 1056 — 5y

Fixed, has no effect compUcomp 417 — 5y

Problems with maze generator ported from JS to Lua?

1 answer

Answer this question