Maze Generation

--//Recursive Backtracking Maze (Created By Vaeb) (ServerSide)

wait(1/30)

local Plrs = game:GetService("Players")
local LP = Plrs.Vaeb

local IsRandom = true --false
local FullX = 21 --21
local FullY = 21 --21
local CellWidth = 14 --12
local WallWidth = 2 --2
local FullHeight = 13 --13
local ElasticNum = 1 --1

local HalfHeight = FullHeight/2

local WaitNum = 0
local Checking = false

local EndHeight = 0.2
local EndCFY = EndHeight/2

local BaseOffset = -60 --(FullY*CellWidth)/2 - CellWidth/2 OR -30

local StartCF = workspace.Base.CFrame * CFrame.new(-((FullX*CellWidth)/2), workspace.Base.Size.Y/2, (-FullY*CellWidth) + BaseOffset) --(Goes Down-Right)

local StartCellNumX = math.ceil(FullX/2)
local StartCellNumY = math.ceil(FullY/2)
local HalfWall = WallWidth/2
local RealCellWidth = CellWidth - WallWidth
local AddedCellWidth = CellWidth + WallWidth
local WallOffset = RealCellWidth/2 + HalfWall
local ExtraCellWidth = CellWidth + HalfWall

local NodeWidth = RealCellWidth - 1.5

local EndPart = nil

local HasChanged = {}

local CF = CFrame.new
local Heartbeat = game:GetService("RunService").Heartbeat

local HitCon = nil
local MazeCons = {}

local pow = math.pow
local sin = math.sin
local cos = math.cos
local pi = math.pi
local sqrt = math.sqrt
local abs = math.abs
local asin  = math.asin

local StepCons = {}

local CellPart = Instance.new("Part")
CellPart.Name = "MazePart"
CellPart.FormFactor = "Custom"
CellPart.Locked = true
CellPart.BrickColor = BrickColor.new("Bright yellow")
CellPart.Material = "Neon"
CellPart.Anchored = true
CellPart.CanCollide = false
CellPart.TopSurface = "SmoothNoOutlines"
CellPart.BottomSurface = "SmoothNoOutlines"
CellPart.FrontSurface = "SmoothNoOutlines"
CellPart.BackSurface = "SmoothNoOutlines"
CellPart.LeftSurface = "SmoothNoOutlines"
CellPart.RightSurface = "SmoothNoOutlines"

local MazePart = Instance.new("Part")
MazePart.Name = "MazePart"
MazePart.FormFactor = "Custom"
MazePart.Locked = true
MazePart.BrickColor = BrickColor.new("Camo")
MazePart.Anchored = true
MazePart.CanCollide = true
MazePart.Material = "Grass"
MazePart.TopSurface = "SmoothNoOutlines"
MazePart.BottomSurface = "SmoothNoOutlines"
MazePart.FrontSurface = "SmoothNoOutlines"
MazePart.BackSurface = "SmoothNoOutlines"
MazePart.LeftSurface = "SmoothNoOutlines"
MazePart.RightSurface = "SmoothNoOutlines"

local function QuaternionFromCFrame(cf)
    local mx, my, mz, m00, m01, m02, m10, m11, m12, m20, m21, m22 = cf:components();
    local trace = m00 + m11 + m22 if trace > 0 then
        local s = math.sqrt(1 + trace);
        local recip = 0.5/s;
        return (m21-m12)*recip, (m02-m20)*recip, (m10-m01)*recip, s*0.5;
    else
        local i = 0;
        if m11 > m00 then
            i = 1;
        end;
        if m22 > (i == 0 and m00 or m11) then
            i = 2 end if i == 0 then
            local s = math.sqrt(m00-m11-m22+1);
            local recip = 0.5/s return 0.5*s, (m10+m01)*recip, (m20+m02)*recip, (m21-m12)*recip;
        elseif i == 1 then
            local s = math.sqrt(m11-m22-m00+1);
            local recip = 0.5/s;
            return (m01+m10)*recip, 0.5*s, (m21+m12)*recip, (m02-m20)*recip ;
        elseif i == 2 then
            local s = math.sqrt(m22-m00-m11+1);
            local recip = 0.5/s;
            return (m02+m20)*recip, (m12+m21)*recip, 0.5*s, (m10-m01)*recip;
        end;
    end;
