[Bug] Inter-city roads not built (R2489 and probably previous)

[jamespetts]

Following a bug report of the latest version of Simutrans-Experimental that inter-city roads were not being built (topic here), I found that the problem also appears in Simutrans-Standard R2489. No inter-city roads are generated on map creation with any settings.

[whoami]

Whenever you publish a new STE version, please tell us the revision of ST-main that it matches with most closely. This should make it easier to compare the behaviour of both when testing.

[Dwachs]

Should be fixed in rev 2490. However this 'bug' did not appear for large enough values of intercity-road-length in the new-world dialogue. I.e. length=8000 worked for me on a 256x256 map.

[jamespetts]

Whoami,

that is not as easy as I'd like it to be, because the R-numbers are not present in the code or the comments by the time that they get to the Git mirror that I use...

[jamespetts]

Ahh, I'm afraid that this hasn't fixed the problem, I'm sorry: Simutrans-Standard at R2490 will not create inter-city roads. I tested with the following settings:

• Pak128
• 256x256 map
• 16 cities
• Inter-city road length: 7,000

I ran the test several times: not a single inter-city road was created.

[Dwachs]

thank you. It was due to different sizes of the townhalls. I hope it is fixed in 2491.

[z9999]

Did you test in r2491 ?
I tested it with default settings of pak64.
It was full of roads and bridges. Too bad.

Please back to old behavior.

[gerw]

It should be sufficient, to set 'intercity road length' to a much smaller value, e.g. 50. Now it's the tile distance between cities and not further the squared euclidean distance.

[Dwachs]

I suggest using 1.5 or 2 times map size.

[z9999]

Please don't change the game design.

[gerw]

I suggest using 1.5 or 2 times map size.

This is way to much. Using this values, you will see the evil side of the waybuilder

[Dwachs]

Please don't change the game design.

This is not about game design. It is about bugs and inconsistencies - fixing these or living with these.

It was IMHO completely unlogical to chose an seemingly arbitrary large number to at least generate a few intercity roads. Now one chooses some kind of maximal distance for these intercity roads.

I think a complete overhaul of algorithm to generate this roads is necessary. Not generating roads between all cities but only to neighboring cities using triangulation or spanning-tree algorithms.

[jamespetts]

I agree with Dwachs that the new lower numbers make more sense. And I shall be very interested to see a proper road building algorithm - that would be intriguing! Also on the subject of road building - has any thought been given to a mechanism, in cases where not all cities are linked at the outset, for the public player automatically to add roads between cities one by one as the game progresses, if the player chooses that option?

[z9999]

I think a complete overhaul of algorithm to generate this roads is necessary. Not generating roads between all cities but only to neighboring cities using triangulation or spanning-tree algorithms.

I agree with that.

But current your design makes too many separated ways and bridges than older versions.
This is really bad.

[gerw]

But current your design makes too many separated ways and bridges than older versions.

It's the same with old versions, if you choose high numbers. Try 131072(=2*256^2) on a 256x256 map and you will observe the same.

[z9999]

We can't choose more than 9999.
And we should compare the normal settings which many player use.

[gerw]

Then the input field (and default value) has to be adopted, too.

[Dwachs]

I will try something like minimum spanning tree etc. this evening. This should give reasonable raod network for all values of the input parameter.

[Dwachs]

Here is a patch. The intercity-road-length is taken as maximal length of roads.

In phase=1 a minimal spanning tree is built. If you change the while condition to 'phase<1' only this step is performed.

In the second phase additional roads are built. Before each attempt to build, it checkes whether the given cities are already connected.

This is kind of proof of concept. Not aimed at performance. So expect that map creation takes some time if you chose to create a large number of cities (>40). The smaller the intercity-road-length the faster should be the map creation process.

Code Select Expand

Index: simworld.cc
===================================================================
--- simworld.cc (revision 2493)
+++ simworld.cc (working copy)
@@ -923,6 +923,8 @@
bauigel.set_keep_existing_ways(true);
bauigel.set_maximum(umgebung_t::intercity_road_length);

