Re-scaling Simutrans

Topic: Re-scaling Simutrans (Read 35705 times) previous topic - next topic

Re-scaling Simutrans

July 21, 2009, 11:23:54 pm

Abstract

Because this is a long post, it might be helpful to summarise the post for those who do not want to read it all in depth. In short, to make the most out of Simutrans-Experimental features that use the absolute values of journey times (in particular, comfort, catering and journey time tolerance), as well as to make long-distance rail and any sort of aviation viable, it is necessary to use much larger maps and to adjust other aspects of the scale used in Simutrans accordingly, abandoning the 1 tile = 1km rule that has previously obtained, replacing it with something closer to 1 tile = 200m. The advantages of and challenges in doing so are explored further below.

Note: This feature has now been implemented in Simutrans-Experimental version 6.0 (and later). See here for a description of how the feature now works as implemented.

Introduction - why change the scale?

In my work to separate different types of vehicles for different uses (for p****engers: local/rural; inner suburban; outer suburban; and express), as well as testing the new journey time tolerance feature, it has become apparent that the current scale in Simutrans does not work well for such separation. Simutrans (deliberately) has two, inconsistent scales used at once: the graphics scale and the distance scale. In the graphics scale, one tile represents about 40m (in Pak128.Britain, at least - other paksets may vary). Traditionally, in the distance scale, 1 tile represents 1km, or 1,000m.

However, when I first put journey times and average speeds into Simutrans, I realised that the 1km/tile scale was unsatisfactory. Extrapolating from the vehicles' speeds as displayed ****uming 1km/tile meant that, at ordinary speeds, a 'bus journey a few tiles accross a small village would be presumed to take 30-45 minutes. A train ride between two neighbouring towns would be ****umed to take hours. Since I was keen to introduce a system whereby different vehicles had different levels of comfort, and p****engers would tolerate certain comfort levels for only so long, and that I wanted to use realistic time scales for that tolerance, I had to make an alteration to the time scale. At the time, I decided simply to multiply all the times by 30% (the figure is adjustable in simuconf.tab). That gave values much closer to reality.

In version 5.0, I introduced the journey time tolerance feature. This means that p****engers will not travel at all if their journey takes too long. Different p****engers have greatly different journey time tolerances, which is partly random and partly based on how far that they want to go (at default settings, fewer p****engers are generated for longer distance travel), anything from one to twelve hours at default settings. When I tested this feature with the 30% figure and existing saved games, I found that there was an enormous drop-off in the number of p****engers willing to travel, and many previously profitable saved games plunged heavily into loss. After eliminating a few bugs and further testing, I found that the problem was that the journeys were simply being registered as being too long. Further reducing the 30% to 20% made journey times make much more sense relative to the size and position of towns and the size of vehicles.

However, the consequence of this was that, even on what has so far been considered a fairly large map of 512x512 or so, there is little scope for fast, comfortable travel. Express trains would be of limited benefit and aircraft of little use at all. With the 20% multiplier, journey times are based on the ****umption that each tile represents 200m. 512 tiles at 200m is 102.4km, or 64 miles (****uming that 1 mile = 1.6km). Even with the old 30% multiplier, that would still be equivalent to a map side of only 96 miles.

Real-world long distance transport, however, involves much greater distances than that. Even setting entirely aside international aviation that will probably always be beyond what Simutrans can cope with, short-haul aviation is not generally considered worthwhile unless the equivalent land journey takes longer than three hours. To take three hours, a 64 mile journey would have to be undertaken at an average speed of only fractionally over 20mph. That clearly makes aviation entirely pointless on a 512x512 map.

Even taking more generous circumstances: a 1024x1024 (or even 1024x512) map, and long-distance rail travel instead of aviation. There, the longest side would be the equivalent of 128 miles. At fairly lax timings, long-distance trains often average around 75mph (this is the average speed ****umed for the deliberately ponderous Night Riviera sleeper service from London to Cornwall: if they made it any faster, the train would arrive far too early in the morning). High-speed rail of the sort prevalent in continental Europe may well produce average speeds of well over double that. Even ****uming an average speed of 75mph, however, a journey of 128 miles would take less than one and three quarter hours. That is only just inside what might, in railway terms, be considered "long distance". Most long distance rail journeys even in a small country such as the UK take far longer than that. (For reference, the distance between London and Bristol is 106 miles. The distance between London and Edinburgh is 332 miles). Even on a 1024x1024 map, therefore, aviation would be nearly useless, and most railway journeys would be either in the "local" or the "outer suburban" distance bracket.

The solution - larger maps

The only solution to that problem is to have much larger maps. Consider, for instance, a 2048x4096 map. The longest dimension - 4096 tiles - is equivalent to 512 miles, and there is the possibility of diagonal journeys. Aviation, at least short-haul (and possibly into the realms of medium-haul), becomes sensible, and long-distance railway journeys are a realistic possibility. Even a slightly smaller map than that: say, 3840 x 1792 would give a maximum dimension on the longest side equivalent to 480 miles, again, with the possibility of diagonal journeys. That would also be sufficient for at least short-haul aviation and long-distance rail travel.

The advantages of such an approach are more than just having a larger area on which to play: there is also far more incentive to use appropriate types of vehicle and network. There can be a real separation between outer suburban and long distance, which is not possible with the current scale, with large, complicated networks of suburban rail or 'bus routes in larger urban areas that, with the previous scale, would be confined to one or two simple 'buses or trams. The impact of different levels of acceleration, comfort, and loading time for different types of routes will interplay delicately with each other and produce networks with very different characteristics depending on the circumstances.

Challenges

Economic balancing

However, increasing the scale in one place must be balanced by increasing it in others, or else the delicate balance of the game will be upset. I list below all of the things that I have thought of that will need commensurate changes to match the scale. I should be very grateful if anyone else could point out any other things that also will need to be changed.

