[11.17/18] Strange Routing

[Carl]

Some things are easier shown than explained:

https://dl.dropboxusercontent.com/u/61716/oddrouting.rar

Our convoy of interest is the London Midland convoy 1479 at Rugby. Follow it as far as Nuneaton. In order to get there it follows a very strange routing involving a 180 degree turn on the wrong track - you'll see. Given the waypoint between Rugby and Nuneaton (see line schedule), this is clearly the wrong route to take. Notice also that after Nuneaton the convoy follows a convoluted route north out of the station rather than taking the straight track towards its destination.

This occurs in 11.17 and 11.18 but not in 11.15 - if loaded in 11.15 or earlier, the convoy will follow the expected route on the left-most track straight to Nuneaton. (I'm afraid I don't have 11.16 to check).

Ordinarily when something like this happens I would expect to find an obstacle on the correct track; but since it works as expected in previous versions, I guess this particular is down to a bug.

[jamespetts]

Thank you for this report. I can reproduce it, but I am having great difficulty in finding out what is causing it. All that I have discovered so far is (1) deleting a segment of the wrong route causes the train to take the correct route; (2) deleting the waypoint has no effect; and (3) disabling:

Code Select Expand


   if(w->is_diagonal())
   {
      // Diagonals are a *shorter* distance.
      costs = (costs * 5) / 7; // was: costs /= 1.4
   }


in int waggon_t::get_kosten(const grund_t *gr, const sint32 max_speed, koord from_pos) has no effect. The convoy is taking an extra 16 tiles at least to reach its destination, which is singularly odd. I had initially thought that it might be helpful to check whether the problem is that it is not treating corners as having a higher cost than straight tiles, but this would not account for being 16 tiles out on this particular configuration. It also takes an odd route out of the station once it has stopped (if it stopped at the correct platform), but, again, it is not clear why.

If anyone has any suggestions as to what might be going on here, I should be grateful. For reference, the current get_kosten function is as follows:

Code Select Expand


int waggon_t::get_kosten(const grund_t *gr, const sint32 max_speed, koord from_pos)
{
   // first favor faster ways
   const weg_t *w = gr->get_weg(get_waytype());
   if(  w==NULL  ) {
      // only occurs when deletion during waysearch
      return 9999;
   }

   // add cost for going (with maximum speed, cost is 10)
   const sint32 max_tile_speed = w->get_max_speed();
   int costs = (max_speed <= max_tile_speed) ? 10 : 40 - (30 * max_tile_speed) / max_speed;

   // effect of slope
   if(  gr->get_weg_hang()!=0  ) {
      // Knightly : check if the slope is upwards, relative to the previous tile
      from_pos -= gr->get_pos().get_2d();
      if(  hang_t::is_sloping_upwards( gr->get_weg_hang(), from_pos.x, from_pos.y )  ) {
         costs += 250;
      }
   }

   //@author: jamespetts
   // Strongly prefer routes for which the vehicle is not overweight.
   uint16 weight_limit = w->get_max_axle_load();
   if(vehikel_t::get_sum_weight() > weight_limit && welt->get_settings().get_enforce_weight_limits() == 1 || welt->get_settings().get_enforce_weight_limits() == 3)
   {
      costs += 400;
   }

   if(w->is_diagonal())
   {
      // Diagonals are a *shorter* distance.
      costs = (costs * 5) / 7; // was: costs /= 1.4
   }

   //const ribi_t::ribi our_direction_bits = ribi_typ(from_pos, gr->get_pos());


   return costs;
}


Until I manage to find what the problem is, I can only suggest more waypoints. If you are able to find any pattern in this sort of problem occurring, I should be very grateful if you could let me know.

Edit: Further testing suggests that the issue occurs because the left hand track has a lower speed limit than the right hand track, which translates to a higher cost function. The following code, however, still produces the problem:

Code Select Expand


int waggon_t::get_kosten(const grund_t *gr, const sint32 max_speed, koord from_pos)
{
    // first favor faster ways
    const weg_t *w = gr->get_weg(get_waytype());
    if(  w==NULL  ) {
        // only occurs when deletion during waysearch
        return 9999;
    }

    // add cost for going (with maximum speed, cost is 10)
    const sint32 max_tile_speed = w->get_max_speed();
    int costs = (max_speed <= max_tile_speed) ? 1 : 4 - ( 3 * max_tile_speed) / max_speed;
    costs *= 10;

    // effect of slope
    if(  gr->get_weg_hang()!=0  ) {
        // Knightly : check if the slope is upwards, relative to the previous tile
        from_pos -= gr->get_pos().get_2d();
        if(  hang_t::is_sloping_upwards( gr->get_weg_hang(), from_pos.x, from_pos.y )  ) {
            costs += 250;
        }
    }

    //@author: jamespetts
    // Strongly prefer routes for which the vehicle is not overweight.
    uint16 weight_limit = w->get_max_axle_load();
    if(vehikel_t::get_sum_weight() > weight_limit && welt->get_settings().get_enforce_weight_limits() == 1 || welt->get_settings().get_enforce_weight_limits() == 3)
    {
        costs += 400;
    }

    if(w->is_diagonal())
    {
        // Diagonals are a *shorter* distance.
        costs = (costs * 5) / 7; // was: costs /= 1.4
    }

    //const ribi_t::ribi our_direction_bits = ribi_typ(from_pos, gr->get_pos());


    return costs;
}


