Updated benchmark.
2 Likes
Maybe later on if I want to consider making this into a resource. This is simply a showcase.
1 Like
Not to be rude but I very much doubt this is optimal or very comparable to pathfindingservice if you’re not building a navmesh. It looks pretty jank
2 Likes
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
1 Like
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.
4 Likes
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.
1 Like
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.
1 Like
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
2 Likes
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.
you’re right. But, can you list some?
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.
Have a good day.
1 Like
They use A* on the game’s navmesh and if you try Pathfinding Improved Search you’ll see Roblox’s attempt to optimize and improve the heuristics of A*.
I’ve had this confirmed in 3 different conversation’s with the team members working on Pathfinding/Game AI.
Yes, I noticed after Judgy_Oreos reply.
Thanks for confirming.
The only logical thing I can see this being useful for is in the case of Roblox pathfinding failing to make an alternative route/path – then again using :MoveTo or attempting a different route position are alternatives already without a new system entirely. Without having the ability to query the NavMesh I do not think it will be superior then Roblox’s own systems.
I’d be unable to give comparative feedback compared to Roblox on the limited detail here as @tyridge77 points out I believe.
My game implements an in-house Dijkstra’s algo for mapping roads as it’s simply better for our use case and distance but that is not feasible universally hence why it’s in house. Therefore I do not think your approach is going to be useful universally as PathfindingService and I would be critical of how this can be used as a better approach compared to the already existent ones.
As I mentioned in my argument with tyrdige. I’m comparing it with pathfinding service based on accuracy and the ability to make a path with complex map geometry.
Therefore, it’s simply useless to repeat the previous argument once more.
If you have any valuable feedback by which I could potentially improve this, like pointing out actual flaws then please list them. If you have don’t, then please read the above argument and go on with your day.
Understandable - best of luck with what you are trying to achieve and let me know if you want any future feedback on additions here.
As @tyridge77 said, navmesh would be 10x better and more performance optimal. I do think this is a really good demonstration of an A* pathfinding system, but this won’t help your NPC interact with the environment, it seems like mostly what your doing is point and click navigation which is a really good idea for certain games, navmesh would allow for it to find it’s way around basically every obstacle, now that’s not to say yours can’t but I would use navmesh with this.
You’re right, just like M_etrics and tyridge77 (not pinging to avoid disturbance). And I’m also right in my case, which is that this is simply a showcase, it’s not done, it’s meant to show off the fact of how accurate my implementation is and how it can solve obstacle courses. I won’t go for a navigation mesh system because it’s a bit trickier than a simple voxel-based system, and it’s not always accurate (Roblox navigation mesh and Unity navigation mesh as examples.)
Technically:
Voxel-based provides accuracy.
Navigation Mesh provides scalability.
2 Likes