end;

local function QuaternionToCFrame(px, py, pz, x, y, z, w)
    local xs, ys, zs = x + x, y + y, z + z;
    local wx, wy, wz = w*xs, w*ys, w*zs;
    local xx = x*xs;
    local xy = x*ys;
    local xz = x*zs;
    local yy = y*ys;
    local yz = y*zs;
    local zz = z*zs;
    return CFrame.new(px, py, pz,1-(yy+zz), xy - wz, xz + wy,xy + wz, 1-(xx+zz), yz - wx, xz - wy, yz + wx, 1-(xx+yy))
end;

local function QuaternionSlerp(a, b, t)
    local cosTheta = a[1]*b[1] + a[2]*b[2] + a[3]*b[3] + a[4]*b[4];
    local startInterp, finishInterp;
    if cosTheta >= 0.0001 then
        if (1 - cosTheta) > 0.0001 then
            local theta = math.acos(cosTheta);
            local invSinTheta = 1/math.sin(theta);
            startInterp = math.sin((1-t)*theta)*invSinTheta;
            finishInterp = math.sin(t*theta)*invSinTheta;
        else
            startInterp = 1-t finishInterp = t;
        end;
    else
        if (1+cosTheta) > 0.0001 then
            local theta = math.acos(-cosTheta);
            local invSinTheta = 1/math.sin(theta);
            startInterp = math.sin((t-1)*theta)*invSinTheta;
            finishInterp = math.sin(t*theta)*invSinTheta;
        else startInterp = t-1 finishInterp = t;
        end;
    end;
    return a[1]*startInterp + b[1]*finishInterp, a[2]*startInterp + b[2]*finishInterp, a[3]*startInterp + b[3]*finishInterp, a[4]*startInterp + b[4]*finishInterp;
end;

local function outElastic(t, b, c, d, a, p)
  if t == 0 then return b end

  t = t / d

  if t == 1 then return b + c end

  if not p then p = d * 0.3 end

  local s

  if not a or a < abs(c) then
    a = c
    s = p / 4
  else
    s = p / (2 * pi) * asin(c/a)
  end

  return a * pow(2, -10 * t) * sin((t * d - s) * (2 * pi) / p) + c + b
end

function VLerpEaseElas(a,b,t)
    a = CFrame.new(a)
    b = CFrame.new(b)
    local qa={QuaternionFromCFrame(a)};
    local qb={QuaternionFromCFrame(b)};
    local ax,ay,az=a.x,a.y,a.z;
    local bx,by,bz=b.x,b.y,b.z;
    local per = 0.5 --lower per=increase elasticity
    return QuaternionToCFrame(outElastic(t, ax, bx-ax, 1, nil, per), outElastic(t, ay, by-ay, 1, nil, per), outElastic(t, az, bz-az, 1, nil, per), QuaternionSlerp(qa, qb, t)).p;
end

--[[function Rand(min, max, accuracy, seed)
    accuracy = (accuracy and accuracy > 100 and 100) or 100
    seed = seed or (os and os.time() or tick())
    function randomizeSeed(seed)
        -- Make our seed more "random" so a number only repeats more than once pseudo randomly
        local sum = 0
        for n = 1, 100, 101 - accuracy do
            local num = (seed  * n) % tonumber(string.reverse(n)) -- Something I just went with
            sum = sum + num
        end
        return seed % sum
    end
    local reseed = randomizeSeed(seed)
    local rnum = reseed % (max + 1 - min) + min
    return math.floor(rnum)
end]]

local Rand = math.random

local RandX = Rand(1, FullX)
local RandY = Rand(1, FullY)

local CellStack = {}
local Grid = {}
local Discared = {}

function OnHit(Hit)
    if Hit.Parent and Plrs:GetPlayerFromCharacter(Hit.Parent) and Checking == false then
        Checking = true
        local WonChar = Hit.Parent
        HitCon:disconnect()
        HasChanged[EndPart] = "brickcolor"
        EndPart.BrickColor = BrickColor.new("Bright red")
        local Hint = Instance.new("Hint", workspace)
        Hint.Text = WonChar.Name .. " won the maze game!"
        wait(4)
        if Hint and Hint.Parent then
            Hint:Destroy()
        end
        Checking = false
    end
