§
------------------------------------------------
RRC - Simutrans RouteCost 再実装パッチ

				Jul  7, 2012
				 for RRC-004
				    wackdone
------------------------------------------------

かつて実験されていた RouteCost に相当する機能を再実装したパッチです。
RouteCost は経路計算、および駅での列車への乗車判断に、駅間を結ぶ列車の
最小途中停車数を使用します。

(ここで言う「経路」とは旅客や貨物が、出発駅と終点駅を決定し、
そこから途中にどの駅で乗り換えるかを決めたもののことを指します。
乗り物が次駅まで行くのに、どの線路や道路を通るかを選ぶ計算とは階層が違います。)

旧来のSimutransの経路計算では、一つの乗り物による乗換駅から乗換駅までの移動の
コストは全て等しいものとして、乗換数が最小になるよう計算していました。
これに対して RouteCost では、乗車中に途中停車する駅の数をコストとして取り入れ、
これによって途中停車駅数最小の経路を計算します。

RouteCost によって旅客は、より短時間(正確には途中停車が少ない)の経路で移動したり
緩急接続(丁度良い路線があれば、普通→優等→普通の乗り継ぎなども)を
利用するようになります。

またこの再実装では、オリジナルのRouteCostで試みられていたパラメータの調整の一部や
新たな乗車列車選択の試みも実装しています。


--------------------
= バージョン情報
--------------------
パッチバージョン: RRC Version 0.03
対応Simutransソース: Nightly r5788
パッチファイル名: simutrans-r5788-rrc-003.patch

== 適用可能ソースについて
手元では、Release 111.3 (r5772) にも適用できることを確認しています。


--------------------
= セーブファイルのバージョン
--------------------
本パッチをあてたことによるセーブファイルバージョンの変更はありません。

ただし後述する ROUTECOST_SETTINGS_SAVEHACK を有効にした場合、
RouteCostで使用する設定項目をファイルに保存しますが、
この時、一時的に max_transfers の値を大きくすることでファイルバージョンを識別しています。
(これは私の作成している他のパッチと共存させるために、仕方なくしたハックです。)
SAVEHACKが有効になっているSimutransでセーブしたファイルは、
オリジナルのSimutransではロードできません。
(エラーも出ずにクラッシュする可能性が充分にあります。)
ご注意ください。

現在、International Forum の方でこのパッチへの注目が来ており、
近い将来に採用される可能性もあります。そうなればこのような
問題はなくなります。いましばらくお待ちください。
(本家側に機能追加された際には、現状のデータから本家への移行のための
一時的なバイナリなども製作するようには努力いたします。)


--------------------
= パッチの適用とビルド
--------------------
Simutransのビルドが可能な環境とスキルがあることを前提に説明します。

== パッチの適用
Nightlyのソースを入手し、これに対して同梱のパッチファイル
  simutrans-r5788-rrc-003.patch
をpatchコマンドなどを使ってあててください。

例:
{{{
  svn co -r5788 svn://tron.homeunix.org/simutrans/simutrans/trunk
  cd trunk
  patch -p0 < simutrans-r5788-rrc-003.patch
}}}

== コンフィグ
ビルドコンフィグファイル (config.defaultなど) の中に以下の行を追加してください。

{{{
  CFLAGS += -DROUTECOST_CHOOSE_CLASS
  CFLAGS += -DROUTECOST_SETTINGS
}}}

またこの他にも以下のマクロ定義を追加することで拡張機能が有効になります。

  ROUTECOST_SETTINGS_SAVEHACK
    RouteCostで使用するパラメータをセーブファイルに保存します

  ROUTECOST_CHOOSE_BY_WAITTIME
    拡張の一つである、待ち時間ベースでの乗車判定調整を有効にします

  ROUTECOST_CHOOSE_CLASS_DEBUG
    乗り物への旅客・貨物の乗車判断の結果を標準出力に表示します。
    (Windowsではコンソールビルドしないと表示されません)

なおソースコード上は全てこれを元にifdefで制御されており、
これらのマクロ定義をしなければ、動作がオリジナル通りになります。
障害時にはこの定義を切り替えて動作を比較してください。

== ビルド
オリジナルと同様に make でコンパイル/リンクできます。


--------------------
= 元のRouteCostの機能
--------------------
別ドキュメントにメモを記録しています。ご参照ください。

--------------------
= 説明のための用語
--------------------
以降、このドキュメントで機能や実装を説明する際に使用する用語や記号を
簡単に定義しておきます。
(かならずしも、Simutransの中使っている用語と完全一致しているわけではありません)

