They scan the entire open list and recompute the heuristic value for every node all so they can find the min. Yikes! Seriously guys, implement a binary heap. It's easy and your pathfinder will be much faster for it!
It's open source. You could even go ahead and submit a PR with your improvements.
I guess the point of submission is to draw attention to the library and garner community comments. I feel I've made my contribution to that discussion.
Well, I didn't like the tone of your comment. People building such an engine obviously aren't incompetent, just because one part of the code you looked at wasn't as optimized as possible.
He should definitely have done it elsewhere.
Since I wasn't the one who posted it, the only reason I found the bug reports is because a friend recognized my username on GitHub, and sent me a message about it. I would have preferred bad tickets to total silence...
> P.T. Barnum:
> Without promotion, something terrible happens... nothing!
Basically, you keep promoting and promoting and maybe, maybe, there's a slight chance of something happening. But by default nothing happens.
A bad pathfinder will make it near impossible to develop certain types of games -- RTS games or any other kind of game where the map is of a non trivial size and there are agents making their way between changing pairs of locations. In addition, pathfinding is usually a fundamental operation in most of what passes for AI in games and it's not uncommon to see developers calling the pathfinder constantly, for example to reason about distances between things.
Well, yes, but with respect you can make the same argument for any other subsystem. If simplicity is the only criteria I see no reason to bother with A* at all. Just implement a bug algorithm or even blind search and let "the developer" sort it out. But that argument isn't very compelling, especially as Godot is an engine whose main selling point is making game development easier.
Still not convinced? How about this: A* is supposed to run in O(n*log(n)). By implementing the open list as an unsorted flat array, instead of a binary heap, its runtime changes to O(n^2).
gradstudent, I understand the implications of making the algorithm more efficient. You're still not getting the point that the video I linked points towards, though. An inefficient solution works if it works well enough for enough people.
When you're building an engine that contains many moving parts you don't want to spend too much time optimizing each part to the best of your abilities because if you do that you'll never have a product that people can actually do something with. That's not even to get into the main point, which is that you don't need to run the pathfinding algorithm every frame and that most of the time it actually isn't an issue. So if you spend time optimizing it you spend time doing unnecessary work. The developer of the engine agrees with this notion: https://github.com/godotengine/godot/issues/11492.
Take the advice on the video to heart, gradstudent, you'll benefit from it immensely as a programmer.
Irrespective of any other criteria, the algorithm implemented here is wrong. It's not A* but an inferior best-first derivative with much worse complexity. Anyone using this code and making face-value assumptions about its performance is in for a rude shock. The difference between O(nlog(n)) and O(n^2) is huge in practice. At the very least they should rename the class to avoid misleading potential users.
isn't just suffering from a poorly implemented A but employing