OpenTTD

Tasklist

FS#3637 - Second highest competing station rating doubly penalized when distributing cargo

Attached to Project: OpenTTD
Opened by Clarence Risher (sparr) - Monday, 22 February 2010, 19:39 GMT
Last edited by Remko Bijker (Rubidium) - Tuesday, 28 September 2010, 22:00 GMT
Type Bug
Category Core
Status Closed
Assigned To No-one
Operating System All
Severity High
Priority Normal
Reported Version trunk
Due in Version 1.1.0
Due Date Undecided
Percent Complete 100%
Votes 4
  • Fugas (Fugas) (2010-02-22)
  • xi (xi) (2010-02-22)
  • Clarence Risher (sparr) (2010-02-22)
  • Radium Mercury (Radium) (2010-02-22)
Private No

Details

In the current MoveGoodsToStation calculation, the penalty adjustment (effectively dividing the rating in half) to the second highest station rating is applied too broadly. It correctly (as documented, but not quite desirably, the subject of another feature request) affects the split of goods available to the two stations. However it remains in effect when the amount of wasted goods are calculated for the second station, which seems like an undesired and unanticipated side effect.

By way of an example, simplified to % instead of internal n/255ths, two stations have ratings of 80% and 60%. 100 goods are split between them with the first being assigned (100+1)*80/(80+(60/2))=73 of them and the second the remaining 27. The first then actually gets 73*80/100+1=59 goods. The bug occurs when the second gets 27*(60/2)/100+1=9 goods instead of 27*60/100+1=17, strangely increasing its internal post-split wastage from the expected 40% to around 70%.

Attached is a patch that moves the penalty to the correct location.
This task depends upon

Closed by  Remko Bijker (Rubidium)
Tuesday, 28 September 2010, 22:00 GMT
Reason for closing:  Fixed
Additional comments about closing:  In r20857
Comment by Clarence Risher (sparr) - Monday, 22 February 2010, 20:10 GMT
This patch fixes the style issue of ">>" vs " >> "
Comment by Clarence Risher (sparr) - Monday, 22 February 2010, 21:07 GMT
In OpenTTD two competing stations with ratings of 82% result in 71% of the goods from the industry being transported. In TTD (for Windows), two competing stations with ratings of 80% result in 79% of the goods from the industry being transported. I think this illustrates a disconnect between the design and implementation.
Comment by Remko Bijker (Rubidium) - Friday, 26 February 2010, 14:44 GMT
With your the patch applied the combined 'rating' would become 90%.
Given 'amount' = 255, station rating = 80% -> 204.
t = (204 * (255 + 1)) / (204 + (204 / 2)) = 170
station 1 moves: 170 * 204 / 256 + 1 = 136
amount becomes 119
station 2 moves: 119 * 204 / 256 + 1 = 95
total moved: 136 + 95 = 231 -> 231/255 = 90% moved

So your patch does not behave like TTD.

Now for the 'fun' part with your patch:
Given 'amount' = 255, station rating = 25% -> 64.
t = (64 * (255 + 1)) / (64 + (64 / 2)) = 170
station 1 moves: 170 * 64 / 256 + 1 = 43
amount becomes 212
station 2 moves: 212 * 64 / 256 + 1 = 54
total moved: 43 + 54 = 97 -> 97/255 = 38% moved
Hmm, so the *second* station does get more than the first station. Where's the penalty gone? This happens with all ratings < 50%! So your patch does not give a penalty all the time, i.e. it's comment is at least wrong.

Given 'amount' 255, station ratings 25% and 24% -> 64 and 61
t = (64 * (255 + 1)) / (64 + (61 / 2)) = 174
station 1 moves: 174 * 64 / 256 + 1 = 44
amount becomes 211
station 2 moves: 211 * 61 / 256 + 1 = 51
total moved: 44 + 51 = 95 -> 95/255 = 37% moved
This is even more interesting. Here the *second* station gets more cargo than the first station even though the first station has a higher rating. So the patch actually breaks the 'best station gets most cargo' behaviour!

