Optimising map creation

[jamespetts]

I am quite keen on playing on larger maps (> 1024x1024), and with a larger scale in terms of economics than 1km/tile (closer to 200m/tile), but I find that the map generation gets exponentially slower the larger that the map is, and, in particular, the more cities that are added. That means that a map that can be handled perfectly well by a reasonably high performance modern desktop computer once it is generated will take an unreasonable amount of time to generate.

A large part of the problem seems to be the city generation code, and in particular the way in which it works out if it is too close to an existing city: this system checks the distance from every possible city building point to every city already built for every considered location, causing the number of iterations to increase exponentially with the number of cities. With a debug build and the breakpoint set to break every 4096 hits, I was waiting about ten seconds between the breakpoints being triggered. After about five minutes of map generating (before I had set the breakpoint), there were still over 70,000 iterations to perform. The relevant part of the code (including my latest addition for preferring city locations on lower ground) is reproduced below:

Code Select Expand


// geeigneten platz zur Stadtgruendung durch Zufall ermitteln
// "determine suitable place to the city foundation through chance" (Google)
// "anzahl" = "amount" (Google)
vector_tpl<koord>* stadt_t::random_place(const karte_t* wl, const sint32 anzahl, sint16 old_x, sint16 old_y)
{
int cl = 0;
for (int i = 0; i < MAX_CLIMATES; i++)
{
if (hausbauer_t::get_special(0, haus_besch_t::rathaus, wl->get_timeline_year_month(), false, (climate)i))
{
cl |= (1 << i);
}
}

// For clustering cities by climate type, we need a list of at least 4x the number of sites actually needed
// for towns so that, from that expanded list, the final locations can be chosen.
const sint32 multiplied_number = anzahl * 4;

DBG_DEBUG("karte_t::init()", "get random places in climates %x", cl);
slist_tpl<koord>* list = wl->finde_plaetze(2, 3, (climate_bits)cl, old_x, old_y);
DBG_DEBUG("karte_t::init()", "found %i places", list->get_count());
weighted_vector_tpl<koord>* pre_result = new weighted_vector_tpl<koord>(multiplied_number);

for (int i = 0; i < multiplied_number; i++)
{
int len = list->get_count();
// check distances of all cities to their respective neightbours
while (len > 0)
{
int minimum_dist = 0x7FFFFFFF;  // init with maximum
koord k;
const int index = simrand(len);
k = list->at(index);
list->remove(k);
len--;

// check minimum distance
for (int j = 0; (j < i) && minimum_dist > minimum_city_distance; j++)
{
int dist = koord_distance( k, (*pre_result)[j] );
if (minimum_dist > dist)
{
minimum_dist = dist;
}
}
if (minimum_dist > minimum_city_distance)
{
// all cities are far enough => ok, find next place
const sint16 height_above_water = welt->lookup_hgt(k) - welt->get_grundwasser();
uint32 weight;
switch(height_above_water)
{
case 1:
weight = 24;
break;
case 2:
weight = 22;
break;
case 3:
weight = 16;
break;
case 4:
weight = 12;
break;
case 5:
weight = 10;
break;
case 6:
weight = 9;
break;
case 7:
weight = 8;
break;
case 8:
weight = 7;
break;
case 9:
weight = 6;
break;
case 10:
weight = 5;
break;
case 11:
weight = 4;
break;
case 12:
case 13:
weight = 3;
break;
case 14:
case 15:
weight = 2;
break;
default:
weight = 1;
};
pre_result->append(k, weight);
break;
}
// if we reached here, the city was not far enough => try again
}

if (len <= 0 && i < anzahl - 1)
{
dbg->warning("stadt_t::random_place()", "Not enough places found!");
break;
}
}
list->clear();
delete list;

vector_tpl<koord>* result = new vector_tpl<koord>(anzahl);

uint16 weight = 0;
const uint16 total_weight = pre_result->get_sum_weight();
for (int i = 0; i < anzahl; i++)
{
// Now produce the real results from the pre-list.
weight = simrand(total_weight);
if(!result->append_unique(pre_result->at_weight(weight)))
{
i--;
}
}

pre_result->clear();
delete pre_result;

return result;
}