P****enger/goods revenue per tile will need to be decreased
The building and maintenance cost of ways will need to be decreased
The per tile running cost of vehicles will need to be decreased
The use of "km" in the UI will have to be discontinued everywhere where "km" is said to represent a tile
Towns will need to be made larger
The coverage radius of stops will need to be increased
The p****enger level will need to be decreased (although the journey time tolerance feature might have this effect to a sufficient level in any case)

* Further consideration is required as to whether or not this should include tunnels and bridges - one might say that the existing tunnels and bridges are more in proportion with the graphics scale than the distance scale, and therefore that increasing the scale will help their cost to balance better with that of ordinary ways. A similar consideration applies with aircraft runways.

All of these things can be achieved by changes in the paksets and/or simuconf.tab, but changing, for example, the running cost of each and every vehicle is enormously laborious, and not all players who play that particular pakset might want to use the larger scale; their computers might not be capable of such large maps. In relation to the vehicle and way costs, it would be very helpful to be able to divide them by a certain amount specified in simuconf.tab, so that all of the scale settings could be set in simuconf.tab and apply without having to recompile the pakset. I am currently working on just such a feature for the next version of Simutrans-Experimental, and would be grateful for any suggestions on how best to do it or (and in particular) whether there may be any pitfalls of this system or any easy mistakes to avoid.

I should also very much like feedback about what to do about all the instances of "km" being used in the UI. Should the term "km" remain, but the values be converted to mean actual kilometres, rather than tiles (so, the price for ways, for example, would give the price for five tiles, rather than one tile when it quotes a "per km" price), or should the reference to "km" be expunged entirely and replaced simply with a reference to "tiles"? Edit: Also, ought the divider necessarily be the same as the journey time multiplier (by default, 20%), or ought it be possible to set it to some other figure?

Technical issues

Larger maps take longer to generate and consume more memory. Running in a debugger, 2048x4096 map in Pak128.Britain without any transport network, but with 512 towns and 256 industry chains took just over 400Mb, although a release build should take much less. Older computers cannot readily cope, which is why the larger scale needs to be optional, as discussed above. However, even on a relatively powerful computer (my 3.0Ghz Pentium IV is a little old now, but it does have 2Gb of dual channel RAM), map generation of larger sized maps with many cities (and, to get a sensible city distribution, it is necessary to increase greatly the number of cities when the map size is increased) can take an unreasonable amount of time (well over ten minutes, albeit with a debug build - I ran it overnight). That topic is discussed in more detail in this thread, and I should be grateful for any further suggestions as to how map generation times might be optimised.

Further, as discussed in this thread, automatically generated larger maps do not give a plausible terrain because of the settings. In that thread, VS intimated that he had found good settings for larger maps, but that they did not work for smaller maps. The easy solution would be to use different settings depending on the desired map size, but I do not know what settings VS had found that worked for the larger maps. If anyone can ****ist with that topic, I should be very grateful indeed.

One possible workaround is to use height maps, although the difficulty there is the relative lack of variety. A good range of height maps can be downloaded here, but none have a largest dimension of much over 1280 tiles. One thing that would be very helpful, therefore, is a set of higher resolution height maps, of both real and fictional locations.

Finally, the performance of such a large map under game conditions is somewhat uncertain. In earlier versions of Simutrans-Experimental, the path searching algorithm would have been excessively slow on a large and complicated map and would have made playing unpleasant, with frequent pauses every month. Knightly's optimised centralised system has largely abated this, but other issues remain. Trees, for example, are a big drag on performance, and this gets worse the larger the map. I do not know whether any optimisations are possible with respect to trees (which I find a problem even on smaller maps), but, in the meantime, the solution is probably to edit forestrules.tab to reduce tree density. Running a debug build on the 2048x4096 map, with Firefox and the debugger running in the background, made the game somewhat unresponsive, although this was largely intermittent.

I should be very grateful for any input on any other performance issues that might affect reasonably modern but not necessarily cutting edge hardware running maps of the sizes that I describe, and possible solutions or workarounds to those issues. I am very keen, if at all possible, to make Simutrans playable in a larger scale, and will be extremely appreciative of any input, either on the techincal or game-play aspects.

Re: Re-scaling Simutrans

Reply #1 – July 22, 2009, 07:13:11 am

Larger maps is the way to go but I am concerned about the performance requirement of such large maps.

On the graphic scale, I wonder whether it is possible to make buildings larger to match the scale of vehicles. Buildings currently occupy 1 square tile could become 4 sq tiles in size while all road and rail systems remain unchanged. This way vehicles and buildings can look more in scale without too much underlying changes.

On performance, I use a fairly new computer with dual core 2GHz and 3GB ram to run Simutrans 102 and Pak128.Britain. Generating a new map of 2048x2048 takes more than 1:30 min. The generated map is sluggish at its vanilla state.

And the map tool in Simutrans does not scale well with larger maps. By default it uses a scale of 1:1 which is useless in large maps. Also the max scale of the map is limited to 4:1. To show a complete map, the map tool would take up considerable screen space.

Re: Re-scaling Simutrans

Reply #2 – July 22, 2009, 08:49:35 am

Thank you very much for your feedback. This is why optimisation is necessary. I should be interested in the views of the developers as to what exactly makes an empty large map unresponsive. Perhaps somebody with access to Valgrind could undertake some profiling on a large map?

As to the sizes of the buildings, that is related to the rather different question of internal inconsistencies in the graphics scale.

Re: Re-scaling Simutrans

Reply #3 – July 22, 2009, 08:53:20 am

James,

I appreciate your endless efforts in making Simutrans Experimental realistic.

However, when I tried to build an empty map of size 2048 x 2048 using v5.1 and pak128, memory consumption is already 243MB. By empty, I mean no city, no industry, no tourist attraction, and no tree. I can't image how much more memory is needed if you try an even larger map with many cities which have to be larger in size.

Before you plunge into such a daunting project, I suggest you to set up a poll to see whether your project is welcomed or supported. It may turn out to be a waste of your time if few people are interested in or can afford (in terms of hardware) such large games.

Knightly

Re: Re-scaling Simutrans

