------------------------------------------------
Patch for Simutrans
RRC - Selective loading by convoys' class of service ('less-stop'-ness)

Jul 6, 2012 for RRC-003
by wackdone
------------------------------------------------

This patch-set extends Simutrans to provide "Selective Loading" function
at loading goods (including passengers) onto convoys at halts.

With this patch, goods/passengers will ride only faster convoys
(faster convoys is serving less time to trip).

For example:

        Station A  --->  Station B  --->  Station C  ---> Station D  ...

Express    stops          (passes)          stops           (passes)
Local      stops           stops            stops           stops

Passengers in Station A: [Original Simutrans]
  for Station B:  ride only Local.
  for Station C:  ride either Express or Local.
  for Station D:  ride only Local

Passenters in Station A: [by this patch (without any relaxation)]
  for Station B:  ride only Local.
  for Station C:  ride only Express.
  for Station D:  ride Express and transfer at Station C for Local.


(CAUTION: Behavier of passengers for station D depends on parameters
 of route calculation.
 If cost of transfer is so high, passengers will not choose transfer at 
 Station C. They simply ride Local at Station A for Station D.)


Selection logic is based on generic 'fastness' of the arriving convoy, 
for each destination (next-transfer) halt.
If the arrived convoy is enough faster than other convoys servicing
same halt-connection, goods for the next-hop halt are loaded onto
this 'fastest' convoy.

Currently, 'number of stops' until reaching to target halt are used
as (inverse of) 'fastness'.
It is a same value with 'weight' value cached in halt.connections[]
which is used in route calculation of goods (finding halt-by-halt path of goods).
But the concept of the selection can be expandable for generic 'cost'.
It is now under development as one of example use of this selection.
to use best 'real-trip-time' (measured by convoys self)

Essence of this algorithm (in abbreviated form):

   cost = COST_BASE;

   for (dest_halt; each halt in fahrplan of the convoi (sorted)) {
      cost += COST_FOR_ONE_STOP;
      if (cost > connections[dest_halt].cost)) {	// compare with best
         continue;  // ignore this convoy to use in trip for the dest_halt.
      }

      load goods for the dest_halt...
   }


The algorithm is implemented to be:
  * simpler
  * less calculation cost, less memory usage
  * less parameters, user settings
  * parameters only for the world, no indivisual parameter for each convoy, halt.
  * better differentiation between convoys running for same set of halts
    (but, not 'best' in some circumstances)
  * (optional) adoptive determination logic for difference of
    each balance of fast-slow mixation.

It was tested with some simple 'Express and Local' serviced lines in game.
But it's not tested under complex network / complex classification.
Please evaluate it with your map, and give me suggestion for futer imporovement.


--------------------
= History
--------------------
Basic concepts and early implementations were proposed in the
Japanese Simutrans community (2ch bbs and wiki), 2 years ago.
That implementation was called 'RouteCost'.
By growth of original Simutrans, 'RouteCost' becomes not able to be
applied for newer Simutrans source.
Then, I started rewriting and extending 'RouteCost' for current Simutrans.
"RRC" is abbreviation of "Re-implementation of RouteCost".

