Patch: Maximum Subsidy Distance

[wleader]

Ok, I've been playing with the latest trunk code and I've really like playing with the towns set to very low. I did notice that the subsidy offers were extremely rare though on this setting. So after some digging I have found that in the SubsidyMonthlyHandler function in economy.cpp there is a %25 chance of a subsidy being offered each month, however even if it hits the %25 chance, the distance between to and from must be less than 70. My trouble is that on the very low town setting few things are as close as 70 tiles so few subsidies get offered. Additionally this 70 is a hard coded constant, so I have created my second patch.

This patch makes the maximum subsidy route distance a configurable variable. 70 is the original value, so using it is the same as not using this patch. Setting the value to 0 effectively disables subsidies. Setting it as high as 4096 allows potential subsidies from anywhere to anywhere on a 2048 x 2048 map.

FYI: MagicBuzz already has a patch similar to this: http://www.tt-forums.net/viewtopic.php?t=29578

[athanasios]

That one has more details than yours I suppose. Nevertheless something like this should make it into the trunk as soon as possible. (Lack of it actually alters the original game behavior in larger maps. It is a MUST, not an addition.)

[wleader]

I do agree. It might not need to be a configurable patch. It could just be a function of map size. larger maps allow a larger distance, smaller maps a smaller distance. I didn't even really notice it as a problem until I started playing with very low towns, but yes, you are right. A larger map will have less frequent subsidy offers.

[wleader]

After some play testing tonight, to anyone checking this out, I wouldn't recommend setting the distance much higher than 200, Its easy to nab subsidies for things that can be sent by air when they are real far, but if its too far and can't be sent by air, Its just about impossible, (unless the tracks are already there, But even then it can take nearly they full year to get a load and get to the destination.)

[belugas]

I'm wondering if it would not be easier to simply rescale the distance, based on the new size of the map, knowing that the 256*256 was the previous biggest size map.
Doing so will eliminate the need of YET another patch option...

[fabca2]

I'm wondering if it would not be easier to simply rescale the distance, based on the new size of the map, knowing that the 256*256 was the previous biggest size map.
Doing so will eliminate the need of YET another patch option...

very good idea,
a new option for that is not needed I think.
take this formula :
new_subsid_max=sqr(map_size_x * map_size_y) / 3.7

That gives for a 256x256 the distance of 69 (near of original 70)
and for example a 1024x512 => 195
for 2048x2048 => 553

[jklamo]

very good idea,
a new option for that is not needed I think.
take this formula :
new_subsid_max=sqr(map_size_x * map_size_y) / 3.7

That gives for a 256x256 the distance of 69 (near of original 70)
and for example a 1024x512 => 195
for 2048x2048 => 553

nice idea, what about age of subsidy? same way formula?
subsidy_age=sqr(map_size_x * map_size_y) / 21

app. 12.2 for 256x256 (original 12)
app. 48.8 for 1024x1024
app. 97.5 for 2048x2048

[wleader]

You have to be carefull though, The thing to remember is that the code that generates a subsidy runs each month. First there is a 1 in 4 chance that it will run. Then It has to find a route (selected randomly from all towns and industries). Then the randomly selected route must be within a certain distance. Currently the distance is calculated as a Manhattan distance (Change in X plus Change in Y).

