(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