The Simutrans-Standard version does not have a pre_result, or the last for loop, or the switch case statement and the two preceding statements, and at that point instead simply adds the koord k to the "result" list, but is otherwise substantially the same.

I am not much of a mathematician, and my low-level programming abilities are somewhat limited, so I should be very grateful for any thoughts on how to make city generation take a sane amount of time at map generation. There must, surely, be a better way of doing it than the brute force method above? I should be extremely grateful for any suggestions about how to address this issue.

[Dwachs]

I doubt that the computational effort grows exponentially with map size and city number. If the map has size NxN, then a worst case estimate would be N^4 for the number of iterations.

I agree however, that for a large number of cities the time spend in this routine will become significant.

Edit: In contrast to your observation, I think the map generation time for a large number of cities is dominated by the routine that builds the intercityroads.

[Severous]

Do trees in forests take much computer effort..to generate (I doubt)..or to maintain..(perhaps?). 

Fewer forests perhaps?  I don't think gameplay would be hurt by having fewer trees..currently there seems more than enough.

[jamespetts]

Dwachs,

do you think that it could be optimised all the same?

[Dwachs]

I suppose (*) that most of the work is spend finding paths to build the roads. In the second phase of the road construction, there is also a test-vehikel driving around.

You can try whether it helps to change line 992 in simworld.cc to

Code Select Expand