Reply #4 – July 22, 2009, 09:32:30 am

Knightly,

I gave the memory consumption for a populated 2048 x 4096 map above in debug mode. Since all of the settings will be in simuconf.tab (and therefore optional) and the scaling settings for the prices will not be too difficult to implement in terms of the code, it is not necessary that such a feature would be preferred by a majority in order for it to be useful. Those who do not want to use it will lose nothing by its presence.

I am, however, interested in any possible way to optimise Simutrans-Experimental to enable it to run more efficiently at larger map sizes. If you or anyone else have any thoughts about how that might be done, I should be most grateful for any input.

Re: Re-scaling Simutrans

Reply #5 – July 22, 2009, 09:57:12 am

Simutrans was designed with map sizes of 256x256 in mind, a long time I could not run more than 128x128 on my PC.

Prissi has done a lot to allow for larger maps. But you must be aware that you venture in grounds way beyond the original design ideas, and that this usually means that a lot of ****umptions that went into the existing code, no longer hold. I don't say it won't work. But I want to warn you, that this might have a whole lot of side-effects that you need to take care of, too, and which are not apparent right now.

Re: Re-scaling Simutrans

Reply #6 – July 22, 2009, 09:59:51 am

James,

Given the general laginess of Simutrans-Experimental without Knightlys input using what appears to be more correct physics, I don't see how maps of the size you are talking about would be any use to anyone not using a Cray Super Computer.

Also I think you are taking Simutrans in to the realms of Transport Tycoon, which most of us were trying to avoid like the plague. Your current Experimental has improved out of sight from what you originally had. I think that it would even greatly improve if you applied true physics to your calculations.
I don't purport to know how you would do that, it's just a gut feeling that I have that something is wrong with your calculations. Also I don't propose to tell you your job, but I think you should confer/listen to Knightly when it comes to applied physics.

Re: Re-scaling Simutrans

Reply #7 – July 22, 2009, 10:05:07 am

Quote from: jamespetts – on July 22, 2009, 08:49:35 am

Thank you very much for your feedback. This is why optimisation is necessary. I should be interested in the views of the developers as to what exactly makes an empty large map unresponsive.

I don't have an answer here. But you must be aware that the core of Simutrans was worked on since many years, and often by good programmers. If there were obvious ways to speed up things, or to make Simutrans leaner in terms of memory consumption, people would already have done that.

Again, I don't say it's impossible to optimize further. But I want to say, that you should not expect big breakthroughs, because the former developers tried to optimize already, as good as they could.

Re: Re-scaling Simutrans

Reply #8 – July 22, 2009, 10:09:49 am

Hajo,

thank you for your insight - it is particularly useful to know the size that was originally contemplated. Certainly, at 256x256, 1km/tile makes sense.

It is precisely to avoid the potential unforeseen consequences to which you refer that I have posted this thread so that any underlying ****umptions that I have missed can be identified and accounted for, if possible. Can you (or anyone else) think of any that I have not listed?

Of course, as this is optional, such side effects can be borne out of testing, with users free to revert to the conventional scale if they so choose.

As to optimisations, with a larger map, even a small optimisation that may make no noticable difference on a small map might have a significant impact on performance.

Any thoughts from anyone on the question of whether "per km" in the UI should refer to actual kilometres in the game, or should be re-named to "per tile"?

Colin,

thank you for your input. Knightly was not referring to physics, however - what do you mean exactly? The alterations that I have made to physics relate only to steam railway locomotives and are somewaht conservative. It may be that the entire physics engine needs re-designing at some stage, but that would be a major project in an area in which I lack expertise.

I agree that performance is an issue that needs to be considered (which is why any re-scaling needs to be made optional), but it is not a reason by itself not to have the option, especially as computers advance. It is a reason, however, to consider carefully what takes extra time in large maps and what, therefore, can be optimised.

I am not sure that I understand the reference to Transport Tycoon, however - I always thought that Simutrans always was loosely based on Transport Tycoon, and was meant to be in an approximately similar style but (1) free; and (2) better. How would the scale suggestion make Simutrans more lke Transport Tycoon? The idea is to make Simutrans more realistic. Even Simutrans-Standard is far more realistic and fun than Transport Tycoon because of its grater economic depth; the idea of Simutrans-Experimental is to go even further in that desirable direction.

Re: Re-scaling Simutrans

Reply #9 – July 22, 2009, 10:15:19 am

Quote from: jamespetts – on July 21, 2009, 11:23:54 pm

I should be very grateful for any input on any other performance issues that might affect reasonably modern but not necessarily cutting edge hardware running maps of the sizes that I describe.

The bandwidth for memory accesses. While RAM size, and CPU speed has grown immensely over the past years, memory transfer rates have grown less.

Such large maps require a lot of read/write accesses to update all items in the simulation. I think memory bandwidth will be the major bottleneck.

Edit:

Read some ideas here: http://www.simugraph.com/library/articles/opti/optimizing.html
And try this program (also linked from the optimzation guide): http://www.simugraph.com/library/articles/opti/memaccess.c

It's simple, but Simutrans hasn't that much more clever ways to access memory, so the numbers should give you a fair idea what is possible.

Re: Re-scaling Simutrans

Reply #10 – July 22, 2009, 10:20:19 am

Hajo,

very useful information, thank you. The idea is that a larger map will be, in terms of transportation infrastrucutre at least, a sp****r map (with the amount of space taken by transportation relative to the total land closer to reality than in the smaller scale used at present). Therefore, in terms of transportation infrastructure, the increase in quantity will be considerably less than proportional to the increase in the surface area of the map.

That being the case, what other, non-transport items need a large amount of memory bandwith to deal with in their step() (or even sync_step()) cycles? Is there anything there that can be optimised to happen, not every cycle, but every n cycles? I was already considering reducing the running costs of vehicles, not simply by dividing the amount by the stipulated divider, but by charging the per kilometre cost only when the vehicle has traversed enough tiles to constitute a kilometre, which would involve calling the running cost method 1/5th of the time that it is currently called. Can anyone think of any similar optimisations, especially for "empty map" items?