+
+
int old_progress_count = 16+2*new_anzahl_staedte;
int count = 0;
const int max_count=(einstellungen->get_anzahl_staedte()*(einstellungen->get_anzahl_staedte()-1))/2
@@ -942,8 +944,134 @@
k.append( koord3d::invalid );
}
}
-
+ // compute all distances
+ uint8 conn_comp=1; // current connection component for phase 0
+ vector_tpl<uint8> city_flag; // city already connected to the graph? >0 nr of connection component
+ array2d_tpl<sint32> city_dist(einstellungen->get_anzahl_staedte(), einstellungen->get_anzahl_staedte());
for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
+ for (int j = max(i + 1, old_anzahl_staedte); j < einstellungen->get_anzahl_staedte(); j++) {
+ city_dist.at(i,j) = koord_distance(k[i], k[j]);
+ city_dist.at(j,i) = city_dist.at(i,j);
+ }
+ city_flag.append( i < old_anzahl_staedte ? 1 : 0 );
+ }
+ if (old_anzahl_staedte==0) city_flag[0]=true;
+
+ // get a default vehikel
+ route_t verbindung;
+ fahrer_t* test_driver;
+ vehikel_besch_t test_drive_besch(road_wt, 500, vehikel_besch_t::diesel );
+ test_driver = vehikelbauer_t::baue(koord3d(), spieler[1], NULL, &test_drive_besch);
+
+ bool ready=false; uint8 phase=0; // 0 - min span tree , 1- completion
+ while(phase<2) {
+ ready = true;
+ koord conn = koord::invalid;
+ sint32 best = umgebung_t::intercity_road_length;
+
+ if (phase==0) {
+ // loop over all unconnected cities
+ for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
+ if (city_flag[i]==conn_comp) {
+ // loop over all connections to connected cities
+ for(int j = old_anzahl_staedte; j < einstellungen->get_anzahl_staedte(); j++) {
+ if (city_flag[j]==0) {
+ ready=false;
+ if ( city_dist.at(i,j) < best ) {
+ best = city_dist.at(i,j);
+ conn = koord(i,j);
+ // printf("Best so far: %8d ... %s --> %s\n", best, stadt[j]->get_name(), stadt[i]->get_name());
+ }
+ }
+ }
+ }
+ }
+ // did we completed a connection component?
+ if (!ready && best==umgebung_t::intercity_road_length) {
+ // next component
+ conn_comp++;
+ // try the first not connected city
+ ready = true;
+ for(int i = old_anzahl_staedte; i < einstellungen->get_anzahl_staedte(); i++) {
+ if (city_flag[i]==0) {
+ city_flag[i]=conn_comp;
+ // printf("Try: %s\n", stadt[i]->get_name());
+ ready=false;
+ break;
+ }
+ }
+ }
+ }
+ else {
+ // loop over all unconnected cities
+ for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
+ for(int j = max(old_anzahl_staedte, i+1); j < einstellungen->get_anzahl_staedte(); j++) {
+ if (city_dist.at(i,j) < best && city_flag[i]==city_flag[j]) {
+ bool ok = true;
+ // is there a connection i..l..j ? forbid stumpfe winkel
+ for(int l = 0; l < einstellungen->get_anzahl_staedte(); l++) {
+ if ( city_flag[i]==city_flag[l] && city_dist.at(i,l) == umgebung_t::intercity_road_length && city_dist.at(j,l) == umgebung_t::intercity_road_length) {
+ // cosine < 0 ?
+ koord3d d1 = k[i]-k[l];
+ koord3d d2 = k[j]-k[l];
+ if ( d1.x*d2.x + d1.y*d2.y <0) {
+ //printf("Forbid: %s .. %s \n", stadt[i]->get_name(), stadt[j]->get_name());
+ city_dist.at(i,j) = umgebung_t::intercity_road_length+1;
+ city_dist.at(j,i) = umgebung_t::intercity_road_length+1;
+ ok = false;
+ break;
+ }
+ }
+ }
+ if (ok) {
+ ready = false;
+ best = city_dist.at(i,j);
+ conn = koord(i,j);
+ //printf("Best so far: %8d ... %s --> %s\n", best, stadt[j]->get_name(), stadt[i]->get_name());
+ }
+ }
+ }
+ }
+ }
+ // valid connection?
+ if (conn.x>=0) {
+ // is there a connection already
+ bool connected = phase==1 && verbindung.calc_route(this,k[conn.x],k[conn.y],  test_driver, 0);
+ // now try this connnection
+ if (connected)
+ bauigel.set_maximum(verbindung.get_max_n() / 2);
+ else
+ bauigel.set_maximum(umgebung_t::intercity_road_length);
+
+ bauigel.calc_route(k[conn.x],k[conn.y]);
+
+ if(bauigel.max_n >= 1) {
+ bauigel.baue();
+ //city_flag[ conn.x ] = 1;
+ city_flag[ conn.y ] = conn_comp;
+ printf("Built:  %s --> %s\n", stadt[conn.y]->get_name(), stadt[conn.x]->get_name());
+ // mark as built
+ city_dist.at(conn) =  umgebung_t::intercity_road_length;
+ city_dist.at(conn.y, conn.x) =  umgebung_t::intercity_road_length;
+ }
+ else {
+ printf("Failed(%d/%d): %s --> %s\n", bauigel.max_n, 2*verbindung.get_max_n(), stadt[conn.y]->get_name(), stadt[conn.x]->get_name());
+ // do not try again
+ city_dist.at(conn) =  umgebung_t::intercity_road_length+1;
+ city_dist.at(conn.y, conn.x) =  umgebung_t::intercity_road_length+1;
+ }
+ } else printf("Did nothing\n");
+
+ if (ready) {
+ phase++;
+ ready = false;
+ }
+ }
+ delete test_driver;
+
+
+/*
+ for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
// Only new cities must be connected:
for (int j = max(i + 1, old_anzahl_staedte); j < einstellungen->get_anzahl_staedte(); j++) {
if(koord_distance(k[i].get_2d(),k[j].get_2d()) < umgebung_t::intercity_road_length) {
@@ -969,7 +1097,7 @@
}
}
}
- }
+ }*/