簡単化かつイメージしやすいように以下の鉄道で使用する呼び名で

  列車:  Simutrans内での一般名称は convoi (convoy)、状況によって vehicle, vehikel
    乗り物全般を表わします (列車、自動車、船舶、飛行機、トラム、...)

  旅客:  Simutrans内での一般名称は goods
    郵便物や貨物も含めます
    同様に、積載と降ろしも含めて、乗車、降車と言います

  駅:  Simutrans内での一般名称は halt
    乗り物が停止して旅客の乗降を取り扱う施設全般です (バス停、港、空港も含む)


また以下の用語を使用します。

line: 路線
  複数の列車に割当てられる共通運行スケジュール
  ここでは簡単化のために、乗り物だけに割当てられているスケジュールも含めて
  一つの line (路線) と呼びます。
  (一般的に言う、「なになに線」というような「路線」ではありません)

link: リンク、Simutransではコネクションとも
  ある駅からある駅へ、一つの乗り物で直接行ける場合に、この関係を表します。
  複数の停車駅がある

source: 出発駅
destination: 目的駅  

nexthop: 次段停車駅
  旅客が保持している(心に決めている)次の乗換駅 (目的駅の場合もある) です。
  現在いる駅から一つの路線の列車に乗るだけで直接、このnexthopへ到達できます。

linkcost: リンクコスト
  linkで駅間を移動した場合にかかるコストの一般的な呼び方です。
  RouteCostでは、乗車してから下車するまでの列車の停車駅数を使っていましたが、
  文脈によっては、この計算方法に限定せず何らかのコスト評価を経て得られた
  コスト値とします。
  なおオリジナルSimutrans内部では、weight (重み、重さ) という表現を使っています。
  計算されたリンクコストは、駅の詳細情報画面の中で見ることができます。


--------------------
= R-RouteCost の実装の概要
--------------------
現在最新 (少なくとも Release 111.3 から) のSimutrans には、
すでにリンクの最小途中駅数を元にした旅客の経路計算が行われています。
ただしこの時のコストは16ビット符号無し値で表現され、
  最初に 8   (列車が来るまでの待ちを表す？)
  途中停車で 1
  乗換に 9   (上二つの合計)
になっています。

今回のRRCでは原則としてこのSimutransオリジナルの仕組みをそのまま使用することとして、
RouteCostのもう一つの機能である、駅での到着列車への乗車判断のみをまず実装しました。
また、これまで行われてきたようである RouteCost の拡張に追従できるよう、
このコスト値や、乗車判断の際の判定基準の一部のパラメータを設定で変更できるように
しました。
設定は、「高度な設定」ウィンドウの中の max_transfers (最大乗換回数) と
同じ場所で行うことができます。
なお、この設定が有効になるのは、次に駅ごとのlink再収集が行われるタイミングです。

----------
== 乗車の判断
----------
駅に列車が到着すると、その駅で待機しているそれぞれの旅客に対して乗車判定が
行われます。
この時、スケジュール上で次に停車する駅から順に走査して
 「その駅をnexthopとして持つ旅客を積載する」
を繰り返します。
(オリジナルSimutransの挙動)

この時、RouteCostでは以下の判断を加えています。
  この列車が、その駅へ行ける列車の中で最も途中停車駅数が少ないものか？
これを満たしていない場合は、乗車しません。

例えばA駅からB駅に
   普通列車なら途中 5 駅停車
   優等列車なら途中 2 駅停車
で各種別の列車が運行されていた場合、A駅にいるB駅あて(nexthopがB駅)の
旅客は、優等列車にのみ乗車します。普通列車が到着しても無視します。

この判断には、経路計算に先立つ駅ごとのリンク情報の収集の段階で
すでにリンクに記録されているリンクコストを使っています。


----------
== 拡張1: 途中停車駅数によるリンクコストの重みの設定化
----------
オリジナルSimutransでは固定であったリンクコスト計算の際の重みを
設定できるようにしました。

  routecost_initial
    リンクの始端で加算される値です。デフォルトは 8

  routecost_stops
    リンクの途中で駅に停車した際に加算される値です。デフォルトは 1

  routecost_transfer
    経路計算の時に、乗換で加算される値です。デフォルトは 9

同じ値が乗車判定にも使用されます。


----------
== 乗車判断でのマージン挿入
----------
乗車判断のさいに使われる条件式に、
  当該列車の目的駅までのコスト ≦ 最速列車の目的駅までのコスト ＋ マージン
となるようにマージン値を入れられるようにしました。