Re: Re-scaling Simutrans

Reply #11 – July 22, 2009, 10:23:41 am

James,

Firstly, my quoted memory consumption is from v5.1 when it is *not* in debugging mode. Secondly, what Colin refers to "physics" actually refers to my observation regarding memory consumption.

The true problem which you are facing is that, the distances are not long enough for your comfort factor to take full effect. If that is the case, why not just "scale down" your formula for comfort, so that the comfort factor have greater effect on shorter distances? Why don't you adjust your comfort formulas to fit the current scale? Wouldn't that be simpler than scaling everything else? I think you are just creating new problems for yourself, and attempting on a feature that few people will find useful.

As for sluggishness on large maps -- if you have a completely empty map, it will not be sluggish. Any sluggishness is caused by objects on the map. So if you add many large cities with numerous industry chains, and together with huge forests of tree, you can't blame Simutrans for running slowly. And I have to warn you : although it is still an educated guess, but most likely your step_p****agiere() is taking up too much processing time, so if you try a large map with many cities, each of which have many city buildings, the game will very likely to be sluggish.

You are right to say that technological advancement allows larger games. However, even when I currently have 4GB RAM on my PC, I will not try such large maps.

Knightly

Re: Re-scaling Simutrans

Reply #12 – July 22, 2009, 10:25:36 am

Larger maps are sluggish for several reasons. First is simple mathematics: Object number (and thus processing power) scaled quadratically with the map size. (Even cubic with underground, in principle.) This applies to p****engers too!

But there is more: memory. A 2048*2048 requires about 800MB memory for a filled map (with trees, cities etc). All those objects need to be processed every season change at least. Also the sync_lists will get big, and they need to be processed every sync_step. To make things worse, memory gets slow when exceeding 3rd level cache, something like 2-8MB with current high end processors. Those can access main memory usually in 256 Byte chunks, even if only a single Byte is needed, why additionally clutters the cache. Thus on smaller maps (up to 1024*1024) all the objects that change more or less fit in the chace. But beyond things get difficult and the OS may even put seldomly accessed tiles (like water) into the swap in favour of other programs. (And memory consumption in debug mode should not be different from release but for a few percent at max.)

But also handling is a problem. The overview map does not average over different pixels to make sure no relevant information is lost and so on.

Simutrans could have a 3D map with a 16x16 mesh on a single tile which could give 16 times larger maps wihtout loosing to much detail level, imho. But that is ratehr a new effort which would be only loosely built on SImutrans.

Re: Re-scaling Simutrans

Reply #13 – July 22, 2009, 10:30:07 am

Knightly,

as explained above, it is rather more complicated than just the calibration of the comfort. Down-calibrating the comfort settings would mean that only journies of a very few tiles would count as short enough for the purposes of comfort (and journey time tolerance). The possibilities for interesting suburban transport networks would then be extremely limited. Anything but a journey from one side of a small town to another would require, for comfort, something in at least the "outer suburban" category. Journies between all but very closely neighbouring towns would all require something in the "express" category. The opportunity to use 'buses would be greatly diminished. Aircraft would have an excessive advantage over land transport.

You may be right that step_p****agiere() takes much processing time on empty maps. Can you (or anyone else) think of any good ways to optimise it? I should be most grateful for any suggestions.

Edit:

Prissi,

thank you very much for the information - it is most helpful. Certainly, one partial workaround is to use non-square maps to achieve larger distances without incraesing the overall size as much as with square maps.

As stated above, one possible optimisation would be calling certain functions only every n steps instead of every single step. This might make a real differnece to responsiveness if done in a sync_step(). Can you think of anything in respect of which this could be done?

Re: Re-scaling Simutrans

Reply #14 – July 22, 2009, 10:30:47 am

Quote from: jamespetts – on July 22, 2009, 10:20:19 am

That being the case, what other, non-transport items need a large amount of memory bandwith to deal with in their step() (or even sync_step()) cycles? Is there anything there that can be optimised to happen, not every cycle, but every n cycles?

You must be aware that reading and increasing a counter already does a read/write pair on memory, dirties a cache line and needs a main memory update later. Optimising for memory bandwidth actually means to read and alter as little data as possible, which will be very hard with a program like Simutrans where buildings, trees, water and more are updated all the time.

Re: Re-scaling Simutrans

Reply #15 – July 22, 2009, 11:19:19 am

A sync_step handles moving of the vehicles and as such there is nothing that can be made about it. I optimized simutrans quite a lot, it is now about four times faster than the 88.x version. Unfourtunately that means you can double mapsize. SInce before 640*640 was the limit for sensible games now it is rather 1280*1280. I have not many ideas how to go much beyond this.

Most time is actually spend in haltestelle_t::suche_route (on a very busy map up to 10% of the time) and then in sync_step (dito 8% of the time). You can find more exhausive profiles in other threads, but this is the one for simutrans tandard, fast forward (so drawing will be as little as possible). The problem that all stuff like == operator for koord is used by many objects. Dobule the map size => four times more of those objects => four time more of those "tiny" functions that actually in the end consume most time.

Code: [Select]

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
  9.17     27.77    27.77  1464066     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*, bool)
  8.27     52.80    25.03    18190     0.00     0.00  karte_t::sync_step(long, bool, bool)
  6.57     72.69    19.89  7202190     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  3.20     82.39     9.70    14631     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  2.62     90.31     7.93 1600259493     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  2.14     96.78     6.47 1617542176     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::get_count() const
  1.84    102.36     5.58 146667782     0.00     0.00  grund_t::get_weg(waytype_t) const
  1.77    107.73     5.37 18667682     0.00     0.00  convoi_t::calc_acceleration(long)
  1.75    113.02     5.29 241168851     0.00     0.00  grund_t::get_hoehe() const
  1.65    118.03     5.01 189289339     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.63    122.98     4.95 135841753     0.00     0.00  planquadrat_t::get_boden_in_hoehe(short) const
  1.61    127.85     4.87 1827594415     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  1.59    132.67     4.82 1530247510     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  1.58    137.44     4.77 158718767     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.56    142.15     4.71 1550056419     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::operator[](unsigned int) const
  1.44    146.52     4.37 32313318     0.00     0.00  convoi_t::sync_step(long)
  1.31    150.49     3.97 494281345     0.00     0.00  koord::koord(short, short)
  1.30    154.42     3.93  1814820     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, schedule_t*)
  1.22    158.12     3.70 524431256     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.04    161.26     3.14 81318192     0.00     0.00  ding_t::is_moving() const
  1.01    164.32     3.06 353483309     0.00     0.00  koord3d::get_2d() const
  1.01    167.38     3.06 259974142     0.00     0.00  operator==(koord const&, koord const&)

