local I=200 local x=200 local u=game:GetService("\082\101\112\108\105\099\097\116\101\100\083\116\111\114\097\103\101")local U=require((u:WaitForChild("\080\114\111\106\101\099\116")):WaitForChild("\082\101\112\108\105\099\097\116\101\100\083\116\111\114\097\103\101"))local k=U:GetResource("\071\097\109\101\068\097\116\097\046\071\101\110\101\114\097\116\105\111\110\046\077\097\112\067\101\108\108\115")local R=U:GetResource("\071\097\109\101\068\097\116\097\046\071\101\110\101\114\097\116\105\111\110\046\078\080\067\076\111\099\097\116\105\111\110\115")local p=U:GetResource("\083\116\097\116\101\046\080\097\116\104\070\105\110\100\046\067\097\099\104\101\100\071\114\097\112\104\083\111\108\118\101\114")local z=p:Extend()z:SetClassName("\077\097\112\071\114\097\112\104\083\111\108\118\101\114")function z.Create()local I=z.new()I:PopulateMapData()return I end function z.GetCellsForLine(k,I,x,u,U)local R={}local p={}local function z(I,x)if not p[tostring(I)..("\095"..tostring(x))]then table.insert(R,{X=I,Y=x})p[tostring(I)..("\095"..tostring(x))]=true end end z(I,x)z(u,U)if I~=u then if u<I then I,u=u,I x,U=U,x end for k=I,u,1 do local R=(k-I)/(u-I)z(k,math.round(x+(U-x)*R))end end if x~=U then if U<x then I,u=u,I x,U=U,x end for k=x,U,1 do local R=(k-x)/(U-x)z(math.round(I+(u-I)*R),k)end end return R end function z.GetCellType(u,I,x)if not k[I]then return-1 end return k[I][x]or-1 end function z.IsPathBlocked(k,I,x,u,U)for I,x in pairs(k:GetCellsForLine(I,x,u,U))do local u=k:GetCellType(x.X,x.Y)if u==4 or u==5 then return true end end return false end function z.CellIsRoadNode(u,I,x)if u:GetCellType(I,x)~=6 then return false end local U,k,R,p=u:GetCellType(I,x+1)==6,u:GetCellType(I,x-1)==6,u:GetCellType(I+1,x)==6,u:GetCellType(I-1,x)==6 if U and(not k and(not R and not p))then return true elseif not U and(k and(not R and not p))then return true elseif not U and(not k and(R and not p))then return true elseif not U and(not k and(not R and p))then return true elseif not U and(not k and(not R and not p))then return true end return false end function z.PopulateConnectedRoads(u)local U={}for I=1,I,1 do for x=1,x,1 do if u:GetCellType(I,x)==6 then local k,R,p,z=u:GetCellType(I,x+1)==6,u:GetCellType(I,x-1)==6,u:GetCellType(I+1,x)==6,u:GetCellType(I-1,x)==6 if not(k and(R and(not p and not z)))and not(not k and(not R and(p and z)))then local R=tostring(I)..("\095"..tostring(x))U[R]={I,x;R;p,k}u:AddNode(R,I,x)end end end end for k,R in pairs(U)do if R[4]then for I=R[1]+1,I,1 do local x=tostring(I)..("\095"..tostring(R[2]))if U[x]then u:AddEdge(k,x)break end end end if R[5]then for I=R[2]+1,x,1 do local x=tostring(R[1])..("\095"..tostring(I))if U[x]then u:AddEdge(k,x)break end end end end end function z.PopulateRoadEnds(u)local U={}for I=1,I,1 do for x=1,x,1 do if u:CellIsRoadNode(I,x)then local k=tostring(I)..("\095"..tostring(x))table.insert(U,{I;x,k})u:AddNode(k,I,x)end end end for I=1,#U,1 do local x=U[I]local k,R={},{}for I=I+1,#U,1 do table.insert(k,I)R[I]=u:GetDistance(x[3],U[I][3])end table.sort(k,function(I,x)return R[I]<R[x]end)for I,k in pairs(k)do local R=U[k]if not u:IsPathBlocked(x[1],x[2],R[1],R[2])then u:AddEdge(x[3],R[3])break end end end end function z.PopulateNPCs(I)local x={}for u,U in pairs(R)do local k,R=U.CellX,U.CellY local p=tostring(k)..("\095"..tostring(R))x[p]={k;R;p}I:AddNode(p,k,R)end for u,U in pairs(x)do local k,R=math.huge,nil for u,p in pairs(I.Nodes)do if u~=U[3]and not x[u]then local x=I:GetDistance(U[3],u)if x<k then k=x R=u end end end if R then I:AddEdge(U[3],R)end end end function z.PopulateMapData(I)I:PopulateRoadEnds()I:PopulateConnectedRoads()I:PopulateNPCs()end return z
--[[
TheNexusAvenger

Creates and solves graphs of the map.
--]]