while( phase < 1  ) {

Then only a tree-like road net is build. I.e. it will not contain any loops.

(*) guessing, no profiling done

[jamespetts]

Dwachs,

I don't think that it can be mainly the road-building algorithm, since, as stated above, when I put a breakpoint in the particular bit of code quoted above (which does nothing other than calculate where to put cities), it showed that that part took a very long time to complete: about ten seconds for each 4096 iterations, and there were over 70,000 iterations left to run after five minutes. Is there any way that that particular algorithm can be optimised?

[Dwachs]

What are your map settings? Size and city number?

[prissi]

City growth can take a considerate amount, when cities become very large (>30000). Then the normal growth routine (which tries to avoid similar buildings next to each other) tries to upgrade many buildings and just realize each time an update is futile. But of course the chances of finding an empty place within the city limits or a place where a building can be upgraded is less and less likely the higher the total number of inhabitants is. In such a case the progress bar stalls at the very beginning.

Intercityroad creating was sped up quite a bit by your work Daniel ... Route search for a vehicle is fast, since less than 1000 tiles needs to tested, while for way search on a 1000*1000 map up to a millions possible tiles could exist. THis is now not too bad. Industry creation could take a long time; but, on the other hand on a large map there is also a higher chance of a suitable ground somewhere. Industry creation stall the progress bar at the very end.

I do not deny the possibility of optimising this; however, reusing existing code seems much more better in terms of stability.

One could think of making it feel faster by giving more feedback, i.e. writing crating map/creating cities/built intercity roads/Creating industry/distributing trees.

[knightly]

I don't think that it can be mainly the road-building algorithm, since, as stated above, when I put a breakpoint in the particular bit of code quoted above (which does nothing other than calculate where to put cities), it showed that that part took a very long time to complete: about ten seconds for each 4096 iterations, and there were over 70,000 iterations left to run after five minutes. Is there any way that that particular algorithm can be optimised?

James, I think you are exaggerating the problem here. When you run Simutrans from Visual Studio, the part of code where you have set breakpoints will run slower, especially if they are conditional breakpoints. I also have similar experiences before while debugging.

[hApo]

I think that jamespetts is right. My computer isn't so bad and it takes more than 10 minutes to generate the map 1024x1024

[Dwachs]

Please write also, how many cities and industry chains are to be created.

[prissi]

Just increase the mean city size and see how much longer in takes, even with a single city. Please James, the debug mode in MSVC does not even use inlines, this is about 3-5 times slower in certain cases than the normal release compile. One really needs to do profiling.

Only one city mean 160000 inhabitants 1024*1024 map: Most of the time is spend in bewerte_loc, i.e. in finding suitable place for houses.

Code Select Expand


Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
time   seconds   seconds    calls   s/call   s/call  name   
21.31      5.93     5.93 252620208     0.00     0.00  int_noise(long, long)
  7.97      8.15     2.22 11095303     0.00     0.00  stadt_t::bewerte_loc(koord, char const*, int)
  4.63      9.45     1.29  1218599     0.00     0.00  baum_t::random_tree_for_climate_intern(climate)
  2.91     10.26     0.81  1912087     0.00     0.00  baum_t::get_anzahl_besch(climate)
  2.71     11.01     0.76 28068912     0.00     0.00  smoothed_noise(int, int)
  2.59     11.73     0.72 80003038     0.00     0.00  koord::koord(short, short)
  2.51     12.43     0.70 63077281     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  2.44     13.11     0.68 207508567     0.00     0.00  vector_tpl<baum_besch_t const*>::operator[](unsigned int)
  2.17     13.72     0.60   260760     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  2.15     14.32     0.60 62999129     0.00     0.00  planquadrat_t::get_kartenboden() const
  1.94     14.86     0.54 58813427     0.00     0.00  karte_t::lookup(koord) const
  1.94     15.40     0.54  2423717     0.00     0.00  grund_t::calc_back_bild(signed char, signed char)
  1.69     15.87     0.47 166454793     0.00     0.00  baum_besch_t::is_allowed_climate(climate) const
  1.62     16.32     0.45  7017228     0.00     0.00  interpolated_noise(double, double)
  1.47     16.73     0.41 169585479     0.00     0.00  vector_tpl<baum_besch_t const*>::get_count() const
  1.33     17.09     0.37 27906358     0.00     0.00  karte_t::ist_in_gittergrenzen(short, short) const
  1.31     17.46     0.36 15396385     0.00     0.00  simrand_plain()
  1.08     17.76     0.30 17826879     0.00     0.00  simrand(unsigned int)
  0.90     18.01     0.25 42976248     0.00     0.00  karte_t::lookup_kartenboden(koord) const
  0.86     18.25     0.24   744919     0.00     0.00  stadt_t::baue()
  0.79     18.47     0.22  8078627     0.00     0.00  dingliste_t::get_top() const
  0.72     18.67     0.20  1169538     0.00     0.00  perlin_noise_2D(double, double, double)
  0.68     18.86     0.19  1241397     0.00     0.00  karte_t::ist_platz_frei(koord, short, short, int*, climate_bits) const
  0.66     19.05     0.19 21051684     0.00     0.00  linear_interpolate(double, double, double)
  0.63     19.22     0.17  2052633     0.00     0.00  baum_t::plant_tree_on_coordinate(karte_t*, koord, unsigned char)
  0.56     19.38     0.16    24675     0.00     0.00  MTgenerate()
  0.54     19.52     0.15  2372596     0.00     0.00  grund_besch_t::get_ground_tile(signed char, short)
  0.50     19.66     0.14 14654207     0.00     0.00  koord3d::get_2d() const
  0.50     19.81     0.14 14461618     0.00     0.00  operator+(koord const&, koord const&)
  0.50     19.95     0.14   162026     0.00     0.00  get_aus_liste(vector_tpl<haus_besch_t const*> const&, int, unsigned short, climate)
  0.47     20.07     0.13  1054850     0.00     0.00  karte_t::raise_clean(short, short, short)
  0.47     20.20     0.13       68     0.00     0.07  baum_t::create_forest(karte_t*, koord, koord)
  0.45     20.33     0.13  2294136     0.00     0.00  karte_t::max_hgt(koord) const
  0.45     20.45     0.13   925329     0.00     0.00  pixcopy(unsigned short*, unsigned short const*, unsigned int)
  0.43     20.57     0.12  6256792     0.00     0.00  operator==(koord const&, koord const&)
  0.43     20.70     0.12  1218599     0.00     0.00  baum_t::baum_t(karte_t*, koord3d)
  0.43     20.82     0.12        2     0.06     0.90  karte_t::cleanup_karte(int, int)
  0.43     20.93     0.12        2     0.06     4.37  karte_t::distribute_groundobjs_cities(int, short, short)
  0.39     21.05     0.11  3607547     0.00     0.00  freelist_t::gimme_node(unsigned int)
  0.39     21.16     0.11  2290187     0.00     0.00  dingliste_t::loesche_alle(spieler_t*, unsigned char)
  0.38     21.26     0.11       31     0.00     0.00  setsimrand(unsigned int, unsigned int)
  0.36     21.36     0.10   553433     0.00     0.00  binary_heap_tpl<route_t::ANode*>::pop()
  0.36     21.46     0.10    21986     0.00     0.00  display_text_proportional_len_clip(short, short, char const*, int, unsigned short, long)
  0.36     21.56     0.10       32     0.00     0.06  wegbauer_t::intern_calc_route(vector_tpl<koord3d> const&, vector_tpl<koord3d> const&)
  0.36     21.66     0.10                             _Unwind_SjLj_Unregister
  0.32     21.75     0.09  8306545     0.00     0.00  haus_besch_t::is_allowed_climate(climate) const
all other are less than 0.3% contribution


So height calculation takes aparently a lot of time on large maps (21 second!) and next is the test if a tile is suitable for building/road etc (which cannot be skipped, since it is at the core of the town generation rules.)

[Spike]

So height calculation takes aparently a lot of time on large maps (21 second!) and next is the test if a tile is suitable for building/road etc (which cannot be skipped, since it is at the core of the town generation rules.)

Wouldn't that be 5.9s for the map height calculation, and 21% of the overall time? Still the dominant factor in this map.

[prissi]

Sorry of course, I swapped the numbers.

Now 16 large towns, same setting (largest twon was actually 635000 inhabitants and filled 128X128 squares), 8000 intercityroads, no industry. I am afraid, both routines int_noise and bewerte_loc are nearly a simple as they could get. The only way out would be to call them less, which is possible for int_noise but I think is difficult for bewerte_loc (since if I know beforehand, what to put there, I would not need to call it to find out ... ). One can think to select the right rotation of the rules beforehand, that might save some time.

(The removing is there, because I also deleted the map during quitting of course.)

Code Select Expand


Each sample counts as 0.01 seconds.
 %   cumulative   self              self     total          
time   seconds   seconds    calls   s/call   s/call  name    
28.87     31.30    31.30 162455421     0.00     0.00  stadt_t::bewerte_loc(koord, char const*, int)
 6.58     38.42     7.13 517413273     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
 5.25     44.12     5.69 243772848     0.00     0.00  int_noise(long, long)
 3.44     47.84     3.73 466915735     0.00     0.00  karte_t::lookup_kartenboden(koord) const
 3.34     51.47     3.62 513160236     0.00     0.00  karte_t::lookup(koord) const
 2.80     54.49     3.03 497365158     0.00     0.00  planquadrat_t::get_kartenboden() const
 2.09     56.77     2.27  9200337     0.00     0.00  stadt_t::baue()
 1.93     58.85     2.09 118149050     0.00     0.00  simrand(unsigned int)
 1.68     60.67     1.82   260745     0.00     0.00  weighted_vector_tpl<gebaeude_t*>::remove(gebaeude_t*)
 1.57     62.38     1.70 218311104     0.00     0.00  koord::koord(short, short)
 1.42     63.91     1.53 82555141     0.00     0.00  simrand_plain()
 1.13     65.14     1.23   260745     0.00     0.00  weighted_vector_tpl<gebaeude_t*>::remove_at(unsigned int)
 1.10     66.33     1.19  1373449     0.00     0.00  get_aus_liste(vector_tpl<haus_besch_t const*> const&, int, unsigned short, climate)
 1.08     67.50     1.17  1295324     0.00     0.00  baum_t::random_tree_for_climate_intern(climate)
 0.96     68.55     1.04   521289     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
 0.96     69.58     1.04 31614650     0.00     0.00  grund_t::first_obj() const
 0.96     70.63     1.04                             __dynamic_cast
 0.89     71.58     0.96 71757196     0.00     0.00  haus_besch_t::is_allowed_climate(climate) const
 0.87     72.53     0.94 105140918     0.00     0.00  grund_t::get_weg(waytype_t) const
 0.76     73.35     0.82 27085872     0.00     0.00  smoothed_noise(int, int)
 0.75     74.16     0.81 220450746     0.00     0.00  vector_tpl<baum_besch_t const*>::operator[](unsigned int)
 0.72     74.94     0.78  2033806     0.00     0.00  baum_t::get_anzahl_besch(climate)
 0.70     75.69     0.76   132301     0.00     0.00  MTgenerate()
 0.68     76.44     0.74 164966441     0.00     0.00  koord::koord()
 0.64     77.13     0.69      228     0.00     0.04  wegbauer_t::intern_calc_route(vector_tpl<koord3d> const&, vector_tpl<koord3d> const&)
 0.62     77.80     0.67  3041528     0.00     0.00  binary_heap_tpl<route_t::ANode*>::pop()
 0.59     78.44     0.64    19227     0.00     0.00  slist_tpl<weg_t*>::remove(weg_t*)
 0.59     79.07     0.64 40637329     0.00     0.00  stadt_t::bewerte_pos(koord, char const*)
 0.58     79.70     0.63 71482193     0.00     0.00  koord3d::get_2d() const
 0.57     80.32     0.62 42296438     0.00     0.00  karte_t::ist_in_gittergrenzen(short, short) const
 0.54     80.91     0.59 37719012     0.00     0.00  operator==(koord const&, koord const&)
 0.52     81.47     0.56  6771468     0.00     0.00  interpolated_noise(double, double)
 0.46     81.97     0.50 47373792     0.00     0.00  grund_t::get_hoehe() const
 0.46     82.47     0.50  3948750     0.00     0.00  grund_t::calc_back_bild(signed char, signed char)
 0.45     82.96     0.49 42689537     0.00     0.00  stadt_t::bewerte_haus(koord, int, char const*)
 0.44     83.44     0.48 177035343     0.00     0.00  baum_besch_t::is_allowed_climate(climate) const
 0.44     83.92     0.48 29480525     0.00     0.00  stadt_t::was_ist_an(koord) const
 0.42     84.37     0.45 43789975     0.00     0.00  grund_t::hat_wege() const
 0.42     84.82     0.45 14210234     0.00     0.00  grund_t::get_vmove(koord) const
 0.37     85.22     0.40 180364473     0.00     0.00  vector_tpl<baum_besch_t const*>::get_count() const
 0.37     85.62     0.40  3630522     0.00     0.00  hausbauer_t::get_special(int, haus_besch_t::utyp, unsigned short, bool, climate)
 0.35     86.00     0.38  3258671     0.00     0.00  wegbauer_t::is_allowed_step(grund_t const*, grund_t const*, long*)
 0.33     86.36     0.36 156859342     0.00     0.00  boden_t::get_typ() const
 0.33     86.72     0.36  1179221     0.00     0.00  stadt_t::bewerte_res_com_ind(koord, int&, int&, int&)
 0.32     87.07     0.35 54269426     0.00     0.00  route_t::ANode::operator<=(route_t::ANode) const
 0.31     87.41     0.34  1190069     0.00     0.00  stadt_t::renoviere_gebaeude(gebaeude_t*)
 0.30     87.74     0.33 12870082     0.00     0.00  marker_t::ist_markiert(grund_t const*) const
 0.30     88.07     0.33                             __cxxabiv1::__si_class_type_info::__do_dyncast(int, __cxxabiv1::__class_type_info::__sub_kind, __cxxabiv1::__class_type_info const*, void const*, __cxxabiv1::__class_type_info const*, void const*, __cxxabiv1::__class_type_info::__dyncast_result&) const
 0.30     88.39     0.32 52712918     0.00     0.00  dingliste_t::bei(unsigned char) const
 0.30     88.71     0.32 32467794     0.00     0.00  karte_t::lookup_hgt(koord) const
and rest with less than 0.3%


[Spike]

I feel uncertain if optimizing map creation is really a priority, maps are created only so often, but played for hours, days and weeks, so overall it doesn't seem important that map creation is particularly fast. But since I know that map creation sometimes creates bad map, people need to redo this step, and then it's understandable that they want it fast - but actually, wouldn't they rather want good maps in the first creation step, and then accept a longer wait?

(From experience I know that people sometimes demand one thing, but actually they want this just to achieve something. So if one gives them other ways to achieve what they want, it also solves the need for the one thing ...)

[prissi]

THis is why I was thinking of more feedback was probably also helpful in this case.

[gerw]

What I've observed, is the following:
If you have a high number of industry chains (maybe 40 on a 512x512 map (and 8 cities a 1 inhabitant)), most of the industry can be found on a small part of the map. Roughly more than 1/2 of the industries can be found on 1/9 of the map.

The worst I've get in 3 runs (The factories that aren't in the lower left corner, are only some non-consuming power plants):

