That is not a dynamic pathfinding. it doenst work like that
Thatâs why Iâm saying look into D* lite. Itâs designed for the exact purpose of pathfinding in dynamic environments and youâll probably find the optimizations youâre looking for while implementing it.
If you are doing it far distances, you probably should just avoid A* altogether honestly. I would recommend using a greedy best first search as it will search far less cells and still give a reasonable outcome
How did roblox pathfinding work with long distanced is it not a*?
I have managed to improve performance a lot by changing how you get the current node, before you were doing a table.sort on the entire openSet and then grabbing the first index, this is very unnessecary as the only one you need sorted is the first one in the array, so as the amount of objects in the open set increased, so did the computation time a lot
How I fixed this was just to do a simple loop through the open set and pick the one with the lowest fScore:
debug.profilebegin("Determine Current New")
local current, lowest = nil, math.huge
local index = nil
for i, v in openSet do
local score = fScore[v]
if score < lowest then
index = i
current = v
lowest = score
end
end
debug.profileend()
Roblox uses A* for their pathfinding, however roblox does not use a grid system for theirs, as with every 3d game with pathfinding, Roblox uses a navmesh, you can view it in studio settings.
For me it works the same, here is what i did:
local function heuristic(PosA, PosB)
return (PosA - PosB).magnitude
end
local function snap(pos : Vector3)
return Vector3.new(math.floor(pos.X/3)*3+1.5,math.floor(pos.Y/3)*3+1.5, math.floor(pos.Z/3)*3+1.5)
end
local blocks = {}
for i,v in pairs(workspace.WalkableParts:GetChildren()) do
local rounder = snap(v.Position)
blocks[rounder] = 1
end
local function getNeighbors(node, walkableParts)
local neighbors = {}
local directions = {
Vector3.new(3, 0, 0), Vector3.new(-3, 0, 0),
Vector3.new(0, 0, 3), Vector3.new(0, 0, -3),
Vector3.new(3, 0, 3), Vector3.new(3, 0, -3),
Vector3.new(-3, 0, 3), Vector3.new(-3, 0, -3)
}
for _, direction in ipairs(directions) do
local neighborPos = snap(node + direction)
if blocks[neighborPos] == nil then
table.insert(neighbors, neighborPos)
end
end
return neighbors
end
local function reconstructPath(cameFrom, current)
local totalPath = {current}
while cameFrom[current] do
current = cameFrom[current]
table.insert(totalPath, 1, current)
end
return totalPath
end
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
local current, lowest = nil, math.huge
local index = nil
for i, v in openSet do
local score = fScore[v]
if score < lowest then
index = i
current = v
lowest = score
end
end
current = table.remove(openSet, 1)
if (current - goal).Magnitude < 1 then
s = reconstructPath(cameFrom, current)
return reconstructPath(cameFrom, current)
end
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)
end
end
end
end
end
-- Example usage
local function moveToPosition(path)
for _, part in ipairs(path) do
print(part.Position)
part.Color = Color3.new(1, 0, 0.0156863)
end
end
local startPart = workspace.Start.Position
local goalPart = workspace.Target.Position
while wait(0.1) do
if startPart and goalPart then
local path = aStar(startPart, goalPart, blocks)
if path and path[2] then
print(path[2])
startPart = path[2]
local a = Instance.new("Part", workspace)
a.Anchored = true
a.Size = Vector3.new(3,3,3)
a.CanCollide = false
a.Color = Color3.new(0, 0, 0.498039)
a.Position = path[2]
else
warn("No path found!")
end
else
warn("Start or goal part not found in walkable parts!")
end
end```How far apart is the start and goal positions? I still had lag spikes from long distances but they werenât as bad, I donât really have any more suggestions on how to make it faster though other than just switching to greedy best first search and adding a limit to how long each frame can take and if it goes over that limit, to call task.wait()
50~ studs (qr4124214214214151)
Hey, thanks for the mention.
It seems like the question is already solved, though Iâll give it a look, maybe something was missed.
1 Like
I gave it a quick read, and found some issues, starting with reconstructPath. It has a time complexity of O(n²) and a space complexity of O(n)! I used a more performant function (a generic reverseTable function) which has a time complexity of O(n) and a space complexity of just O(1) making it way more performant, here it is:
--- Reverses a table.
---@param t the table to reverse.
---@return T
local function reverseTable<T>(t: T): T
for i = 1, math.floor(#t / 2) do
local j = #t - i + 1
t[i], t[j] = t[j], t[i]
end
return t
end
You are using 2 extra tables for both gScore and fScore, I personally went with a more OOP approach, I had a Node object to store them, it was simple like this:
local server = script.Parent.Parent.Parent -- Ugly, sadly needed.
local types = require(server.FixedModules.types)
local Node = {}
Node.__index = Node
--- Creates a new `Node` object
---@param position table<number, number>
---@param parent? Node
---@return Node
function Node.new(position: {number}, parent: types.Node?): types.Node
return setmetatable({
Position = position,
Parent = parent,
g = 0,
h = 0,
f = 0
}, Node)
end
return Node
h is the heuristic (distance, not function).
I see you are sorting the openSet every loop, why?
Now for neighbors, you have getNeighbors which has a loop, then u loop again. A better option would be to do the loop inside the aStar function and completely remove getNeighbors, it only adds an extra loop.
Another note on it, you should create directions outside of the function (in the main scope) instead of initializing it every time the function is called, that will be a big boost, especially on large distances.
Also an extra note, I didnât use Vector3, I needed 2-axis movement only but I didnât use Vector2 either. I just made a simple table and 2 functions to calculate distance and whether or not 2 nodes are âclose enoughâ, I think that will also help with performance since you wonât need the overhead that these types add, like .Unit and other things. Just a guess though.
Those are stuff I noticed with a quick look, I tried my best to make my points clear.
I would also like to point out, the code I sent was from another A* implementation (not the one linked), which I made very performant, since it was running on the server, I didnât stress test it or anything but I was running it with 60 NPCs all walking (together, while obeying rules of not hitting each other), and I had no decrease in FPS, at all.
I didnt understand the first code of reverse table. My table hasnt been created until
reconstructPath
How would i need to reverse the table if i dont have a table of points created?
So to start, you will in no real way be able to compete with robloxâs speed. This is a fundamental limitation of making this in lua. Additionally you appear to be going with a grid based method. This often results in more cells existing that you need to search than using something like a navmesh fundamentally.
To start though, I recommend a couple things that might help. First, I would not sort this table
table.sort(openSet, function(a, b) return fScore[a] < fScore[b] end)
All you are sorting that for is to get the smallest number. The trouble is that sorting algorithms fundamentally cannot reliably run in linear time complexity (basically you have to look at the elements more than once or waste a ton of memory or time to realistically sort). You however, only need to look at the elements once to determine which number is smallest. So instead of sorting, you should loop through the list and keep track of the smallest number or create a structure that is more aware of the order to speed this up.
local minimum = fScore[openSet[1]]
local minIndex = 1
for i, cell in pairs(openSet) do
if fScore[cell] < minimum then
minimum = fScore[cell]
minIndex = i
end
end
--now minIndex is the index of the cell in openSet that is associated with the lowest fScore
(Note at scale a priority queue (heap) will be better)
Additionally removing an element from the beginning of a list like you do right after the sort, requires lua to shift every single element in the list down 1 to retain itâs order. But since order technically doesnât matter in this case, you could save some work by replacing the item you want to delete with the last item in the list, then just destroy the last item to remove the duplicate and sidestep that whole reindexing code.
local function unsortedQuickRemove(myTable, index) --elements can be removed more efficiently if order doesn't need to be preserved
myTable[index] = table.remove(myTable)
end
As for optimization, I recommend trying to split up these cells into regions, and pathfinding between regions before pathfinding smaller segments (hierarchical pathfinding). With simple implementations this will likely lead to a few edge cases where the optimal path isnât found but only a valid path is, but most of the time it will still be accurate while removing a significant amount of processing depending on the regions properties. You could also cache valid paths between regions to remove a lot of the necessary pathfinding there again at a potential slight cost to accuracy or complexity as well. Iâm sure these accuracy issues can be resolved with extra thought and complexity, but a naive algorithm can probably get the job done most of the time.
And for dynamic regeneration. I would not try to recalculate the path over and over, but make it so that when something blocks a grid, any path that uses that cell in the path gets told to recalculate. This way you are only recalculating grids that actually change. This might work and might not depending on how you get your data specifically though. But overall, an event based system will let you avoid redundant work if you can find a way to design this as such without excessive overhead.
Iâm unsure of what you mean but, if youâre saying that youâre creating an entirely new path like using pfs:CreatePath() you donât need to do that. You can just do :ComputeAsync() and use break to change the path. (Which would lead to less lag)
No. i use a custom a star pathfinding, there is no ComputePath()
Iâve never used A star before but Iâm pretty sure itâs just a module right? Isnât it still under the same framework as pathfindingservice?
A* is a pathfinding algorithm. Itâs how you calculate a path from a graph representing the game world. Modules would use it under the hood.
Thatâs pretty smart. Although Iâve never needed to use it. Well then idk I canât really help with the problem sorry.
No, its a custom pathfinding not inside roblox pathfinding service
Alright then, youâre really smart. But Iâm not smart enough to help you sorry lol.
Sorry I forgot to mention, you should save the nodes that has been traversed till the current path, I did that in the Node class by storing the parent of the Node but seems like Iâve forgot to mention that part there. Apologies.