Honestly, I think it all depends on how well you make the system. I think its totally possible to make a custom path-finding system that works better than Roblox’s right now, but that all depends on how skilled you are at making it.
That being said, there might be some simple workarounds that we are just not seeing to common pathfinding issues that require no change of the system on Roblox’s part.
The biggest issue is the nav mesh isn’t accurate.
The nav mesh says it can get over a certain object, but in reality it cannot.
Maybe it’s something I’m doing when computing the path? Maybe I need to set an agent size?
What is A*?
Well it more than possible that the pathfindingService isnt accounting for the size of the character and how its head/legs/torso could collide with things.
Did someone mention pathfinding?!? I love pathfinding, go to my profile and search “pathfinding” for all sorts of interesting comments about it.
As you’ve found out, quite practical. Making a pathfinder is not at all difficult. It does take some debugging knowledge, research, and the ability to implement a well documented algorithm.
Theoretically, yes. The reason is that Roblox’s pathfinder is meant to work on every game. You, however, are developing a pathfinder for your own game and can make many assumptions where Roblox had to be more general. In addition, Roblox internally uses the open source Recast and Detour pathfinding libraries, but has only tacked on very abtract support for them and doesn’t near the level of detail and sophistication to make use of such a powerful library. Roblox does have the advantage though that their pathfinder is compiled in C and C++, making it much, much quicker out of the box than one implemented in Lua.
We’ll see if Roblox actually puts effort into a better pathfinding API in the future. In the mean time, here are some thing you can do to make your pathfinder more efficient than the Roblox one.
Hopefully that helps! Pathfinding is fun 
Pathfinding would take a really long time to write for little benefit in my opinion.
I would just go through and manually fix cases where roblox’s default pathfinding doesn’t work (for example, by putting invisible bricks in between steps on the stairs)
It would save a lot of time, and let you focus on making your actual game.
Can I see your code, please? It seems to me like A* really struggles with 3d maps. Either that, or I’m doing something wrong.
If you want to fix cases where the monster cannot go up stairs you dont need your own system, i made my own (you can check it out on my profile) and it was an arduous task.
What you need to do is simply find the nearest stair to the player and pathfind from there to make sure the stair is the one you need, then pathfind to the stair and make a movement animation to go upwards.
I see that your heuristic formula works very well for 2D maps. But since mine is 3D, the pathfinding doesn’t work so well. Would you like to see my code? Maybe Im doing something wrong.
function getXYDist(pointA, pointB)
return (Vector3.new(pointA.x, 0, pointA.z) - Vector3.new(pointB.x, 0, pointB.z)).magnitude
end
function findPath(stringStartP, stringEndP) --these are strings
print("started")
local open = {}
local closed = {} --hash
--costs
local sGCost = getXYDist(StringToVec(stringStartP), StringToVec(stringStartP))
local sHCost = getXYDist(StringToVec(stringEndP), StringToVec(stringStartP))
local sFCost = sGCost + sHCost
table.insert(open, {
gCost = sGCost,
hCost = sHCost,
fCost = sFCost,
point = StringToVec(stringStartP)
})
local function QuickRemove(tbl, index)
local size = #tbl
tbl[index] = tbl[size]
tbl[size] = nil
end
local function foundInOpen(point)
local found, num = false, nil
for i, v in pairs(open) do
if v.point == point then
found = true
num = i
break
end
end
return found
end
local toDraw = {}
local function removeFromOpen(point)
local it = 1
while it < #open do
if open[it].point == point then
toDraw[tostring(point)] = true
QuickRemove(open, it)
break
else
it = it + 1
end
end
end
while (#open > 0) do
local currentNodeInfo = open[1] --vec
for nodeNum = 1, #open do
--to compare
local cGCost = getXYDist(StringToVec(stringStartP), open[nodeNum].point)
local cHCost = getXYDist(StringToVec(stringEndP), open[nodeNum].point)
local cFCost = cGCost + cHCost
if (cFCost < currentNodeInfo.fCost) or (currentNodeInfo.fCost == cFCost) then
if cHCost < currentNodeInfo.hCost then
currentNodeInfo = open[nodeNum]
end
end
end
--remove from open set
removeFromOpen(currentNodeInfo.point)
closed[tostring(currentNodeInfo.point)] = true
if tostring(currentNodeInfo.point) == stringEndP then
print("path computation finished")
return
end
for stringNeighborPoint, _ in pairs(webCache[tostring(currentNodeInfo.point)].Neighbors) do
if not closed[stringNeighborPoint] then
local found = foundInOpen(StringToVec(stringNeighborPoint))
local currentNGCost = getXYDist(StringToVec(stringStartP), StringToVec(stringNeighborPoint))
local nGCost = currentNodeInfo.gCost + getXYDist(currentNodeInfo.point, StringToVec(stringNeighborPoint))
local nHCost = getXYDist(StringToVec(stringEndP), StringToVec(stringNeighborPoint))
local nFCost = nGCost + nHCost
if (nGCost < currentNGCost) or not found then
if not found then
table.insert(open, {
parent = currentNodeInfo,
gCost = nGCost,
hCost = nHCost,
fCost = nFCost,
point = StringToVec(stringNeighborPoint)
})
end
end
end
end
end
end
You can use 3D magnitude as your h cost since it is always “less than or equal to the actual shortest path length”. If you choose a different function closer to the actual shortest path length that still satisfies that property, then A* will run faster. If your h cost is ever greater than the shortest path length then A* may not find the shortest path.
I’d consider moving the G, H, and F costs as well as the point to their own tables. Have a couple tables of values instead of a table of tables of values. If you do this, then you lose the overhead of creating a table for every node visited.
The functions inside of findPath should be moved out. Not only does this reduce indentation, promote independence, and prevent accidental manipulation and access but it also will increase performance by preventing closures from being bade when findPath is called. If the functions need access to variables, they can be passed in as arguments or as file level upvalues.
The heavy work of finding in and removing from open can be offloaded to lightning fast C by using an integer point ID as the key. All node references (like neighbors) should use this node ID integer instead. Doing so causes C place the ID in the hash map portion of the table. The result is a O(log(n)) operation for insertion, search, and deletion whereas your array implementation is currently O(1) for insertion but O(n) for search and deletion. Since a search needs to be performed before every insertion in our use case, your insertion is also effectively O(n) (very bad considering A* often performs many times more insertions than deletions).
That should be zero for any valid cost function. In addition, the parsed version of the start and goal points should be cached, especially since you need to check if every node you visit is the goal and get the distance to it every time you insert a point. I also noticed that you use the start point every time you insert a node. Not only is the duplication of parsing being done here a performance issue, but this is a bug.
The G cost should be a a running total of the walked distance to get to a point – not the straight line distance from the point to the start. It is different from the H cost as it not only represents how far we’ve come verses how far we have to go, but it is an exact and known value whereas the H cost is a heuristic (that is why it is called the H cost). In addition when the goal is the current point, the G cost represents the shortest path length to the goal. Looking further down in the code, I believe that cGCost should be set to open[nodeNum].gCost, and similarly for the other two costs.
Since
We don’t need to check if the H cost is lower than the current HCost. This will lead to inefficient behavior. The total cost (F cost) should be the only one used to determine the next point to expand. In addition, <= rather than a < and then a == is the idiomatic Lua practice.
Since the G, H, and F costs are related, you only need to store two of them and the third and be quickly calculated. This is an option, but may not be best for your uses.
Equality can be checked for Vector3 once you cache the goal point in Vector4 form.
The logic is strong here. Boolean algebra tells us that this is equivalent to
if not found then
...
end
I think you just meant to leave out the inner if statement. Also currenNGCost should only be set if the point was found, and it should be set to the point’s current G cost rather than the straight line distance from the start to the point (which no G cost will ever be less than, due to the properties of the cost function mentioned above).
I just realized that if nodeNum is stored outside the for loop then this call
removeFromOpen(currentNodeInfo.point) can be turned into this one QuickRemove(open, nodeNum) which is O(1) instead of O(n). This would also be true if you were to use node IDs instead.
You should consider using a Binary Heap from GitHub for a O(log(n)) pop operation rather than O(n).
Haha, I too have learned not to use Vector3s in hash tables! It turns out that even if two Vector3’s == eachother (due to the __eql metamethod) they they may not hash to the same value. I’m truly sorry if you ran into this and had to debug it. Using integer node ID keys resolves this issue. I wish Roblox would make immutable Vector3s unique like Lua strings, but alas it is a CPU-memory trade-off.
These costs can be computed only if they are needed inside the if statement below.
I gave an excellent implementation of the basics of A* here: Pathfinding in a Cave Network - #7 by IdiomicLanguage
I don’t know if i’m implementing the algorithm right or my set up is wrong. It somewhat finds the path, but it skips nodes occasionally and can’t find over obstacles.
EDIT: sorry for late reply
You’ll have to post the code for me to see if anything is wrong with it. A place file would be best, but not required.
BTW, I just recently implemented a A* pathfinder on a generated maze. What I found was that my pathfinder was always at least 10 times faster than the built in pathfinder. I didn’t implement hierarchical or deferred pathfinding either. However, my pathfinder took advantage of information the built in pathfinder didn’t have: which cells of the maze were connected and which were not. Even after the built in pathfinder refused to find a path because it was too long, my pathfinder was still performing well. I plan on adding more features to this pathfinder and hosting it on my service, which you may be familiar with, RBXMod. This way, I can sell access to my premium pathfinder and perform pathfinding operations without any hit of lag on servers since it will run remotely on mine. ANYWAYS, that is off topic. I’m just excited about it.
Post some code and I’ll take a look.
Here’s my A* implentation:
function StringToVec(str)
local tab = {}
for s in string.gmatch(str,"[^,]+") do
table.insert(tab,tonumber(s))
end
return Vector3.new(unpack(tab))
end
function getXYDist(pointA, pointB)
return (Vector3.new(pointA.x, 0, pointA.z) - Vector3.new(pointB.x, 0, pointB.z)).magnitude
end
function findPath(stringStartP, stringEndP) --these are strings
print("started")
local open = {}
local closed = {} --hash
--costs
local sGCost = getXYDist(StringToVec(stringStartP), StringToVec(stringStartP))
local sHCost = getXYDist(StringToVec(stringEndP), StringToVec(stringStartP))
local sFCost = sGCost + sHCost
table.insert(open, {
gCost = sGCost,
hCost = sHCost,
fCost = sFCost,
point = StringToVec(stringStartP)
})
local function QuickRemove(tbl, index)
local size = #tbl
tbl[index] = tbl[size]
tbl[size] = nil
end
local function foundInOpen(point)
local found, num = false, nil
for i, v in pairs(open) do
if v.point == point then
found = true
num = i
break
end
end
return found
end
local toDraw = {}
local function removeFromOpen(point)
local it = 1
while it < #open do
if open[it].point == point then
toDraw[tostring(point)] = true
QuickRemove(open, it)
break
else
it = it + 1
end
end
end
while (#open > 0) do
local currentNodeInfo = open[1] --vec
for nodeNum = 1, #open do
--to compare
local cGCost = getXYDist(StringToVec(stringStartP), open[nodeNum].point)
local cHCost = getXYDist(StringToVec(stringEndP), open[nodeNum].point)
local cFCost = cGCost + cHCost
if (cFCost < currentNodeInfo.fCost) or (currentNodeInfo.fCost == cFCost) then
if cHCost < currentNodeInfo.hCost then
currentNodeInfo = open[nodeNum]
end
end
end
--remove from open set
removeFromOpen(currentNodeInfo.point)
closed[tostring(currentNodeInfo.point)] = true
if tostring(currentNodeInfo.point) == stringEndP then
print("path computation finished")
return
end
for stringNeighborPoint, _ in pairs(webCache[tostring(currentNodeInfo.point)].Neighbors) do
if not closed[stringNeighborPoint] then
local found = foundInOpen(StringToVec(stringNeighborPoint))
local currentNGCost = getXYDist(StringToVec(stringStartP), StringToVec(stringNeighborPoint))
local nGCost = currentNodeInfo.gCost + getXYDist(currentNodeInfo.point, StringToVec(stringNeighborPoint))
local nHCost = getXYDist(StringToVec(stringEndP), StringToVec(stringNeighborPoint))
local nFCost = nGCost + nHCost
if (nGCost < currentNGCost) or not found then
if not found then
table.insert(open, {
parent = currentNodeInfo,
gCost = nGCost,
hCost = nHCost,
fCost = nFCost,
point = StringToVec(stringNeighborPoint)
})
end
end
end
end
end
end
The web cache is “pasted” at the start of the game. There are many modules that hold the points, structured in a convenient way to look up neighbors. These modules are generated and written to in my map web computation system.
Here’s the code for pasting to webCache
local webCache = {} --contains nodes
for i, v in pairs(PointMobuldes:GetChildren()) do
local piecePoints = DEEPCOPY.Copy(require(v).Points)
for i, v in pairs(piecePoints) do
webCache[i] = v
end
end
I’ve attached the Point Modules so you can get an idea of how the points are structured.
point modules.rbxm (2.3 MB)
This is nearly the same function as you posted earlier. I thought you might have fix the issues I pointed out in it. Not all of it where stylistic / performance related, but I also found a couple bugs. The main issue is that the G cost of nodes is being computed incorrectly. I mentioned how in my post above. Once those things I mentioned are changed, I’d be happy to take another look.
Alright. My bad it was so long since I went back to this post.
By the way, is your pathfinding 3D? Can i see a demo?