delete pos;
}

[z9999]

I couldn't test this because Simutrans didn't launch.

sim_road.exe caused an Access Violation at location 0051ab07 in module sim_road.exe Reading from location 00000118.

Registers:
eax=00000000 ebx=00000000 ecx=00000002 edx=00000000 esi=00000002 edi=00000000
eip=0051ab07 esp=0023e630 ebp=0023e9a8 iopl=0         nv up ei ng nz na pe cy
cs=001b  ss=0023  ds=0023  es=0023  fs=003b  gs=0000             efl=00000283

Call stack:
0051AB07  sim_road.exe:0051AB07  spieler_t::buche(long long, player_cost)  simplay.cc:446
   ...
   assert(type < MAX_PLAYER_COST);
   
>   finance_history_year[0][type] += betrag;
   finance_history_month[0][type] += betrag;
   
   ...

0057E63C  sim_road.exe:0057E63C  karte_t::enlarge_map(einstellungen_t*, signed char*)  simworld.cc:1459
   ...
   marker.init(new_groesse_x, new_groesse_y);
   
>   distribute_groundobjs_cities(sets->get_anzahl_staedte(),old_x, old_y);
   
   // hausbauer_t::neue_karte(); <- this would reinit monuments! do not do this!
   ...

005B7951  sim_road.exe:005B7951  WinMain  simsys_w16.cc:774
00401247  sim_road.exe:00401247
00401298  sim_road.exe:00401298
7C817077  kernel32.dll:7C817077  RegisterWaitForInputIdle

[Dwachs]

Sorry! thanks for trying. I updated the previous post.

Here is a demo of the result:

[gerw]

Looks very nice!

[jamespetts]

That looks very promising - I like that! Any chance of having a system in which any unconnected cities are slowly added to the road network automatically by the public player later in the game, or in which the inter-city roads are slowly upgraded one by one (if built by the public player) as new road types become available?

