ershn
commented
9 months ago I'm quite surprised to know the current implementation uses a linear search ! Having a fast way to find the next node to traverse is pretty essential to the performance of the A* algorithm so this proposal seems pretty high priority to me. I can take a stab at it if you're too busy.
It's a different problem but splitting up that 450+ lines function into smaller parts to improve readability and maintainability also wouldn't hurt.
sandygk
Describe the project you are working on
This applies to any repo that uses navigation agents
Describe the problem or limitation you are having in your project
The current implementation of the AStar algorithm in NavAgents uses a linear search to find the node with the minimum cost. This approach is inefficient, especially in complex scenes with numerous nodes, leading to performance bottlenecks during pathfinding operations.
Describe the feature / enhancement and how it helps to overcome the problem or limitation
Replace the linear search method in the AStar algorithm used by NavAgents with a heap-based approach to find the node with the minimum cost. This change will significantly improve the efficiency of the pathfinding process, reducing the computational load and enhancing the performance, particularly in scenes with a large number of polygons.
Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams
This is where the linear search takes place, the proposal here is to replace it with a
heap.popoperation:https://github.com/godotengine/godot/blob/923ef2b46a04e8f54c0a60bae8a0a6269fa52ed2/modules/navigation/nav_map.cpp#L358C1-L369C4
If this enhancement will not be used often, can it be worked around with a few lines of script?
No
Is there a reason why this should be core and not an add-on in the asset library?
This is already an internal implementation of the Engine