Fix to Fibonacci Heap library (version 2)

Discuss the new AI features ("NoAI") introduced into OpenTTD 0.7, allowing you to implement custom AIs, and the new Game Scripts available in OpenTTD 1.2 and higher.

Moderator: OpenTTD Developers

Post Reply
User avatar
Zuu
OpenTTD Developer
OpenTTD Developer
Posts: 4553
Joined: 09 Jun 2003 18:21
Location: /home/sweden

Fix to Fibonacci Heap library (version 2)

Post by Zuu »

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.
Attachments
fibonacci_heap2-fix.patch
(582 Bytes) Downloaded 332 times
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
User avatar
Zuu
OpenTTD Developer
OpenTTD Developer
Posts: 4553
Joined: 09 Jun 2003 18:21
Location: /home/sweden

Re: Fix to Fibonacci Heap library (version 2)

Post by Zuu »

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.
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
Post Reply

Return to “OpenTTD AIs and Game Scripts”

Who is online

Users browsing this forum: No registered users and 35 guests