NodeQueue implementation issues

[sssooonnnggg]

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]

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]

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]

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

[ikpil]

thank you. I will check it and mention you!

[ikpil]

First of all, thank you for your interest and for sharing the code.

From an algorithmic standpoint, the binary heap does seem to be a better choice. However, in actual tests, it did not result in better performance.

This might be because RcSortedQueue includes some specialized logic that is more suitable for RecastNavigation. Specifically, RcSortedQueue has a custom mechanism where it sorts the internal data only when necessary during a Pop operation.

So, here are my perspectives:

1. When comparing the pros and cons of giving users the ability to choose the algorithm, is the benefit significant enough?
2. When evaluating the performance of RcSortedQueue versus RcBinaryMinHeap, does the advantage of the binary heap clearly outweigh the disadvantages of the sorted queue?

I’d love to hear your thoughts or any other angles you think we might be missing. @sssooonnnggg

[sssooonnnggg]

Thanks for reviewing😘

I think this might depend on the number of pathfinding iterations and the size of the open set. Each iteration involves popping one element and pushing n elements into the open set. If a SortedList is used and the open set contains many items, each pop operation would trigger a full re-sorting (O(nlogn)). In such cases(n > 1 + push count in one iteration), a SortedList would be slower than a binary heap.

In my actual tests, the start and end points were set relatively far apart. In this case, the binary heap performed better.