In past time, route calculation of original Simutrans was
using connection cost == one (searching least-transfer route).
The former 'RouteCost' was providing two extension:

  a. Route calculation with using best 'less-stop'-ness of convoy between halts
     (using Dijkstra's; one of A* with zero-heuristics)

  b. Selective loading by 'less-stop'-ness of convoy arrived.

Nowadays, (a) has been implemented already in latest Simutrans (almost same with algorithm in RouteCost).
My work is mainly for realizing (b).

--------------------
= How to build
--------------------
(1) Apply the patchfile for original Simutrans source using 'patch' command.
Like as:
{{{
  svn co -r5788 svn://tron.homeunix.org/simutrans/simutrans/trunk
  cd trunk
  patch -p0 < simutrans-r5788-rrc-003.patch
}}}

(2) Configure build settings with some additional CFLAGS.
for example, add following lines to config.${CFG} file (such as "config.default")
{{{
  CFLAGS += -DROUTECOST_CHOOSE_CLASS
  CFLAGS += -DROUTECOST_SETTINGS
}}}
Details of preprocessor macros which can be specified here,
are described later.

(3) Build with make command.
as same as original.


--------------------
= Configuration of patch functions
--------------------
Some preprocessor macros are avaiable to switch the function of RRC.

ROUTECOST_CHOOSE_CLASS
  toplevel switch. If it's undefed, all functions of RRC are disabled.
  When you encounter a problem while running patched program,
  you can disable all functions by undef this macro and rebuild, run,
  to distinguish cause of the problem.

ROUTECOST_SETTINGS
  parameters become configurable in Settings Dialog (dialog_tool[27]).
  To open this dialog in the game playing, uncomment line
{{{
    dialog_tool[27]=,@
}}}
  in pak/config/menuconf.tab, and press '@'.
  Description of configurable parameters is written later.

ROUTECOST_SETTINGS_SAVEHACK
  save/load parameters of RRC.
  (using tricky way to keep savefile version number. use with caution!)

ROUTECOST_CHOOSE_BY_WAITTIME
  introduce some adoptive logic to make selection better.

ROUTECOST_CHOOSE_CLASS_DEBUG (for debugging of the algorithm)
  print 'denial of load/ride' log to stdout.


--------------------
= Parameters of RRC
--------------------
When ROUTECOST_SETTINGS is enabled at buildtime, some parameters can be
editable in 'Route' panel of Settings Dialog.

== Parameters used by both Route Calculation and Selective Loading
Following parameters are also used in Route Calculation of original.
These are coded as constant value in the original source file "simhalt.cc".
RRC makes these configurable.

routecost_initial  (WEIGHT_WAIT in "simhalt.cc")
  initial value of connection cost (weight).
  default: 8

routecost_stops    (WEIGHT_HALT in "simhalt.cc")
  value added to cost for each stopping
  default: 1

routecost_transfer (WEIGHT_MIN  in "simhalt.cc")
  value added to cost for each transfer in path
  It is only affect route calculations.
  (so, it is used only in search_route())
  default: 9

Example:
 If you would like to make trasfer from Express to Local, like shown above,
 set transfer cost to zero.

 Another example when routecost_transfer is varied:
 in example, fix routecost_initial == 0, routecost_stops == 1

          A - B - C - D - E - F - G
 Express  *       *       *       *
 Local    *   *   *   *   *   *   *
          A - B - C - D - E - F - G

 (1)fastest cost from A: at transfer >= 2
              1   1   3   2   5   3
              L   E   L   E   L   E
 (2)fastest cost from A: at transfer == 1
              1   1   3   2   4   3
              L   E   B   E   T   E
 (3)fastest cost from A: at transfer == 0
              1   1   2   2   3   3
              L   E   T   E   T   E

 L: ride Local
 E: ride Express
 B: ride Local or Express
 T: ride Express and transfer Local before destination


== Parameters used by Selective Loading
Following parameters affect selection logic with relaxed/adoptive correction
(when ROUTECOST_CHOOSE_BY_WAITTIME is enabled at buildtime).
Details of correction logic are written later.

NOTE:
  To DISABLE 'Selective Loading' at runtime,
    set HUGEVALUE for routecost_load_margin, such as 10000.


--------------------
= Relaxed or Adoptive Selection (experimental)
--------------------
While basic algorithm of RRC is working, all passangers and goods choose
convoy by fastness STRICTLY.
It sometime makes serious unbalanced load of convoys, like as
  "Express Trains are always full-load,
   Local Tranins are always nearly empty."

In real world, passengers can change preference.
They may choose slower trains instead of fastest one, in situations like
  * trip time for the destination is not so different btween Express and Local
  * wait time to the next Express is too long, and Local trains comes frequently
  * Express trains always have no space to ride!!

There are 3 experimental logic to improve the base selection logic.
Base of all logics are same: adding relaxation value for comparision.
In selection of load, test expression is modified as

  cost > connections[dest_halt].cost + MARGIN

Each logic has different calculation of this MARGIN value.
And some logics use trend of selection recorded in connection lists of halts.


== Constant Margin
It makes the selection relax, constantly.
Passengers may choose second best or third (ore more) best convoy.

Parameter:
  routecost_load_margin   (default: 0  (means disable))

Logic:
  In selection (cost evaluation) at load, test expression is changed as
    cost > connections[dest_halt].cost + routecost_load_margin


== Sense Hurry by Wait Time
(define ROTUECOST_CHOOSE_BY_WAITTIME to enable it)
A logic of a trend-tracking based. ("More haste, less speed")

Last loading time (game world time, zelt_ms) is recorded
in the connection informatin for the here-to-target.
Selection depends on difference between the last load time and now.

Passengers become to ride a slower train  if waiting time goes too long.

Parameter:
  routecost_time_to_wait   (default: 0 (means disable))

Algorithm:
  if (last_load_time is recorded) {
    MARGIN = ((now - last_load) /1024) / routecost_time_to_wait;
  }

  selection uses MARGIN.

  if (do_load) {
    last_load_time = now;
  }


== Sense Hurry by Rejection Count
Another logic of a trend-tracking based.

Rejected count is recorded in the connection information.
Selection depends on this count.
If it passed, the count is resetted.
Otherwise, the count is increased.

Passengers become to ride a slower train  after they ignored too many trains.

Parameter:
  routecost_hurry_by_wait  (default: 0 (means disable))

Algorithm:
  MARGIN = rejection_count in the connection info;

  selection uses MARGIN.

  if (do_load) {
    rejection_count = 0;
  }
  else {
    rejection_count += routecost_hurry_by_wait;
  }


--------------------
= Problems about difference of version
--------------------
When you revert using from RRCed-version to original,
some problems may be happen.

  1. loading "settings.xml" will fail
    Some new entries are inserted into settings.xml by RRC.
    There is no smart way to recover it.
    Remove it, or edit it by hand.

  2. loading savegame file of RRC.
    It's impossible by original Simutrans. The program may crash eventually.
    If requests are coming, I'll consider to make workaround for this problem.
    (down-versioning save, etc.)

Currently, because of some conflicts between patches I'm developping,
savefile version number is NOT changed by RRC.
But with enabling 'ROUTECOST_SETTINGS_SAVEHACK', format of savefile is
changed. Then, Simutrans cannot distinguish difference of these.
Sorry for its current inconvinience.


--------------------
= To be discussed/considered
--------------------

== Parameters by Locallity
In current implementation, all parameters are common in the game world.
It cannot control selection of each line with its circumstances.

One of them may be a line
  Local=frequent, Express=less and limited

and another may be
  Express=main, Local=auxiliary

The parameters of selection should be different between each other.

Althogh, some new problems appear while the designing of the differentiation:
  * memory consumption
  * size of savefile
  * user interface


== Memory consumption
Without ROTUECOST_CHOOSE_BY_WAITTIME, no extra memory  (except parameters, few words for the world).

Enabling ROTUECOST_CHOOSE_BY_WAITTIME, it uses up to 6..8 bytes by-connection-by-halt.

Is it considered feasible?


== Calculation time
so small in this impl.
but, codes checking "is the halt already tested?" in a halt-by-halt loop
are little bit expensive.

Smarter algorithm, data structures are hoped.