end

for _,v in pairs(workspace:GetChildren()) do
    if v.Name == "MazePart" then
        v:Destroy()
    end
end

function ProtObj(Obj)
    coroutine.wrap(function()
        local ObjClone = Obj:Clone()
        local StepIndex = #StepCons+1
        StepCons[StepIndex] = Obj.Changed:connect(function(P)
            if HasChanged[Obj] == nil or HasChanged[Obj] ~= P:lower() then
                for i = 1, FullX do
                    for j = 1, FullY do
                        for q = 2, 5 do
                            if Grid[i][j][q] and Grid[i][j][q][1] == Obj then
                                Grid[i][j][q][1] = ObjClone
                            end
                        end
                    end
                end
                if Obj.Parent ~= nil then
                    Obj:Destroy()
                end
                ObjClone.Parent = workspace
                if Obj == EndPart then
                    EndPart = ObjClone
                    HitCon:disconnect()
                    HitCon = nil
                    Checking = false
                    HitCon = EndPart.Touched:connect(OnHit)
                end
                ProtObj(ObjClone)
            else
                if Obj.Parent ~= nil then
                    ObjClone = Obj:Clone()
                    wait(1/30)
                    HasChanged[Obj] = nil
                end
            end
        end)
    end)()
end

local function CreateGrid()
    for i = 1, FullX do
        Grid[i] = {}
        Discared[i] = {}
        for j = 1, FullY do
            Grid[i][j] = {3}
            if i == RandX and j == RandY then
                local NewSize = Vector3.new(NodeWidth, EndHeight, NodeWidth)
                local NewCFrame = StartCF * CFrame.new(i*CellWidth, EndCFY, j*CellWidth)

                EndPart = CellPart:Clone()
                EndPart.Transparency = 1
                EndPart.Size = NewSize
                EndPart.CFrame = NewCFrame
                EndPart.Parent = workspace

                ProtObj(EndPart)

                Checking = false
                HitCon = EndPart.Touched:connect(OnHit)
            end
        end
    end
end

local function CreateWalls()
    local DoneX = false
    local DoneY = false

    coroutine.wrap(function()
        for j = 1, FullY do
            local LastTab = {}

            for i = 1, FullX+1 do
                local NewSize = Vector3.new(WallWidth, FullHeight, AddedCellWidth)
                local NewCFrame = StartCF * CFrame.new(i*CellWidth - WallOffset, HalfHeight, j*CellWidth)

                local Part = MazePart:Clone()
                Part.Size = NewSize
                Part.CFrame = NewCFrame
                Part.Parent = workspace

                ProtObj(Part)

                local NewTab = {Part}

                if i ~= 1 then
                    local newco = i-1
                    local FoundCell = Grid[newco][j]
                    FoundCell[2] = NewTab
                    FoundCell[3] = LastTab
                end

                LastTab = NewTab
            end

            WaitNum = WaitNum + 1
            if WaitNum % 4 == 0 then
                Heartbeat:wait()
            end
        end
        DoneX = true
    end)()

    coroutine.wrap(function()
        for i = 1, FullX do
            local LastTab = {}

            for j = 1, FullY+1 do
                local NewSize = Vector3.new(AddedCellWidth, FullHeight, WallWidth)
                local NewCFrame = StartCF * CFrame.new(i*CellWidth, HalfHeight, j*CellWidth - WallOffset)

                local Part = MazePart:Clone()
                Part.Size = NewSize
                Part.CFrame = NewCFrame
                Part.Parent = workspace

                ProtObj(Part)

                local NewTab = {Part}

                if j ~= 1 then
                    local newco = j-1
                    local FoundCell = Grid[i][newco]
                    FoundCell[4] = LastTab
                    FoundCell[5] = NewTab
                end

                LastTab = NewTab
            end

            WaitNum = WaitNum + 1
            if WaitNum % 4 == 0 then
                Heartbeat:wait()
            end
        end
        DoneY = true
    end)()

    repeat wait(1/30) until DoneX == true and DoneY == true
end

local function ChooseStart()
    if IsRandom == true then
        local RandX = Rand(1, FullX)
        local RandY = Rand(1, FullY)
        CellStack[1] = {RandX, RandY}
    else
        CellStack[1] = {StartCellNumX, FullY}
    end
