4 ms·

I hope the quality of their pathfinding code is not indicative of the overall quality of this engine: https://github.com/godotengine/godot/blob/master/core/math

I hope the quality of their pathfinding code is not indicative of the overall quality of this engine: https://github.com/godotengine/godot/blob/master/core/math/a_star.cpp https://github.com/godotengine/godot/blob/master/core/math/a... 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!

makepanic 9y ago
Why not open an issue with references on how to improve it? It's open source. You could even go ahead and submit a PR with your improvements.
- gradstudent 9y ago
  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.
  - dan00 9y ago
    > 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.
    - Xoros 9y ago
      And writing a comment here instead of in an issue where the developers might hear of it is not a smart move either :) He should definitely have done it elsewhere.
  - mrmekon 9y ago
    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...
    - oblio 9y ago
      Sorry to disappoint you: > 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.
    - carussell 9y ago
      The real takeaway here is that the barrier to reporting bugs for your project is too high.
      - TazeTSchnitzel 9y ago
        GitHub has made reporting bugs extremely easy. It's sheer laziness that most don't bother.
        carussell 9y ago
        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.)
- wyldfire 9y ago
  Thankfully someone's done it [1] [1] https://github.com/godotengine/godot/issues/11492 https://github.com/godotengine/godot/issues/11492
adnzzzzZ 9y ago
You would benefit from hearing this anecdote, gradstudent https://www.youtube.com/watch?v=JjDsP5n2kSM#t=13m20s https://www.youtube.com/watch?v=JjDsP5n2kSM#t=13m20s
- gradstudent 9y ago
  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.
  - adnzzzzZ 9y ago
    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.
    - gradstudent 9y ago
      > 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).

makepanic 9y ago

Why not open an issue with references on how to improve it? It's open source. You could even go ahead and submit a PR with your improvements.

gradstudent 9y ago
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.
- dan00 9y ago
  > 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.
  - Xoros 9y ago
    And writing a comment here instead of in an issue where the developers might hear of it is not a smart move either :) He should definitely have done it elsewhere.
- mrmekon 9y ago
  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...
  - oblio 9y ago
    Sorry to disappoint you: > 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.
  - carussell 9y ago
    The real takeaway here is that the barrier to reporting bugs for your project is too high.
    - TazeTSchnitzel 9y ago
      GitHub has made reporting bugs extremely easy. It's sheer laziness that most don't bother.
      - carussell 9y ago
        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.)
wyldfire 9y ago
Thankfully someone's done it [1] [1] https://github.com/godotengine/godot/issues/11492 https://github.com/godotengine/godot/issues/11492

adnzzzzZ 9y ago

You would benefit from hearing this anecdote, gradstudent https://www.youtube.com/watch?v=JjDsP5n2kSM#t=13m20s https://www.youtube.com/watch?v=JjDsP5n2kSM#t=13m20s

gradstudent 9y ago
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.
- adnzzzzZ 9y ago
  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.
  - gradstudent 9y ago
    > 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).