How would i get to code a* pathfinding to run far distances without FPS drop?

How would i make my pathfinding to be faster?

local function heuristic(PosA, PosB)
	return (PosA - PosB).magnitude
local function snap(pos : Vector3)
	return*3+1.5,math.floor(pos.Y/3)*3+1.5, math.floor(pos.Z/3)*3+1.5)
local blocks = {}
for i,v in pairs(workspace.WalkableParts:GetChildren()) do
	local rounder = snap(v.Position)
	blocks[rounder] = 1

local function getNeighbors(node, walkableParts)
	local neighbors = {}
	local directions = {, 0, 0),, 0, 0),, 0, 3),, 0, -3),, 0, 3),, 0, -3),, 0, 3),, 0, -3)

	for _, direction in ipairs(directions) do
		local neighborPos = snap(node + direction) 
		if blocks[neighborPos] == nil then
			table.insert(neighbors, neighborPos)

	return neighbors

local function reconstructPath(cameFrom, current)
	local totalPath = {current}
	while cameFrom[current] do
		current = cameFrom[current]
		table.insert(totalPath, 1, current)
	return totalPath

local function aStar(start, goal, walkableParts)
	local openSet = {start}
	local cameFrom = {}
	local gScore = {[start] = 0}
	local fScore = {[start] = heuristic(start, goal)}
	local s
	while #openSet > 0 do
		table.sort(openSet, function(a, b) return fScore[a] < fScore[b] end)
		local current = table.remove(openSet, 1)

		if (current - goal).Magnitude < 1 then
			s = reconstructPath(cameFrom, current)
			return reconstructPath(cameFrom, current)

		for _, neighbor in ipairs(getNeighbors(current, walkableParts)) do
			local tentativeGScore = gScore[current] + (current - neighbor).magnitude
			if tentativeGScore < (gScore[neighbor] or math.huge) then
				cameFrom[neighbor] = current
				gScore[neighbor] = tentativeGScore
				fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, goal)
				if not table.find(openSet, neighbor) then
					table.insert(openSet, neighbor)


-- Example usage
local function moveToPosition(path)
	for _, part in ipairs(path) do
		part.Color =, 0, 0.0156863)

local startPart = workspace.Start.Position
local goalPart = workspace.Target.Position
while wait(1) do
	if startPart and goalPart then
		local path = aStar(startPart, goalPart, blocks)
		if path and path[2] then
			startPart = path[2]
			local a ="Part", workspace)
			a.Anchored = true
			a.Size =,3,3)
			a.CanCollide = false
			a.Color =, 0, 0.498039)
			a.Position = path[2]
			warn("No path found!")
		warn("Start or goal part not found in walkable parts!")

It runs very slow, Can anyone help me to optimize it?


Compute faster or make the NPC go from point A to B faster? Also, could you include a video of it working? (an NPC going from A to B). That could help me see the issue.

From a glance, I noticed you’re using wait() instead of task.wait(). I can recommend trying to use task.wait() as I’ve heard it is faster for computing.

1 Like

Compute faster or make the NPC go from point A to B faster?

i meant to make it run with less lag. when i make the target little bit further(like 50 studs) the fps starts to drop drastically. I will change the question of the topic to be more clear


a* pathfinding is something I’m not too knowledgable in. After some looking, I found that @msix29 made the following:

Maybe they can jump in here on how to make the OP’s algorithm run faster

I can also share these:

1 Like

What you could do is create a second node map, where you place the nodes at roads or paths that are used for navigation. And place these nodes as far apart as possible. The issue is when you have large distances, the algorithm has to search through many many nodes if you have nodes placed each like 1 stud or so. But if you have a second node map that only has nodes on roads etc then this is much faster. To accomplish this. Use the target position, and by using the main node map, let the a* algo create a path to the nearest navigation node, (What you could do is create a second algo that will search neighboring nodes until it finds a navigation node). And then do the same for the start position. This way you will be able to find a path to enter the navigation node map, and to exit it and get to the target. After a path has been found to enter and exit the navigation node map. You can then run the a* algo on the navigation node map from the start node to the end node. Then when its found you basically return the nodes it has to follow, so first the nav path to get to the navigation node map, then the nodes that traverse the navigation path. Then the nodes that exits the nav path to the end pos.

1 Like

Yes but im trying to make a dynamic pathfinding algorithm

1 Like

Hmm what do you mean by dynamic, like that it does so automaticly or?

1 Like

No dynamic means when i place and obstecle it will know

Oh like automaticly create the nodes etc? (The nodes arent manually palced)

What I’ve done in the past to speed up the pathfinding was to pre-calculate all the possible paths and cache the results. This makes the look ups pretty much instantaneous. However, it’s only really convenient to do that when you know the node layout isn’t likely to change anymore, but you can still cache results on the fly after they are calculated once.

In that case, it might be worth looking into the D* lite algorithm: Dstar Lite: An Optimal Algorithm for Robotics Pathfinding - NHSJS.

This algorithm is capable of solving the shortest path problem and also incorporates additional functionality such as path replanning and path correction.

I’ve never used it personally so I can’t really say how well it would apply here.

yes (wpepqoeiqwoeiqqeewqeqwq[iw)

Isnt that the same as a*?(weqewqe)

Is there a way to instead of making OpenSet as a table to index the open things like OpenSet[key] = pos?

D* is a variant of A* so they are similar in how they solve pathfinding solutions. The key difference seems to be that D* can update it’s path in response to the environment changing (like an obstacle being placed in the path) while A* cannot.

Again, I’ve never used D* personally but it might be worth looking into.

If you look at the code i posted above, you can see that my path is dynamic. Each second it calculates the entire path and gets the second node. is there a way to optimize that?

Oh I see. So you’re calculating the entire path multiple times, but only using the second node? That in itself seems inefficient and doesn’t seem like how A* is intended to be used. Typically you calculate the path once and traverse all the nodes in the path without re-calculating the path every second.

Are you doing that to support the dynamic feature you want?

No i calculate the entire path once per second, not multiple times per second, then i get the second node of that path.

Im trying to make a pathfinding that will replace roblox one because the roblox pathfinding service doesnt work very good.

How can i optimize it?

I understand that, but you’re calculating the entire path every second just to discard most of the nodes anyways. That seems inefficient and you’d probably want to address that. At the very least, you can cache the result of the initial path so you can do quick look ups once you start from the next node. If you run into an obstacle, only then should you recalculate the entire path again from the current starting position.

I haven’t implemented graph-based pathfinding algorithms that need to worry about dynamic environments so when I calculate the initial path, I’m done and I just traverse all the nodes in the path. I don’t recalculate the path every second. I recommend looking into D* lite since it’s specifically designed to handle dynamic environments.

I dont understand, you are saying I should use raycast to the target?

If you’re referring to how you should detect obstacles, that completely depends on your game and how you want to handle that. Using raycasts is definitely an option.

What I’m saying is that if you’re going to recalculate the path every second, you should at least cache the results.

For example, you calculate an initial path from a start node N1 to a target node Nk:
(N1, N2, ..., Nk). So you have a path that goes from N1 to Nk. One second later, you’re using N2 as the starting node and calculating a path from N2 to Nk. Well, you can see from the first initial path that you already know the path from N2 to Nk. You needed to calculate it in order to calculate the initial path. So you can probably just re-use those results (N2, ..., Nk). No need to recalculate the entire path again.