A* Pathfinding... or is it? I can't tell

(This is my first forum post, so I apologize if it is in the wrong location, or if the formatting is wrong in any way.)

Having been disappointed with the built-in Roblox Pathfinding Service, I begrudgingly began researching creating my own custom pathfinding service. That has been, to say the least, one heck of a journey. I found many links to but a handful of sources on the subject, and there was hardly anything that made sense, at first.

After some lengthy ordeals, and essentially translating all pseudocode I could find into lua, I found myself with the following pathfinding code.

I have two scripts running in ServerScriptService. The first one generates all nodes on the map (I am willing to provide that script as well, if needed for the discussion). The second calculates a path from the green square to the red square. It is this second script that I wish to make particular mention of.

The script is intended to use A* pathfinding. However, from the simulations I have used, my code appears to behave more like Breadth-First Search. Attached is a video of the script running, with a visualization of how the script branches out to each neighboring node:

robloxapp-20200728-0918109.wmv (341.4 KB)

What I want to know is if the script I have created is really using A* pathfinding, Breadth-First Search or any other form of pathfinding. If it isn’t A*, I want to know what is needed for it to behave the way I intend it to.

My only current thought on what could be happening is that my code doesn’t utilize a ‘closed list,’ or a list containing all nodes that have already been calculated. Despite this, the script doesn’t seem to return to previously-calculated neighbors (as demonstrated in the video).

Finally, here is the pathfinding code. If you are not familiar with A* or pathfinding in general, I would recommend that you move on to another post, as this will probably make your brain hurt as much as it did mine in the beginning.

--Many thanks to ForeverDev for his A* code

local ServerStorage = game:GetService("ServerStorage")
local GameFolder = ServerStorage:WaitForChild("Game")
local nodesFolder = GameFolder:WaitForChild("Nodes")

local DIRECTIONS = {Vector2.new(0, 1), Vector2.new(1, 1), Vector2.new(1, 0), Vector2.new(1, -1), Vector2.new(0, -1), Vector2.new(-1, -1), Vector2.new(-1, 0), Vector2.new(-1, 1)}
local BLOCK_SIZE = 4
local OFFSET = BLOCK_SIZE / 2

local function snapTo(number, step)
	return number - (number % step)
end

local nodesList = {}
local function onNodeAdded(node)
	--	print("Adding node") --DEBUG
--	print(tostring(node.Value.X .. node.Value.Z)) --DEBUG
	nodesList[tostring(node.Value.X .. node.Value.Z)] = node
--	print(nodesList[tostring(node.Value.X .. node.Value.Z)].Value) --DEBUG
end
local nodes = nodesFolder:GetChildren()
for node = 1, #nodes do
--	print(nodes[node]) --DEBUG
	onNodeAdded(nodes[node])
end
nodesFolder.ChildAdded:connect(onNodeAdded)

local function heuristic(a, b)
	--Manhattan distance on a square grid
	return math.abs(b.Value.X - a.Value.X) + math.abs(b.Value.Y - a.Value.Y)
end

local function getNeighbors(node)
	local neighborNodes = node:GetChildren()
	return neighborNodes
end

local function getCost(nodeA, nodeB)
	local cost = (nodeA.Value - nodeB.Value).magnitude
--	print(cost) --DEBUG
	return cost
end

local function createEdge(pointA, pointB) --DEBUG
	local part1 = Instance.new("Part")
	part1.Transparency = 1
	part1.CanCollide = false
	part1.Anchored = true
	part1.Position = pointA
	local attachment1 = Instance.new("Attachment")
	attachment1.Parent = part1
	local part2 = Instance.new("Part")
	part2.Transparency = 1
	part2.CanCollide = false
	part2.Anchored = true
	part2.Position = pointB
	local attachment2 = Instance.new("Attachment")
	attachment2.Parent = part2
	local beam = Instance.new("Beam")
	--	beam.Color = Color3.fromRGB(0, 255, 0)
	beam.FaceCamera = true
	beam.Parent = part1
	beam.Attachment0 = attachment1
	beam.Attachment1 = attachment2
	part1.Parent = workspace
	part2.Parent = workspace
	wait(0)
end

----------------------------------------------------------------------------------------

