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!
I could indeed and thank you for the suggestion. However I'd need to be motivated enough to spend time submitting tickets (good tickets!) to a project I'm not currently invested in. Which I am not.
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.
This was pretty much my experience with getting a project posted in HN. A bunch of bugs reported in the HN comments, and not a single issue opened on GitHub.
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...
Replace file a bug on GitHub with sign in using Facebook Connect. Is the amount of effort it takes really the only conceivable reason someone could have for opting out? (And regardless, threshold of effort isn't even a bad reason for not doing something.)
> 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.
Thank you for the interesting video. The problem I refer to in the Godot pathfinder is not a case of premature optimisation; it's not (as discussed at 16:10 in your video) code whose performance is negligible in the overall scheme of things. It's the exact opposite.
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.
For most use cases someone doesn't need to run pathfinding operations every frame and someone isn't making an RTS, so from the perspective of the engine developer the best thing they can do is just a good enough solution that works well enough for most people. In the case where the pathfinder really does become a bottleneck the developer has the option to develop his own more efficient solution.
> In the case where the pathfinder really does become a bottleneck the developer has the option to develop his own more efficient solution.
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).
>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.
> 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.
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
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!