(Notice the slight change from:

Code Select Expand


int costs = (max_speed <= max_tile_speed) ? 10 : 40 - (30 * max_tile_speed) / max_speed;


to

Code Select Expand


int costs = (max_speed <= max_tile_speed) ? 1 : 4 - ( 3 * max_tile_speed) / max_speed;
    costs *= 10;


This seems to produce lower differentials if only by having more rounding inaccuracies, but does not prevent the unusual routing from occurring.

The code in Standard is:

Code Select Expand


int automobil_t::get_kosten(const grund_t *gr, const sint32 max_speed, koord from_pos) const
{
// first favor faster ways
const weg_t *w=gr->get_weg(road_wt);
if(!w) {
return 0xFFFF;
}

// max_speed?
sint32 max_tile_speed = w->get_max_speed();

// add cost for going (with maximum speed, cost is 1)
int costs = (max_speed<=max_tile_speed) ? 1 : 4-(3*max_tile_speed)/max_speed;

// assume all traffic is not good ... (otherwise even smoke counts ... )
costs += (w->get_statistics(WAY_STAT_CONVOIS) > ( 2 << (welt->get_settings().get_bits_per_month()-16) ) );

// effect of slope
if( gr->get_weg_hang()!=0 ) {
// Knightly : check if the slope is upwards, relative to the previous tile
from_pos -= gr->get_pos().get_2d();
if( hang_t::is_sloping_upwards( gr->get_weg_hang(), from_pos.x, from_pos.y ) ) {
costs += 15;
}
}
return costs;
}


The parts concerning hills are not relevant as there are no hills on this route and the code is not called. The relevant difference, therefore, is this line:

Code Select Expand


int costs = (max_speed<=max_tile_speed) ? 1 : 4-(3*max_tile_speed)/max_speed;


and the absence of this part from Experimental:

Code Select Expand


if(w->is_diagonal())
    {
        // Diagonals are a *shorter* distance.
        costs = (costs * 5) / 7; // was: costs /= 1.4
    }


The change between 11.15 and 11.17 was to replace

Code Select Expand


int costs = (max_speed<=max_tile_speed) ? 1 : 4-(3*max_tile_speed)/max_speed;


with

Code Select Expand


int costs = (max_speed <= max_tile_speed) ? 10 : 40 - (30 * max_tile_speed) / max_speed;


to avoid rounding truncation in the diagonals section. It is this that seems to cause the issue, although quite how to correct it is not entirely clear to me at this juncture.

Edit 2: Ahh, I have found it: there were some specific cornering settings in route.cc and I had not updated all of them to work with values of a magnitude of 10. Now fixed on the 11.x branch. Thank you for your report!

[prissi]

The cornering costs are done in route.cc, and must not be duplicated in the get_kosten. Because when a vehicle goes diagonally you cannot guess from is_diagonal() at all. For instance it may also go diagonal over switches.

[jamespetts]

I did wonder about switches. This issue was not what was causing the problems reported by Carl, but it is probably worth dealing with in any event. How is it best to detect whether a train is going over a switch for diagonal purposes (as a diagonal must be considered to be shorter than a straight)?

[prissi]

As written, this is already done in route.cc, since only there the previous and preprevious tile is known (and these are needed to decide on diagonal or not). This information must lag one tile behind the actual cost information, since the decision of the next tile will affect the current cost. Hence simvehikel is really the wrong place for this.

is_diagonal is only a flag that a way has curved and diagonal images but should use the latter. If a way has only curved (may be still visually diagonals), then those will be used on diagonals (like rivers for instance). Also a train going on a siding will travel over a visual curve but internally will never go stronger than 45 degree.

About the strange routing, I would suspect that with a very high value of cornering backwards value (also in route.cc) there might be an overflow.

[jamespetts]

Hmm - I am slightly confused. Where is the code in route.cc for testing whether a tile is diagonal (as distinct from being a corner)? Being diagonal requires a lower cost than being a straight, since a diagonal is a slightly shorter distance in Simutrans.

The strange routing, incidentally, was solved, as noted above, by finding that I had multiplied some but not all cost values by 10 for the purposes of avoiding truncation with the diagonal calculation.

[Carl]

Thank you for your work in tracking down this error, James!