Roblox Pathfinding: A* Algorithm (Node Lookup Concern)

[FormallyMarc]

Hello, developers!

I’m currently working on an A-star algorithm for my game since I heard it’s (rather) better than Roblox’s Pathfinding services.

While working on it, I encountered some issues in detecting the nearest nodes that the script uses to create a path. There were also some instances where the paths are zigzagged, and they may have skipped the order or a few nodes in creating a path.

Here’s a picture to show you what I really want to fix:

Here’s the code snippet. I referred to numerous pathfinding videos on YouTube
(also a way for me to understand how the algorithm works)

-- A* Algorithm
while task.wait(1) do
	local Nodes: Folder = game.Workspace["A-Star"].Nodes
	local startingNode: Part, targetNode: Part = nil, nil
	
	repeat startingNode = Nodes[math.random(1, #Nodes:GetChildren())] task.wait() until startingNode ~= nil
	repeat targetNode = Nodes[math.random(1, #Nodes:GetChildren())] task.wait() until targetNode ~= nil and targetNode ~= startingNode

	local previousNode = nil
	local searchNodes = { startingNode }
	local processedSet = {}

	local gScores = {}
	local hScores = {}
	local fScores = {}

	-- Basically attains the distance between two nodes.
	local function getNodeDistance(a, b)
		return (a.Position - b.Position).Magnitude * 10
	end

	-- Initialization, basically tested out values here.
	for _, node in ipairs(Nodes:GetChildren()) do
		gScores[node] = math.huge
		hScores[node] = getNodeDistance(node, targetNode)
		fScores[node] = math.huge
		
		node.BrickColor = BrickColor.new("Medium stone grey")
		for _, asset in node:GetChildren() do
			if asset:IsA("Beam") or asset:IsA("Attachment") then 
				asset:Destroy()
			end
		end
	end

	gScores[startingNode] = 0
	fScores[startingNode] = hScores[startingNode]

	-- Limit the neighbors via max distance.
	local MAX_DISTANCE = 150
	local function getNeighbors(node)
		local neighbors = {}

		for _, other in ipairs(Nodes:GetChildren()) do
			if other ~= node then
				local dist = getNodeDistance(node, other)

				if dist <= MAX_DISTANCE then
					neighbors[dist] = other
				end
			end
		end
		
		local sortedNeighbors = table.clone(neighbors)
		table.sort(sortedNeighbors, function(a, b)
			return getNodeDistance(node, a) > getNodeDistance(node, b)
		end)
		
		return sortedNeighbors
	end

        -- Gets the neighboring node that has the lowest F Score (from F = G + H)
	local function getLowestFNode()
		local best = searchNodes[1]
		for _, node in ipairs(searchNodes) do
			if fScores[node] < fScores[best] or (fScores[node] == fScores[best] and gScores[node] < gScores[best]) then
				best = node
			end
		end
		return best
	end

	local function AStar()
		while #searchNodes > 0 do
			local currentNode = getLowestFNode()
			
			if previousNode then
				local Beam = Instance.new("Beam")
				Beam.Color = ColorSequence.new(Color3.new(1, 0, 0))
				Beam.FaceCamera = true
				Beam.LightInfluence = 0
				Beam.Width0 = 0.25
				Beam.Width1 = 0.25
				Beam.Attachment0 = Instance.new("Attachment", currentNode)
				Beam.Attachment1 = Instance.new("Attachment", previousNode)
				Beam.Parent = previousNode
			end
			
			-- Remove from open set
			table.remove(searchNodes, table.find(searchNodes, currentNode))
			processedSet[currentNode] = true
			previousNode = currentNode
			
			currentNode.BrickColor = BrickColor.new("Really red")

			if currentNode == startingNode then
				startingNode.BrickColor = BrickColor.new("Toothpaste")
			end
			
			if currentNode == targetNode then
				targetNode.BrickColor = BrickColor.new("Lime green")
				return true
			end

                        -- Change or update the scores of each neighboring node.
			for dist, neighbor in getNeighbors(currentNode) do
				local costToNeighbor = gScores[currentNode] + getNodeDistance(currentNode, neighbor)
				if costToNeighbor < gScores[neighbor] then

					gScores[neighbor] = costToNeighbor
					hScores[neighbor] = getNodeDistance(neighbor, targetNode)
					fScores[neighbor] = gScores[neighbor] + hScores[neighbor]

					-- Only add if not already in open set
					if not table.find(searchNodes, neighbor) then
						table.insert(searchNodes, neighbor)
					end
				end
			end

			task.wait(0.1)
		end

		return false
	end
	AStar()
end

This is basically a rough draft of my code. I’m still trying to add many things into it, but I want to focus on making the nodes more “in order” or “sequential.” Also, imagine that the nodes are scattered around.

[Axe3z (Tagerhero3)]

Hey, found 3 bugs:

1. Nodes[math.random(...)] — you can’t index a Folder like an array, use Nodes:GetChildren()[math.random(...)]
2. neighbors[dist] = other — if two nodes have the same distance one gets overwritten, plus table.sort doesn’t work on dictionaries. Just use table.insert(neighbors, other)
3. You never made a cameFrom table — without it A* has no way to reconstruct the actual shortest path, so you were just drawing the exploration order (hence the zigzag). Add cameFrom[neighbor] = currentNode in the neighbor loop and a reconstructPath function that walks it backwards

Here’s the full fix: [-- A* Algorithm
while task.wait(1) do
local Nodes: Folder = game.Workspace[“A-Star”].Nodes
local startingNode: Part, targetNode: Part = nil, nil

local children = Nodes:GetChildren() -- cache to avoid repeated calls

repeat startingNode = children[math.random(1, #children)] task.wait() until startingNode ~= nil
repeat targetNode = children[math.random(1, #children)] task.wait() until targetNode ~= nil and targetNode ~= startingNode

local processedSet = {}
local searchNodes = { startingNode }
local cameFrom = {} -- Tracks which node we came from (used for path reconstruction)

local gScores = {}
local hScores = {}
local fScores = {}

-- Basically attains the distance between two nodes.
local function getNodeDistance(a, b)
	return (a.Position - b.Position).Magnitude * 10
end

-- Initialization, basically tested out values here.
for _, node in ipairs(children) do
	gScores[node] = math.huge
	hScores[node] = getNodeDistance(node, targetNode)
	fScores[node] = math.huge

	node.BrickColor = BrickColor.new("Medium stone grey")
	for _, asset in node:GetChildren() do
		if asset:IsA("Beam") or asset:IsA("Attachment") then
			asset:Destroy()
		end
	end
end

gScores[startingNode] = 0
fScores[startingNode] = hScores[startingNode]

-- Limit the neighbors via max distance.
local MAX_DISTANCE = 150
local function getNeighbors(node)
	local neighbors = {}

	for _, other in ipairs(children) do
		if other ~= node then
			local dist = getNodeDistance(node, other)

			if dist <= MAX_DISTANCE then
				table.insert(neighbors, other) -- FIX: use array insert instead of dist as key (caused collisions + broke table.sort)
			end
		end
	end

	table.sort(neighbors, function(a, b)
		return getNodeDistance(node, a) < getNodeDistance(node, b)
	end)

	return neighbors
end

-- Gets the neighboring node that has the lowest F Score (from F = G + H)
local function getLowestFNode()
	local best = searchNodes[1]
	for _, node in ipairs(searchNodes) do
		if fScores[node] < fScores[best] or (fScores[node] == fScores[best] and gScores[node] < gScores[best]) then
			best = node
		end
	end
	return best
end

-- Walks backwards through cameFrom to build the actual shortest path.
local function reconstructPath(endNode)
	local path = {}
	local current = endNode
	while current do
		table.insert(path, 1, current)
		current = cameFrom[current]
	end
	return path
end

-- Draws beams along the final reconstructed path only (not during search).
local function drawPath(path)
	for i = 1, #path - 1 do
		local nodeA = path[i]
		local nodeB = path[i + 1]

		local Beam = Instance.new("Beam")
		Beam.Color = ColorSequence.new(Color3.new(1, 0, 0))
		Beam.FaceCamera = true
		Beam.LightInfluence = 0
		Beam.Width0 = 0.25
		Beam.Width1 = 0.25
		Beam.Attachment0 = Instance.new("Attachment", nodeA)
		Beam.Attachment1 = Instance.new("Attachment", nodeB)
		Beam.Parent = nodeA
	end
end

local function AStar()
	while #searchNodes > 0 do
		local currentNode = getLowestFNode()

		-- Remove from open set
		table.remove(searchNodes, table.find(searchNodes, currentNode))
		processedSet[currentNode] = true

		currentNode.BrickColor = BrickColor.new("Really red")

		if currentNode == startingNode then
			startingNode.BrickColor = BrickColor.new("Toothpaste")
		end

		if currentNode == targetNode then
			targetNode.BrickColor = BrickColor.new("Lime green")
			-- FIX: reconstruct the actual optimal path and draw it
			local path = reconstructPath(targetNode)
			drawPath(path)
			return true
		end

		-- Change or update the scores of each neighboring node.
		for _, neighbor in ipairs(getNeighbors(currentNode)) do
			if not processedSet[neighbor] then
				local costToNeighbor = gScores[currentNode] + getNodeDistance(currentNode, neighbor)
				if costToNeighbor < gScores[neighbor] then
					cameFrom[neighbor] = currentNode -- FIX: record where we came from for path reconstruction

					gScores[neighbor] = costToNeighbor
					hScores[neighbor] = getNodeDistance(neighbor, targetNode)
					fScores[neighbor] = gScores[neighbor] + hScores[neighbor]

					-- Only add if not already in open set
					if not table.find(searchNodes, neighbor) then
						table.insert(searchNodes, neighbor)
					end
				end
			end
		end

		task.wait(0.1)
	end

	return false
end
AStar()

end]

[FormallyMarc]

Thanks! Will try this soon, it’s been a while since I coded lots in studio, this really helped

[FormallyMarc]

Okay, tested it, this is really cool. I probably forgot about this crucial step, where I have to actually construct the path. Thanks, works really well now!