local I=game:GetService("\082\101\112\108\105\099\097\116\101\100\083\116\111\114\097\103\101")local x=require((I: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 u=x:GetResource("\069\120\116\101\114\110\097\108\085\116\105\108\046\078\101\120\117\115\073\110\115\116\097\110\099\101\046\078\101\120\117\115\079\098\106\101\099\116")local U=u:Extend()U:SetClassName("\071\114\097\112\104\083\111\108\118\101\114")function U.__new(I)I:InitializeSuper()I.Nodes={}I.Edges={}end function U.AddNode(U,I,x,u)if not U.Nodes[I]then U.Nodes[I]={X=x,Y=u}U.Edges[I]={}end end function U.AddEdge(u,I,x)for I,u in pairs(u.Edges[I])do if u==x then return end end table.insert(u.Edges[I],x)table.insert(u.Edges[x],I)end function U.GetDistance(u,I,x)return((u.Nodes[I].X-u.Nodes[x].X)^2+(u.Nodes[I].Y-u.Nodes[x].Y)^2)^.5 end function U.GetShortestDistance(u,I,x)local U=1 local k,R={},{}local p,z={},{}k[I]=true p[I]=0 z[I]=u:GetDistance(I,x)while U>0 do local I,n=math.huge,nil for x,u in pairs(k)do local U=z[x]if U<I then I=U n=x end end if n==x then return p[x]end k[n]=nil U=U-1 R[n]=true for I,J in pairs(u.Edges[n])do if not R[J]then local I=p[n]+u:GetDistance(n,J)if not p[J]or I<p[J]then p[J]=I z[J]=I+u:GetDistance(J,x)if not k[J]then k[J]=true U=U+1 end end end end end end return U
--[[
TheNexusAvenger

Implementation of A* to find the shortest paths.
--]]

local ReplicatedStorage = game:GetService("ReplicatedStorage")

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

local NexusObject = ReplicatedStorageProject:GetResource("ExternalUtil.NexusInstance.NexusObject")

local GraphSolver = NexusObject:Extend()
GraphSolver:SetClassName("GraphSolver")



--[[
Creates a graph solver.
--]]
function GraphSolver:__new()
    self:InitializeSuper()

    --Set up the state.
    self.Nodes = {}
    self.Edges = {}
end

--[[
Adds a node to the graph.
--]]
function GraphSolver:AddNode(Id,X,Y)
    if not self.Nodes[Id] then
        self.Nodes[Id] = {X=X,Y=Y}
        self.Edges[Id] = {}
    end
end

--[[
Adds an edge between 2 nodes.
--]]
function GraphSolver:AddEdge(Id1,Id2)
    --Return if the edge exists.
    for _,EdgeId in pairs(self.Edges[Id1]) do
        if EdgeId == Id2 then
            return
        end
    end

    --Add the edge.
    table.insert(self.Edges[Id1],Id2)
    table.insert(self.Edges[Id2],Id1)
end

--[[
Returns the distance between 2 nodes.
--]]
function GraphSolver:GetDistance(Id1,Id2)
    return (((self.Nodes[Id1].X - self.Nodes[Id2].X) ^ 2) + ((self.Nodes[Id1].Y - self.Nodes[Id2].Y) ^ 2)) ^ 0.5
end

--[[
Returns the shortest distance between 2 nodes.
--]]
function GraphSolver:GetShortestDistance(StartId,EndId)
    local TotalOpenNodes = 1
    local OpenNodes,ClosedNodes = {},{}
    local GScores,FScores = {},{}
    OpenNodes[StartId] = true
    GScores[StartId] = 0
    FScores[StartId] = self:GetDistance(StartId,EndId)

    while TotalOpenNodes > 0 do
        --Determine the next lowest node.
        local LowestFScore,LowesetNodeId = math.huge,nil
        for NodeId,_  in pairs(OpenNodes) do
            local FScore = FScores[NodeId]
            if FScore < LowestFScore then
                LowestFScore = FScore
                LowesetNodeId = NodeId
            end
        end

        --Return if the current node is the target.
        if LowesetNodeId == EndId then
            return GScores[EndId]
        end

        --Move the node to the used set.
        OpenNodes[LowesetNodeId] = nil
        TotalOpenNodes = TotalOpenNodes - 1
        ClosedNodes[LowesetNodeId] = true

        --Add the neighbor nodes if they aren't used already.
        for _,NeighborNodeId in pairs(self.Edges[LowesetNodeId]) do
            if not ClosedNodes[NeighborNodeId] then
                local NewGScore = GScores[LowesetNodeId] + self:GetDistance(LowesetNodeId,NeighborNodeId)
                if not GScores[NeighborNodeId] or NewGScore < GScores[NeighborNodeId] then
                    GScores[NeighborNodeId] = NewGScore
                    FScores[NeighborNodeId] = NewGScore + self:GetDistance(NeighborNodeId,EndId)
                    if not OpenNodes[NeighborNodeId] then
                        OpenNodes[NeighborNodeId] = true
                        TotalOpenNodes = TotalOpenNodes + 1
                    end
                end
            end
        end
    end
end



return GraphSolver