マージン値が適当な量であれば、乗客は期待より少し遅い(途中停車駅の多い)列車が
来てもその列車に乗車することになります。

例えばA駅からB駅に
   普通列車なら途中 5 駅停車
   快速列車なら途中 3 駅停車
   急行列車なら途中 2 駅停車
で各種別の列車が運行されていた場合、A駅にいるB駅あて(nexthopがB駅)の旅客は
マージンが 0の時:
   急行列車にしか乗らない
マージンが 1〜2の時:
   急行列車および快速列車に乗る
マージンが 3以上の時:
   全ての列車に乗る
という乗り分けをするようになります。

これにより、最速だけを待ち続けることなく、準優等列車にも乗車するようになります。

このマージン値の設定・算出には以下の三つの方法を実験的に導入しています。
これらのマージン算出値はすべて積算されて使用されます。
(つまり、複数のマージン決定を同時に使うことができます)

-----
=== A. 固定マージン
-----
設定にて
  routecost_load_margin
    デフォルトは0
を設定すると、乗車判定の際にこの値が、リンクコストに加算されます。
(経路計算には影響しません)

このマージン決定方法は、とても負荷の軽い処理であり、動作速度をほぼ維持したまま
乗車判定を改善することができます。

しかし、この値は全ての駅と路線に対して共通で、それも定数的に適用されるため、
路線ごとの事情の違いを吸収することができなくなります。
加算ではなく、比率の乗算で行った方がいいのかもしれませんが、それとて
路線ごとの事情を完全に吸収できるわけではありません。

-----
=== B. 待ち時間マージン
-----
(コンフィグでROUTECOST_CHOOSE_BY_WAITTIME が指定されている場合のみ有効です)
設定にて
  routecost_time_to_wait
    デフォルトは0
を設定すると、直近に乗車に成功してから現在までの経過時間を、この値で割った値を
マージンとして使用します。
設定値が 0 の場合や、直近乗車時刻が記録されていない場合は、この計算を行いません。
この値の単位は 1024msec(約1秒) です。

乗車判定によって、あるリンクについての待ちが長ければ長いほどマージンが
増大します。
乗車判定の結果、乗車すると判定された場合は直近乗車時刻が現在の時刻に更新されます。
(列車の空き容量には関係ありません。よって結局は乗車できなかった場合にも
直近乗車時刻が更新されてしまいます)

普通が多く優等が少い区間では、マージンがないと
旅客が普通を無視し続け優等が到着するのを待ち続けてしまいます。
この見送り回数マージンを入れることでこれを低減させられます。

この方式は「時間」を使っているので、値がグローバル設定であっても
比較的使いやすくなるのではと考えています。
  「だいたい世の中、何時間あれば１駅くらいは行くものだ」
という考え方ですね。
ですがやはり、「1駅」(距離ではない)ということと、地域格差が表現できないという
問題があります。

この方法は、列車への積載時の計算量の増加が気になるとともに、
プログラム内の記憶量も増大します。
(現在はリンク一つにつき4バイト)
なおゲーム時間と同様に 32bit で扱っていますので、これが溢れる時は
ゲーム時間も溢れています。

なお現在の実装では、駅ごとのリンクの再収集が行われると、直近乗車時刻は
リセットされてしまいます。(ゲームのロード時を含む)
リンクごとの直近乗車時刻は、駅詳細情報ウィンドウの接続している各駅の覧の
駅の右に "L=" に現在時刻からの差として表示されます。 (単位は1024msec)
ただし、その駅への旅客や貨物が過去に積載されたことがある時のみ表示します。

-----
=== C. 見送り回数マージン
-----
(コンフィグでROUTECOST_CHOOSE_BY_WAITTIME が指定されている場合のみ有効です)
設定にて
  routecost_hurry_by_wait
    デフォルトは0
を設定すると、乗車判定でリンクが無視されるたびに、この値がマージンとして蓄積加算されます。
次の列車到着にともなう判定ではより大きなマージンが使用されることになります。

リンクに対応する乗車に成功すると、蓄積値はリセットされます。
(正確には、乗車判定で「乗車」と判断されるとなので、
列車の容量に余裕が無く、結局乗車できなかった場合でもリセットされます)

待ち時間マージンと同様
「なかなか優等が来ないから、普通でもいいので乗ってしまえ」
という判断をさせられるようになります。
この方法では時間に関係なく「見送った回数」なので、路線ごとの事情をある程度は
とり入れたものになっていると思います。
しかしやはり、地域によっての優等列車の飛ばし具合の差を取り入れられていません。

