Bug: Last item in queue is not in correct order

[Sp3ci3s8472]

Version used: 5.1.0

.net Version used: netstandard2.1

Project SDK: Godot.NET.Sdk/3.3.0

IDE: Rider

Priority queue used: FastPriorityQueue

When working on my AI in my game I noticed the AI behaving not as expected. While debugging the queue showed me the following results.

As can be seen the last item in the queue is not in the correct position. I also tested this with positive values. This does not seem to be expected behaviour, since I would expect it to be at the third place [2].

At construction I created the FastPriorityQueue with a maxNodes that is the theoretical maximum in my use case (the amount of tiles I have on my ship). Just to be sure I tested it with 4 also to make sure that was not the problem.

I hope this can be fixed since I enjoy using this also for my A* pathfinding!

Note: the Weight parameter you see is used as a workaround by now sorting a list each time (which uses the Weight parameter).

If I need to provide any additional details please let me know.

[BlueRaja]

Hmm. This is intentional behavior, as there's no good way to enumerate the queue in priority-order without copying into a new queue and calling Dequeue over and over. However, I never noticed that this is not documented, and I can see why this wouldn't be expected.

One option would be to update GetEnumerator() to do exactly that. However this could lead to hard-to-find performance issues, such as your above code which calls IEnumerable<T>.First() instead of IPriorityQueue<T>.First, which would result in copying the entire queue every time you call it.

Another option would be to update the documentation to make it clear that the queue is not enumerated in priority-order.

I'll need to think on this some more. Out of curiosity, what is your use-case for needing to enumerate the queue? Note that, due to implementation details, your call to IEnumerable<T>.First() above will always be equal to IPriorityQueue<T>.First, so the issue shouldn't be there.

---

[Edit] There's also this feature request which I apparently wrote 4 months ago and completely forgot about.

[Sp3ci3s8472]

Ah that explains it, I assumed that iterating with GetEnumerator() would be in the correct order. If that would be documented that would solve some confusion.

Quite sure I called your IPriorityQueue.First method; is it perhaps a good idea to change the name of that to Peek like any other queue. To be honest I had to search since I expected Peek to be there.

Firstly I enqueue all the tasks that are in the rooms of the AI ship, due to this naïve behaviour it does enqueue tasks that might already be done by some AI (I want my AI to have the least state as possible). To make sure an idle AI character does not take that task I iterate over the the characters until I found their current task and remove that (it does a bit more but that is the short of it).

It seems it might have been a mistake on my end. Also this case seems to be better suited to just use a list and sort that. The amount of nodes is so small compare to e.g. A*. Anyway I'll recheck my other code that uses the queue to make sure I don't use the enumerator.

Hah that feature request now makes sense!

[BlueRaja]

Quite sure I called your IPriorityQueue.First method

IPriorityQueue.First is a property so you'd need to call it without the parentheses. I named it First to keep it consistent with C# naming conventions.

[Sp3ci3s8472]

Quite sure I called your IPriorityQueue.First method

IPriorityQueue.First is a property so you'd need to call it without the parentheses. I named it First to keep it consistent with C# naming conventions.

Now that you mention it, the suggestions of Rider are helpful most of the time; not this time. I hope my suggestion for a Peek instead of First might get implemented.

I guess this bug might be closed.