end

local function NotInStack(X, Y)
    if Discared[X][Y] ~= nil then
        return false
    end
    for i = 1, #CellStack do
        local TempCell = CellStack[i]
        if TempCell[1] == X and TempCell[2] == Y then
            return false
        end
    end
    return true
end

local function GetNear(X, Y)
    local Nearby = {}
    if WaitNum % 40 == 0 then
        wait(1/30)
    end
    for i = 1, 4, 1 do
        if i == 1 then --Right
            local NewX = X+1
            if Grid[NewX] and Grid[NewX][Y] and NotInStack(NewX, Y) then
                Nearby[#Nearby+1] = {NewX, Y, i+1}
            end
        elseif i == 2 then --Left
            local NewX = X-1
            if Grid[NewX] and Grid[NewX][Y] and NotInStack(NewX, Y) then
                Nearby[#Nearby+1] = {NewX, Y, i+1}
            end
        elseif i == 3 then --Up
            local NewY = Y-1
            if Grid[X][NewY] and NotInStack(X, NewY) then
                Nearby[#Nearby+1] = {X, NewY, i+1}
            end
        else --Down
            local NewY = Y+1
            if Grid[X][NewY] and NotInStack(X, NewY) then
                Nearby[#Nearby+1] = {X, NewY, i+1}
            end
        end
    end
    return Nearby
end

local function KnockDown(X, Y, DirNum)
    local PartTab = Grid[X][Y][DirNum]
    local Part = PartTab[1]

    HasChanged[Part] = "parent"
    Part:Destroy()

    WaitNum = WaitNum + 1
end

local function ChooseNext()
    local NumCell = #CellStack
    if NumCell > 0 then
        local CurrentCell = CellStack[NumCell]
        local CurrentX = CurrentCell[1]
        local CurrentY = CurrentCell[2]
        local Nearby = GetNear(CurrentX, CurrentY)
        if #Nearby > 0 then
            local NextCell = Nearby[Rand(1, #Nearby)]
            CellStack[NumCell+1] = {NextCell[1], NextCell[2]}
            KnockDown(CurrentX, CurrentY, NextCell[3])
        else
            Discared[CurrentX][CurrentY] = true
            CellStack[NumCell] = nil
        end
        --wait(0.3)
        ChooseNext()
    end
end

CreateGrid()

CreateWalls()

ChooseStart()

math.randomseed(tick())

ChooseNext()

HasChanged[Grid[StartCellNumX-1][FullY][5][1]] = "parent"
HasChanged[Grid[StartCellNumX][FullY][5][1]] = "parent"
HasChanged[Grid[StartCellNumX+1][FullY][5][1]] = "parent"

Grid[StartCellNumX-1][FullY][5][1]:Destroy()
Grid[StartCellNumX][FullY][5][1]:Destroy()
Grid[StartCellNumX+1][FullY][5][1]:Destroy()

HasChanged[Grid[StartCellNumX-1][1][4][1]] = "parent"
HasChanged[Grid[StartCellNumX][1][4][1]] = "parent"
HasChanged[Grid[StartCellNumX+1][1][4][1]] = "parent"

Grid[StartCellNumX-1][1][4][1]:Destroy()
Grid[StartCellNumX][1][4][1]:Destroy()
Grid[StartCellNumX+1][1][4][1]:Destroy()

--[[Grid[1][StartCellNumY-1][5][1]:Destroy()
Grid[1][StartCellNumY][5][1]:Destroy()
Grid[1][StartCellNumY+1][5][1]:Destroy()

Grid[FullX][StartCellNumY-1][5][1]:Destroy()
Grid[FullX][StartCellNumY][5][1]:Destroy()
Grid[FullX][StartCellNumY+1][5][1]:Destroy()]]

HasChanged[EndPart] = "transparency"
EndPart.Transparency = 0

print("COMPLETED")

local ChatCon = nil

local PriorityQueue = {}

function GetNearSolve(X, Y)
    local Nearby = {}
    for i = 1, 4, 1 do
        if i == 1 then --Right
            local NewX = X+1
            if Grid[NewX] and Grid[NewX][Y] and Grid[X][Y][2][1].Parent == nil then
                Nearby[#Nearby+1] = {NewX, Y, 2}
            end
        elseif i == 2 then --Left
            local NewX = X-1
            if Grid[NewX] and Grid[NewX][Y] and Grid[X][Y][3][1].Parent == nil then
                Nearby[#Nearby+1] = {NewX, Y, 3}
            end
        elseif i == 3 then --Up
            local NewY = Y-1
            if Grid[X][NewY] and Grid[X][Y][4][1].Parent == nil then
                Nearby[#Nearby+1] = {X, NewY, 4}
            end
        else --Down
            local NewY = Y+1
            if Grid[X][NewY] and Grid[X][Y][5][1].Parent == nil then
                Nearby[#Nearby+1] = {X, NewY, 5}
            end
        end
    end
    return Nearby
end

function GetPri()
    local ReturnTab = PriorityQueue[1][2]
    table.remove(PriorityQueue, 1)
    return ReturnTab
end

function SetPri(Node, Priority)
    local AddTab = {Priority, Node}
    for i = 1, #PriorityQueue do
        if Priority < PriorityQueue[i][1] then
            table.insert(PriorityQueue, i, AddTab)
            return
        end
    end
    table.insert(PriorityQueue, AddTab)
end

function ValInCosts(Node, Costs)
    for OldNode,OldCosts in pairs(Costs) do
        if OldNode[1] == Node[1] and OldNode[2] == Node[2] then
            return OldCosts
        end
    end
    return false
end

function TraceBack(LastNode, CameFrom)
    while true do
        local BackTrackedNode = CameFrom[LastNode]
        if #BackTrackedNode == 0 then
            print("COMPLETED SOLVE")
            break
        end

        LastNode = BackTrackedNode

        WaitNum = WaitNum + 1

        if WaitNum % 10 == 0 then
            wait(1/30)
        end

        local Part = CellPart:Clone()
        Part.CanCollide = false
        Part.Transparency = 0
        Part.Anchored = true
        Part.Material = "Wood"
        Part.BrickColor = BrickColor.new("Bright bluish green")
        Part.Size = Vector3.new(NodeWidth, EndHeight, NodeWidth)
        Part.CFrame = StartCF * CFrame.new(LastNode[1]*CellWidth, EndCFY, LastNode[2]*CellWidth)
        Part.Parent = workspace

        ProtObj(Part)
    end
end

function Heuristic(Goal, Current)
    return abs(Goal[1] - Current[1]) + abs(Goal[2] - Current[2])
end

local Ended = false
ChatCon = LP.Chatted:connect(function(Msg)
    if Msg:lower() == "generate" or Msg:lower() == "/e generate" then
        ChatCon:disconnect()
        HitCon:disconnect()
        if #StepCons > 0 then
            for i = 1, #StepCons do
                StepCons[i]:disconnect()
            end
        end
        Ended = true
        print("Ended last maze")
    elseif Msg:lower() == "solve" or Msg:lower() == "/e solve" then
        local Start = {StartCellNumX, FullY}

        SetPri(Start, 0)

        local CameFrom = {}
        local TotalCost = {}

        CameFrom[Start] = {} --Maybe won't work as might record same coords on multiple searches and overwrite
        TotalCost[Start] = 0

        local GoalTab = {RandX, RandY}

        while #PriorityQueue > 0 do

            if Ended == true then
                print("Stopped search")
                break
            end

            local CurrentNode = GetPri()
            local NodeX = CurrentNode[1]
            local NodeY = CurrentNode[2]

            if NodeX == RandX and NodeY == RandY then
                print("FOUND")
                TraceBack(CurrentNode, CameFrom)
                break
            end

            local Nearby = GetNearSolve(NodeX, NodeY)

            for i = 1, #Nearby do
                local NextNode = Nearby[i]
                local NewCost = TotalCost[CurrentNode] + 1
                local ValueInCosts = ValInCosts(NextNode, TotalCost)
                if ValueInCosts == false or NewCost < ValueInCosts then
                    TotalCost[NextNode] = NewCost
                    local Priority = NewCost + Heuristic(GoalTab, NextNode)
                    SetPri(NextNode, Priority)
                    CameFrom[NextNode] = CurrentNode
                end
            end
        end
    end
end)