[jamespetts]

Ahh, some very interesting discussion. Thank you Prissi for explaining the way that this all works and what can and cannot be optimised. Any optimisation of the parts that can be optimised would be most welcome. I also agree that visual feedback of the process would make a big difference. Currently, if a user generates a large map and, while waiting for it to work, clicks away from the Simutrans window, the window will not respond when the user returns to it until the map generation is finished. If the window were to become responsive and show positive (even if small) progress on each return, this would significantly enhance the user experience.

I appreciate the point about the debugger making things slower, especially if breakpoints are set. However, when I set the breakpoints, the map generation had already been running for about five minutes with no breakpoint set. I was concerned that my new code had caused some infinite loop, so I set the breakpoints only to find that it was going very slowly through that part of the code. There is still some room for trying to optimise that part, I think.

Gerw,

interesting results with the industry. Why do you think that it behaves like that?

Edit: To answer Prissi's original questions, I do not currently have the exact numbers to hand as I am at work, but I did indeed set the cities to have a large size. Since the idea is to increase the scale of Simutrans, in effect, it is necessary to have larger cities. Also, in order to have a reasonable city density, it is necessary to increase the number of cities in line with the increase in the size of the map.

[Spike]

interesting results with the industry. Why do you think that it behaves like that?

I think that is because new industries spawn within a certain radius around the "parent" industry.

