Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

NodeQueue implementation issues #89

Open
sssooonnnggg opened this issue Feb 27, 2025 · 3 comments
Open

NodeQueue implementation issues #89

sssooonnnggg opened this issue Feb 27, 2025 · 3 comments

Comments

@sssooonnnggg
Copy link
Contributor

Hi, I'm interested why use a sorted queue to implement the NodeQueue, based on benchmarks and my own tests, the version based on binary heap is faster than sorted list, and the official C++ recast implementation is also using a binary heap.

@sssooonnnggg
Copy link
Contributor Author

As far as I know, the EnqueueDequeue_* test is closer to a real pathfinding scenario.
Because in the A* algorithm, it is generally to pop the best node first and then push n neighbors within a loop.

@ikpil
Copy link
Owner

ikpil commented Mar 2, 2025

I apologize, I can't recall the details as I implemented it myself due to a bug during development. If you have the tested code, could you share it with me? If, as you mentioned, the binary heap implementation is better, I will review it and apply the changes!

@sssooonnnggg
Copy link
Contributor Author

Ok, I have submitted a PR to compare the performance differences of the node queue data structure. Please refer to #90.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants