Terrain Generator with chunk loader, and LOD system

--[[
    Please note several of the methods used in this are non-conventional; part of the challenge i gave myself
    for this was to only use methods of my own making, without looking up how other people did it.
--]]


local Player = game.Players.LocalPlayer
repeat wait() until game.ReplicatedStorage.Seed.Value~=0
repeat wait() until Player.PlayerGui
repeat wait() until workspace.CurrentCamera

Player.Chatted:connect(function(c)
    if c:sub(1,3) == "ws/" then
        local speed = tonumber(c:sub(4))
        if speed and Player.Character then
            Player.Character.Humanoid.WalkSpeed = speed
        end
    end
end)
workspace.CurrentCamera.FieldOfView = 50

wait(2)


-- Stats gui is disabled by default, i enable it for studio testing

local StatsGui = Player.PlayerGui:WaitForChild("Stats")
local Label = StatsGui.TextLabel
Label.Parent = nil

QueueSizeGui = Label:clone()
QueueSizeGui.Parent = StatsGui

QueueTimeGui = Label:clone()
QueueTimeGui.Parent = StatsGui

QueueClearTimeGui = Label:clone()
QueueClearTimeGui.Parent = StatsGui

SortTimeGui = Label:clone()
SortTimeGui.Parent = StatsGui

TotalTimeGui = Label:clone()
TotalTimeGui.Parent = StatsGui


local randomCache = {}
--[[
    Terrain values are cached since they're somewhat expensive to generate, this leads to a
    slow increase in RAM when travelling far distances, since I don't currently clear the cache.
--]]
function random2d(x,y,seed)
    local cache = randomCache[seed]
    if not cache then
        cache = {}
        randomCache[seed]=cache
    end
    local cacheX = cache[x]
    if not cacheX then
        cacheX = {}
        cache[x]=cacheX
    end
    local value = cacheX[y]
    if not value then
        local seedMulti = Random.new(seed or 1):NextInteger(1,1000000)
        local xRand = Random.new(x*seedMulti):NextInteger(1,1000000)
        local yRand = Random.new(-y*seedMulti):NextInteger(1,1000000)
        value = Random.new(xRand+yRand):NextNumber()
        cacheX[y]=value
    end
    return value
end

function slerp(a,b,c) -- sine interpolation
    return a+(b-a)*((math.sin(math.pi*(c-.5))+1)/2)
end

function lerp(a,b,c) -- linear interpolation
    return a+(b-a)*c
end

function squeeze(h,e)
    --[[ this function is used to make mountains rarer and plains more common, it
        squeezes height values towards 0.5, which is water level for this terrain generator
    --]]
    if h>=0.5 then
        return 0.5+((((h-0.5)/0.5)^e)/2)
    else
        return 0.5-((((0.5-h)/0.5)^e)/2)
    end
end

function colerp(a,b,c) -- linear interpolation for colors
    return Color3.new(a.r+(b.r-a.r)*c,a.g+(b.g-a.g)*c,a.b+(b.b-a.b)*c)
end

function biterpolate(x,y,tl,tr,bl,br,lerp)
    -- bilinear interpolation, gets the value of a point based on the values of the surrounding 4 points
    if lerp then
        local top = lerp(tl,tr,x)
        local bottom = lerp(bl,br,x)
        return lerp(top,bottom,y)
    else
        local top = tl+(tr-tl)*x
        local bottom = bl+(br-bl)*x
        return top+(bottom-top)*y
    end
end

function randomTerrain(x,y,scale,seed)
    local xs,ys = math.floor(x/scale),math.floor(y/scale)
    local tl = random2d(xs,ys,seed)
    local tr = random2d(xs+1,ys,seed)
    local bl = random2d(xs,ys+1,seed)
    local br = random2d(xs+1,ys+1,seed)

    local h = biterpolate((x/scale)%1,(y/scale)%1,tl,tr,bl,br,slerp)
    return h
end

local nodes = {}
local grid = {}
local chunks = {}
local chunklist = {}
local seed = game.ReplicatedStorage.Seed.Value --123
local chunkscale = 64*2 -- How wide the chunks are, in studs


-- Layers is a list of the heightmaps layered to generate the terrain
-- the first value is how wide the heightmap nodes are (inverse amplitude)
-- the second value is the magnitude (how much the heightmap layer effects the height)
-- generally the smaller the width the lower the magnitude

--[/[
local Layers = {
[1]={300,8,{}};
[2]={100,3,{}};
[3]={50,1.5,{}};
[4]={25,.5,{}};
[5]={10,.3,{}};
[6]={5,.1,{}};
[7]={3,.06,{}};
[8]={1,.02,{}};
}
--]]