wait() --This is just to make sure all the nodes have been loaded before pathfinding
local startNodeString = tostring(snapTo(workspace.StartNode.Position.X, BLOCK_SIZE) .. snapTo(workspace.StartNode.Position.Z, BLOCK_SIZE))
local goalNodeString = tostring(snapTo(workspace:WaitForChild("GoalNode").Position.X, BLOCK_SIZE) .. snapTo(workspace:WaitForChild("GoalNode").Position.Z, BLOCK_SIZE))
--print(startNodeString) --DEBUG
--print(goalNodeString) --DEBUG
--print(nodesList[startNodeString].Name) --DEBUG
--print(nodesList[goalNodeString]) --DEBUG
local startNode = nodesList[startNodeString]
local goalNode = nodesList[goalNodeString]

--local function AStarPathfind()

--Tables used to represent the pathfinding state
local frontier = {}
table.insert(frontier, {startNode, 0})
local cameFrom = {}
cameFrom[startNode] = nil
--print(cameFrom[startNode]) --DEBUG
local currentCost = {}
currentCost[startNode] = 0
--print(currentCost[startNode]) --DEBUG
local path = {}

-- helper function used to insert into the frontier. frontier is
-- sorted by its nodes' cost values, so make sure to
-- insert at the correct index
local function putInOpenSet(node)
--	print(node) --DEBUG
--	print(node[1], node[2]) --DEBUG
	local priority = node[2] + heuristic(node[1], goalNode)
--	print(priority) --DEBUG
	for index, existingNode in ipairs(frontier) do
		if node[2] < existingNode[2] then
			table.insert(frontier, index, node)
			return
		end
	end
	table.insert(frontier, node)
end

