News:

Want to praise Simutrans?
Your feedback is important for us ;D.

[Code v3.4] Possible Overflow and Precision of Recorded Time

Started by knightly, May 06, 2009, 06:44:45 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

knightly

Hi James,

For this part of your code :

Quote
uint16 haltestelle_t::get_average_waiting_time(halthandle_t halt, uint8 category) const
{
   if(&waiting_times[category].get(halt) != NULL)
   {
      fixed_list_tpl<uint16, 16> times = waiting_times[category].get(halt);
      const uint16 count = times.get_count();
      if(count > 0 && halt.is_bound())
      {
         uint16 total_times = 0;
         ITERATE(times,i)
         {
            total_times += times.get_element(i);
         }
         total_times /= count;
         // Minimum waiting time of 1 minute (i.e., 10 tenths of a minute)
         // This simulates the overhead time needed to arrive at a stop, and
         // board, etc. It should help to prevent perverse vias on a single route.
         return total_times >= 10 ? total_times : 10;
      }
         return 10;
   }
      return 10;
}

(1) It is highly possible that when adding up a few uint16 amounts to another uint16 variable (total_times), you will encounter overflow, which can happen more than once in your loop for adding up the recorded times. So probably you should use uint32 for total_times instead. uint16 can only hold 0~65535, and it's not large enough to avoid possible overflow.

(2) IMHO recording time down to a precision of tenths of a minute is neither necessary nor desirable. In Simutrans world, a minute is fleetingly transient at the standard speed (= 1.00), so measuring time down to tenths of a minute is not very meaningful or useful. As for recording time using uint16, such precision of time only allows you to record time up to ~4.55 days [ = 65535 / (10 x 60 x 24) ] -- but longer journeys can easily take more than 5 days, so are waiting times at infrequently served stops. Thus, I would suggest to record time in minutes -- it's already precise enough to achieve your goal, and you can record up to ~45.5 days with uint16, which allows longer journey times or waiting times to be recorded.




Edit :

(3)
Regarding the following code :

Quote
inline uint16 haltestelle_t::get_waiting_minutes(uint32 waiting_ticks) const
{
   return (2 * welt->get_einstellungen()->get_journey_time_multiplier() * waiting_ticks) / 409.6F;
}

It is not impossible that the whole expression evaluates to a amount over 65535, since waiting_ticks is uint32. Better check for possible overflow before allowing implicit cast from float to uint16 (the return type).

(4)
Similar problem in haltestelle_t::add_connexion() :

Quote
   new_connexion->journey_time = (((float)journey_distance / (float)average_speed) * welt->get_einstellungen()->get_journey_time_multiplier() * 600);

journey_distance is uint32, so if average_speed is low, it is possible that the whole expression evaluates to amount over 65535 (new_connexion->journey_time is uint16). Again, overflow checking is desirable here.

(5)
A suggestion for floating-point arithmetics :  it may be worthwhile to use double instead of float to increase the precision of your calculations in some cases.

jamespetts

Knightly,

thank you very much for your feedback. I have, as you suggested, replaced uint16 with uint32 for "total_times" in the latest release (3.5) to prevent any possible overflow. I doubt that an overflow would exist elsewhere, when not summing times, however, as 6,553 minute is a very long time! As to the float/double thing, I am not sure that that level of accuracy is needed in those calculations - double gives a very large number of decimal places, and takes twice the memory of float.

I think that you misunderstand what the times are supposed to represent, however, As might be apparent, Simutrans has two quite separate scales for time running parallel (just as it has two separate scales for distance: one in which a tile is the approximate length of a fairly long vehicle, and one in which a tile is one kilometre). One scale is the one displayed on the clock/calendar at the bottom right of the screen, and another is the scale in which vehicles move around the map. If one were to take a vehicle moving at 100km/h, for example, it would not move 100 game tiles in one hour (less than a second in real time) on the map!

The journey times and waiting times are both based on that second scale - the same scale as that on which the speeds are calculated. If, therefore, a vehicle has an average speed of 100 km/h over a distance of 100 km, the journey time will be one hour, however many game weeks/months that it actually takes the vehicle to traverse 100 tiles. The waiting times are calibrated to the same scale, but the numbers are damped a little to represent the fact that, in reality, services are timetabled, and passengers/goods can plan their journeys in accordance with those timetables (this is necessary when using waiting times in the calculation of the shortest path, to prevent waiting times becoming disproportionately important in that respect).

Thank you again for your feedback - I hope that you enjoy testing 3.5 :-)
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.