The fibonacci heap have a bug. If you insert an element with a priority >= 268435455, and you then pop elements until this element is the only one left and tries to pop it, you will trigger a crash.
This is the cause of the bug in CluelessPlus that have puzzled me for probably more than a year. (It doesn't explain why CluelessPlus have insert a such high value, but it is the cause of the crash)
The attached patch fixes this problem with the fibonacci heap version 2. It is possible that some of you might be able to optimize this fix and make it faster. An alternative is to use the fibonacci heap implementation that Morloth has written for NoCAB, which doesn't have this problem. He claims that his implementation also is faster, but I don't know if it is true or not.
Fix to Fibonacci Heap library (version 2)
Moderator: OpenTTD Developers
Fix to Fibonacci Heap library (version 2)
- Attachments
-
- fibonacci_heap2-fix.patch
- (582 Bytes) Downloaded 379 times
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
Junctioneer (a traffic intersection simulator)
Re: Fix to Fibonacci Heap library (version 2)
As nobody has complained or said anything against my proposed changes for more than a month now, I have published a new version with my changes and committed them to the VCS.
Most important, if you used Fibonacci Heap 2, when you upload a new version of your AI, remember to change your AI to include version 3 and pick version 3 in the list. Otherwise you will lose the dependency to this library in your bananas entry.
Most important, if you used Fibonacci Heap 2, when you upload a new version of your AI, remember to change your AI to include version 3 and pick version 3 in the list. Otherwise you will lose the dependency to this library in your bananas entry.
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
Junctioneer (a traffic intersection simulator)
Who is online
Users browsing this forum: No registered users and 8 guests