NodedPathAlgorithm.lua

local function GetIndexFromNode(nodedIndex, node)
	return nodedIndex[node]
end

local function GetNodeFromIndex(indexedNodes, index)
	return indexedNodes[index]
end

--[[
    Link two nodes if it has a weld constraint in it connected to another node.
    Assuming that WeldConstraint is parented to Part0
]]
local function ConnectNodes(indexedNodes, nodedIndex) --// {A, ...} = {B, ...} = magnitude
	local connectedNodes = {}
	for indexA, node:BasePart in indexedNodes do 
		for _, weld: WeldConstraint in node:GetChildren() do
			if not weld:IsA("WeldConstraint") or not weld.Part0 or not weld.Part1 then
				continue
			end

			local indexB = GetIndexFromNode(nodedIndex, weld.Part1)
			if not indexB then
				continue
			end
			if not connectedNodes[indexA] then
				connectedNodes[indexA] = {}
			end
			if not connectedNodes[indexB] then
				connectedNodes[indexB] = {}
			end
			local magnitudeOfAB = (weld.Part0.Position - weld.Part1.Position).Magnitude
			connectedNodes[indexA][indexB] = magnitudeOfAB
			connectedNodes[indexB][indexA] = magnitudeOfAB
			--weld:Destroy()
		end
	end
	return connectedNodes
end

--[[
    Instead of {1 = node, 2 = node, ...}, we do {node = 1, node = 2, ...}.
    Means less for loop searching, but more memory used.
    nodes[node] = index
]]
local function NodeIndex(indexedNodes)
	local nodedIndex = {}
	for index, node in indexedNodes do
		nodedIndex[node] = index
	end
	return nodedIndex
end

local function RecursiveSearch(self, start, goal, visited, currentMagnitude)
	local visited = visited or {}
	local currentMagnitude = currentMagnitude or 0
	local reachedGoal = false
	local totalMagnitude = nil
	local shortestPath = {start}
	visited[start] = true
	for nextNode, magnitude in self.connectedNodes[start] do
		if nextNode == goal then
			reachedGoal = true
			if not totalMagnitude or totalMagnitude > magnitude then
				totalMagnitude = magnitude
				shortestPath = {nextNode}
			end
			continue
		end
		if visited[nextNode] then continue end
		local canReachGoal, endMagnitude, currentPath = RecursiveSearch(self, nextNode, goal, visited, currentMagnitude + magnitude)
		if not canReachGoal then
			continue
		end
		reachedGoal = canReachGoal
		if not totalMagnitude or totalMagnitude > endMagnitude then
			totalMagnitude = currentMagnitude + magnitude
			table.insert(currentPath, nextNode)
			shortestPath = currentPath
		end
	end
	return reachedGoal, totalMagnitude, shortestPath
end

local nodeMethods = {}

function nodeMethods.GetIndex(self, node: BasePart): number
	return GetIndexFromNode(self.nodedIndex, node)
end

function nodeMethods.GetNode(self, index: number): BasePart
	return GetNodeFromIndex(self.indexedNodes, index)
end

function nodeMethods.GetPath(self, nodeA: BasePart, nodeB: BasePart)
	return (function()
		local nodedForm = {}
		local bool, totalMagnitude, path = RecursiveSearch(self, self:GetIndex(nodeA), self:GetIndex(nodeB))
		for index = #path, 1, -1 do
			table.insert(nodedForm,  self:GetNode(path[index]))
		end
		return nodedForm
	end)()
end

local function new(nodes: Folder | Model)
	if not nodes then
		return
	end
	local indexedNodes = nodes:GetChildren()
	local nodedIndex = NodeIndex(indexedNodes) --// create a table with nodes as its index and indexes as its value.
	local nodeClass = setmetatable({
		indexedNodes = indexedNodes,
		nodedIndex = nodedIndex,
		connectedNodes = ConnectNodes(indexedNodes, nodedIndex) --// create a table with nodes that are connected to each other with its value set to the magnitude between.
	}, {__index = nodeMethods})
	return nodeClass
end

return setmetatable({new = new}, {__index = nodeMethods})