Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Sat Mar 23, 2019 2:08 pm

All times are UTC




Post new topic  Reply to topic  [ 2 posts ] 
Author Message
PostPosted: Sat Mar 24, 2012 8:15 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4549
Location: /home/sweden
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 209 times

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
Top
   
PostPosted: Sun Apr 29, 2012 11:02 am 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4549
Location: /home/sweden
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)


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 2 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000-2019 phpBB Limited

Copyright © Owen Rudge/The Transport Tycoon Forums 2001-2019.
Hosted by Zernebok Hosting.