計算は比較的軽いのですが、待ち時間マージンと同様にプログラム内の記憶量を必要とします。
(現在はリンク一つにつき2バイト)
値の上限は 15bit符号無し (32767) までで、それ以上はこの上限で打ち止めになるようにしています。
(なお残りの1bitは、このリンクが参照されたかに使っています。
 使用されていないリンクについての情報を隠すための措置です。)

なお現在の実装では、駅ごとのリンクの再収集が行われると、蓄積値はリセットされて
しまいます。(ゲームのロード時を含む)
リンクごとの蓄積値は、駅詳細情報ウィンドウの接続している各駅の覧の
駅の右に "H=" に続いて表示されます。
ただし、その駅への旅客や貨物が過去に積載されたことがある時のみ表示します。

--------------------
= 詳細情報ウィンドウでの蓄積値の表示について
--------------------
各リンクの情報はオリジナルでも駅の詳細情報ウィンドウにて参照することができます。
このパッチではこれに加えて、主に各マージンアルゴリズムの妥当性評価のために
以下の二つの情報を追加しています。
  L=  現在時刻 - 直近乗車時刻 (単位は 1024msecに切り捨てて表示)
  H=  見送り回数
これまでに直近乗車時刻が記録されていない場合は "L=none"と表示されます。

なお直近時間の表示は、そのリンクが一度以上使用されている場合にのみ表示します。
(そのリンクに基く乗車がこれまであった場合です。)
また後述の「リンクの再収集」が行われると、この「使用された」という情報も
失われてしまいます。

--------------------
= 参考: 駅のリンクの再収集が行われるタイミング
--------------------
駅ごとのリンクはいくつかの条件で再収集が行われます。
前述の通り、現在の実装では「待ち時間マージン」や「見送り回数マージン」に
使われる蓄積値は、この再収集のタイミングで失われてしまいます。
(若干重くなってしまいますが、これを保存するように努力することは技術的には可能です。)

全てのケースを完全に調べきれたわけではないですが、Simutransのソースから
読みとれる、この再収集が行われる条件を以下に列挙します。

スケジューリングカウンタによるもの: (karte_t::set_schedule_counter())
  全駅が対象。
  (どこか一つの路線や駅に対する操作であっても、全駅が再計算の対象になる)
  トリガーされると少しずつ計算が進行する。(その場で全駅一度に計算するわけではない)
  * マップの拡大
  * マップの回転
  * ゲームのロード直後
  * 編成の消滅、運行開始、スケジュール変更
  * 路線に所属する編成の増減で、路線の扱う貨物種別が変化
  * (編成の所属する) 路線のスケジュール変更
  * 停車点移動ツール (詳細条件未確認)
  * 駅のタイルの追加・削除 (これによって路線や編成の停車が変化することがあるため)

これ以外のトリガー: 今のところ見つかっていません。

--------------------
= 検討中の課題
--------------------
リンクコストの評価に 距離 / 評定速度 (つまり評定時間) を導入されている
方もいらしたようですが、より正確な所要時間を求められるかが疑問だったので
試していません。

一方で、TTT (簡易タイムテーブル) では実績所要時間の計測と計画所要時間の設定が
されているので、これであればリンクコストに使用できるかもしれません。
ただしこの場合、未計測の車両やタイムテーブルの設定されていない路線の
取り扱いをどうするかという問題があります。
(マンハッタン距離と車両の最高速度から概算で求めて代用するなどか？)

TTTと両方が有効な場合にこのコスト評価も試せるようにはしたいと考えています。
(ただし乗車判定は、やはり停車駅数最小やった方が軽い気がする)

また、乗車判定の改善方法もいろいろと考えられるとは思いますが、
  * なるべく記憶を残したくない (実行記憶も節約したいし、セーブするのも仕組み上困難に近い)
  * なるべく計算が軽くあって欲しい
という条件が厳しいところです。


--------------------
= ご利用上の注意点とお願い
--------------------
このパッチは現在、αクオリティです。
一切の動作の保証はできませんのでご了承ください。
簡単な動作は確認していますが、複雑な路線網を組んでの実験はほとんどできていません。

バグのご報告や機能改善のご提案はウェルカムです。
(ただし充分に対応できる余裕はございませんので対応が遅れましてもご了承ください。)
ご連絡は日本語フォーラム
  Japanese Simutrans Forum
の該当トピックへお願いいたします。

改造、パッチの再配布や
バイナリをビルドしての再配布もご自由にどうぞ。
機能の拡張時は、こちらにもお知らせ頂けると幸いです。