Re: Re-scaling Simutrans

Reply #16 – July 22, 2009, 12:30:35 pm

Hajo and Prissi,

thank you both very much for your input. The profiling is especially helpful - I am very grateful to you for providing this. It does seem that there is not a great deal further that can be optimised (although I do still wonder whether there are any optimisations that only produce a significant benefit when the map size is larger in the first place). In particular, I wonder whether those relative percentages would be the same on a very large map, or whether other functions would be called a higher proportion of the time.

In any event, given that, in terms of running (rather than generating) maps, at least, there is not much further room for optimisation, it might be possible to get usable distances by tweaking the figures slightly. Suppose that I set the journey time multiplier to 25%, rather than 20%. That would mean that each tile was effectively 250m, instead of 200m. In that setup, a map of 1024 x 2048 tiles would have a longest distance of the equivalent of 320 miles - not ideal (especially for aviation), but enough for proper long-distance trains and at least short-haul aviation. That distance is not far off the London to Edinburgh distance quote above, and, certainly, express trains and jet aircraft are used for that distance regularly. The possibility of diagonal journies on such a map would further increase the possibilies for long distance travel.

At 1280 x 1280, the total number of tiles is 1,638,400. At 1024 x 2048, the total number of tiles would be 2,097,152, an increase by a factor of about 1.28. By contrast, a map of 2048 x 4096 has 8,388,608, an incraese by a factor of of 5.12. Although still larger than current maps, therefore, a 1024 x 2048 map could be feasible on at least modern hardware. There is also a possibility for even narrower maps, such as 896 x 2048 (1,835,008 tiles) or even 768 x 2048 (1,572,864 tiles), although the more extreme the imblanace in dimensions, the less entertaining that the maps are.

Thus, the technical issues, it would seem, can be worked around by compromising the figures slightly (still within reasonable limits), and using non-square maps to achieve good distances in at least one direction. Of course, if anybody can think of any further optimisations that would benefit large maps in particular, I should very much like to know. I should also be very interested in any thoughts from Prissi or Hajo as to whether, for dividing vehicle revenues, it would be faster simply to pre-calculate the divided amount for each vehicle on loading/creating the map and store it in a separate value in the vehicle's besch cl****, or use the full amount, but add an extra uint8 variable to the vehicles counting how many tiles that have p****ed since the last payment of running costs, and calling the running costs method only when that number is divisible by the set divider (which would, at 250m/tile be 4). The former approach is probably simpler to code, so, if there is no real difference in perforamnce, that would seem the one to adopt.

Other issues

The issue of performance aside, I should still be very interested in views on: (1) gameplay/balancing; and (2) UI. Can anyone think of anything that I have not mentioned that would also need to be adjusted? What are people's thoughts on whether the costs should be per tile or per kilometre in a system where a tile does not equal a kilometre? My initial view is that displaying a real per kilometre cost is more user-friendly, because it enables players to calculate relative costs based on the same scale as is used for speed, but I should appreciate any other views on the point.

Finally, I should also very much appreciate input into the issue of map generation optimisation and/or visual feedback and better quality terrain for larger maps, in their appropriate threads.

Thank you all again for your swift and comprehensive replies on the issue of performance :-)

Re: Re-scaling Simutrans

Reply #17 – July 22, 2009, 04:52:00 pm

This is an interesting subject, and one which I've looked into a bit in the past.

I have long wanted to develop a transport game which uses realistic scaling, where everything is to scale. This would almost certainly require a completely different style of game engine to that of Simutrans (full-3D is really the only way to go here I think). The idea would be to use the same kind of perlin noise generator to produce the maps but to generate terrain on the closest "zoom" levels on the fly only when required. E.g. you generate, to start with, a map based on 1km squares (like Simutrans maps are now). You can however zoom in using the procedurally generated terrain to a resolution of 100m, 10m, or even 1m if required. Local terrain modifications would be stored in addition to the procedural mesh, so earthworks/cuttings would only need to be stored as they affect the original terrain.

The entire structure would be stored as a quad tree to conserve memory (which would also provide a neat solution for rendering the terrain, since quad trees are easily backface culled on the first p****). Given that the limiting factor on modern PC systems tends to be hard disk space and memory rather than processing power moving towards a procedurally generated model seems sensible.