Imagine a circle, take a random point in the circle and draw another circle around that point. Repeat with a point in the new circle.

If you are kinda unlucky with your random points, the circles will overlap much, and results are as Gerw has experienced. I think it is inherent to the system, just not obvious unless you do the circle game.

[Dwachs]

What I've observed, is the following:
If you have a high number of industry chains (maybe 40 on a 512x512 map (and 8 cities a 1 inhabitant)), most of the industry can be found on a small part of the map. Roughly more than 1/2 of the industries can be found on 1/9 of the map.

This should be fixed in rev 2589, it was due to a wrong initialization of the number of inhabitants in an array that carries the positions of cities weighted by their inhabitant number. If simutrans wants to generate a city with a very small number of inhabitants (0, 1 or so), it in fact creates a city with at least 126 inhabitants (pak64?) due to the townhall. The bug was, that the wrong number (the small one) was used as weight, resulting in a weight=0 for some cities, which made it impossible to found an industry chain there.

@James:
One can surely optimize the routine you mentioned. Using some ordering (w.r.t. to the x-coordinate) of the positions vector.

[jamespetts]

Dwachs,

thank you for your suggestion (and for your fix). Can you elaborate on what you mean by "w. r. t. to the x-coordinate" here? As stated in the first post, I am somewhat shaky on low-level programming and advanced mathematics...

[TrainMith]

Borrowing from a computer science algorithms book, I am wondering if R-trees would work better for city and industry situations?  Have not completely put enough thought into this, but I'll mention it for now and consider it later.

Btw, the nightly r2610 seemed to prefer generating industries in very small and tight groups.  Most times, on a 1024x1024 pak128 map with only 3 or 4 industry chains specified in the options, a single group appears nearby to only one city.  Occasionally 2 or 3 groups appear nearby 2 or 3 cities, a group per city, with the largest containing 15 or 25 industry buildings in a very small area.

Update:
@Dwachs:  Whatever fix might have been applied back in r2589 has definitely not corrected the problem in r2610.  I have yet to grab r2611, though.

[jamespetts]

You can specify a minimum distance between industries in simuconf.tab (or perhaps citurules.tab - I forget which off the top of my head).

[mjhn]

Last time I check minimm distance between industries seemed to be the minimum between any pair of industries, not just those in a given industry chain, and then given that restriction the industry builder seems to build them as close together as possible. I once tried to make the minimum spacing large enough to force the industries to be in seperate cities, but then the game crashed when it ran out of space for industries.

What we need is a seperate option for the average distance between two industries in the same chain.