New city generation function.

Topic: New city generation function. (Read 18691 times) previous topic - next topic

New city generation function.

July 03, 2010, 12:46:00 pm

Ok. Release time.

Changes:

'minimum_city_distance' in cityrules.tab was deleted. There is 'city_repulse_factor' instead (I need better name).
It set how much cities avoids each other.

Water now attracts cities. How much is set in 'Water appeal' setting in climate dialog.
It does not work well with 'Cities ignore height' option. Result is confusing.
Use 'Cities ignore height'==on and 'water appeal' !=0 or 'Cities ignore height'==off and 'water appeal' =0

Cities now form clusters. 'Number of clusters' and 'Cluster size' in Create new game dialog.
Number of clusters == 0 means no clustering.

See 'Cities ignore height' option thread for screenshots.

Re: New city generation function.

Reply #1 – July 03, 2010, 01:22:38 pm

city_repulse_factor --> city_avoid_factor?

Re: New city generation function.

Reply #2 – July 03, 2010, 03:27:57 pm

Demo Windows binary posted to patches.simutrans-germany.com

Re: New city generation function.

Reply #3 – July 03, 2010, 03:40:57 pm

And small MSVC compatibility patch.

Re: New city generation function.

Reply #4 – July 03, 2010, 09:02:53 pm

Inkelyad,

thank you very much for your patch; most interesting. I have not yet had the opportunity to try it (I am currently away from home), but shall investigate when I get a chance.

However, you will need to make this work well with the system for making cities more likely to be built on lower ground before I can release it. May I ask what the problem is with interaction between the two systems is so far?

Edit: Also, can I check - does this significantly slow down map generation for, say, a 1024x2048 map with 250 cities?

Re: New city generation function.

Reply #5 – July 03, 2010, 09:15:31 pm

Rivers usually lower ground too. 'Cities ignore height' status become almost useless when 'water appeal' is enabled.

It is somewhat slower. But city growth stage is much longer. I don't change that part.

Re: New city generation function.

Reply #6 – July 03, 2010, 09:23:13 pm

In Simutrans, rivers lower ground by one tile immediately around the river. Cities being attracted to water does not have the same effect as cities preferring lower ground. Cities' preference for lower ground should not be almost useless when they are attracted to water: the two are distinct.

Re: New city generation function.

Reply #7 – July 03, 2010, 09:27:58 pm

It is really hard to notice when there is many rivers on the map. All lower ground become near water. Rivers flow that way.

Re: New city generation function.

Reply #8 – July 03, 2010, 09:38:48 pm

I am not sure that I understand - what is really hard for whom to notice? And what of the case where there are not so many rivers on the map? What of distinguishing between medium high, high and very high ground?

Re: New city generation function.

Reply #9 – July 03, 2010, 09:45:48 pm

Quote from: Isaac.Eiland-Hall – on July 03, 2010, 01:22:38 pm

city_repulse_factor --> city_avoid_factor?

City isolation factor?
City mutual attraction factor? (if you invert it)

Re: New city generation function.

Reply #10 – July 03, 2010, 09:50:07 pm

Quote from: jamespetts – on July 03, 2010, 09:38:48 pm

I am not sure that I understand - what is really hard for whom to notice?

It hard to notice 'Cities ignore height' effect. All rivers/seas pull cities to coastline. It is 'lower ground' -> no cities at mountains. Like when 'Cities ignore height' == off.

Quote from: jamespetts – on July 03, 2010, 09:38:48 pm

And what of the case where there are not so many rivers on the map?

Then 'Cities ignore height' == off works.

Re: New city generation function.

Reply #11 – July 03, 2010, 10:24:58 pm

Quote from: AP – on July 03, 2010, 09:45:48 pm

City isolation factor?

I will use it.
How about all others parameters? I doubt 'water appeal' and 'Clusters' too.

Re: New city generation function.

Reply #12 – July 03, 2010, 10:52:50 pm

repulsion and attraction would be terms corresponding well.

Re: New city generation function.

Reply #13 – July 04, 2010, 08:11:56 am

Quote from: sdog – on July 03, 2010, 10:52:50 pm

repulsion and attraction would be terms corresponding well.

It will conflict with 'Tourists attractions'

Re: New city generation function.

Reply #14 – July 04, 2010, 12:38:11 pm

Quote

city_repulse_factor >> "city isolation factor"

maybe then:
Water appeal >> "City river proximity factor"

