AStar Pathfinding Optmization

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.

I use a hash table for detecting close objects on a large scale. It may or may not improve performance on a small scale, but it could definitely lessen the load on the distance detecting function.

1 Like

I am not super familiar with hastables, could you give an example?

Basically a 2d array. For example, if I have an object at (x,y) on a 2d plane, I could insert that object into a 2d table. It would look like Table[rounded X pos][rounded Y pos]. You can round the number to a multiple of 5 for example, and it would create larger sections of area covered by the table. Then when you want to find nearby objects, you would check the adjacent slots in the table too where the origin point is.
Looking at the situation again, I’m not sure of hash tables will be practical because they just break up objects into nearby chunks. If you needed to find an object even if it wasn’t in a nearby chunk, then you would have to load the chunks adjacent to those already loaded.

1 Like

In the development of my game I had a similar problem and I learned many things.

First you have to define your problem well. Only by knowing what you have and what you want to achieve can you make optimisations. Are you using standard NPCs (with humanoid)?, is your labyrinth or map fixed?, do you have many or few alleys?, do the NPCs need to go through the alleys? Is speed or finding the shortest path more important? Answering these kinds of questions can drastically simplify the problem.

From the details you mention I can see some shortcomings that maybe should be changed:

  • It is simpler to calculate Manhattan distance than Euclidean distance.
  • The A* algorithm is designed to find the shortest path, not to be the fastest. Greedy is faster for example.
  • You should use an efficient implementation of the Pathfinding algorithm instead of creating your own. There are plenty of them on the internet.
  • The only advantage of metatables is improved syntax, not efficiency.

Finally, 2000 nodes is too many. The labyrinth (or map) in the image is quite simple and would require at most 10 to 30 nodes.

Well, I hope it was useful.

1 Like

Is this just a tech demo or for an actual project? Because robloxs native pathfinding uses a form of A* already and it’s seen as the meta for pathfinding.

That makes sense. In game, there will be far less nodes so that will be the solution. Will have to look at Manhattan distance instead of Euclidean distance.
Thank you for your insight!

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.