Now if we consider the original max map size of 256x256, and the number of towns and industries on the 'normal' setting. (on a quick generate random I got about 30 towns, about 50 industries.) From this we would need to create a list of compatible to and from locations and exclude any that were greater than 70. So just some rough estimates that means there are about 900 passenger routes, and 2500 industrial routes. Toss out distance I am going to estimate that maybe 10 percent of the towns routes are close enough to be a route (I'd think Much Lower.) So maybe 90 town routes. Now for inustry, I'd guess that only 1 in 10 are going to have compatible cargo, so that cuts it down to 250, Again 1 in 10 for distance an that makes it 25 industrial routes. This means that only about 120 routes out of a possible 3400 are able to be subsidy routes.

Yet another thing to consider is that the distance of 70 was the same for every map size, so a 64x64 map and a 256x256 map both used 70. The result is that a subsidy offer is much more likely on a smaller map than a larger map because when randomly picking to and from, the odds of them being less than 70 tiles away is much greater on a smaller map.

This means that in order to create a system where gameplay is uneffected, you have to find the odds of a subsidy on each size map, and create a curve, then spread that curve out over the new larger maps, and come up with.

All this doesn't even start to address the issue of number of towns and industries. How are the chances different when there is a high towns and low industries, or any other combination? It might be better to leave things as they are have lower odds of subsidy on larger maps. Subsidies become less critical when players are more spread out and compete less.

The more I think about it the more I come to think that letting it be configureable is is simple enough, and that any other solution if we want to stick to ideals of not cluttering the patches window, and not altering gameplay is going to require a lot more code and effort than turning a constant into a variable like I have done.

I'd like to export some real data from game ram and go over this again. Shouldn't be to hard to do some analysis with spreadsheets.

[wleader]

After having done quite a bit of research into how OpenTTD generates maps I have been able to come up with some useful information. To keep matters simple I am confining the search for knowledge to the temperate map, and the map state at the time of generation. Additionally I will be using all default settings for patches. Obviously the progress of the game will affect the game state.

First off is a nice big table that will show how many towns and each given industry can be found on a randomly generated map with the various number of towns and number of industry settings (High, Medium, Low, Etc.) You should find that table attached as an HTML file (OpenTTDPredictors.htm).

Now with that information at hand, we can start to determine just what the chances of a subsidy being offered really are. First off let’s look at the SubsidyMonthlyHandler function in economy.cpp around line 1084. This function has code to loop 1000 times looking for a subsidy (after the %25 chance each month.) This 1000 iteration loop is vital to the success of finding a subsidy. Mainly because the odds are quite small, but with enough attempts, the chance of a single success increases. Additionally since it searches for both a passenger and a cargo route inside each run of the loop, the number of searches performed is doubled, again increasing the chance of a successful find. It’s been my experience that with a route distance correction, once they code gets past the initial 25% chance, it will find a subsidy (at least early in the game when there are still unconnected routes.)

To start with, let’s consider passenger routes. Most players will tell you that passenger subsidies are more likely simply from personal experience. The main reason why this is the case is that Towns don't have to match cargo types. They only have to match size (population of 400) and distance (currently 70 tiles.) Matching population requirements does not depend on map size so we can ignore that. Additionally they can not have more than %42 of their cargo being transported. The only thing that changes with map size is the 70 tiles distance which we will address in a minute.

Now we can also consider the odds of finding an industry match. If we recognize that the proportions of industries are the same across all map sizes, we can safely say that the chance of any two randomly selected industries having matching cargo is the same across all map sizes. Additionally the percentage of cargo already being transferred is also independent of map size. There is another requirement for when some cargo is delivered to a town. The Town must have a population of 900. Again this is not affected by map size. So like passenger routes, the only part of the route selection process that is affected by map size is the 70 tile distance requirement.

So how is the distance requirement affected by map size? It goes like this. For any given point on the map there are a fixed number of tiles that are less than 70 tiles away. If I have calculated correctly that number is 9660. Because the distance of 70 is fixed across all map sizes, the number of tiles in range is fixed at all map sizes. However the total number of tiles changes. Lets take a look at what is considered normal, the 256 x 256 map. If we say that there are 65536 tiles in a 256 x 256 map, and 9660 tiles that are within a 70 range of a given location, then we can say that the chance of any two locations being within 70 tiles of each other on this map is 65536 / 9660 = .147 or about 15%. If we assume that we want to have the same chances of a route being in range on a larger map, then as the map size changes, we must change the distance to maintain that ratio.

There are a couple of options already available to us. We could ScaleByMapSize (see Map.cpp line 106), but that makes the range far too long on larger maps. We could leave the value fixed at 70, but the value is far too small on larger maps, and far too big on smaller maps. I also considered scaling by 1D (See Map.cpp line 121) but that too produces less than desired results.

I suggest a new formula to calculate map size. In pseudo code: return Sqrt(( MapSize() * .15) / 2); This formula generated a subsidy distance that causes there to always be a 15% chance that any two locations on a map will be in range of one another. The only down side I see to this method is that on the very largest of maps (2048 x 2048) the range is as high as 560 which is a very long run, and will be difficult to complete in the early game. (On a side note I feel like that does make things more challenging since the player might have to decide if a subsidy is really worth it or if they should let it go. Currently almost all subsidy offers are worth taking.) To illustrate the differences in the methods, I have created a table and attached it to this message (SubsidyDistanceCalculations.htm).

The only thing left to address is preserving the game play on smaller maps (smaller than 256 x 256). If we always used the new distance calculation for smaller maps, the offers for subsidies would be reduced. In which case we can use whichever is greater the new calculation or 70. This will allow more subsidy offers on larger maps, and preserve game play on smaller maps.

At this point I've created a patch to test this. all the changes are in economy.cpp and requires no patch options. However I did need to include <cmath> which is probably a bad idea for portability reasons. It compiles fine for me on MSVC++ Express 2005. Hopefully a more experienced programmer can help me correct any coding no-no’s I have made.

[fabca2]

After having done quite a bit of research...

Wouha!... you spent how many days to try/found that ?!

I mean you validated pythagore principe... I don't want to offence you, but, yes no need to build a patch to discover the formulas must be sqrt-based, as the "space" here is in 2D.

ok, your formulas is : Range = Sqrt((MapSize*0.15)/2) = sqr(x*y)/3.6515
Mine was Range = Sqrt(x*y)/3.7

Your results gives for 512x1024 => 198 (mine 195)
and 2048x2048 => 560 (mine 553)

I don't see a lot of difference.

By the way : thank you to "validate" my (obvious) formulas.

Ho, and for small maps, just use function max() to avoid tiny range :
range = max(70,sqr(x*y)/3.7);

But a good question is the subsidy_age...
it's not so easy... I would think more about log based formulas
giving more time to exploit the subsidy is a good idea (long distance : more time to travel) but it should not be linear...

[DaleStan]

the formulas must be sqrt-based, as the "space" here is in 2D.

Not true. Many of TTD's formulas are based on the Manhattan distance (|Δx| + |Δy|) not the Euclidean distance.

[wleader]

Wouha!... you spent how many days to try/found that ?!

By that I mean "getting more familiar with the code." I've only been working with OpenTTD code for a few weeks in my spare time. I'm still a newbie what with my whopping 18 posts in the forum.

The majority of the time was spent discovering that the numbers of industries and town sizes was a fixed ratio on any map size. This was important for me to learn so I could say the chance of matching cargo types and town sizes was the same on all sizes so we could throw it out of the discussion and concentrate on route distance. Someone more familiar with the code might have skipped that step.

ok, your formulas is : Range = Sqrt((MapSize*0.15)/2) = sqr(x*y)/3.6515
Mine was Range = Sqrt(x*y)/3.7

Yup, roughly the same. I made my formula the way I did because the MapSize() function was handy, and 0.15 (15%) was a separate value I could easily tweak while testing so I would be able to know what I was changing.

But a good question is the subsidy_age...
it's not so easy... I would think more about log based formulas
giving more time to exploit the subsidy is a good idea (long distance : more time to travel) but it should not be linear...

Why not base it off the actual distance of the route? Max(12,( RouteDistance / 70 * 12)). This would mean for really long hauls Up to 570 on 2048 x 2048 maps, then they could take up to 8 years to build and run the route. On second thought that seems kind of long, so it seams your right about it not being linear. Whatever we come up with, It may need a good bit of play testing to get it right (like we need more excuses to play.)

The tricky part I suppose would be coming up with a way to do this without modifying the Subsidy structure which I assume would affect the save game files. Not impossible, but not as easy as adding a member to the structure.

Not true. Many of TTD's formulas are based on the Manhattan distance (|Δx| + |Δy|) not the Euclidean distance.

Most of these distances are Manhattan because you can't actually travel diagonally on the grid. Diagonals are actually zig-zag so Manhattan works just fine for distance because the distance is the sum of the legs. vehicles never truly travel a hypotenuse. What we are dealing with here is the number of tiles within a boundary, an area and not a line. As with area calculations the math would deal with squares and roots.

[chrissicom]

I'm wondering if it would not be easier to simply rescale the distance, based on the new size of the map, knowing that the 256*256 was the previous biggest size map.
Doing so will eliminate the need of YET another patch option...

very good idea,
a new option for that is not needed I think.
take this formula :
new_subsid_max=sqr(map_size_x * map_size_y) / 3.7

That gives for a 256x256 the distance of 69 (near of original 70)
and for example a 1024x512 => 195
for 2048x2048 => 553

I don't think it's that simple. It would only work this way when the 2048x2048 maps contains the same amount of towns, i.e. the distances between towns are larger on average. But when you play with Towns: High for example you would probably get way too many subsidies.

[Korenn]

I'm wondering if it would not be easier to simply rescale the distance, based on the new size of the map, knowing that the 256*256 was the previous biggest size map.
Doing so will eliminate the need of YET another patch option...

very good idea,
a new option for that is not needed I think.
take this formula :
new_subsid_max=sqr(map_size_x * map_size_y) / 3.7

That gives for a 256x256 the distance of 69 (near of original 70)
and for example a 1024x512 => 195
for 2048x2048 => 553

I don't think it's that simple. It would only work this way when the 2048x2048 maps contains the same amount of towns, i.e. the distances between towns are larger on average. But when you play with Towns: High for example you would probably get way too many subsidies.

there is always a 25% chance per month of getting a subsidy, the only reason there were so few subsidies on large maps is because the game simply couldn't find one. So there will not be more subsidies than was intended in the original game.

[wleader]

I don't think it's that simple. It would only work this way when the 2048x2048 maps contains the same amount of towns, i.e. the distances between towns are larger on average. But when you play with Towns: High for example you would probably get way too many subsidies.

there is always a 25% chance per month of getting a subsidy, the only reason there were so few subsidies on large maps is because the game simply couldn't find one. So there will not be more subsidies than was intended in the original game.

If you look at the tables I posted earlier, the number of towns and industries does scale with the map size. So the density of the towns is the same. This means the average distance to the nearest town is the same, But the subsidy code randomly chooses two towns. The average distance between any two towns on a large map is definately not the same. So Korenn is right in that there is always a 25% chance per month of finding a subsidy. Clearly the origional code was written to be unlikey to fail. However changing map sizes, and density has made the chance of failure much more likely. The code change being discussed here reduces the chance of failure, but the base odds of 25% remains unchanged.

Even then there is still at limit on the total number of subsidies pegged at MAX_PLAYERS or 8. So even with easier to find subsidies you'll never see more than 8 in total (on offer or in effect).

So to sum up my points:
The problem is that larger maps currently have a lower than normal number of subsidy offers. We are trying to not change the frequency of subsidies, we want to correct the frequency of subsidies on larger maps. We are willing to allow a longer distance for routes, but since larger maps generally means longer routes anyway I personally do not see this as a problem.

[MagicBuzz]

After some play testing tonight, to anyone checking this out, I wouldn't recommend setting the distance much higher than 200, Its easy to nab subsidies for things that can be sent by air when they are real far, but if its too far and can't be sent by air, Its just about impossible, (unless the tracks are already there, But even then it can take nearly they full year to get a load and get to the destination.)

My patch (but it should be deprecated) was fixing this issue, by changing the subsidy duration according to the distance. By this way, very long subsidies routes were available for up to 48 months instead of 12. The rewards were the same, and were during a longer time to help the player getting the subsidie advantage for a longer time (48 months again).

PS : This patch was also fixing the mail subsidy : for not default range, I added a 25% chance of generating a mail subsidy.

[wleader]

Updated the patch to the current trunk.

[belugas]

Code: Select all

+#include <cmath>

Big nono...
I know it's easier that way, but all the calculations are done with integers (and others alike), since float handling is not garanteed to be the same on all platforms.

[wleader]

Code: Select all

+#include <cmath>

Big nono...
I know it's easier that way, but all the calculations are done with integers (and others alike), since float handling is not garanteed to be the same on all platforms.

I would happily change it if I had a clue. Do you have a clue for me?

[NukeBuster]

Try this:

http://www.homeschoolmath.net/teaching/ ... orithm.php

Do make it a function somewhere if it isn't already available.