With the clusters, if set to >0 , are you specifying the precise number of clusters, or a probability? Ie, if set to 2, on a 2000x2000 map, will you still only get 2 clusters same as on a 200x200 map? Or does it "scale"? I quite like the term "cluster" though, it explains itself well.

One other thing, I wonder if "settlement" would not be better than "city" as a term, since a village of 300 people is not exactly a city!

Re: New city generation function.

Reply #15 – July 04, 2010, 01:32:56 pm

Quote from: AP – on July 04, 2010, 12:38:11 pm

maybe then:
Water appeal >> "City river proximity factor"

"City river proximity factor" really does not say anything about what it do.

Quote from: AP – on July 04, 2010, 12:38:11 pm

With the clusters, if set to >0 , are you specifying the precise number of clusters, or a probability?
Ie, if set to 2, on a 2000x2000 map, will you still only get 2 clusters same as on a 200x200 map? Or does it "scale"? I

It will be 2 clusters.

Quote from: AP – on July 04, 2010, 12:38:11 pm

One other thing, I wonder if "settlement" would not be better than "city" as a term, since a village of 300 people is not exactly a city!

Simutrans uses term 'city'. I think to change it is not wise -- it will break all translations.

Re: New city generation function.

Reply #16 – July 04, 2010, 01:51:36 pm

"cities_like_water=xx" is a good name, I think, for the water setting. To my mind, Inkelyad's existing terminology for "city clusters" is clear enough, and he is right about the consistent use of "city" in Simutrans to mean any conurbation.

Re: New city generation function.

Reply #17 – July 04, 2010, 02:05:37 pm

Quote from: jamespetts – on July 04, 2010, 01:51:36 pm

"cities_like_water=xx" is a good name, I think, for the water setting

For *.tab file, yes. But it is part of climate dialog now. Shuld I move it in *.tab file too?

Re: New city generation function.

Reply #18 – July 04, 2010, 03:28:04 pm

It should probably be used consistently for the config.tab file and climate dialogue.

Re: New city generation function.

Reply #19 – July 05, 2010, 06:43:33 pm

'Water appeal' renamed to 'Cities like water'
'city_repulse_factor' renamed to 'city_isolation_factor'
Some minor math tweaking regarding 'Cities like water'.

Re: New city generation function.

Reply #20 – July 11, 2010, 07:08:27 am

Some profiling data.

3072x1024 map, 128 cities.
unpatched:

Code: [Select]

index % time    self  children    called     name

-----------------------------------------------
               27.53 62961.33     100/100         karte_t::enlarge_map(einstellungen_t*, signed char*) [4]
[6]     63.1   27.53 62961.33     100         karte_t::distribute_groundobjs_cities(int, short, short) [6]
                0.05 40672.88   12800/12800       stadt_t::stadt_t(spieler_t*, koord, int) [8]
                0.00 8847.02   40515/43866       wegbauer_t::calc_route(koord3d const&, koord3d const&) [24]
                1.86 8838.05     100/100         stadt_t::random_place(karte_t const*, int, short, short) [27]
               31.71 1628.01 209344308/2306701683     karte_t::lookup_kartenboden(koord) const [7]
                0.00 1548.64   26459/26465       route_t::calc_route(karte_t*, koord3d, koord3d, fahrer_t*, unsigned int, unsigned int, unsigned int) [52]
                0.00  788.25     100/100         karte_t::create_rivers(short) [69]
                0.00  530.16   16212/30612       wegbauer_t::baue() [59]
                0.33   28.08 79228917/79228917     groundobj_t::random_groundobj_for_climate(climate, signed char) [177]

--------------
                1.86 8838.05     100/100         karte_t::distribute_groundobjs_cities(int, short, short) [6]
[27]     8.8    1.86 8838.05     100         stadt_t::random_place(karte_t const*, int, short, short) [27]
                0.60 8824.66     100/100         karte_t::finde_plaetze(short, short, climate_bits, short, short) const [28]
                0.97    6.77   51200/54551       weighted_vector_tpl<koord>::remove(koord) [237]
                1.10    0.79 37050074/37050074     slist_tpl<koord>::remove_first() [362]

patched

Code: [Select]

               68.95 5786.79     100/100         karte_t::enlarge_map(einstellungen_t*, signed char*) [4]
