Custom Pathfinding Just Isn't Working

Cyber_Star00 · March 31, 2021, 5:00am

Hello, all.

Preface

I would first like to explain that this post arises from a culmination of research and previous posts regarding the same project. As such, I will make several references to other posts, and include sites that I have come across in my own research.

What I am trying to accomplish

I am trying to create a pathfinding system for units (such as infantry and tanks) to navigate a map.
The pathfinder must be able to calculate paths very quickly, even on large-scale maps. In addition, the pathfinder must be dynamic, meaning that it will take into account obstacles, such as buildings, when they are added / removed.

Map Conditions & Unit Behaviors

In this game, a map has three possible levels of elevation, as shown in this image:
test map
Land units may only access platforms of higher / lower elevation if there is a ramp connected to them. Cliffs (the edges between platforms of differing elevations) are marked as “blocked,” while platforms and ramps are marked as “open.”
When a building is placed on the map, any space occupied by that building is also marked as “blocked.” Mobile units do not create “blocked” space in this way; instead they push each other out of the way, similar in nature to StarCraft 2’s unit collision.
I would like for there to be different types of terrain that are easier / harder to move through. For example, units would move faster over concrete / glass, but slower in snow / water. However, I am willing to sacrifice this mechanic for the sake of optimization, if necessary.
It should be mentioned that air units do not need to use any sort of pathfinding algorithm, since they are capable of flying over obstacles. However, I need a pathfinding system for units that are unable to do so.
Units in this game do not use Humanoids, and cannot jump.

The Issue

I have made several attempts to create this particular system, and most of the criteria I have set in the previous section have been satisfied (different types of terrain have not yet been included). However, there is one singular issue that has haunted (I daresay “taunted”) me from the very beginning: pathfinding is simply not fast / efficient enough when the map is scaled to a practical size. I will attempt to explain this further in the following section.

What I have tried so far

Roblox Pathfinding Service

In the early days of the game’s development, I used the Roblox Pathfinding Service; but over time it became clear that it simply had too many difficulties for my liking. It has been a long time since I’ve used it, so unfortunately I cannot remember the specifics of why it didn’t work. What I can say for certain is that it was unreliable in some instances

A* Pathfinding with a uniform-cost grid

In my research finding an alternate solution, I found threads where developers mentioned this thing called “A* Pathfinding”^[1]^[2]. I wasn’t sure what it meant at the time, but based on everything I had read thus far, it seemed to be the most recommended solution. I had also read posts mentioning a more efficient “JPS Pathfinding” system, but I’ll get to that in the next section.
I should make it clear that node generation goes hand-in-hand with the pathfinding algorithm, since nodes are what the algorithm examines to create a path. In this, my first custom pathfinding system, I generated what is called a “uniform-cost grid,” meaning that nodes are evenly distributed across the map.
The issue I discovered with this system was that there were just too many nodes on the map for a path to be calculated quickly^[3]. Units could take several seconds (at worst) before finally reacting to their command. I considered creating a system to reduce the number of nodes generated, but I first decided to “upgrade” the algorithm…

JPS Pathfinding with a uniform-cost grid

As I mentioned earlier, I had read comments made by other developers in other forum posts that the JPS pathfinding algorithm performed much better than A*^[4]. The reason I chose to work on this method first is because, in my research, it was explicitly stated that JPS required a uniform-cost grid in order to work properly; and I already had a uniform-cost grid ready to go.
Now, I’m going to make a bold statement here: those developers didn’t know what they were talking about.
I am willing to make the assumption that none of the developers I found making this recommendation had ever actually applied the algorithm in their own work-- or at least, not at this scale. I spent a lot of time trying to decipher the impenetrable fog of mathematical jargon that is the JPS Algorithm Papers^[5]^[6]^[7]^[8], and was lucky enough to find someone’s completed version of the JPS Algorithm on GitHub^[9]. I was able to convert the code into Roblox lua, and in my small-scale tests, certainly worked. However, once I implemented it in my test map, it actually performed worse than A*^[10]. Even with optimizations made based on other developers’ resources^[11]^[12], it was impossible to create a path from one point to another without the game completely freezing for at least a 5th of a second. Not even A* did that!
The only conclusion I can come to, after all this, is that Roblox lua is simply too high-level of a language for the JPS algorithm₁.
Needless to say, I was heavily discouraged by this, and had to take a long break from working on this game due to burnout. However, upon returning to this project, I attempted yet another strategy: optimizing node generation.

A* Pathfinding with a QuadTree grid (current)

I did some sleuthing in the Roblox Developer Forum, and came upon a thread that discussed using a “QuadTree” to generate nodes^[13]. To describe it as simply as possible, a QuadTree organizes groups of empty nodes into a single, larger node. (This is not really how it works if you looked into the code, but the final product is the same.) I did some research, and was pleasantly surprised to find that this programming method was quick to learn and apply (at least, compared to JPS or A*).

(This is the same map as shown in the previous image.)
While the first iteration of this system worked quite well, I still had to make the QuadTree dynamic. In other words, I needed to update the layout of nodes whenever an obstacle, such as a building, was placed on the map. As programming usually goes, the more I tried to make a quick fix for it, the more frustrating the issue became, and eventually I realized that an overhaul of the system was required. Long story short, I spent some time figuring out how to do it, and then did it. The QuadTree system now updates, whenever a building is placed / removed, almost instantly.
However, despite the optimization of this system, to my dismay the one issue remains the same: upon scaling the map to a more reasonable size (a size that I would imagine even a simple 1v1 map to be), pathfinding is still slow and laggy.

Post Script