local MAP_SIZE_X = 200
local MAP_SIZE_Y = 200



local ReplicatedStorage = game:GetService("ReplicatedStorage")

local ReplicatedStorageProject = require(ReplicatedStorage:WaitForChild("Project"):WaitForChild("ReplicatedStorage"))

local MapCells = ReplicatedStorageProject:GetResource("GameData.Generation.MapCells")
local NPCLocations = ReplicatedStorageProject:GetResource("GameData.Generation.NPCLocations")
local CachedGraphSolver = ReplicatedStorageProject:GetResource("State.PathFind.CachedGraphSolver")

local MapGraphSolver = CachedGraphSolver:Extend()
MapGraphSolver:SetClassName("MapGraphSolver")



--[[
Creates a map graph solver.
--]]
function MapGraphSolver.Create()
    local Solver = MapGraphSolver.new()
    Solver:PopulateMapData()
    return Solver
end

--[[
Returns the cells between 2 points.
--]]
function MapGraphSolver:GetCellsForLine(StartX,StartY,EndX,EndY)
    local Points = {}
    local UsedPointsMap = {}

    --[[
    Adds a point.
    --]]
    local function AddPoint(X,Y)
        if not UsedPointsMap[tostring(X).."_"..tostring(Y)] then
            table.insert(Points,{X=X,Y=Y})
            UsedPointsMap[tostring(X).."_"..tostring(Y)] = true
        end
    end
    AddPoint(StartX,StartY)
    AddPoint(EndX,EndY)

    --Add the cells going in the X direction.
    if StartX ~= EndX then
        if EndX < StartX then
            StartX,EndX = EndX,StartX
            StartY,EndY = EndY,StartY
        end
        for X = StartX,EndX do
            local Ratio = (X - StartX)/(EndX - StartX)
            AddPoint(X,math.round(StartY + ((EndY - StartY) * Ratio)))
        end
    end

    --Add the cells going in the Y direction.
    if StartY ~= EndY then
        if EndY < StartY then
            StartX,EndX = EndX,StartX
            StartY,EndY = EndY,StartY
        end
        for Y = StartY,EndY do
            local Ratio = (Y - StartY)/(EndY - StartY)
            AddPoint(math.round(StartX + ((EndX - StartX) * Ratio)),Y)
        end
    end

    --Return the points.
    return Points
end

--[[
Returns the cell type for a given position.
--]]
function MapGraphSolver:GetCellType(X,Y)
    if not MapCells[X] then
        return -1
    end
    return MapCells[X][Y] or -1
end

--[[
Returns if a path is blocked.
--]]
function MapGraphSolver:IsPathBlocked(StartX,StartY,EndX,EndY)
    --Return true if the path hits rock or water.
    for _,Cell in pairs(self:GetCellsForLine(StartX,StartY,EndX,EndY)) do
        local CellType = self:GetCellType(Cell.X,Cell.Y)
        if CellType == 4 or CellType == 5 then
            return true
        end
    end

    --Return false (not blocked).
    return false
end

--[[
Returns if a cell is a road node.
--]]
function MapGraphSolver:CellIsRoadNode(X,Y)
    --Return if the cell isn't a road.
    if self:GetCellType(X,Y) ~= 6 then
        return false
    end

    --Return depending on the surrounding cells.
    local TopIsRoad,BottomIsRoad,LeftIsRoad,RightIsRoad = self:GetCellType(X,Y + 1) == 6,self:GetCellType(X,Y - 1) == 6,self:GetCellType(X + 1,Y) == 6,self:GetCellType(X - 1,Y) == 6
    if TopIsRoad and not BottomIsRoad and not LeftIsRoad and not RightIsRoad then
        return true
    elseif not TopIsRoad and BottomIsRoad and not LeftIsRoad and not RightIsRoad then
        return true
    elseif not TopIsRoad and not BottomIsRoad and LeftIsRoad and not RightIsRoad then
        return true
    elseif not TopIsRoad and not BottomIsRoad and not LeftIsRoad and RightIsRoad then
        return true
    elseif not TopIsRoad and not BottomIsRoad and not LeftIsRoad and not RightIsRoad then
        return true
    end
    return false
