[patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

EarthlingKira
Engineer
Engineer
Posts: 17
Joined: 11 Jan 2018 15:19
Location: Solingen (Germany)

[patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by EarthlingKira » 12 Jan 2018 19:31

While playing OpenTTD since years the PAX amount bugged me. Small villages always seemed to be fine and I was able to serve them properly with buses but after a short while the PAX numbers figuratively exploded and instead of 2 buses I needed like 50 (and I'm only talking about a small city now, big cities are absolutely ludicrous).

Then I've patched OpenTTD myself in the past to halve the passenger generation, but then I noticed that small villages are no longer fun. So I had a patch in the past where I checked t->cache.population if it was below 300, that somewhat fixed my problem.


*BUT* - here comes the plot twist.


Passenger and mail cargo generation was and is broken in OpenTTD!


Let me show you one screenshot first where I've tried to find good examples of the bug in-game:
Screenshot_20180110_214532.png
Screenshot showing the magnitude of the bug
(315.86 KiB) Not downloaded yet
Sentbridge has 800 citizens while Slonnley has 269. We would expect Sentbridge to have about three times as many passengers (800 / 269), but in reality it has 20 times as many!

Why is this?

Code: Select all

if (GB(r, 0, 8) < hs->population) {
    uint amt = GB(r, 0, 8) / 8 + 1;

This is the code to generate the amount of passengers. It uses the house population twice and accidently causes quadratic growth of generated passenger amount!

In the example Slonnley has houses with mostly 13 and 30 inhabitants while big cities after some game-time have mostly houses with up to 180 inhabitants.

We would expect that a house with 30 inhabitants generates about 2.3 times (30/13) as many PAX as the house with 13 inhabitants.

And finally we would expect that a house with 180 inhabitants generates 13.85 times as many PAX as the house with 13 inhabitants (180/13) and 6 times (180/13) as many PAX as the house with 30 inhabitants.

Right?


Now let me show you what really happens when you put these numbers into the algorithm:

13 inhabitants = 13/256 chance to generate 1-2 PAX (minimum: floor(0/8) + 1, maximum: floor(12/8) + 1)
=> a 13-inhabitant-house generates 0.076 PAX on average every call.


Now our expectation for a 30-inhabitant-house is 0.175 (0.076 * 30 / 13) PAX -- let's see:

30 inhabitants = 30/256 chance to generate 1-4 PAX (minimum: floor(0/8) + 1, maximum: floor(29/8) + 1)
=> a 30-inhabitant-house generates 0.293 PAX on average every call. This is nearly the double our expectation!


Now our expectation for a 180-inhabitant-house is 1.052 PAX based on 13-inhabitant-house (0.076 * 180 / 13) and 1.758 PAX based on the already higher 30-inhabitant-house (0.293 * 180 / 30) -- let's see:


180 inhabitants = 180/256 chance to generate 1-23 PAX (minimum: floor(0/8) + 1, maximum: floor(180/8) + 1)
=> a 180-inhabitant-house generates 8.438 PAX on average every call. This is 8 times higher than expected based on 13-inhabitant-house and 4.8 times higher than expected based on 30-inhabitant-house



CONCLUSION

A house with 14 times as many inhabitants (180:13) generates 111 times as many PAX and mail!!


patches in next post

kind regards,
Kira
Last edited by EarthlingKira on 13 Jan 2018 12:19, edited 7 times in total.

EarthlingKira
Engineer
Engineer
Posts: 17
Joined: 11 Jan 2018 15:19
Location: Solingen (Germany)

Re: [PATCH] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by EarthlingKira » 12 Jan 2018 19:34

(Patches tested on r27962)


Since the PAX and mail generation was quadratic it was not easy to decide on the proper algorithm, so I've created 3 patches (based on 32-, 64-, and 128-inhabitant-houses). All patches fix the quadratic growth and all of them make sure that the PAX and mail growth is linear to the city size.

Basically the effect of the patches is that it makes small villages (much) more worthwhile while decreasing the insane profit and transportation requirements for bigger cities.
Attachments
fix_pax_and_mail_generation_based_on_small_cities_r27962.patch
Fixed algorithm based on 32-inhabitant-houses
(697 Bytes) Downloaded 87 times
fix_pax_and_mail_generation_based_on_medium_cities_r27962.patch
Fixed algorithm based on 64-inhabitant-houses
(697 Bytes) Downloaded 99 times
fix_pax_and_mail_generation_based_on_big_cities_r27962.patch
Fixed algorithm based on 128-inhabitant-houses
(697 Bytes) Downloaded 73 times
Last edited by EarthlingKira on 12 Jan 2018 20:12, edited 4 times in total.

frosch
OpenTTD Developer
OpenTTD Developer
Posts: 979
Joined: 20 Dec 2006 13:31
Location: Aschaffenburg

Re: [PATCH] Passenger and Mail cargo amount is broken in OpenTTD (accidental exponential growth!) - patch for r27962

Post by frosch » 12 Jan 2018 19:54

The generation is quadratic, not exponential.
⢇⡸⢸⠢⡇⡇⢎⡁⢎⡱⢸⡱⢸⣭⠀⢸⢜⢸⢸⣀⢸⣀⢸⣭⢸⡱⠀⢰⠭⡆⣫⠰⣉⢸⢸⠀⢰⠭⡆⡯⡆⢹⠁⠀⢐⠰⡁

EarthlingKira
Engineer
Engineer
Posts: 17
Joined: 11 Jan 2018 15:19
Location: Solingen (Germany)

Re: [PATCH] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by EarthlingKira » 12 Jan 2018 19:56

frosch wrote:The generation is quadratic, not exponential.
You are technically right, it's "only" quadratic :P I've changed the term, but of course it doesn't change the observed values

EarthlingKira
Engineer
Engineer
Posts: 17
Joined: 11 Jan 2018 15:19
Location: Solingen (Germany)

Re: [PATCH] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by EarthlingKira » 13 Jan 2018 11:23

There were 2 comments on the IRC channel yesterday, I would like to reply to them.

<frosch123> well, it's like that in ottd 0.1, so most likely original ttd behaviour
You are right, I just checked it, original TTDX also seems to have quadratic growth on a short comparison between cities with low-population houses and big-population houses. But I already hated it in the original game :D
<blathijs> Sounds like it might be by design too, linear growth is probably boring. And bigger towns also generate more movement per resident, I'd expect, since people are more used to moving around.
The problem I have is the following: Passenger generation does not follow population count of cities at all.

In case you still want to have a bigger growth for cities and bigger difference between skyscrapers and small houses I would propose that we still change to a linear algorithm but we should rather change the houses. E.g. change the 13-inhabitant-house to be a 5-inhabitant-house and the 30-inhabitant-house to be a 10-inhabitant-house... This would then mean that bigger houses still have a much larger PAX generation but the population count of the city is more correct ;-)

User avatar
fonso
President
President
Posts: 945
Joined: 13 Oct 2007 08:28

Re: [PATCH] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by fonso » 13 Jan 2018 11:36

Brilliant. An equivalent piece of code was already in r1 from Aug 9, 2004, titled "(svn r1) Import of revision 975 of old (crashed) SVN"

Code: Select all

    if ( (byte)r < _housetype_population[house] ) {
        uint amt = ((byte)r >> 3) + 1, moved;
So, was this intentional? Was it already in TTD? Can we somehow get to the contents of the "old (crashed) SVN" to figure that out? - The word "crashed" sounds discouraging, but maybe someone has an archive somewhere ...

Edit: Oops someone was faster to comment
The guy on the picture is not me, it's Alonso.

EarthlingKira
Engineer
Engineer
Posts: 17
Joined: 11 Jan 2018 15:19
Location: Solingen (Germany)

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by EarthlingKira » 13 Jan 2018 11:46

fonso wrote:So, was this intentional? Was it already in TTD?
I just had a really really short look at dosbox with TTDX, so I'm not sure if it was the same in TTD. The small town actually seemed to produce more passengers than in OpenTTD... But the PAX generation still didn't seem linear. So I'm not sure if it's really the same quadratic algorithm for houses. And I was only in year 1950, so I'm not sure about the even bigger houses starting from 1975~

The big question though: Even if there was exactly the same algorithm in TTDX, was it actually intentional? :D Because I can see the rationale for the code, this seems like a micro-optimization... If the random value is less than the population size you can also use it for getting the generated amount without needing to have a second if-clause and without additional calculations. Because otherwise you would've needed to do a modulo calculation or use two different random numbers...

McZapkie
Tycoon
Tycoon
Posts: 1175
Joined: 18 Jan 2014 18:10

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by McZapkie » 13 Jan 2018 13:04

JGR patch pack already include town generation patch: viewtopic.php?t=46399 which allow to adjust exponent value using 0.1 increments, so you can have for example passenger/mail production proportional to residents^1.9 instead of original residents^2 (or opposite, if someone want to have zilions of passengers).
I strongly recommend to insert this simply patch into the trunk. Default pass/mail generation is usually overpowered, and in case of cargodist, even annoying, and there is no way to prevent it by game settings.
My experimental openTTD server: 149.156.194.203:3979 non-standard client, now testing: JGRPP http://tiny.pl/ggnch
Projects: Reproducible Map Generation patch, NewGRFs: Manpower industries, PolTrams, Polroad, 600mm narrow gauge, preindustrial houses, wired, ECS industry extension, V4 CEE train set.
Addicted to freeciv longturn.

EarthlingKira
Engineer
Engineer
Posts: 17
Joined: 11 Jan 2018 15:19
Location: Solingen (Germany)

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by EarthlingKira » 13 Jan 2018 13:18

McZapkie wrote:JGR patch pack already include town generation patch: viewtopic.php?t=46399 which allow to adjust exponent value using 0.1 increments, so you can have for example passenger/mail production proportional to residents^1.9 instead of original residents^2
No, that patch does not fix it! I've found that patch beforehand and that patch neither fixes nor changes the quadratic PAX generation!

What it actually does: it uses the same broken quadratic PAX (and mail) algorithm and only applies the factor *afterwards*. So when you use that patch to reduce PAX amount of big cities your small villages are even more worthless than in vanilla :cry:


PS: Same is true for JGR's patch pack, it also does not fix the quadratic algorithm, see:

Code: Select all

if (GB(r, 0, 8) < hs->population) {
    uint amt = GB(r, 0, 8) / 8 + 1;
 
-    if (EconomyIsInRecession()) amt = (amt + 1) >> 1;
-    t->supplied[CT_PASSENGERS].new_max += amt;
-    t->supplied[CT_PASSENGERS].new_act += MoveGoodsToStation(CT_PASSENGERS, amt, ST_TOWN, t->index, stations.GetStations());
+    TownGenerateCargo(t, CT_PASSENGERS, amt, stations, true);

The patch applies the factor afterwards on the generated PAX and mail amount but does not touch the chance to generate cargo at all.

This means the effect is completely different..


The problem is not the amount on its own, the problem is that a house with double population has double the chance to generate cargo and the amount is doubled... And those patches only apply a factor to the multiplied amount but the chance to generate amount is still multiplied as before.


Calculation example for the mentioned patches, let's say we use cf = -1 (which is supposed to halve the generated amount)

house with 30 inhabitants:
30/256 chance to generate 1 to 2 PAX (former maximum of 4 was halved by the other patch) = 0.176 PAX on average

house with 180 inhabitants:
180/256 chance to generate 1 to 12 (former maximum of 23 was halved by the other patch) = 4.57 PAX on average (expected would've been 1.056 PAX ((180/30) * 0.176)


So you see even with these other patches the quadratic growth is not fixed, only the magnitude is somewhat reduced



rgds, Kira

McZapkie
Tycoon
Tycoon
Posts: 1175
Joined: 18 Jan 2014 18:10

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by McZapkie » 13 Jan 2018 16:13

EarthlingKira wrote: No, that patch does not fix it! I've found that patch beforehand and that patch neither fixes nor changes the quadratic PAX generation!
What it actually does: it uses the same broken quadratic PAX (and mail) algorithm and only applies the factor *afterwards*.
Well, you are right, description of this patch was ambiguous, anyway I was happy using this.
Any patch which can change generated pass/mail amount is welcome.
By the way, I'm not sure if quadratic model is bad at all, because vehicles speed*capacity grow non-linearly.
the best solution is to have amplitude and exponent both scalable.
My experimental openTTD server: 149.156.194.203:3979 non-standard client, now testing: JGRPP http://tiny.pl/ggnch
Projects: Reproducible Map Generation patch, NewGRFs: Manpower industries, PolTrams, Polroad, 600mm narrow gauge, preindustrial houses, wired, ECS industry extension, V4 CEE train set.
Addicted to freeciv longturn.

EarthlingKira
Engineer
Engineer
Posts: 17
Joined: 11 Jan 2018 15:19
Location: Solingen (Germany)

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by EarthlingKira » 13 Jan 2018 16:19

McZapkie wrote:the best solution is to have amplitude and exponent both scalable.
That would require a completely new formula / algorithm. Because in vanilla OpenTTD the house size is used twice for chance and again for amount.

User avatar
supermop
Tycoon
Tycoon
Posts: 1042
Joined: 21 Feb 2010 00:15
Location: Fitzroy North - 96

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by supermop » 13 Jan 2018 16:44

Neat work! This certainly seems like it could be helpful, particularly with town sets that provide fairly dense buildings for large cities. I know that Swedish or Japanese Houses can get to a point where the passenger demand starts to make a game no longer fun beyond a certain size.

I could understand a non-linear growth, after all, the center of a large city would presumably have more economic activity per capita, and thus each resident there would make more trips than residents in small villages. However, the effect seems out of hand in game, as you have discovered. Something like "big house produces 10-50% more passengers per capita" would be more fun than 200-800% more.

EarthlingKira
Engineer
Engineer
Posts: 17
Joined: 11 Jan 2018 15:19
Location: Solingen (Germany)

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by EarthlingKira » 13 Jan 2018 16:49

supermop wrote:Something like "big house produces 10-50% more passengers per capita" would be more fun than 200-800% more.
Yes, in theory I understand this as well. But consider this: a house with 220 inhabitants already has ~17 times as many PAX per tile compared to a house with 13 inhabitants. Isn't that already a big enough change? :shock:


Another approach would be to extend the NewGRF specification so that they offer 2 values: Inhabitants (which are added to city size) and passenger generation rate. This would fix many issues at the same time. On the one hand you could still create houses with massive passenger generation and on the other hand buildings like a soccer arena don't need to increase the citizen count to generate many passengers :3

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: [PATCH] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by ic111 » 22 Jan 2018 08:44

EarthlingKira wrote:There were 2 comments on the IRC channel yesterday, I would like to reply to them.

<frosch123> well, it's like that in ottd 0.1, so most likely original ttd behaviour
You are right, I just checked it, original TTDX also seems to have quadratic growth on a short comparison between cities with low-population houses and big-population houses. But I already hated it in the original game :D
But wasn't there a limit concerning size of cities of between 4000 and 5000 inhabitants in the very old times?

Maybe I'm wrong, but my feeling is that there was something like that...

Of course, if such a limit gets removed, a quadratic function tends to do things that originally weren't intended...

Eddi
Tycoon
Tycoon
Posts: 7369
Joined: 17 Jan 2007 00:14

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by Eddi » 26 Jan 2018 20:50

i don't think there ever was such a limit.

but many house newgrfs tended towards denser houses, making the problem worse.
You might not exactly be interested in Ferion, but if you are, have fun :)

User avatar
jfs
Route Supervisor
Route Supervisor
Posts: 500
Joined: 08 Jan 2003 23:09
Location: Denmark

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by jfs » 07 Nov 2018 16:59

Looking at this again, I think a new approach might be available. Current master has had a branch new map array extension added, 16 bits extra per tile. This is only used additional railtypes right now, unused for houses.

What if the two bytes were used as cargo generation counters for houses? Every TileLoop visit to a house it increments the cargo production counter by the house population. A random value is then tested against the counter, is the random is less, then the house generates random/8 cargo and the counter resets to 0. If the counter overflows during the increment, the house always generates cargo based on random/8.
I think that should solve the quadratic issue, without forcing the player/game admin to make a choice about house generation level.



Edit: After a bit of convincing the counting in the map array is a bad/pointless idea, I developed another idea that should instead produce a normal distribution of cargo produced, rather than a linear/equal chance of cargo amount.
I unified the three patches above, along with my own idea, and made a patch here which also adds a new game setting to control how town cargo is generated: https://github.com/OpenTTD/OpenTTD/pull/6965

EarthlingKira
Engineer
Engineer
Posts: 17
Joined: 11 Jan 2018 15:19
Location: Solingen (Germany)

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by EarthlingKira » 15 Feb 2019 22:20

jfs wrote:Looking at this again, I think a new approach might be available. Current master has had a branch new map array extension added, 16 bits extra per tile. This is only used additional railtypes right now, unused for houses.

What if the two bytes were used as cargo generation counters for houses? Every TileLoop visit to a house it increments the cargo production counter by the house population. A random value is then tested against the counter, is the random is less, then the house generates random/8 cargo and the counter resets to 0. If the counter overflows during the increment, the house always generates cargo based on random/8.
I think that should solve the quadratic issue, without forcing the player/game admin to make a choice about house generation level.



Edit: After a bit of convincing the counting in the map array is a bad/pointless idea, I developed another idea that should instead produce a normal distribution of cargo produced, rather than a linear/equal chance of cargo amount.
I unified the three patches above, along with my own idea, and made a patch here which also adds a new game setting to control how town cargo is generated: https://github.com/OpenTTD/OpenTTD/pull/6965

I love seeing the discussion on the pull request and that my "hack" using some randomness to decrease the amount was used :) Since we can't transport limbs this was tbh the best solution I found without doing super big refactorings everywhere and it's awesome that you agree :)

User avatar
TrainLover
Engineer
Engineer
Posts: 87
Joined: 01 Jul 2015 15:03

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by TrainLover » 18 Feb 2019 21:19

Doesn't trunk OpenTTD have a patch which makes the generation of cargo different? For example, you could go and make the generation of cargo quadratic, or you could make it linear, or etc.

Eddi
Tycoon
Tycoon
Posts: 7369
Joined: 17 Jan 2007 00:14

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by Eddi » 19 Feb 2019 01:04

TrainLover wrote:Doesn't trunk OpenTTD have a patch
no. trunk is by definition "without any patches". you either have trunk, or a patch, never both.
You might not exactly be interested in Ferion, but if you are, have fun :)

User avatar
TrainLover
Engineer
Engineer
Posts: 87
Joined: 01 Jul 2015 15:03

Re: [patch] Passenger and Mail cargo amount is broken in OpenTTD (accidental quadratic growth!) - patch for r27962

Post by TrainLover » 19 Feb 2019 22:48

Eddi wrote:
TrainLover wrote:Doesn't trunk OpenTTD have a patch
no. trunk is by definition "without any patches". you either have trunk, or a patch, never both.
I thought trunk has included patches, like cargodist.

Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: Baidu [Spider] and 2 guests