Hey all,
I have a good pathfinding system using A Star that seems to be very accurate and working well however it is quite slow. Here is my implementation:
local module = {}
-- Helper function to calculate distance between two points
local function distance(a, b)
return math.sqrt((a.x - b.x) ^ 2 + (a.y - b.y) ^ 2 + (a.z - b.z) ^ 2)
end
function module.getNearest(nodes, cordinates)
local nearest = nil
local distance = 999
for _, v in ipairs(nodes) do
local mag = (cordinates - Vector3.new(v.position.x, v.position.y, v.position.z)).Magnitude
if mag < distance then
distance = mag
nearest = v
end
end
return nearest or false
end
-- A* algorithm
function module.aStar(nodes, startNode, endNode)
debug.profilebegin("A*")
-- Initialize the open and closed lists
local openList = { [startNode.id] = true }
openList = setmetatable(openList, {
__len = function(t)
local count = 0
for _, v in pairs(t) do
if v then
count += 1
end
end
return count
end,
})
local closedList = {}
-- Initialize the costs and parents of each node
local costs = {}
local parents = {}
for _, node in ipairs(nodes) do
costs[node] = math.huge
end
costs[startNode] = 0
-- Loop until the open list is empty
while #openList > 0 do
debug.profilebegin("Find Lowest Cost Node")
-- Find the node with the lowest cost in the open list
local currentNode
local lowestCost = math.huge
for id in pairs(openList) do
local node = nodes[id]
local cost = costs[node] + distance(node.position, endNode.position)
if cost < lowestCost then
lowestCost = cost
currentNode = node
end
end
debug.profileend()
debug.profilebegin("Construct and Return Path")
-- If we have reached the end node, construct and return the path
if currentNode == endNode then
local path = { endNode }
while path[1] ~= startNode do
table.insert(path, 1, parents[path[1]])
end
return path
end
debug.profileend()
debug.profilebegin("Move Current Node to Closed")
-- Move the current node from the open to the closed list
openList[currentNode.id] = nil
closedList[currentNode.id] = true
debug.profileend()
debug.profilebegin("Update costs and Parents of Nodes")
-- Update the costs and parents of each connected node
for i = 1, #currentNode.connections do
local neighbor = currentNode.connections[i]
-- table.find(closedList, neighbor)
if not closedList[neighbor.id] then
local tentativeCost = costs[currentNode] + distance(currentNode.position, neighbor.position)
if tentativeCost < costs[neighbor] then
costs[neighbor] = tentativeCost
parents[neighbor] = currentNode
-- table.find(openList, neighbor)
if not openList[neighbor.id] then
openList[neighbor.id] = true
-- table.insert(openList, neighbor)
end
end
end
end
debug.profileend()
end
-- If we reach here, there is no path from the start to the end node
debug.profileend()
return nil
end
return module
I have a node gride of about 2000 nodes, which is quite small in my opinion as player’s tycoons could be considerably bigger. It has 2 floors as well, here’s a quick screenshot of what the nodes look like:
At the beginning of the game, the node graph is calculated, and all the connections are calculated. This takes around 600ms, which is not a problem because it’s only done once at the start of the game and only when the grid changes.
The main issue I am having is the slowness of the module.aStar function
When having around 10 NPCs I get very bad frame drops and lag. Some aStar operations take over 200ms to do and sometimes 10 of them need to be done per frame.
Using the microprofiler I’ve determined that that two main hot spots for high frame times are:
Find Lowest Cost Node
and
Update costs and Parents of Nodes
to address these issues, you can see in my code I’ve commented out using table.find to prevent unnecessary recursions; however this has not made the problem any better.
I suspect that I have too many nodes, but if that’s the case, I’m going to need to rethink AStar as a solution.
The roblox pathfinding service is too buggy for my use case and has been used for the past two years in production games, so it is not an option.
I’d appreciate any tips/help optimizing these functions better.