In the video, you can see that my implementation is far better. Myself here, won by 4:1! (Both won in the first one.)
Only one MAJOR drawback to this implementation is performance. But, of course! I’ll fix it. I’m planning on using parallel luaU to make this as fast as Roblox’s pathfinding service.
So, what do you all think about this? What more should I add to it? What more should I test with it?
Many people have actually implemented A* in Roblox before, even myself, but at least this one is 3D whereas many others (including my own) were 2D.
At 0:55, it looks like you did not program the NPC to jump at jump waypoints generated by PathfindingService. You can see the waypoint on the step is Red, which indicates that it’s a waypoint with an Action of Enum.PathWaypointAction.Jump.
That’s why I used the word advanced. Any professional can code a working 2D based A* algorithm. But not every professional can code one which is optimal on 3D. Most people would just add 2 more directions for 3D implementation which can be very laggy and can create useless nodes. My method is much more optimal.
I am using the code provided in the Pathfinding documentation by Roblox. So it in-fact is not the fact that I did not code it. It’s a Roblox issue.
I don’t usually view such update topics, but I’ll check it out and show an improved benchmark.
I seem to have made a small mistake. I assumed Roblox would provide jumping in the code snippet provided in its documentation. I was wrong. I apologize for my mistake and will upload a fixed version of the stair benchmark.
Performance-wise, it currently isn’t optimal. That’s because it doesn’t have parallel processing. But as optimal does not always mean “the best in performance,” it is optimal based on accuracy. The path produced is more accurate and more flexible as compared to the pathfinding service, which, even with the new “improved” algorithm, still can’t jump around walls (neo jump).
The only reason most people use pathfinding service is due to it being optimal and because it uses a built-in navigation mesh. This, doesn’t mean that other attempts are simply “not comparable to it”.
Can you explain more about how it is “pretty jank”?
This is how the A* algorithm works. It’s the most optimal algorithm available. The reason it “looks jank” may have to do with how it’s visualized.
This, doesn’t mean that other attempts are simply “not comparable to it”.
It kinda does. It doesn’t mean other attempts aren’t viable, but if you’re not building a navigation mesh then it’s not very comparable to pathfindingservice. It’s just a pathfinder that works for your game. Which is still cool.
I don’t know what you’re doing to generate your A* graph but I’d be willing to bet it doesn’t work out of the box for most scenarios and isn’t as scalable. That’s what makes pathfindingservice the default go-to.
Navigation meshes are popular for a reason.
Can you explain more about how it is “pretty jank”? This is how the A* algorithm works
The A* isn’t the part that looks jank. It’s whatever you’re running the A* on. If this is a toolkit designed to work with any sort of complex environment and is supposed to be fast(not just the pathing but building the walkable graph to path on), whatever you’re doing is probably not going to be as fast as a voxel based navigation mesh like roblox and many others use.
Again, that’s not to say other approaches don’t work, but they typically work better for controlled static environments where you can hand place your graph, or other situations where you can get away with something simpler due to specific map constraints or something
Of course, there is a major difference with the algorithm and how the algorithm is utilized but in my view, both algorithms and ways they are implemented are comparable.
Can you provide an example of the kind of scenario? I am still working on the system and it’s not even near completion. I would greatly appreciate you giving me an example on the kind of scenario so I can improve the algorithm.
Yes, you’re right. They are popular for their performance and scalability but are notorious for inaccuracies. Consider the Roblox navigation mesh and that of Unity’s.
Can you explain a bit more about what you mean by this? Specifically, what do you mean by the environment?
By the environment I mean the world geometry people are pathfinding on/around.
both algorithms and ways they are implemented are comparable.
Pretty sure roblox uses A*, A* is just the pathfinding algorithm, how you build the graph to pathfind on is a different thing entirely. Roblox uses a dynamic voxel based navigation mesh(we do as well for our games). Then algorithms like A* and some other algorithms as well are used(like funnel algorithms)
My point is it’s one thing to say your “advanced A* algorithm” is something pretty much no one has done yet on roblox(super loaded statement), but it’s another thing entirely to compare it to something that likely serves a different purpose than yours(even if yours works better in some situations)
If you don’t know what other people have made, it’s silly to claim it’s better than everyone elses or even roblox’s.
If you don’t know that your toolkit can work as fast, as scalable, completely dynamic, and as out of the box with no setup work as roblox’s pathfindingservice(even with its inaccuracies), it’s silly to compare it to pathfindingservice.
As far as I’m aware, Roblox actually uses Dijkstra’s Algorithm.
Oh, I understand. So, for example, some people use pre-placed nodes and such. You are referring to that, correct? Personally, for this, I won’t do that as I want to keep it dynamic.
I said that because in my research, I did not find anyone who had made such a system. Most custom algorithms I see are just 2D, and very few are 3D, by using 2 additional directions, which is extremely unoptimal. If I made a mistake and there is a better custom-made A* algorithm available, then please mention it, and I will take back my statement.
I still don’t really understand how mine and Roblox’s systems serve a completely different purpose… It’s probably just how I consider Roblox’s algorithm and how I see mine.
I did do my research. The best I did find were:
and
where both do not support 3-dimensional movement. Although I’m not saying they are bad. They are great and are greatly optimized than my implementation. However, we are talking about features here in which they aren’t the most ideal.
I’m comparing it to a pathfinding service to give the viewer an idea on how accurate this is. I have mentioned in the original post as well about performance issues and such. As for the “out of the box”. I asked you to explain it a bit more. What do you mean by it? As in, what kind of scenarios? If you can explain it then I could replicate it and improve the algorithm even more.
Your demonstration does not showcase certain pathfinding features, I think is what they are referring to, such as AgentRadius, AgentHeight, WaypointSpacing, as well as Navigation Costs and Pathfinding Links, Climbing, or the recent Partial Paths, which make it more narrow than Roblox’s in terms of scope and where it can be used.
I’m no expert, but I think Detour (which is part of the navigation bundle “Recast & Detour”, being the pathfinder, which Roblox, Unreal, Unity and Godot all use to my knowledge) supports both A* and Dijkstra.
You’ve shown us a tiny grey boxed map with a very simple path , making the claim it’s better than pathfindingservice which can handle anything you throw at it decently well for most people’s use cases , is just a bit silly
Not even talking about performance here
And as for other pathfinding implementations , this probably isn’t among the 5 most “advanced” on Roblox from what you’ve shown. Not to put you down or anything I believe that’s just a bit of an arrogant claim when you don’t know what people have made. A couple people who decide to share stuff on the dev forum make up a tiny fraction of the people who are engineering these things for their games
I think you’re still working on something cool , but there’s no need to make comparisons that are just wild assumptions at best that you have no real ability to back up in order to make the post look better
Pathfindingservice still kinda sucks(we’ve made a better one entirely in serial) but it still has a unique set of features that you can’t really replicate optimally unless you’re doing the same thing it does or similar. This is why most game engines use recast and detour or some similar navmesh toolkit
I have mentioned previously that this is a work in progress. Now that you mention such aspects. I’ll add them soon and update this post.
Interesting. Thanks for correcting me.
The goal of the demonstration is to show how my implementation is able to solve obstacle courses whereas Roblox’s service cannot. I thought it was obvious but I’ll mention it. That’s why I called mine better.
I did my research, I didn’t find any “top 5 most advanced pathfinding algorithms”. So, I called mine the most advanced. If there are some better, then I’ll remove it.
As for your second statement, you are absolutely right. But you or I can’t really say that people who engineer these implementations privately are better without proper evidence. They may be better, but they may also not be better.
Thanks.
The comparisons aren’t wild assumptions. I showed you in the demo. I’m comparing my system to Roblox’s in terms of accuracy and the ability to solve obstacle courses…
Yes you’re right. But, can you list some?
In this entire argument you are really providing me with little to no feedback on how I could actually end up improving my creation. Please, tell me what scenarios I could make that would make it “comparable as you keep putting it” to pathfinding service. As well as providing me with at least one public showcase on pathfinding which is better than mine. And telling me the features I could add to this.
I think it would be much better if we continue this in a private chat as this all is simply off topic.
That’s a lil off topic for this conversation, there’s probably thousands of articles on the internet talking about navmesh pathfinding in game dev , the problems it solves , the reasons you might(or might not) want to use it , and why it is a popular choice for most games over pathfinding on a regular grid
There’s not much actual feedback for people to give here because you’re not talking about what you actually made/how it works even briefly on a technical level(just that it’s a* in 3D) so people can’t give suggestions on something that might be better.
You also didn’t show stuff that could gauge its actual feasibility in games, such as a video of it responding quickly to real time changes , pathfinding across a distance of hundreds of studs quickly, etc
I’m sure you’ve built something that works well for what you’re trying to do and that’s great, it’s just a little over simplified to make a statement that it’s “better than Roblox’s” even if it did something better, because navmesh pathfinding vs pathfinding on a grid or whatever you’re doing comes with its own sets of pros and cons. That’s the only point I was trying to make
Not really. I’m asking for features in the Roblox pathfinding that I may have missed.
I’m not wanting feedback on the technical scale. I just want the questions that I asked in my original topic answered. That are:
What can I add?
What scenarios I can test it with? (Like a dynamic map changing every few seconds etc.)
Yes, you are right. That’s because this post is meant to act as a sort of development log. I’ll keep posting features I add and improvements I make over time until I consider releasing this to the public to use.
I understand. And you are right. Both have pros and cons. I’ll try googling it and seeing the differences and I’ll probably try replicating it or simply going for a navigation mesh (unlikely because a navigation mesh is inaccurate most of the time.)
Thank you for participating in the conversation and pointing out some flaws. I hope that you are able to provide me with some solutions to fix such flaws.
” and “This guy 
”.