[5]     53.2   68.95 5786.79     100         karte_t::distribute_groundobjs_cities(einstellungen_t const*, short, short) [5]
                0.00 2256.80   16866/21638       wegbauer_t::calc_route(koord3d const&, koord3d const&) [6]
              376.41 1561.93     100/100         stadt_t::random_place(karte_t const*, vector_tpl<int> const*, unsigned int, unsigned int, short, short) [12]
                0.08  642.40     100/100         karte_t::create_rivers(short) [25]
                0.01  585.30   12800/12800       stadt_t::stadt_t(spieler_t*, koord, int) [27]
               23.66  109.43 628365130/867552698     karte_t::lookup_kartenboden(koord) const [11]

-----------------
              376.41 1561.93     100/100         karte_t::distribute_groundobjs_cities(einstellungen_t const*, short, short) [5]
[12]    17.6  376.41 1561.93     100         stadt_t::random_place(karte_t const*, vector_tpl<int> const*, unsigned int, unsigned int, short, short) [12]
                1.67  709.43     100/100         karte_t::finde_plaetze(short, short, climate_bits, short, short) const [24]
              161.64    0.00 3538043483/1442927365     array2d_tpl<double>::at(unsigned int, unsigned int) [47]

Results are strange. karte_t::finde_plaetze should take almost equal time in in patched and unpatched versions. Bot it is not.
Some for stadt_t::stadt_t.

Re: New city generation function.

Reply #21 – July 11, 2010, 09:39:12 am

With the patch, I notice quite a number of things with very greatly increased values, for example, "stadt_t::random_place(karte_t const*, vector_tpl<int> const*, unsigned int, unsigned int, short, short) [12]" increases from 1.86 to 376.41, or from 8.8% of time taken to 17.6%. Do you find that this has a noticable impact on real-world performance?

Edit: I have tried applying this patch to the latest version of -devel, but it appears that recent changes to the code merged in from Standard break this patch so that it can no longer be applied. Do you think that you could post an updated patch (or, better yet, create a Github branch and use that instead)?

Re: New city generation function.

Reply #22 – July 12, 2010, 05:20:29 am

Quote from: jamespetts – on July 11, 2010, 09:39:12 am

With the patch, I notice quite a number of things with very greatly increased values, for example, "stadt_t::random_place(karte_t const*, vector_tpl<int> const*, unsigned int, unsigned int, short, short) [12]" increases from 1.86 to 376.41, or from 8.8% of time taken to 17.6%. Do you find that this has a noticable impact on real-world performance?

I find stadt_t::random_place execution time almost irrelevant. Total map generation time very depends on settings. When default settings are used ( upatched: N cities; patched: N cities, one big) my version is faster.
Compare 629.61 sec/map with 57.86 sec/map. When I use 'all cities are big' it is not so.

Another setting 'intercity road length' eat time pretty fast too.

Quote from: jamespetts – on July 11, 2010, 09:39:12 am

I have tried applying this patch to the latest version of -devel, but it appears that recent changes to the code merged in from Standard break this patch so that it can no longer be applied. Do you think that you could post an updated patch (or, better yet, create a Github branch and use that instead)?

I'll do it when my home ISP recover from recent thunderstorm. It fired the big part of access network. I don't have Internet access at home now.

Re: New city generation function.

Reply #23 – July 12, 2010, 08:31:18 pm

Done http://github.com/inkelyad/simutrans-experimental

Re: New city generation function.

Reply #24 – July 13, 2010, 09:57:24 pm

Inkelyad,

thank you very much for this. I notice that you include the new city settings in "einstellungen.cc" rather than "umgebung.cc"; was there a particular reason for this? The settings in relation to cities are used only when a new map is generated; they do not, therefore, need to be loaded and saved with saved games or transmitted accross the network in network multiplayer games (when that feature is finalised); or am I missing something?

Re: New city generation function.

Reply #25 – July 14, 2010, 03:13:07 am

Quote from: jamespetts – on July 13, 2010, 09:57:24 pm

thank you very much for this. I notice that you include the new city settings in "einstellungen.cc" rather than "umgebung.cc"; was there a particular reason for this?

No. It was analogy. anzahl_staedte is in einstellungen => all others city-related setting must be in einstellungen too.

Re: New city generation function.

Reply #26 – July 16, 2010, 11:59:05 pm

I have moved settings to umgebung_t (see github repository)

Re: New city generation function.

Reply #27 – July 17, 2010, 01:32:18 pm

Inkelyad,

