Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
2

Problems with maze generator ported from JS to Lua?

Asked by
compUcomp 417 Moderation Voter
4 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:

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
1
thanks for the javascript and html code bro, this will help me LOL greatneil80 2647 — 4y
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 vector3_zero 1056 — 4y
0
Fixed, has no effect compUcomp 417 — 4y

1 answer

Log in to vote
1
Answered by 4 years ago
Edited 4 years ago

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.

0
Thanks for your answer! I'll test it soon and accept it if it works compUcomp 417 — 4y
0
It works! tysm compUcomp 417 — 4y
Ad

Answer this question