I’d like to thank those who set aside the time to read this. I may make edits to this post in the near future, to add more links / images for developers to gain a better understanding of what the pathfinding looks like. If possible, I will also respond to users’ questions by editing this main post; otherwise I will reply to them directly.
As always, any thoughts / advice / critiques / additional references are appreciated.

Sources

Additional Sources

These are sources that I did not mention / include in the previous sections, but that I have used in my programming “journey,” so to speak. I’ve decided to put them here to save other developers the hassle of finding these sources in the first place (as well as show developers what I have already looked at whilst working on this project).
Please note that I have used some sources more than others, so I cannot guarantee that you will find all of these sources helpful.

A* pathfinding / pathfinding in general

JPS pathfinding

QuadTree

Footnotes

In fact, whilst working on this forum thread, I found this post by @IdiomicLanguage explaining that JPS performs slower in lua… if only I had found this earlier.

ryan00107rules · March 31, 2021, 5:04am

hmmm… do you want to just point to the destination or take them automatically?

ryan00107rules · March 31, 2021, 5:07am

if what u r looking for is for it to auto take u this is a script for it to take the humanoid to take them to the destination. It does use the roblox pathfinding service tho…

local PathfindingService = game:GetService(“PathfindingService”)

local Humanoid = script.Parent.Humanoid
local Root = script.Parent:FindFirstChild(“HumanoidRootPart”)
local goal = game.Workspace.Goal.Position

local path = PathfindingService:CreatePath()

path:ComputeAsync(Root.Position, goal)

local waypoints = path:GetWaypoints()

for i, waypoint in ipairs(waypoints) do
Humanoid:MoveTo(waypoint.Position)
if waypoint.Action == Enum.PathWaypointAction.Jump then
    Humanoid.Jump = true
end
Humanoid.MoveToFinished:Wait()
end

Also the spacing is not working properly??
I copy and pasted from studio but the script spacing does not work apparently

Pokemoncraft5290 · March 31, 2021, 5:09am

He specifically said that it had too many difficulties and that it was unreliable.

ryan00107rules · March 31, 2021, 5:10am

I did notice that but I don’t know any other way to do that…

IdiomicLanguage · March 31, 2021, 9:05am

Hierarchical A* should be fast enough for any use case. It is a generalization of the Quadtree method. Parent nodes need not contain only 4 children, all leaves a part of a parent node leading to a complete higher level map, parents only contain children that are connected to each other, and the tree stops when all separate graphs have a single parent.

You can choose any method to form the tree, but the depth vs breadth have tradeoffs in which cases are more efficient. You can choose to always include 4 children like the Quadtree to start.

Pathfinding begins by finding the ancestor nodes of the goal and start. If any ancestors are shared, then they are reachable then there exists a path between them. You can perform A* on the topmost node’s children (using cached distances between the nodes, or strait distance estimates which costs more and causes a longer search). And then break down the nearest node and perform pathfinding again (note, the goal is the parent’s sibling, start is the ancester of start which is a sibling in the nodes we are searching).

Note that it’s a little more complicated but I shortened it since I am typing on ny phone. You should look up papers on it. You must perform the search down the hierarchy with the goal’ ancestors, and keep track of some paths as you search downward. Nodes at a higher level may have multiple connections to other siblings so each unique, reachable path between a connection from the start ancestor and a connection to the goal ancestor must be stored. (Unique as in not using the same start and goal connections). Those costs are increased and the paths pruned and searches continue downwards.

To analyse the performance theoretically, lets consider a map of 1,000,000 x 1,000,000 studs. If we hap a depth of 7 with the leaf node being a single stud, and parents containing 100 leaves, then each level will cover these many studs per node:
1: 1
2: 100
3: 10,000
4: 1,000,000
5: 100,000,000
6: 10,000,000,000
7: 1,000,000,000,000

Note, lvl 7 is 1,000,000 x 1,000,000.

Now, by pathfinding on the top level we traverse at most 50 nodes. If we consider the worst case again and the nodes land such that their nearest shared ancestor is the tree root, then we traverse again at lost 50 nodes as we go down each lines of ancestors, 6 ancestors each. That is 600 nodes for going down plus the 50 on top. We traversed a worst case of 650 nodes to find a know perfect path in 1,000,000 x 1,000,000 grid.

For a path in 1,000 x 1,000 studs level 4 is enough with at most 350 nodes being traversed.

For a path in 100 x 100 studs, 250 nodes are traversed at max.

IdiomicLanguage · March 31, 2021, 9:10am

The other option is offloading the work to a server. I am super fast at writing pathfinders, so I could make a fast one for you and have it up in a week for a price. Send me a message if you are interested.

It would require a starting version of you map to be submitted, and per-place dynamic updates. The cost will depend upon the number the requests and game instances running. I can make the cost transparent and add on a slight fee for development and maintenance.

When I ran RBXMod, the latency was around 16 ms after the TCP connection was initialized. So it would be a pretty fast service.

Guruu_G · March 31, 2021, 4:58pm

I’d look into something called Ray Marching If you haven’t already, can defiantly handle more stress if done right.

I made a regular a* pathfinding algorithm once that would find path on opposite ends of 4 max size baseplates in under 1 second. Only problem with it was the retracing of shortest path. So when i had collisions it would stack nodes to count as a valid path for shortest path cause its trying to go around the collision so it gets all possible routes around it as a valid node…

How I achieved under 1 second? Simple Heap Data Structure was used with Heap Sorting algorithm in place.

Problems for large grids? Long startup server times.
More nodes,
Accuracy of nodes based on diameter size per node space… You want less accuracy for bigger grids as you’d get less nodes to store.

The pathfinding algorithm doesn’t go through all nodes just uses as references points to travel through he grid.