I have finally got around to trying this: see my -devel branch for it integrated with two minor changes (a compile error fix and some slight alterations to GUI text). I very much liked the functionality, especially the "cities like water" settings, which make for a much improved map generation experience. This will make it much easier to play in the pre-canal era with boats on rivers and the sea.

One or two things still need to be done, I think: firstly, there needs to be a way of saving the values entered for "city cluster size", "cities like water", etc. between sessions, in the same way as "number of cities" is saved between sessions. There are two possibilities here. Either the values can be read from simuconf.tab (which might require adding some of the code for reading the values to einstellugen.cc), in which case, pakset authors can determine the default settings, or they need to be saved to settings.xml by using the rdwr function in umgebung.cc (and, in that case, it needs to check for an experimental saved game version number greater or equal to 9). I should be interested in people's comments as to which of the two is preferable.

Edit: One problem that I have noticed with this, however, is that it very often does not produce the number of cities stipulated. I stipulated 200 cities, for example, and it produced about 25. This was with city cluster size 50, 3 clusters and 3 big cities, with "cities like water" at 60%.

Re: New city generation function.

Reply #28 – July 17, 2010, 04:38:57 pm

Quote from: jamespetts – on July 17, 2010, 01:32:18 pm

One problem that I have noticed with this, however, is that it very often does not produce the number of cities stipulated. I stipulated 200 cities, for example, and it produced about 25. This was with city cluster size 50, 3 clusters and 3 big cities.

There is not enough room for 200 cities. cluster size 50 is very small cluster.
Define DBG_WEIGHTMAP(used in unutils/dbg_weightmap.*) in compilation flags and look for generated .pgm files.
I don't know how work in Windows compilation environment.

Re: New city generation function.

Reply #29 – July 17, 2010, 06:13:45 pm

Inkelyad,

if there is not enough room for the number of cities specified, the game should give some feedback to explain the reason that the user's settings are not being respected. The previous behaviour was always to build the number of cities stipulated.

Re: New city generation function.

Reply #30 – July 17, 2010, 06:25:59 pm

What is the best way to do it? I don't know how GUI works to call message box directly from stadt_t::random_place.

relevant code is

Code: [Select]

                if (index_to_places.empty() ) {
                        if(city_nr < sizes_list->get_count() - 1) {
                                dbg->warning("stadt_t::random_place()", "Not enough places found!");
                        }
                        break;
                }

Edit: Another way is to place rest of cities outside of clusters.

Re: New city generation function.

Reply #31 – July 17, 2010, 08:57:44 pm

Hmm, I don't remember off the top of my head how to generate a GUI message: if I were doing it, I'd look to see how it is done elsewhere in the code by searching through the project to find the untranslated string of just such a message.

It is indeed a good idea to build cities outside clusters rather than fail to build cities at all, although the user should probably still be given some warning that it has failed. Also, can it be predicted the minimum cluster size that any given number of cities can tolerate? If so, the allowable number of cities and/or cluster sizes can be adjusted in the GUI.

In any event, thank you again for all your work on this: it does really make a difference to map generation!

Re: New city generation function.

Reply #32 – July 17, 2010, 09:32:31 pm

Quote from: jamespetts – on July 17, 2010, 08:57:44 pm

It is indeed a good idea to build cities outside clusters rather than fail to build cities at all,

Changes pushed to github. No warning message, sorry.

Quote from: jamespetts – on July 17, 2010, 08:57:44 pm

Also, can it be predicted the minimum cluster size that any given number of cities can tolerate?

I don't think so. Real cluster size depends on central city population (bigger city -> bigger cluster around it).
And it is random.

Re: New city generation function.

Reply #33 – July 18, 2010, 10:28:30 am

Inkelyad,

thank you for doing this: however, it appears that the new code has a bug, in that all of the cities generated outside clusters have only a town hall and no city buildings. Do you think that you could look into this? Thank you again for all your efforts in this respect.

Edit: I tried generating without any clusters, and still had some townhall-only cities, so it may not be a clusters issue. Really, there should never be any townhall-only cities at all, as these do not make sense. Perhaps it is something to do with the number of "big cities"?

Re: New city generation function.

Reply #34 – July 18, 2010, 11:23:41 am

City placement go from big city to smaller. Any city outside of clusters will be very small.

'big cities' use 'Median citizens per city' for population (+- gaussian noise).
n-th city after that will use 'Median citizens per city'/n for population (+- gaussian noise again).
(See my posts about Zipf distributions)

It seems city growth engine think that city hall is enough for population less then ~320.