--[[
local Layers = {
    [1]={600,10};
    [2]={300,8};
    [3]={100,4};
    [4]={50,2};
    [5]={25,.75};
    [6]={10,.5};
    [7]={5,.2};
    [8]={3,.1};
    [9]={1,.05};
}
--]]


local Recycler = {}
local RecycleStorage = 0

function RecyclePart(Part)
    --Part.CFrame = CFrame.new(0,-10000,0)
    Part.Parent = nil
    RecycleStorage = RecycleStorage+1
    Recycler[RecycleStorage]=Part
end

function ReusePart()
    local Part = Recycler[RecycleStorage]
    Recycler[RecycleStorage]=nil
    return Part
end

function SpawnChunk(X,Y,Resolution,NoCollide) -- Resolution is how many blocks wide to spawn the chunk
    chunks[X]=chunks[X] or {}
    if not chunks[X][Y] then
        local numLayers = #Layers

        local realSeed = seed*numLayers

        local chunk = {
            X=X;
            Y=Y;
            resolution=Resolution;
            grid={};
            parts={};
            model=Instance.new("Model")
        }
        chunk.model.Name = "chunk "..X.."x"..Y.."y"

        local partScale = chunkscale/Resolution
        local offsetX,offsetY = (X*chunkscale)+(partScale/2),(Y*chunkscale)+(partScale/2)

        for x = 1,Resolution do
            for y = 1,Resolution do
                local pX,pY = offsetX+(partScale*(x-1)),offsetY+(partScale*(y-1)) -- Position of part
                local tX,tY = pX/4,pY/4

                local rx,ry = tX+1000000,tY+1000000
                --[[
                    1000000 added to chunk coordinates, because chunks below 0,0
                    are mirrored and i was to lazy to fix it
                --]]

                local height = 0
                local maxheight = 0
                for i = 1,numLayers do
                    local Layer = Layers[i]
                    local Size = Layer[1]
                    local Power = Layer[2]
                    if Size*8>=partScale then
                        height=height+(randomTerrain(rx,ry,Size,realSeed+i)*Power)
                        maxheight=maxheight+Power
                    end
                end
                height=height/maxheight -- normalize height

                height=squeeze(height,1.5+(math.abs((height-0.5)*2)*1.5))--*1.5))

                local originalheight = height
                height = height*1500 -- height is multiplied in studs how tall the highest mountains should be/2

                height=height-(1500/2) -- move height down by half so water level is at 0
                if height <= 0 then
                    height = 0 -- set height to 0 if under 0, so water gets positioned correctly
                end


                local P = Instance.new("Part")
                P.Anchored = true
                P.TopSurface = "Smooth"
                P.Size = Vector3.new(partScale,height+2,partScale)
                P.CFrame = CFrame.new(pX,(height+2)/2,pY)
                P.CanCollide = not NoCollide
                if height <= 0 then -- water
                    P.Color = Color3.new(0.0352, 0.5372, 0.8117)
                    P.Material = "Foil"
                elseif height<=4 then -- sand
                    P.Color = Color3.new(1,0.8,0.6)
                    P.Material = "Sand"
                else -- grass
                    local mul = height/600
                    P.Color = colerp(Color3.new(0.2431, 1*.8, 0.2274*.8),Color3.new(1,1,1),mul) -- 58/255, 125/255, 21/255
                    P.Material = "Grass"
                end
                P.Parent = chunk.model
                table.insert(chunk.parts,P)
            end
        end
        chunks[X][Y]=chunk
        chunklist[chunk]=true

        chunk.model.Parent = workspace

        return chunk
    else
        return chunks[X][Y]
    end
end

function RemoveChunk(X,Y)
    local chunk = chunks[X] and chunks[X][Y]
    if chunk then
        if chunk.model then
            chunk.model.Parent = nil
        end
        --[[for i,P in pairs(chunk.parts) do
            RecyclePart(P)
        end
        chunk.parts = {}]]

        chunks[X][Y]=nil
    end
end

-- LODS are the ranges at which to load different detail levels
-- size is how wide an area in chunks that LOD applies to
-- resolution is the detail level of the LOD, how many blocks wide to load each chunk
local LODS = {
    {
        size = 2;
        resolution = 32;
    };
    {
        size = 4;
        resolution = 16;
    };
    {
        size = 8;
        resolution = 8;
    };
    {
        size = 12;
        resolution = 4;
    };
    --[/[
    {
        size = 24;
        resolution = 2;
    };
    --]]
    {
        size = 48;
        resolution = 1;
    };
}

local Queue = {}
local QueueIndex = {}

function AddChunkToQueue(x,y)
    local Row = QueueIndex[x]
    if not Row or not Row[y] then
        if not Row then
            Row = {}
            QueueIndex[x]=Row
        end
        Row[y]=true
        table.insert(Queue,{x,y})
    end