[z9999]

Excellent work !

Two things.
1. Is it possible to use progress bar ?
2. If I made a big 1024*1024 map in pak128 without timeline, there will appear many long bridges. This is not realistic.

[Dwachs]

thank you!

1. Is it possible to use progress bar ?

yes

2. If I made a big 1024*1024 map in pak128 without timeline, there will appear many long bridges. This is not realistic.

You can decrease the intercity road length if you do not like the outcome of the generation. All constructed connections are shorter than the intercity road length specified in new-world-dialogue.

[prissi]

To aim a little more at performance I would suggest to add something like

Code Select Expand


if(route and route.length>1.5*koord_distance(city1,city2)  ) {
//built new route


This would also avoid circling half lakes only because there is a shorter route.

[Dwachs]

Edit: New patch, progress bar now correct.

Code Select Expand

Index: simworld.cc
===================================================================
--- simworld.cc (revision 2494)
+++ simworld.cc (working copy)
@@ -895,6 +895,8 @@
printf("*");fflush(NULL);
}
}
+ delete pos;
+
for(  uint32 i=old_anzahl_staedte;  i<stadt.get_count();  i++  ) {
// Hajo: do final init after world was loaded/created
stadt[i]->laden_abschliessen();
@@ -919,59 +921,185 @@
}

wegbauer_t bauigel (this, spieler[1] );
- bauigel.route_fuer(wegbauer_t::strasse, besch, NULL, brueckenbauer_t::find_bridge(road_wt,15,get_timeline_year_month()) );
+ bauigel.route_fuer(wegbauer_t::strasse, besch, tunnelbauer_t::find_tunnel(road_wt,15,get_timeline_year_month()), brueckenbauer_t::find_bridge(road_wt,15,get_timeline_year_month()) );
bauigel.set_keep_existing_ways(true);
bauigel.set_maximum(umgebung_t::intercity_road_length);

