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.
3 Likes
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
1 Like
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
3 Likes
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
1 Like
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?
The pathfinder does work in 3D, if you give it a 3D map and change the distance function. Here is a video on google drive (since it is a bit long): https://drive.google.com/open?id=1OevJHLRTwYv0vQOfD4sHOMEDsvQj2b5Z
And here is the place file:
Pathfinder Test.rbxl (17.1 KB)
4 Likes
Whats the distance function for 3D maps?
The Euclidean distance in 3D works great.
3 Likes
Simply do this.
TargetPositionThatMonsterNeedsToWalkTowards = TargetPosition + (Monsterwalkspeed/TargetVelocity+0.0001)
I know this is an old post but seeing as it still gets views, I decided to mention a few things.
To answer your first question “how practical is it to make your own custom pathfinding system?”, there aren’t many cases where a custom Lua pathfinding would be faster or prove to have more benefits than PathfindingService. I don’t think Roblox’s PathfindingService is “bad” or “slow”, but it would be preferable to have more control over it(i.e. being able to ignore nodes/meshes, better handling for dynamic pathfinding).
To answer your other question, “can it turn out more optimized than Roblox’s current one?”, it really depends. See, the problem doesn’t rely on the actual pathfinding, but the grid generation. Dynamically creating grids is not cheap. If you have a grid before runtime and the state of the grid is constant, I could see custom pathfinding be faster than Roblox’s PathfindingService.
A simple way to generate a grid would be using an approach similar to a flood-fill algorithm. Keep expanding some studs outwards in all directions of your choice and you got a grid. You could then pathfind through the generated grid. However, the problem with most games is that the grid is not static. You could have moving objects which then require you to update your grid again. These updates are not cheap. If your game’s grid doesn’t change, by all means you can use this approach.
Now, if you want to further optimize your algorithm, you need to compress your grid to store relevant information within less nodes. Less nodes == faster processing, but we don’t want it to be lossy.
Here are some common ways to do so:
- Navigation Meshes (Roblox uses this internally, so implementing one in Lua would probably not prove to be more efficient than Roblox’s)
- Waypoints (Only store nodes in where you have to change directions. Great optimization for games with lots of walls and changes in direction)
- Quad-trees (Subdividing your grid so that larger (empty) areas can be represented with less or bigger nodes)
In conclusion, not many cases where custom pathfinding would prove to be better than PathfindingService.
4 Likes