--Main A* loop
while #frontier > 0 do
--	wait(1) --DEBUG
	print(#frontier) --DEBUG
	local currentNode = frontier[1][1]
	table.remove(frontier, 1)
	if currentNode == goalNode then
--		print("We have found the goal node!") --DEBUG
		break
	end
	--Explore all neighbors of the current node
	for _, neighborNode in ipairs(getNeighbors(currentNode)) do
		--		print(neighborNode.Value) --DEBUG
		neighborNode = neighborNode.Value
--		createEdge(currentNode.Value, neighborNode.Value) --DEBUG
		local newCost = currentCost[currentNode] + getCost(currentNode, neighborNode)
		if not currentCost[neighborNode] or newCost < currentCost[neighborNode] then
			currentCost[neighborNode] = newCost
			putInOpenSet({neighborNode, newCost})
			createEdge(currentNode.Value, neighborNode.Value) --DEBUG
			cameFrom[neighborNode] = currentNode
		end
	end
end
--return cameFrom, currentCost

--Retrace the nodes used in the path so that we can return the complete path to the user
--[[
NOTE: This creates a path starting at the GOAL node, and ending at the START node;
essentially the path, but in reverse.
]]--
local currentNode = goalNode
while currentNode ~= startNode do
	table.insert(path, currentNode)
	createEdge(currentNode.Value, cameFrom[currentNode].Value) --DEBUG
	currentNode = cameFrom[currentNode]
end

return path
2 Likes

This is probably where you’re going wrong. It’s not entirely clear to me how putInOpenSet works, but it doesn’t seem like frontier[1][1] is ever guaranteed to be the node in frontier with the lowest f-score, which is necessary for the depth-first search to occur.

The reason this breaks your implementation is that you’re not choosing to first look at the node on the frontier that’s got the best chance of being closest to the goal node. My guess is that you’re looking at whichever node was inserted last. This means the open set grows “in bands”, which is pretty much what breadth-first search is.

EDIT: Here’s an implementation based on the wikipedia page:

A Star.rbxl (20.5 KB)

Wikipedia on A*

EDIT: Here’s a version where the code is visually much closer to the pseudocode on the wiki:

A Star 2.rbxl (22.2 KB)

Fantastic! I’m not sure how I missed these resources.

The code now works as intended. Here is the new script. I will mark this thread as solved.

--Many thanks to ForeverDev for his A* code

local ServerStorage = game:GetService("ServerStorage")
local GameFolder = ServerStorage:WaitForChild("Game")
local nodesFolder = GameFolder:WaitForChild("Nodes")

local DIRECTIONS = {Vector2.new(0, 1), Vector2.new(1, 1), Vector2.new(1, 0), Vector2.new(1, -1), Vector2.new(0, -1), Vector2.new(-1, -1), Vector2.new(-1, 0), Vector2.new(-1, 1)}
local BLOCK_SIZE = 4
local OFFSET = BLOCK_SIZE / 2

local function snapTo(number, step)
	return number - (number % step)
end

local nodesList = {}
local function onNodeAdded(node)
	--	print("Adding node") --DEBUG
--	print(tostring(node.Value.X .. node.Value.Z)) --DEBUG
	nodesList[tostring(node.Value.X .. node.Value.Z)] = node
--	print(nodesList[tostring(node.Value.X .. node.Value.Z)].Value) --DEBUG
end
local nodes = nodesFolder:GetChildren()
for node = 1, #nodes do
--	print(nodes[node]) --DEBUG
	onNodeAdded(nodes[node])
end
nodesFolder.ChildAdded:connect(onNodeAdded)

local function heuristic(a, b)
	--Manhattan distance on a square grid
	return math.abs(b.Value.X - a.Value.X) + math.abs(b.Value.Y - a.Value.Y)
end

local function getNeighbors(node)
	local neighborNodes = node:GetChildren()
	return neighborNodes
end

local function nodeDistance(nodeA, nodeB)
	print(nodeA, nodeB) --DEBUG
	local cost = (nodeA.Value - nodeB.Value).magnitude
--	print(cost) --DEBUG
	return cost
end

local function createEdge(pointA, pointB) --DEBUG
	local part1 = Instance.new("Part")
	part1.Transparency = 1
	part1.CanCollide = false
	part1.Anchored = true
	part1.Position = pointA
	local attachment1 = Instance.new("Attachment")
	attachment1.Parent = part1
	local part2 = Instance.new("Part")
	part2.Transparency = 1
	part2.CanCollide = false
	part2.Anchored = true
	part2.Position = pointB
	local attachment2 = Instance.new("Attachment")
	attachment2.Parent = part2
	local beam = Instance.new("Beam")
	--	beam.Color = Color3.fromRGB(0, 255, 0)
	beam.FaceCamera = true
	beam.Parent = part1
	beam.Attachment0 = attachment1
	beam.Attachment1 = attachment2
	part1.Parent = workspace
	part2.Parent = workspace
	wait(0)
end

----------------------------------------------------------------------------------------

local function edgeWeight(nodeA, nodeB)
	return 1
end

local function reconstructPath(cameFrom, endNode)
	local path = {}
	local currentNode = endNode
	repeat
		table.insert(path, 1, currentNode)
		currentNode = cameFrom[currentNode]
	until not currentNode
	return path
end

local function pathfindBetween(startNode, endNode)
	local open = {startNode}
	local cameFrom = {}
	local gScore = {}
	gScore[startNode] = 0
	local fScore = {}
	fScore[startNode] = nodeDistance(startNode, endNode)	
	
	while #open > 0 do
		local currentNode, currentNodeIndex = open[1], 1
		for index, node in pairs(open) do
			if (fScore[node] or math.huge) < (fScore[currentNode] or math.huge) then
				currentNode = node
				currentNodeIndex = index
			end
		end
		
		if currentNode == endNode then
			return true, reconstructPath(cameFrom, currentNode)
		end
		
		wait()
		
		table.remove(open, currentNodeIndex)
		for _, neighborNode in ipairs(getNeighbors(currentNode)) do
			neighborNode = neighborNode.Value
			local tentativeGScore = gScore[currentNode] + edgeWeight(currentNode, neighborNode)
			if tentativeGScore < (gScore[neighborNode] or math.huge) then
				createEdge(currentNode.Value, neighborNode.Value)
				cameFrom[neighborNode] = currentNode
				gScore[neighborNode] = tentativeGScore
				fScore[neighborNode] = gScore[neighborNode] + nodeDistance(neighborNode, endNode)
				
				if not table.find(open, neighborNode) then
					table.insert(open, neighborNode)
				end
			end
		end
	end
	return false
end

wait() --This is just to make sure all the nodes have been loaded before pathfinding

local startNodeString = tostring(snapTo(workspace.StartNode.Position.X, BLOCK_SIZE) .. snapTo(workspace.StartNode.Position.Z, BLOCK_SIZE))
local goalNodeString = tostring(snapTo(workspace:WaitForChild("GoalNode").Position.X, BLOCK_SIZE) .. snapTo(workspace:WaitForChild("GoalNode").Position.Z, BLOCK_SIZE))
--print(startNodeString) --DEBUG
--print(goalNodeString) --DEBUG
--print(nodesList[startNodeString].Name) --DEBUG
--print(nodesList[goalNodeString]) --DEBUG
local startNode = nodesList[startNodeString]
local goalNode = nodesList[goalNodeString]
pathfindBetween(startNode, goalNode)
2 Likes