+ // **** intercity road construction
+ // progress bar data
int old_progress_count = 16+2*new_anzahl_staedte;
int count = 0;
const int max_count=(einstellungen->get_anzahl_staedte()*(einstellungen->get_anzahl_staedte()-1))/2
- (old_anzahl_staedte*(old_anzahl_staedte-1))/2;
-
-
-                // find townhall of city i and road in front of it
- vector_tpl<koord3d> k;
-                for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
- koord k1 = stadt[i]->get_pos();
- const gebaeude_t* gb = dynamic_cast<gebaeude_t*>(lookup_kartenboden(k1)->first_obj());
- if (gb && gb->ist_rathaus()) {
- k1.y += gb->get_tile()->get_besch()->get_h(gb->get_tile()->get_layout());
- k.append( lookup_kartenboden(k1)->get_pos() );
+ // something to do??
+ if (max_count>0) {
+ // find townhall of city i and road in front of it
+ vector_tpl<koord3d> k;
+ for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
+ koord k1 = stadt[i]->get_pos();
+ const gebaeude_t* gb = dynamic_cast<gebaeude_t*>(lookup_kartenboden(k1)->first_obj());
+ if (gb && gb->ist_rathaus()) {
+ k1.y += gb->get_tile()->get_besch()->get_h(gb->get_tile()->get_layout());
+ k.append( lookup_kartenboden(k1)->get_pos() );
+ }
+ else {
+ k.append( koord3d::invalid );
+ }
}
- else {
- k.append( koord3d::invalid );
+ // compute all distances
+ uint8 conn_comp=1; // current connection component for phase 0
+ vector_tpl<uint8> city_flag; // city already connected to the graph? >0 nr of connection component
+ array2d_tpl<sint32> city_dist(einstellungen->get_anzahl_staedte(), einstellungen->get_anzahl_staedte());
+ for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
+ for (int j = max(i + 1, old_anzahl_staedte); j < einstellungen->get_anzahl_staedte(); j++) {
+ city_dist.at(i,j) = koord_distance(k[i], k[j]);
+ city_dist.at(j,i) = city_dist.at(i,j);
+ // count unbuildable connections
+ if (city_dist.at(i,j)>=umgebung_t::intercity_road_length) count++;
+ }
+ city_flag.append( i < old_anzahl_staedte ? conn_comp : 0 );
+
+ // progress bar stuff
+ if(is_display_init() && (count<=max_count)) {
+ int progress_count = 16+ 2*new_anzahl_staedte+ (count*einstellungen->get_anzahl_staedte()*2)/max_count;
+ if(old_progress_count!=progress_count) {
+ display_progress(progress_count, max_display_progress );
+ old_progress_count = progress_count;
+ }
+ }
}
- }
-
- for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
- // Only new cities must be connected:
- for (int j = max(i + 1, old_anzahl_staedte); j < einstellungen->get_anzahl_staedte(); j++) {
- if(koord_distance(k[i].get_2d(),k[j].get_2d()) < umgebung_t::intercity_road_length) {
-//DBG_DEBUG("karte_t::distribute_groundobjs_cities()","built route fom city %d to %d", i, j);
- bauigel.calc_route(k[i],k[j]);
- if(bauigel.max_n >= 1) {
+ // mark first town as connected
+ if (old_anzahl_staedte==0) city_flag[0]=conn_comp;
+
+ // get a default vehikel
+ route_t verbindung;
+ fahrer_t* test_driver;
+ vehikel_besch_t test_drive_besch(road_wt, 500, vehikel_besch_t::diesel );
+ test_driver = vehikelbauer_t::baue(koord3d(), spieler[1], NULL, &test_drive_besch);
+
+ bool ready=false; uint8 phase=0;
+ // 0 - first phase: built minimum spanning tree (edge weights: city distance)
+ // 1 - secnd phase: try to complete the graph, avoid edges that
+ // == have similar length then already existing connection
+ //      == lead to triangles with an angle >90 deg
+ while(phase<2) {
+ ready = true;
+ koord conn = koord::invalid;
+ sint32 best = umgebung_t::intercity_road_length;
+
+ if (phase==0) {
+ // loop over all unconnected cities
+ for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
+ if (city_flag[i]==conn_comp) {
+ // loop over all connections to connected cities
+ for(int j = old_anzahl_staedte; j < einstellungen->get_anzahl_staedte(); j++) {
+ if (city_flag[j]==0) {
+ ready=false;
+ if ( city_dist.at(i,j) < best ) {
+ best = city_dist.at(i,j);
+ conn = koord(i,j);
+ }
+ }
+ }
+ }
+ }
+ // did we completed a connection component?
+ if (!ready && best==umgebung_t::intercity_road_length) {
+ // next component
+ conn_comp++;
+ // try the first not connected city
+ ready = true;
+ for(int i = old_anzahl_staedte; i < einstellungen->get_anzahl_staedte(); i++) {
+ if (city_flag[i]==0) {
+ city_flag[i]=conn_comp;
+ ready=false;
+ break;
+ }
+ }
+ }
+ }
+ else {
+ // loop over all unconnected cities
+ for(int i = 0; i < einstellungen->get_anzahl_staedte(); i++) {
+ for(int j = max(old_anzahl_staedte, i+1); j < einstellungen->get_anzahl_staedte(); j++) {
+ if (city_dist.at(i,j) < best && city_flag[i]==city_flag[j]) {
+ bool ok = true;
+ // is there a connection i..l..j ? forbid stumpfe winkel
+ for(int l = 0; l < einstellungen->get_anzahl_staedte(); l++) {
+ if ( city_flag[i]==city_flag[l] && city_dist.at(i,l) == umgebung_t::intercity_road_length && city_dist.at(j,l) == umgebung_t::intercity_road_length) {
+ // cosine < 0 ?
+ koord3d d1 = k[i]-k[l];
+ koord3d d2 = k[j]-k[l];
+ if ( d1.x*d2.x + d1.y*d2.y <0) {
+ city_dist.at(i,j) = umgebung_t::intercity_road_length+1;
+ city_dist.at(j,i) = umgebung_t::intercity_road_length+1;
+ ok = false;
+ count ++;
+ break;
+ }
+ }
+ }
+ if (ok) {
+ ready = false;
+ best = city_dist.at(i,j);
+ conn = koord(i,j);
+ }
+ }
+ }
+ }
+ }
+ // valid connection?
+ if (conn.x>=0) {
+ // is there a connection already
+ const bool connected = phase==1 && verbindung.calc_route(this,k[conn.x],k[conn.y],  test_driver, 0);
+ // build this connestion?
+ bool build = false;
+ // set appropriate max length for way builder
+ if (connected) {
+ if (2*verbindung.get_max_n() > 3*city_dist.at(conn)) {
+ bauigel.set_maximum(verbindung.get_max_n() / 2);
+ build = true;
+ }
+ }
+ else {
+ bauigel.set_maximum(umgebung_t::intercity_road_length);
+ build = true;
+ }
+
+ if (build) {
+ bauigel.calc_route(k[conn.x],k[conn.y]);
+ }
+
+ if(build && bauigel.max_n >= 1) {
bauigel.baue();
+ if (phase==0) city_flag[ conn.y ] = conn_comp;
+ // mark as built
+ city_dist.at(conn) =  umgebung_t::intercity_road_length;
+ city_dist.at(conn.y, conn.x) =  umgebung_t::intercity_road_length;
}
else {
-//DBG_DEBUG("karte_t::distribute_groundobjs_cities()","no route found fom city %d to %d", i, j);
+ // do not try again
+ city_dist.at(conn) =  umgebung_t::intercity_road_length+1;
+ city_dist.at(conn.y, conn.x) =  umgebung_t::intercity_road_length+1;
}
- }
- else {
-//DBG_DEBUG("karte_t::distribute_groundobjs_cities()","cites %d and %d are too far away", i, j);
- }
- count ++;
- // how much we continued?
- if(is_display_init()) {
+ count ++;
+ }
+ // progress bar stuff
+ if(is_display_init() && (count<=max_count)) {
int progress_count = 16+ 2*new_anzahl_staedte+ (count*einstellungen->get_anzahl_staedte()*2)/max_count;
if(old_progress_count!=progress_count) {
display_progress(progress_count, max_display_progress );
old_progress_count = progress_count;
}
}
+ // next phase?
+ if (ready) {
+ phase++;
+ ready = false;
+ }
}
+ delete test_driver;
}
-
- delete pos;
}
else {
// could not generate any town


[z9999]

Could you please change default value to rational value ? Thank you.

dataobj/umgebung.cc:63

sint32 umgebung_t::intercity_road_length = 8000;

[Dwachs]

done.

But this value is overridden by the value in pak*/simuconf.tab, so the pak-sets have to adopt also.

[Spike]

This means I must release a new simuconf.tab for pakHajo.Evolution with a new setting for the nightly builds? (Which begs the question why the old value couldn't be kept for compatibility reasons - just scale it appropriately so that it fits to the new code)

The spanning tree of roads looks good though. Nice application of the algorithm

[Dwachs]

You need to do that only, if the bridges in your pak-set don't have a prescribed maximal length and you find it  unrealistic if the generation of intercity roads builds very long bridges.

For some reasons, in the old code the intercity road length corresponds to the squared Euclidean distance of two cities, while now it corresponds to the Manhattan distance.

[Spike]

For some reasons, in the old code the intercity road length corresponds to the squared Euclidean distance of two cities, while now it corresponds to the Manhattan distance.

I think that was a performance optimization since the check (x*x)+(y*y) < limit is faster than sqrt((x*x)+(y*y)) < limit.

I'll see if there are problems with my old simuconf.tab and new versions. I just want to ask to keep the less frequently or unmaintained pak sets in mind, and be careful with changes of such values, in order to keep the old sets usable as long as possible.

[Dwachs]

Old parameter values should be usable with the exception that sometimes very long bridges are built automatically (if no max length for bridges is specified).