News for hackers. Stuff that matters.
Re:Godot Engine – Free and open-source 2D and 3D game engine by gradstudent on Friday September 22, 2017 @09:37PM (#15317508)
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.

Re:Godot Engine – Free and open-source 2D and 3D game engine by adnzzzzZ on Saturday September 23, 2017 @12:24AM (#15318099)
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.
Re:Godot Engine – Free and open-source 2D and 3D game engine by gradstudent on Saturday September 23, 2017 @01:26AM (#15318302)
> 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).

Re:Godot Engine – Free and open-source 2D and 3D game engine by adnzzzzZ on Saturday September 23, 2017 @02:37AM (#15318482)
>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.

Re:Godot Engine – Free and open-source 2D and 3D game engine by gradstudent on Saturday September 23, 2017 @04:40AM (#15318831)
> 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