end

local MaxSortTime = 0
local MaxQueueTime = 0
local MaxQueueClearTime = 0
local MaxTotalTime = 0
local LX,LY = 0,0
game:GetService("RunService").RenderStepped:connect(function()
    if Player.Character then
        local Root = Player.Character.HumanoidRootPart
        local X,Y = math.floor(Root.Position.X),math.floor(Root.Position.Z)

        local Root = Player.Character.HumanoidRootPart
        local worldX,worldY = Root.Position.X/chunkscale,Root.Position.Z/chunkscale
        local ChunkX,ChunkY = math.floor(worldX),math.floor(worldY)

        local chunksremoved = 0
        local partsremoved = 0
        local chunksadded = 0
        local partsadded = 0
        local start = tick()

        if LX~=X or LY~=Y then
            LX,LY = X,Y
            local t = tick()

            local renderDist = LODS[#LODS].size
            for x = ChunkX-renderDist,ChunkX+renderDist do
                for y = ChunkY-renderDist,ChunkY+renderDist do
                    local dist = (((x+.5)-worldX)^2+((y+0.5)-worldY)^2)^.5
                    for i = 1,#LODS do
                        local LOD = LODS[i]
                        if dist<LOD.size*.9 then
                            local chunk = chunks[x] and chunks[x][y]
                            if (not chunk) or chunk.resolution~=LOD.resolution then
                                AddChunkToQueue(x,y)
                            end
                            break
                        end
                    end
                end
            end

            for i,c in pairs(Queue) do
                c[3] = (((c[1]+.5)-worldX)^2+((c[2]+0.5)-worldY)^2)^.5
            end

            table.sort(Queue,function(a,b)
                return a[3]<b[3]
            end)

            local endLOD = LODS[#LODS]
            local maxDist = endLOD.size
            local removed = {}
            for chunk in pairs(chunklist) do
                if chunk.X>ChunkX+renderDist or chunk.X<ChunkX-renderDist or chunk.Y>ChunkY+renderDist or chunk.Y<ChunkY-renderDist then
                    RemoveChunk(chunk.X,chunk.Y)
                    removed[chunk]=true
                end
            end

            for chunk in pairs(removed) do
                chunklist[chunk]=nil
            end

            local SortTime = tick()-t
            if SortTime>MaxSortTime then
                MaxSortTime = SortTime
            end
        end

        -- Queue System

        local QueueRemoval = {}

        local t = tick()
        for i,c in pairs(Queue) do
            if (tick()-t)*1000>5 then break end -- Limits queue time to 5 milliseconds
            QueueRemoval[c]=true
            QueueIndex[c[1]][c[2]]=nil
            local x,y,distance = c[1],c[2],c[3]
            for i,LOD in pairs(LODS) do
                local LODres = LOD.resolution
                if distance <= LOD.size*.9 then
                    local chunk = chunks[x] and chunks[x][y]
                    if chunk and chunk.resolution~=LODres and (i==1 or distance>LODS[i-1].size*.9) then
                        RemoveChunk(x,y)
                        chunklist[chunk]=nil

                        chunksremoved = chunksremoved+1
                        partsremoved = partsremoved+(chunk.resolution^2)

                        chunk = SpawnChunk(x,y,LODres,i>1)
                        chunksadded = chunksadded+1
                        partsadded = partsadded+(LODres^2)
                    elseif not chunk then
                        chunk = SpawnChunk(x,y,LODres,i>1)
                        chunksadded = chunksadded+1
                        partsadded = partsadded+(LODres^2)
                    end
                    break
                end
            end
        end
        local QueueTime = tick()-t
        if QueueTime>MaxQueueTime then
            MaxQueueTime = QueueTime
        end

        local t = tick()
        local newQueue = {}
        for i,c in pairs(Queue) do
            if not QueueRemoval[c] then
                table.insert(newQueue,c)
            end
        end
        Queue = newQueue
        local ClearTime = tick()-t
        if ClearTime>MaxQueueClearTime then
            MaxQueueClearTime = ClearTime
        end

        local TotalTime = tick()-start
        if TotalTime>MaxTotalTime then
            MaxTotalTime = TotalTime
        end
    end
    QueueSizeGui.Text = "QueueSize: "..#Queue
    QueueTimeGui.Text = "MaxQueueTime: "..math.ceil(MaxQueueTime*100000)/100
    QueueClearTimeGui.Text = "MaxQueueClearTime: "..math.ceil(MaxQueueClearTime*100000)/100
    SortTimeGui.Text = "MaxSortTime: "..math.ceil(MaxSortTime*100000)/100
    TotalTimeGui.Text = "MaxTotalTime: "..math.ceil(MaxTotalTime*100000)/100
end)