As you can see at the 'total moved' lines the industry rating gets higher in all cases (except a 100% station rating, i.e. rating 255).
Comment by Clarence Risher (sparr) - Friday, 26 February 2010, 16:23 GMT
Your analysis breaks at "amount becomes 119". The relevant line says "amount -= t;", not "amount -= moved;".

Given 'amount' = 255, station rating = 80% -> 204.
t = (204 * (255 + 1)) / (204 + (204 / 2)) = 170
station 1 moves: 170 * 204 / 256 + 1 = 136
amount becomes 85
station 2 moves: 85 * 204 / 256 + 1 = 68
total moved: 136 + 68 = 204 -> 204/255 = 80% moved

The correction applies to your other examples as well.
Comment by frosch (frosch) - Friday, 26 February 2010, 19:51 GMT
Attached is a TTD (Dos) savegame, you can load both in TTD and OTTD next to each other and unpause. The ratings and transportation percentage match very well. Both can result in 66% transported while both stations have 78% rating (around march 1951).

So please proof your observation.
(application/octet-stream)    trt02.sv1 (181.4 KiB)
Comment by Remko Bijker (Rubidium) - Friday, 26 February 2010, 23:52 GMT
sparr, you're right those numbers are wrong.

Although now the 'real' question becomes. Should we send 'on average' more cargo through than the maximum cargo rating would do in a 1 station case?

With your algorithm/change it would consistently overestimate; for any 'amount'.

With trunk's algorithm it would underestimate for the higher 'amounts' but overestimate with lower 'amounts' (<5). Given that the function is called more more often with lower 'amounts' (amount 1: 25%, amount 2: 14%, amount 3: 9%, amount 4: 7%), so they cancel eachother out over time. Those percentages come from an #openttdcoop savegame over ~1 million calls to the MoveGoodsToStation function).

With your algorithm given 'amount' 2 and equal ratings, station 2 would get occasionally some cargo from rating 209 and lower, with trunk it has a chance from rating 255 and lower. In both cases it's a 50% change, i.e. with even ratings station 2 gets some cargo.

Attached is a spreadsheet to experiment a bit with the numbers. It has an idea for improvement, but I'm not very satisfied with it.


Anyhow... changing this algorithm might increase the amount of generated cargo/passengers and people are already complaining about that. Not quite sure what the best approach is going to be.
Comment by Remko Bijker (Rubidium) - Saturday, 27 February 2010, 16:34 GMT
  • Field changed: Status (New → Confirmed)
But the problem with the cargo distribution to stations is bigger than just this rating issue, so the simple 'fix' doesn't really fix it in all cases. It actually seems to make it worse in some.
Comment by Remko Bijker (Rubidium) - Sunday, 23 May 2010, 18:22 GMT
  • Field changed: Due in Version (Undecided → 1.1.0)
As shown before this is hardly a trivial change, so it needs quite some testing after it's fixed, i.e. not a candidate for the 1.0.x bugfix releases.
Comment by Remko Bijker (Rubidium) - Thursday, 16 September 2010, 16:16 GMT
Could you please test the attached patch, or the binaries at https://devs.openttd.org/~rubidium/fs3637/

I think it needs some real world multiplayer competition game to really test this, right?
Comment by Alexey Torkhov (atorkhov) - Monday, 27 September 2010, 09:25 GMT
Me and V453000 did a test on server that was setup by dihedral. We were picking up of a same industries, station rating was almost the same (+/- 5%) and we got almost equal distribution of cargo in average by graph. So, it this case it works fine, I think.
Comment by Alexey Torkhov (atorkhov) - Monday, 27 September 2010, 10:10 GMT
With this patch it does not give cargo for any station that have rating beyond 3rd. I think this is wrong behaviour if the goal is to have competition.
Also, this means that I can build 2 stations for an industry and nobody else will be able to get cargo from it.
Comment by Remko Bijker (Rubidium) - Monday, 27 September 2010, 10:47 GMT
Previously the third and lower stations didn't get any cargo at all either, and the second did get roughly 75% less cargo than it does now. Sharing the cargo amongst more stations is beyond the scope of this bug; there is another issue about that though.

Loading...