Maze Generator

-- This maze has been generated using Prim's Algorithm

local rows = 100
local colums = 100
local cellSpace = 4
local cellHeight = 10

local maze : {{{Cell : BasePart, Filtered : boolean, Visited : boolean}}} = {}

local startingPosition = Vector3.new(0, 10, 0)

local function createFolder() : Folder
    local folder = Instance.new("Folder", workspace)
    folder.Name = "Maze"
    return folder
end

local function createPart(size : Vector3, position : Vector3) : Part
    local part = Instance.new("Part", workspace:FindFirstChild("Maze") or createFolder())
    part.Name = "Wall"
    part.Anchored = true
    part.TopSurface = Enum.SurfaceType.Smooth
    part.BottomSurface = Enum.SurfaceType.Smooth
    part.Anchored = true
    part.Material = Enum.Material.Grass
    part.Locked = true
    part.BrickColor = BrickColor.new("Bright green")
    part.Size = size
    part.Position = startingPosition + position
    return part
end

local function SnapToGrid(position : Vector3) : Vector3
    return Vector3.new(position.X - position.X % cellSpace + cellSpace / 2, position.Y, position.Z - position.Z % cellSpace + cellSpace / 2)
end

local function SnapToOddNumber(number : number) : number
    if number % 2 == 1 then
        return number
    else
        return number + 1
    end
end

local function createSinglePassage(x : number, z : number) : ()
    maze[x][z].Visited = true
    maze[x][z].Cell:Destroy()
end


local function createPassage(xStart : number, zStart : number, xGoal : number, zGoal : number) : ()
    for index = 1, 2 do
        local differenceX = xGoal - xStart
        local differenceZ = zGoal - zStart
        if differenceX < 0 or differenceZ < 0 then
            maze[xStart - (differenceX < 0 and index or 0)][zStart - (differenceZ < 0 and index or 0)].Visited = true
            maze[xStart - (differenceX < 0 and index or 0)][zStart - (differenceZ < 0 and index or 0)].Cell:Destroy()
        elseif differenceX > 0 or differenceZ > 0 then
            maze[xStart + (differenceX > 0 and index or 0)][zStart + (differenceZ > 0 and index or 0)].Visited = true
            maze[xStart + (differenceX > 0 and index or 0)][zStart + (differenceZ > 0 and index or 0)].Cell:Destroy()
        end
    end
end

local function mergeNeighborsTables(neighborsTable1 : {{X : number, Z : number, Cell : BasePart}}, neighborsTable2 : {{X : number, Z : number, Cell : BasePart}}) : {{X : number, Z : number, Cell : BasePart}}
    local mergedNeighborsTable = {}
    for index, neighbor in neighborsTable1 do
        if not maze[neighbor.X][neighbor.Z].Visited then
            table.insert(mergedNeighborsTable, neighbor)
        end
    end
    for index, neighbor in neighborsTable2 do
        if not maze[neighbor.X][neighbor.Z].Visited then
            table.insert(mergedNeighborsTable, neighbor)
        end
    end
    return mergedNeighborsTable
end

local function generateCells() : ()
    for x = 1, rows do
        maze[x] = {}
        for z = 1, colums do
            if x == 1 or x == rows then
                maze[x][z] = {Cell = createPart(Vector3.new(cellSpace, cellHeight, cellSpace), Vector3.new((x - 1) * cellSpace, cellHeight / 2, (z - 1) * cellSpace)), Filtered = true, Visited = false}
            elseif z == 1 or z == colums then
                maze[x][z] = {Cell = createPart(Vector3.new(cellSpace, cellHeight, cellSpace), Vector3.new((x - 1) * cellSpace, cellHeight / 2, (z - 1) * cellSpace)), Filtered = true, Visited = false}
            else
                maze[x][z] = {Cell = createPart(Vector3.new(cellSpace, cellHeight, cellSpace), Vector3.new((x - 1) * cellSpace, cellHeight / 2, (z - 1) * cellSpace)), Filtered = false, Visited = false}
            end
        end
    end