So on this kind of map you could zoom in to a resolution of 1m, while still only needing to store a tiny fraction of the total map as 1m by 1m squares (only terrain which has been "modified" from the original procedurally generated specification need be stored). Cities, rivers, forests and mountains would all be possible, as would free-form track (maybe based on the bezier-curve driven system I've been developing) and roads. The routefinding graph would be m****ively simplified by tracking only whole sections of track, rather than tile-by-tile, and this could itself be stored in a quad tree to improve the search speed/memory requirements. Fundamentally though if you don't have to store millions of individual tiles and only need to worry about the thousands of objects and thousands of terrain deformation points you free up a lot of memory for other things.

Of course, such an effort would require starting from scratch. I've made some experiemental programs to explore the possibilities, but don't really have the time or 3D modelling expertise to make anything interesting. I quite enjoy 2D sprite-based games as well, which is what I've been working on recently. Some of the same principles of using quad-trees to represent the terrain map, and point-to-point routefinding are transferable. I plan on having the scale in my 2D game be as realistic as possible (if I ever find the time to take the handful of technical demos and turn them into a game!)

Re: Re-scaling Simutrans

Reply #18 – July 22, 2009, 05:22:38 pm

Timothy,

very intereseting thoughts, although I suspect beyond what can realistically be achieved in terms of programming resources for Simutrans in the near future. I certainly agree that a realistic scale is desirable, and although Simutrans will always be somewhat of a compromise, I hope that I can at least make it a better compromise.

Any thoughts on any of the Simutrans-specific issues that I have raised above (the UI, whether any other figures need scaling, etc.)?

Re: Re-scaling Simutrans

Reply #19 – July 22, 2009, 09:53:10 pm

A very intriguing idea. My computer is a Dell box I bought late last year, as a 'budget game computer' - around about the minimum price at which computers commonly have dedicated graphics card. So I think a computer that should be accessible to a large number of gamers, but that there would be a lot of gamers, particularly in the free game market that would have lesser computers. So I think the type of computer that you could design an option of pak for, but not one to design a whole game around. To me I think a pak or config file specically designed and balanced for large map play would be great.

I tried creating some maps at 4096x2048 in both standard and experimental simutrans and failed each time. Maybe didn't wait long enough but in each case the progress bar froze for a few minutes.

Then I generated a map 2560x2560 and it works. It is 100% flat (I hate building over slopes), has no trees, 64 cities, 15 industries, median size 1000. Been playing a few years and it plays quite well. Lags for a few seconds on month change, a lag on opening map, but otherwise perfectly smooth. Current population 55k, highest vehicle ID currently 164.

Gameplaywise finding my way around the map is an issue, particularly with a featureless map. I have timeline from 1930. Started with 3 airport hubs on the 3 biggest cities which were spaced out quite wide, and have dozens of planes on each line, so harder to manage capacity. I would think for such games some type of tool to better estimate capacity required would be great. Something like station x currently generates 500 p****engers a month for line y, and only 330 of them are transported by 33 consists, so you need about 17 more.

Also with large routes, bunching of consists becomes an issue, and I think some feature to smooth out the flow of consists would be great. I would think if for a route you picked a timing point, and then timed how long on average it takes consists to p**** this point. Then divide by the number of consists. This should be average separation. If consists arrive sooner than this, they can be delayed a set amount - I would say a user chosen percentage of the total delay required to achieve the calculated interval.

And finally industry distribution would need to be looked at, as they currently tend to spawn quite close together. I consider this an issue even on maps about 512x512 or so which is what I have been playing mostly.

Re: Re-scaling Simutrans

Reply #20 – July 22, 2009, 10:50:22 pm

I run simutrans with gprof ( with simutrans compiled with fno-inline/fno-default-inline to keep called functions ) during creating map.

Creating map 512x512 ( 16 cities, 6 industries ) took 18 s ( 8 s on optimized build without profiler ) .

Quote

Flat profile:

Each sample counts as 0.01 seconds.
%   cumulative   self self    total
time   seconds   seconds calls   s/call   s/call name
30.25 2.54    2.54 102878640    0.00    0.00 int_noise(long, long)
5.73 3.02    0.48 92709    0.00    0.00 display_img_nc(short, short, short, unsigned short const*)
3.58 3.31    0.30 11430960    0.00    0.00 smoothed_noise(int, int)
3.58 3.62    0.30 27877    0.00    0.00 image_reader_t::read_node(_IO_FILE*, obj_node_info_t&)
2.86 3.85    0.24 280    0.00    0.00 create_textured_tile_mix(bild_besch_t const*, unsigned char, bild_besch_t const*, bild_besch_t const*, bild_besch_t const*, bild_besch_t const*)
2.51 4.07    0.21   651651    0.00    0.00 stadt_t::bewerte_loc(koord, char const*, int)
2.27 4.25    0.19 69412056    0.00    0.00 vector_tpl<baum_besch_t const*>::operator[](unsigned int)
2.27 4.45    0.19 55460617    0.00    0.00 decode_uint16(char*&)
1.85 4.60    0.15 2857740    0.00    0.00 interpolated_noise(double, double)
1.43 4.72    0.12   349794    0.00    0.00 baum_t::random_tree_for_climate_intern(climate)
1.31 4.83    0.11 17618868    0.00    0.00 planquadrat_t::get_kartenboden() const
1.31 4.94    0.11 17572288    0.00    0.00 karte_t::lookup(koord) const
1.19 5.04    0.10 1432460    0.00    0.00 grund_t::get_neighbour(grund_t*&, waytype_t, koord) const
1.13 5.13    0.10    54    0.00    0.00 setsimrand(unsigned int, unsigned int)

Creating map 2048x2048 ( 16 cities, 6 industries ) took 4m 50s ( 1m 8s on optimized build without profiler )

Quote

Flat profile:

Each sample counts as 0.01 seconds.
%   cumulative   self self    total
time   seconds   seconds calls   s/call   s/call name
19.28    11.45 11.45 910421384    0.00    0.00 int_noise(long, long)
8.54    16.52    5.07 2268456581    0.00    0.00 vector_tpl<baum_besch_t const*>::operator[](unsigned int)
6.29    20.25    3.73 143427665    0.00    0.00 planquadrat_t::get_kartenboden() const
5.54    23.54    3.29 34642258    0.00    0.00 baum_t::get_anzahl_besch(climate)
5.39    26.74    3.20 2012634501    0.00    0.00 baum_besch_t::is_allowed_climate(climate) const
4.30    29.30    2.56 8663719    0.00    0.00 baum_t::random_tree_for_climate_intern(climate)
3.58    31.42    2.12 2055940478    0.00    0.00 vector_tpl<baum_besch_t const*>::get_count() const
3.13    33.28    1.86 101157929    0.00    0.00 smoothed_noise(int, int)
1.92    34.42    1.14 83651997    0.00    0.00 simrand(unsigned int)
1.85    35.52    1.10 129127330    0.00    0.00 karte_t::lookup(koord) const
1.73    36.55    1.02 25289479    0.00    0.00 interpolated_noise(double, double)
1.53    37.45    0.91 132    0.01    0.19 baum_t::create_forest(karte_t*, koord, koord)
1.36    38.27    0.81 38166453    0.00    0.00 baum_t::plant_tree_on_coordinate(karte_t*, koord, unsigned char)
1.27    39.02    0.76 9237598    0.00    0.00 grund_t::calc_back_bild(signed char, signed char)
1.22    39.74    0.72 625806692    0.00    0.00 slist_tpl<hashtable_tpl<char const*, groundobj_besch_t*, stringhash_t>::node_t>::empty() const
1.18    40.45    0.70 6196106    0.00    0.00 hashtable_tpl<char const*, groundobj_besch_t*, stringhash_t>::empty() const
1.15    41.12    0.68 26420166    0.00    0.00 baum_t::get_typ() const
0.99    41.71    0.58 3066671    0.00    0.00 karte_t::ist_platz_frei(koord, short, short, int*, climate_bits) const
0.94    42.27    0.56 2    0.28    3.15 karte_t::distribute_groundobjs_cities(int, short, short)
0.89    42.80    0.53 2    0.27    1.89 karte_t::cleanup_karte(int, int)
0.84    43.30    0.50   103346    0.00    0.00 display_img_nc(short, short, short, unsigned short const*)
0.81    43.78    0.48 283692089    0.00    0.00 koord::koord(short, short)
0.76    44.23    0.45 69828794    0.00    0.00 karte_t::lookup_hgt(koord) const
0.74    44.67    0.44 83602020    0.00    0.00 simrand_plain()
0.61    45.03    0.36 52667916    0.00    0.00 dingliste_t::get_top() const
0.60    45.39    0.35 19098119    0.00    0.00 freelist_t::gimme_node(unsigned int)
0.60    45.74    0.35 6    0.06    0.06 setsimrand(unsigned int, unsigned int)
0.56    46.08    0.34 8665740    0.00    0.00 ding_t::mark_image_dirty(unsigned short, signed char) const
0.54    46.40    0.32 145920942    0.00    0.00 karte_t::ist_in_kartengrenzen(short, short) const
0.51    46.70    0.30   133978    0.00    0.00 MTgenerate()
0.49    46.99    0.29 4202626    0.00    0.00 karte_t::raise_clean(short, short, short)
0.45    47.26    0.27 12595211    0.00    0.00 karte_t::calc_natural_slope(koord) const
0.45    47.53    0.27 8642742    0.00    0.00 karte_t::max_hgt(koord) const
0.45    47.80    0.27 46034195    0.00    0.00 grund_t::hat_wege() const
0.44    48.05    0.26 27877    0.00    0.00 image_reader_t::read_node(_IO_FILE*, obj_node_info_t&)
0.41    48.30    0.24 78692899    0.00    0.00 karte_t::get_groesse_x() const
0.39    48.53    0.23 108213142    0.00    0.00 karte_t::ist_in_gittergrenzen(short, sh

So time of creating map is in rough linear with comparison to size.

For 4 M titles some of functions are called for 2 G times, it looks as a quite big amount

Re: Re-scaling Simutrans

Reply #21 – July 22, 2009, 11:01:27 pm

Hanczar,

thank you very much for the profiling - that is extremely helpful. However, 16 cities on a 2048x2048 map would not be a very fun game. Generating cities, it seems, is what takes a very long time. Do you think that you could possibly try again with 512 cities? I'd be extremely grateful if you could. Thank you very much indeed for your time and trouble.

Re: Re-scaling Simutrans

Reply #22 – July 23, 2009, 07:04:52 am

It seems the tree planting routines taken up much time, since there are some loops through the array of all tree that are called again and again. A patch to cache the results of the loops is underway

Re: Re-scaling Simutrans

Reply #23 – July 23, 2009, 07:41:19 am

The trees take only a few percentage at all to generate, compared to cities and industry placement. The vector_tpl<baum_besch_t const*>::operator[](unsigned int) statement is just to save memory, since the way most common objects on the map are trees. But instead saving the whole tree_besch_t pointer, just 12 bit are saved, reducing trees by 4 bytes (i.e. on a normal map 4MB less memory).

int_noise coukld do with caching, since it is called for each point 9 times. By first calculation an array of all points and then just copy them lots of those calls could be saved ...

Re: Re-scaling Simutrans

Reply #24 – July 23, 2009, 08:10:19 am

Quote from: prissi – on July 23, 2009, 07:41:19 am

The trees take only a few percentage at all to generate, compared to cities and industry placement.

That's why it'd be very useful to see the results of the profiling done with more cities and industry... (say, 512 cities and 128 industry chains) ;-)

Re: Re-scaling Simutrans

Reply #25 – July 23, 2009, 08:42:12 am

I think this discussion is really interesting, but I'm not sure if there is real need to rescale Simutrans. Anyway kudos to you James for beeing willing to think out of the "box".

I can think of one thing that is needed if you want larger maps more normal, with or without rescaling:
- The abillity to zoom out more
When playing on my laptop I offen wish that I could zoom out one or two ticks more, so that I could see more of the map at once.

Re: Re-scaling Simutrans

Reply #26 – July 23, 2009, 09:29:59 am

Probably a stupid question, but: are all non transport / non interacting objects (empty terrain, trees, water) updated all the time or only when they are visible? could it be possible to let them "sleep" and self-update only when they enter in the player's view?

EDIT:
An afterthought: could it be possible to use 3D meshes for the terrain (and maybe ways) and all the others, instead, tiles objects?

Re: Re-scaling Simutrans

Reply #27 – July 23, 2009, 10:15:10 am

Quote from: fabio – on July 23, 2009, 09:29:59 am

Probably a stupid question, but: are all non transport / non interacting objects (empty terrain, trees, water) updated all the time or only when they are visible? could it be possible to let them "sleep" and self-update only when they enter in the player's view?

I don't know the current code, but when I was active, the simulation engine did not know which parts of the world are visible to the player (can be more than the main view, due to information windows, followed vehicles ...), and therefore updated all of the world regularly.

Quote from: Timothy – on July 22, 2009, 04:52:00 pm

The entire structure would be stored as a quad tree to conserve memory (which would also provide a neat solution for rendering the terrain, since quad trees are easily backface culled on the first p****). Given that the limiting factor on modern PC systems tends to be hard disk space and memory rather than processing power moving towards a procedurally generated model seems sensible.

I too, think, for such large maps a different architecture is needed. Tree structures as Timothy proposes work well in the current 3D games with big worlds. It would mean to write a new program though, or at least rewrite big parts of Simutrans.

Re: Re-scaling Simutrans

Reply #28 – July 23, 2009, 10:17:09 am

Any tile with a seasonal change is updated, when a season change occurs. Others than that only animated objects are updated regularily (on the whole map). But since most of the load during a game is from distribution goods and moving vehilces, which need to be done on the whole map anyway, and drawing images (which is only done as much as needed with lots of optimisations), doing in on the whole map is preferred.

Re: Re-scaling Simutrans

Reply #29 – July 23, 2009, 11:14:35 am

We have had so far some very interesting and worthwhile discussions about the techincal aspects of re-scaling: thank you to all those who have contributed.

I should be very interested to know of people's views on the economic aspects, however, as discussed in the original post. Does anyone have any thoughts about that? :-)

Re: Re-scaling Simutrans

Reply #30 – July 23, 2009, 02:45:10 pm

I think the economical simulation can work good enough on maps with less tiles, particularly if "realism" in the sense of realistic scales on all levels is not required.

The idea of having a scale of 1km² per tile means that a 256x256 map already covers a area of 256x256 km, which should allow for interesting economic relations already, and maps of 1024x1024 tiles already have the size of average european countries.

Cities spanning 2-20 tiles diameter are "realistic" on that scale, just the simulation is a bit co**** because structures below 1 km cannot be simulated properly, but I think that doesn't need to be.

If the graphical representation is not "realistic", since only one proxy for a 1km² house block is shown, or roads span a whole square, and if this is a problem, I'd suggest to change the representation to something more abstract than the current pak sets have. This might change the beauty of display, but that is a different problem.

Re: Re-scaling Simutrans

Reply #31 – July 23, 2009, 08:08:44 pm

Hajo,

thank you for your input - it is always useful to know the design thinking behind things :-) However, that doesn't really address what I put in my original post as to the reasons for re-scaling: with the new mechanisms in Simutrans-Experimental that require journey times to be measured for matters such as journey time tolerance and comfort, the relative scale of 1km/tile does not work properly, and produces times that are too high. It also allows for insufficient distinction between short, medium and long distance transport (which distinction is important in Simutrans-Experimental, because different sorts of vehicles with different comfort levels, loading times, catering levels, etc. are appropriate for different sorts of journeys).

