Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Mon Dec 10, 2018 9:58 am

All times are UTC




Post new topic  Reply to topic  [ 16 posts ] 
Author Message
PostPosted: Fri Jan 12, 2018 7:31 pm 
Offline
Engineer
Engineer

Joined: Thu Jan 11, 2018 3:19 pm
Posts: 15
Location: Solingen (Germany)
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:

Attachment:
File comment: Screenshot showing the magnitude of the bug
Screenshot_20180110_214532.png [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:
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 Sat Jan 13, 2018 12:19 pm, edited 7 times in total.

Top
   
PostPosted: Fri Jan 12, 2018 7:34 pm 
Offline
Engineer
Engineer

Joined: Thu Jan 11, 2018 3:19 pm
Posts: 15
Location: Solingen (Germany)
(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:
File comment: Fixed algorithm based on 32-inhabitant-houses
fix_pax_and_mail_generation_based_on_small_cities_r27962.patch [697 Bytes]
Downloaded 39 times
File comment: Fixed algorithm based on 64-inhabitant-houses
fix_pax_and_mail_generation_based_on_medium_cities_r27962.patch [697 Bytes]
Downloaded 55 times
File comment: Fixed algorithm based on 128-inhabitant-houses
fix_pax_and_mail_generation_based_on_big_cities_r27962.patch [697 Bytes]
Downloaded 34 times


Last edited by EarthlingKira on Fri Jan 12, 2018 8:12 pm, edited 4 times in total.
Top
   
PostPosted: Fri Jan 12, 2018 7:54 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Wed Dec 20, 2006 1:31 pm
Posts: 978
Location: Aschaffenburg
The generation is quadratic, not exponential.

_________________
⢇⡸⢸⠢⡇⡇⢎⡁⢎⡱⢸⡱⢸⣭⠀⢸⢜⢸⢸⣀⢸⣀⢸⣭⢸⡱⠀⢰⠭⡆⣫⠰⣉⢸⢸⠀⢰⠭⡆⡯⡆⢹⠁⠀⢐⠰⡁


Top
   
PostPosted: Fri Jan 12, 2018 7:56 pm 
Offline
Engineer
Engineer

Joined: Thu Jan 11, 2018 3:19 pm
Posts: 15
Location: Solingen (Germany)
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


Top
   
PostPosted: Sat Jan 13, 2018 11:23 am 
Offline
Engineer
Engineer

Joined: Thu Jan 11, 2018 3:19 pm
Posts: 15
Location: Solingen (Germany)
There were 2 comments on the IRC channel yesterday, I would like to reply to them.


Quote:
<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

Quote:
<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 ;-)


Top
   
PostPosted: Sat Jan 13, 2018 11:36 am 
Offline
President
President
User avatar

Joined: Sat Oct 13, 2007 8:28 am
Posts: 945
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:
    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.


Top
   
PostPosted: Sat Jan 13, 2018 11:46 am 
Offline
Engineer
Engineer

Joined: Thu Jan 11, 2018 3:19 pm
Posts: 15
Location: Solingen (Germany)
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...


Top
   
PostPosted: Sat Jan 13, 2018 1:04 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Sat Jan 18, 2014 6:10 pm
Posts: 1083
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.
Addicted to freeciv longturn.


Top
   
PostPosted: Sat Jan 13, 2018 1:18 pm 
Offline
Engineer
Engineer

Joined: Thu Jan 11, 2018 3:19 pm
Posts: 15
Location: Solingen (Germany)
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:
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


Top
   
PostPosted: Sat Jan 13, 2018 4:13 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Sat Jan 18, 2014 6:10 pm
Posts: 1083
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.
Addicted to freeciv longturn.


Top
   
PostPosted: Sat Jan 13, 2018 4:19 pm 
Offline
Engineer
Engineer

Joined: Thu Jan 11, 2018 3:19 pm
Posts: 15
Location: Solingen (Germany)
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.


Top
   
PostPosted: Sat Jan 13, 2018 4:44 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Sun Feb 21, 2010 12:15 am
Posts: 1031
Location: Fitzroy North - 96
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.

_________________
Image
Trolleybi! Trucks and Buses -- Docklands -- Unspooled -- MLSS


Top
   
PostPosted: Sat Jan 13, 2018 4:49 pm 
Offline
Engineer
Engineer

Joined: Thu Jan 11, 2018 3:19 pm
Posts: 15
Location: Solingen (Germany)
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


Top
   
PostPosted: Mon Jan 22, 2018 8:44 am 
Offline
Director
Director

Joined: Tue Jul 17, 2007 5:56 pm
Posts: 608
EarthlingKira wrote:
There were 2 comments on the IRC channel yesterday, I would like to reply to them.


Quote:
<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...


Top
   
PostPosted: Fri Jan 26, 2018 8:50 pm 
Offline
Tycoon
Tycoon

Joined: Wed Jan 17, 2007 12:14 am
Posts: 7226
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 :)


Top
   
PostPosted: Wed Nov 07, 2018 4:59 pm 
Offline
Route Supervisor
Route Supervisor
User avatar

Joined: Wed Jan 08, 2003 11:09 pm
Posts: 386
Location: Denmark
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


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

All times are UTC


Who is online

Users browsing this forum: Google Adsense [Bot] and 4 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-2018 phpBB Limited

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