Prim's Algorithm/Nodes help?

The ROBLOX Wiki display's this code for the Algorithm and adds a procedure I need help understanding what the :neighbors() is used on and how the nodes work. I am using the algorithm for pathfinding for NPC's. I understand this is very unreasonable question to be posted on the ScriptingHelpers website but if I don't ask here where else am I supposed to ask? And ROBLOX Forums don't count because of the fact that no one will answer and the question will be gone down the page in seconds.

Prim's Algorithm

ROBLOX Wiki Procedure:

1. Add starting node to closed set.
2. For every node in the closed set, find all the adjacent nodes and calculate the distance to that node. **** If the node is already in the closed set, ignore it.
3. Choose the node nearest to a node in the closed set
4. Add it to the closed set.
5. Repeat from step 2 until all nodes have been visited.

ROBLOX Wiki Code:

function Prim(start)
	local closed = {}
	closed[start] = true
 
	--search until all nodes have been found
	while nodes_to_be_found do
		local current_best
		--go through the closed set and find their neighbors
		for parent in pairs(closed) do
			for _, node in ipairs(parent:neighbors()) do
				--make sure node is not in closed set already
				if not closed[node] then
					--compare to what is currently the best node
					if not current_best or node:distance(parent) < current_best:distance(current_best.parent) then
						node.parent = parent
						current_best = node
					end
				end
			end
		end
		--add the selected node to closed set
		closed[current_best] = true
	end
end

If you just want simple, general pathfinding, you just need the PathfindingService.

You only need to implement pathfinding yourself if you need it to be more specific to your particular needs. The PathfindingService assumes you only walk (not jump, or use other methods), and is fixed on a slightly squishy grid.

The goal of Prim's is to take a network of connected nodes and produce the shortest path to each other node -- it doesn't just find the shortest path to one other node. If you want that, you want to use A*, which is similar, but not the same.

A neighbor b of a is adjacent to a -- they are next to each other, so you can get from a to b without having to get anywhere in the middle first.

A path is a sequence of adjacent nodes.

A shortest path from a to b is a path from a to b that is not longer than any other path from a to b.

You can read the pseudo-code they provide for reference, but it's easier for me to show how to implement it yourself:

local start, open
-- start: set to the node to start at
-- open: set to a list of all *other* nodes

-- Add starting node to closed set.
local closed = {start}

-- For every node in the closed set, find all the
-- adjacent (open) nodes and calculate the distance to that node.
local best, bestDistance
while #open > 0 do
	for _, from in pairs(closed) do
		local neighbors = getNeighbors(node)
		-- `neighbors` are the nodes adjacent to `node` that are in open
		-- these are those that are directly accessible from `node`
		-- in a straight line fashion
		for i, to in pairs(neighbors) do
			-- `getDistance` gives how far `other` is from `node`: 
			local distance = getDistance(from, to)
			if not best or distance < bestDistance then
				-- Choose the node nearest to a node in the closed set
				best = {from = from, to = to, toIndex = i}
				bestDistance = distance
			end
		end
		-- `best.from --> best.to` is part of the shortest path
		-- from `start` to `best.to`.
		-- Add `best.to` to the closed set:
		table.insert(closed, best.to)
		-- Remove it from the open set:
		table.remove(open, best.toIndex)
		-- Save its parent, so that you remember how you got here:
		best.to.from = best.from
	end
	-- Repeat until all nodes have been visited
end

There are some details that are missing.

• getNeighbors(from) -- you have to figure out what are the neighbors of any node. If you're talking about a walk-able path, that probably means they are
  • close together
  • unobstructed (Raycast between them and you hit nothing)
  • on the ground (Raycast down and you hit the ground)
• getDistance(from, to) -- you have to figure out how far from is to to. If you're dealing with Vector3s, it's just (x - y).magnitude
• to.from -- You need to record how you got to each point. That means pure Vector3s won't work -- you can't add extra fields to a Vector3.

Here's something how these could be implemented:

-- position: a Vector3
function newNode(position)
	return {position = position}
end

-- returns the distance from `from` to `to`
-- (larger is a longer, less desirable path)
function getDistance(from, to)
	return (from - to).magnitude
end

-- returns nodes that are reachable from `from`
-- (simple implementation assumes that close nodes -- less than 15 studs -- are always
-- reachable from each other.
-- A real implementation needs much more information, since this will ignore
-- small walls)
function getNeighbors(from)
	local neighbors = {}
	for _, to in pairs(open) do
		if getDistance(from, to) < 15 then
			table.insert(neighbors, to)
		end
	end
	return neighbors
end

If we want to find how we got to a finish that was originally put into the open list, we have to follow its .from property:

local path = {}
while node do
	table.insert(path, 1, node)
	node = node.from
end

The idea of this is starting at the end, and walking backwards:

• I'm at Z. Z are my steps so far.
• Go back one step to Y
• I'm at Y. Y is the earliest step so far, so push it before the Z. YZ are my steps so far.
• Go back one step to X.
• I'm at X. X is the earliest step so far, so push it before the YZ. XYZ are my steps so far.
• ...
• I'm at A. A is the earliest step so far, so push it before the BCDE...YZ.
  • Try to go back one step. There wasn't anything before A.
• I'm nowhere. I'm going to stop now.