I had asked a number of specific questions in my original post about economic aspects - I should be very interested indeed in people's views on those particular points. Thank you everyone for your input so far :-)

Re: Re-scaling Simutrans

Reply #32 – July 23, 2009, 08:44:22 pm

Quote from: jamespetts – on July 23, 2009, 08:08:44 pm

with the new mechanisms in Simutrans-Experimental that require journey times to be measured for matters such as journey time tolerance and comfort, the relative scale of 1km/tile does not work properly, and produces times that are too high.

Vehicle speed is a very artificial number in Simutrans. I see no problem to adapting the "time" to a value that works with your formulas?

1km/h doesn't really mean anything currently ... it was just chosen in a manner that 50km/h looked "sensible" to my eyes in a city. You could easily define a "time" scale that fits your formulas - what the player sees on screen is one thing, what the simulation engine uses is another.

Edit: Once I have more time, I'll try to find your questions in the first post. It's a lot of text. But currently I think you try things that Simutrans was not made for, and you might need to program a new transport game core for those ...

Edit 2: I've tried to read a bigger portion of your text. To me, it seems you strive for "realistic" in terms of distance and time scale, which the Simutrans engine cannot provide. So either you drop that requirement, and adjust your formulas so that a 200 tile travel is "uncomfortable" or you need to create a different engine. I'd advice to move from a tile based world to a continuous world, with tables and trees as core date structures, and lookup by object id, not by tile position.

