Godot: Use Binary Heap for A* Pathfinding

[coppolaemilio]

I'm sorry to post this here without knowing exactly the topic but since the initial reporter doesn't want to open a ticket so I will try to do my best to get this info to you guys. You might close if you think it is useless.

Godot reached the top in HN (https://news.ycombinator.com/item?id=15309989) and a reader said this:

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...
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!

Thread here: https://news.ycombinator.com/item?id=15310645

Hope it helps. Cheers!

[groud]

Thanks for submitting the issue, the comment is not useless.
But yet there are a lot of stuff to do in the engine, optimizing such things is not a priority.

If someone complains about it she or he can open a PR. ;)

[kubecz3k]

Some reference I believe: https://www.policyalmanac.org/games/binaryHeaps.htm

[reduz]

The post in HN references this part of the code:

https://github.com/godotengine/godot/blob/master/core/math/a_star.cpp#L234

I already put a comment in there mentioning that it could be optimized but,
honestly, in general given A* is pretty efficient in practical cases, this
is not too bad anyway. There are also many existing optimizations depending
on different topologies, but current implementation is meant to be more
general use case.

On Fri, Sep 22, 2017 at 12:05 PM, kubecz3k [e-mail] wrote:

Some reference I believe: https://www.policyalmanac.org/
games/binaryHeaps.htm

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/godotengine/godot/issues/11492#issuecomment-331473301,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AF-Z2_C66iJdLjtslXu4c3Y7g1tAKS9xks5sk8zTgaJpZM4PgmDV
.

[ghost]

is this a case of premature optimization is the root of all evil ?

[akien-mga]

is this a case of premature optimization is the root of all evil ?

No. It's just a case of low priority optimization as it's already pretty fast, and as @reduz mentioned, needing some research to find out what kind of optimization can be done without compromising the generic nature of our A* implementation. But if someone wants to work on such optimization, it's welcome.

[NathanWarden]

I agree this is low priority. The good thing it that from the user's end there are ways to optimize pathfinding on several agents such as by offsetting their calculations by a frame or two. If you need them to all move at once you wait for all calculations to finish and then start moving them. It's not ideal in some cases, but unless you're moving 200+ agents at once, or you're trying to move them across an extremely dense navmesh, it really shouldn't be too much of an immediate problem :)

[Chaosus]

I think its fixed in https://github.com/godotengine/godot/pull/28925 Closed by bugsquad.