end

local function getNeighbors(x : number, z : number, isVisited : boolean) : {{X : number, Z : number, Cell : BasePart}}
    assert(x >= 1 and x <= rows, "x is out of range")
    assert(z >= 1 and z <= colums, "z is out of range")
    assert(not maze[x][z].Filtered, "Cannot get neighbors of a filtered cell")
    local neighbors = {}
    if isVisited then
        if maze[x] and maze[x][z + 2] and not maze[x][z + 2].Filtered and maze[x][z + 2].Visited then
            table.insert(neighbors, {X = x, Z = z + 2, Cell = maze[x][z + 2].Cell})
        end
        if maze[x] and maze[x][z - 2] and not maze[x][z - 2].Filtered and maze[x][z - 2].Visited then
            table.insert(neighbors, {X = x, Z = z - 2, Cell = maze[x][z - 2].Cell})
        end
        if maze[x + 2] and maze[x + 2][z] and not maze[x + 2][z].Filtered and maze[x + 2][z].Visited then
            table.insert(neighbors, {X = x + 2, Z = z, Cell = maze[x + 2][z].Cell})
        end
        if maze[x - 2] and maze[x - 2][z] and not maze[x - 2][z].Filtered and maze[x - 2][z].Visited then
            table.insert(neighbors, {X = x - 2, Z = z, Cell = maze[x - 2][z].Cell})
        end
    else
        if maze[x] and maze[x][z + 2] and not maze[x][z + 2].Filtered and not maze[x][z + 2].Visited then
            table.insert(neighbors, {X = x, Z = z + 2, Cell = maze[x][z + 2].Cell})
        end
        if maze[x] and maze[x][z - 2] and not maze[x][z - 2].Filtered and not maze[x][z - 2].Visited then
            table.insert(neighbors, {X = x, Z = z - 2, Cell = maze[x][z - 2].Cell})
        end
        if maze[x + 2] and maze[x + 2][z] and not maze[x + 2][z].Filtered and not maze[x + 2][z].Visited then
            table.insert(neighbors, {X = x + 2, Z = z, Cell = maze[x + 2][z].Cell})
        end
        if maze[x - 2] and maze[x - 2][z] and not maze[x - 2][z].Filtered and not maze[x - 2][z].Visited then
            table.insert(neighbors, {X = x - 2, Z = z, Cell = maze[x - 2][z].Cell})
        end
    end
    return neighbors
end

local function generateMaze() : ()
    local cell = {X = 2, Z = 2, Cell = maze[2][2].Cell}
    local neighborsUnvisited = getNeighbors(cell.X, cell.Z, false)
    createSinglePassage(cell.X, cell.Z)
    while table.maxn(neighborsUnvisited) > 0 do
        local randomNeighborUnvisited = math.random(1, table.maxn(neighborsUnvisited))
        local neighborsVisited = getNeighbors(neighborsUnvisited[randomNeighborUnvisited].X, neighborsUnvisited[randomNeighborUnvisited].Z, true)
        local randomNeighborVisited = math.random(1, table.maxn(neighborsVisited))
        createPassage(neighborsVisited[randomNeighborVisited].X, neighborsVisited[randomNeighborVisited].Z, neighborsUnvisited[randomNeighborUnvisited].X, neighborsUnvisited[randomNeighborUnvisited].Z)
        neighborsUnvisited = mergeNeighborsTables(neighborsUnvisited, getNeighbors(neighborsUnvisited[randomNeighborUnvisited].X, neighborsUnvisited[randomNeighborUnvisited].Z, false))
    end
end

rows = SnapToOddNumber(math.max(rows, 3))
colums = SnapToOddNumber(math.max(colums, 3))
startingPosition = SnapToGrid(startingPosition)

generateCells()
generateMaze()