Re: Re-scaling Simutrans

Reply #33 – July 23, 2009, 09:00:59 pm

Hajo,

thank you for your replies :-) I realise that one cannot get it to be completely realistic in Simutrans - I am simply aiming for "more realistic", or, perhaps more accurately, "realistic enough to give full usefulness to the Simutrans-Experimental features". The main reason for the re-scaling is simply to provide a better balance between short, medium and long distance journeys to require the player to use appropriate vehicles for each type, and provide more interesting choices and the possibility for more interesting and subtly intricate networks.

What I found when calculating the figures is that, on any denomination of scale, on a smaller map, either the scale is so small that short distance vehicles are useless because anything more than a few tiles is at least medium distance, or the scale is so large that long distance vehicles are useless because the longest possible straight line journey on the map is barely above what might be considered medium distance. The only solution was to have larger maps. I do not think that a complete rewrite is necessary for that, and in any event, is not something that I have the time or capability to do.

Re: Re-scaling Simutrans

Reply #34 – July 23, 2009, 09:21:30 pm

Quote from: jamespetts – on July 23, 2009, 09:00:59 pm

What I found when calculating the figures is that, on any denomination of scale, on a smaller map, either the scale is so small that short distance vehicles are useless because anything more than a few tiles is at least medium distance, or the scale is so large that long distance vehicles are useless because the longest possible straight line journey on the map is barely above what might be considered medium distance. The only solution was to have larger maps.

Did you try exponential or logarithmic scales? Even something like discomfort = pow(distance, 2), could stretch the short distance comfort zone to about city size, but make longer travels very uncomfortable?