end

--[[
Populates the nodes for the connected roads.
--]]
function MapGraphSolver:PopulateConnectedRoads()
    --Create the nodes.
    local Nodes = {}
    for X = 1,MAP_SIZE_X do
        for Y = 1,MAP_SIZE_Y do
            if self:GetCellType(X,Y) == 6 then
                local TopIsRoad,BottomIsRoad,LeftIsRoad,RightIsRoad = self:GetCellType(X,Y + 1) == 6,self:GetCellType(X,Y - 1) == 6,self:GetCellType(X + 1,Y) == 6,self:GetCellType(X - 1,Y) == 6
                if not (TopIsRoad and BottomIsRoad and not LeftIsRoad and not RightIsRoad) and not (not TopIsRoad and not BottomIsRoad and LeftIsRoad and RightIsRoad) then
                    local Id = tostring(X).."_"..tostring(Y)
                    Nodes[Id] = {X,Y,Id,LeftIsRoad,TopIsRoad}
                    self:AddNode(Id,X,Y)
                end
            end
        end
    end

    --Connect the nodes.
    --Only the top and right are checked since they connect to left and bottom.
    for NodeId,Node in pairs(Nodes) do
        --Connect to the right.
        if Node[4] then
            for X = Node[1] + 1,MAP_SIZE_X do
                local RightId = tostring(X).."_"..tostring(Node[2])
                if Nodes[RightId] then
                    self:AddEdge(NodeId,RightId)
                    break
                end
            end
        end

        --Connect to the top.
        if Node[5] then
            for Y = Node[2] + 1,MAP_SIZE_Y do
                local TopId = tostring(Node[1]).."_"..tostring(Y)
                if Nodes[TopId] then
                    self:AddEdge(NodeId,TopId)
                    break
                end
            end
        end
    end
end

--[[
Populates the nodes for the road ends.
--]]
function MapGraphSolver:PopulateRoadEnds()
    --Create the nodes.
    local Nodes = {}
    for X = 1,MAP_SIZE_X do
        for Y = 1,MAP_SIZE_Y do
            if self:CellIsRoadNode(X,Y) then
                local Id = tostring(X).."_"..tostring(Y)
                table.insert(Nodes,{X,Y,Id})
                self:AddNode(Id,X,Y)
            end
        end
    end

    --Create the edges between the closest end nodes.
    --All possible edges aren't created due to performance reasons.
    for i = 1,#Nodes do
        --Add the nodes and sort by the closest.
        local Start = Nodes[i]
        local ConnectableNodes,Distances = {},{}
        for j = i + 1,#Nodes do
            table.insert(ConnectableNodes,j)
            Distances[j] = self:GetDistance(Start[3],Nodes[j][3])
        end
        table.sort(ConnectableNodes,function(a,b)
            return Distances[a] < Distances[b]
        end)

        --Add the edge.
        for _,EndId in pairs(ConnectableNodes) do
            local End = Nodes[EndId]
            if not self:IsPathBlocked(Start[1],Start[2],End[1],End[2]) then
                self:AddEdge(Start[3],End[3])
                break
            end
        end
    end
end

--[[
Connects the NPCs to the nearest nodes.
--]]
function MapGraphSolver:PopulateNPCs()
    --Create the nodes.
    local Nodes = {}
    for _,NPCLocationData in pairs(NPCLocations) do
        local X,Y = NPCLocationData.CellX,NPCLocationData.CellY
        local Id = tostring(X).."_"..tostring(Y)
        Nodes[Id] = {X,Y,Id}
        self:AddNode(Id,X,Y)
    end

    --Connect the NPCs to the nearest nodes.
    for _,Start in pairs(Nodes) do
        --Get the closest node.
        local LowestDistance,ClosestNodeId = math.huge,nil
        for Id,_ in pairs(self.Nodes) do
            if Id ~= Start[3] and not Nodes[Id] then
                local Distance = self:GetDistance(Start[3],Id)
                if Distance < LowestDistance then
                    LowestDistance = Distance
                    ClosestNodeId = Id
                end
            end
        end

        --Create the edge.
        if ClosestNodeId then
            self:AddEdge(Start[3],ClosestNodeId)
        end
    end
end

--[[
Populates the nodes and edges with the map data.
--]]
function MapGraphSolver:PopulateMapData()
    self:PopulateRoadEnds()
    self:PopulateConnectedRoads()
    self:PopulateNPCs()
end



return MapGraphSolver