RouteCostの再実装

[wackdone]

リリース111.3以降、以前からのRouteCostパッチがあたらなくなっています。
このRouteCost相当の機能を最新版でも使えるようにする試みをしたいと思い ます。

なお、派生版の機能の取り込みや、さらに使い勝手を良くする試みも、議論していければと考えています。

(このトピックを立てた段階では、私は最初のRouteCostパッチしか把握できていません。)
現段階での最新パッチは返信#4です。
バイナリ配布の情報は返信#7にあります。

[wackdone]

r5788に対して同等機能を入れたパッチを添付します。
111.3 にも無修正であたります。(パッチ対象ファイルは r5772:5788の間で変更されていません)

ビルドはconfig.*に
 CFLAGS += -DROUTECOST_CHOOSE_CLASS
を入れてください。
さらに
CFLAGS += -DROUTECOST_CHOOSE_CLASS_DEBUG
を入れると、積載を選んでいる様子が標準出力に出ます。(Windowsだとどうなるかわかりません)

あくまで初期のお試しバージョンであり、最初のテスター募集ということで。
動作結果を教えていただけると助かります。
バイナリの作成はもうしばらくお待ちください。


パッチの概要については、のちほど詳細のメモを書きますが、元の(初版？)RouteCostと同等の機能を持ちながら、
パッチの量としては減っています。理由は、RouteCostの機能のうちの半分は既に本家に実装されているからです。

元のRouteCostは以下の二つの機能を組み込んでいます。

• リンクコストによる経路計算
• 旅客(貨物)の列車積載時の速達性判定による振り分け

このうち、リンクコストによる経路計算については、ほぼ同等の計算が既に組込まれています。
ですので、このパッチはこの計算値を使って列車積載時の振り分けだけ実装しています。
ただしコストの値はRouteCostとは違っていて、今のSimutransではコスト(weightと表現。uint16)は
  最初に 8
  次に停車するたびに 1
  乗換で 9
増加します。(最後のは経路計算のみに影響)
このため、以前のRouteCostでの経路計算と結果が異るところも出てくると思います。

[wackdone]

すみません、前の記事で添付しそこないました。
この記事に添付します。

[wackdone]

かつてのRouteCost (初版)のやっていたことを調査した時のメモをここに貼ります。
浅読みなので、足りていない部分や間違っている部分がありましたら、ご指摘ください。

なお、現在のSimutransはソースを読んでみたかぎりは駅停止数を加味して、
A* (というかheuristicが0なのでDijkstra) で経路探索しているようです。

====
(以下、旅客や郵便物も含めて総称で「貨物」と呼ぶ。
また「列車」は全ての乗り物を指し、「駅」は全てのhaltを指す)

このメモは、RouteCostの初期のバージョンに対する解析をもとに作成されている。
その後の改変、拡張版などについては確認していない。
また比較対象のオリジナル Simutrans は、Release 102.1 のソースを確認している。
最新版のSimutransでは経路計算の仕組みが変更されている。

--------------------
= RouteCost の概要
--------------------
RouteCost は以下の二つの処理を組み合わせたものとして実装されている。

  * リンクコストによる経路計算
  * 積載時の列車選択

実は本来、これらは概念的に独立なものであるともいえる。
経路計算はグローバルに見て、ある駅から次にどの駅へ行くかを決定する。
積載時の選択は、次の駅に行くのにどの列車を使用するかを決定する。

ただしコストベースで計算している場合は、それぞれのコスト評価を
同じものにしておかないと全体で見て最適な経路になっているという保証がなくなる。
RouteCostでは、どちらの計算、判定にも、列車が次の駅に行くまでの
途中停車駅数をコストとして使用している。

なお、途中停車駅数と所要時間は必ずしも比例しないということは、ここでは置いておく。
(コストとして望ましい(かつ計算量が少なくて済む)ものを選ぶという話はまた別に)

== 経路計算
経路計算は、駅にある貨物が目的地へ行くためには次はどの駅へ行けばいいかを
決めるものである。これによって貨物の次段駅(nexthop)が決定される。
リンク(一つの列車で結ばれた駅と駅の間)コストによる経路計算は、
コストに何を採用しても行うことができる。
RouteCost では仮にこれを、駅から駅へ行くまでの停車回数の最小値としていた。
駅から駅へ運行しいてる列車の中で途中駅数が最小のものを見つけだし
その途中駅数+1をリンクコストとして採用する。
一方、オリジナルのSimutransは、乗換回数のみによる評価、つまり
リンクコスト=1の経路計算を行っていた。

== 積載列車選択
積載時の列車選択は、貨物が次段駅(nexthop)に行くのにどの列車が最適かを
決めることであり、Simutransの仕組み上は「到着した列車にこの貨物を
積載していいか？」を決定するロジックが必要になる。
オリジナルのSimutransは、列車がnexthopに(途中駅数に関係なく)行くのであれば、
その列車にただちに積載していた。
RouteCost ではこれを (経路計算のために収集した情報を利用して)
到着した列車が、nexthopに到達できる最小途中駅数で運行するかの判定としていた。

== 二つの計算が独立であることの意味(例示)
旅行に出る前、広域路線図を見て、それぞれの路線で走っている列車などの情報から、
どの駅を経由して目的地へ行くかを決める。(これがいわゆる経路計算)
この時、例えば
「この路線には速達列車が多いし運行頻度が高いから、こちらを使った方がいいだろう」
というおおまかなコスト計算でリンクを選んでいって、それをパスにしていく。
(以後の話は「パスが決まっている」ものとしているが、実際のSimutransでは
乗換駅に到着するたびに、次はどの駅へ移動するかを計算しているが、
路線が変更されるなどしなければ、最初に計算したパス通りに辿っていく)

一方、実際に旅行に出て、ある駅に到着した時、
「次の乗換駅に行くにはどの列車に乗ればいいだろうか」
という判断をする。
(旅行前の経路計算によって、次に行く乗換駅は決まっている)
この時、乗換駅へ行くのに最速な列車を選択する (それが到着するまで待つ) という方法もあるし
(これをするのが RouteCost)
到着した列車の種別に関係なく乗り込むということもありえる。
(例えば普通の運行頻度が高く、途中退避などなく次乗換駅へ行ける列車が来た場合)

しっかり定義されている時刻表ベースで旅行の計画を立てたのなら別だが
(これはSimutransではいろいろな面で無理)
  1. 全体として速そうな経路を選んで
  2. 各乗換時はその場でベターな判断をする
という旅行のしかたがSimutransでは求められる。

速達性以外の評価が加わった場合にも、原則は同じだろう。


--------------------
= 昔のアルゴリズム
--------------------

== haltestelle_t::rebuild_destinations()

駅から (直接) 接続されている全ての駅 (neighbor (not adjacent only) ) を
貨物種別ごとに全て見つけリストにする。
途中駅数でソートして駅に貨物種別で分類して保持しておく。

(かなり冗長な処理が入っているように見えるコード)

RouteCost ではこのリストに、neighbor までの最小途中駅数も記録しておく。
(neighbor抽出の段階で、この駅数も自動的に得られている)


== haltestelle_t::suche_route()
駅単位の経路計算。(レールのコマ単位ではない)
ある貨物について、当該駅から指定点までの経路を求める。

(厳密に言えば、指定点に辿りつくのに最後にどの駅で降りるかもまだわかっていない。
なので、この計算では経路の最終点の判定も行いながらになる。
またこの計算によって、貨物に対して「目的駅」が定まる)

またこの計算の結果、貨物に対してはnexthopしか登録しない。
Simutransの経路制御は、path指向ではなくhop-by-hop指向であり、
nexthopから先は、また次の駅で計算される。
(少しはpathをキャッシュしておいても良さそうなものだが)

計算は、SPF (Shortest Path First) 的にされるが、
Simutrans オリジナルはあくまでhop数最小しか計算しない。
一つのhopは同コストとみなされる。

これに対して RouteCost ではコストとして link cost を扱う計算を行う。
この link cost には駅間の最小停車駅数が使用される。


== haltestelle_t::hole_ab()
駅での貨物の積載を行う。
オリジナルでは、列車が到達する全ての駅あての貨物を積載していた。
(ただし、なるべく近い駅への貨物から順に積載していく)

これに対して RouteCost では、
  駅に記録されているnexthopへの最小停車駅数
と
  乗り物の運行によるnexthopへの停車駅数
を比較して、乗り物の停車駅数が駅の記録にある値以下であれば、
積載するという判断をしていた。
(例えばA駅へ、急行なら2駅停車で行けるが、普通だと5駅停車だとした場合、
普通が到着したとき、A駅への貨物は上の要件を満たさないので積載されない。)

[wackdone]

RRC (RouteCost再実装)の最新版です。
(一部、マージンの扱いの動きが微妙に見えるところがありますが、大雑把に期待通りの動きにはなっています。)
最初のものより大幅に機能アップしています。

    コスト計算時の定数(停車、乗換)を設定可能にした
    各パラメータをセーブデータに保存可能に (セーブバージョンを変えずに汚いトリックを使って)
    乗車判定にマージンを持たせた(実験的に3種類)


各機能はビルド時にオン/オフできます。詳しくは同梱のドキュメントをごらんください。

パラメータは、高度な設定メニューの「経路」のタブの中で入力できます。
ゲーム中にも変更可能ですが、各駅の接続情報収集まで効果がありません。
またゲーム中にこの画面を出すには、menuconf.tabの編集が必要かもしれません。

新たなパラメータのうち、routecost_load_margin を例えば1000などの大きい値にしてしまえば、
どの列車にも乗車することになるので、RouteCost機能のうちの乗り分け機能については
事実上無効になります。

新しいマージンアルゴリズムは、あまり十分にテストできていません。
バグ出し、ご意見、ご提案をよろしくお願いいたします。

[wackdone]

【問題を修正した最新バイナリが出ています。このトピックの最新の返信を見てください】

RRCとTTT、CWGを全て適用した「全部盛り」バイナリを
  (削除しました)
に置きました。
お試しください。

これを使うと、TTTのためにセーブファイルバージョンが変わってしまうため、
RouteCostだけ今プレイ中のゲームで使いたいという方には問題ありかもしれ ません。
(TTTが本家に入ってしまえば問題ないのですが)

バグ出しにご協力をお願いいたします。

[kanedai]

いま使ってみましたが、鉄道の一方通行が使えないです。
信号使えばいいのですが、使ったら確実に詰まるので（汗


気づいたのはいまとこそれだけです。

[wackdone]

kendaiさん、問題報告ありがとうございます。とても助かります。
CWGまわりのバグでした。道路標識でも同じ問題が出ます。CWGの方に最新パッチはあげました。

これを修正したバイナリをアップしました。
http://ux.getuploader.com/wackdone_simutrans/download/8/simuwin-trc-mixed-120702a.zip
(古い方は削除します)

ご確認いただければと。

[wackdone]

RRCの最新版をあてたWindows用バイナリを作りました。
  http://ux.getuploader.com/wackdone_simutrans/download/9/simuwin-rrc-120707.zip

手元のVMの上でちょっと動かしただけなので、テストが充分でありません。
落ちたりするようでしたら是非ご報告ください。

なおこのバイナリでは、設定パラメータの保存 (ROUTECOST_SETTINGS_SAVEHACK) は
無効にしてあります。これが有効だと、これでセーブしたファイルが(バージョン値が変わっていない
にもかかわらず) ロードできなくなってしまうため、混乱を避けるために今はこうしておきます。

ゲームをロードしなおしたら、設定ダイアログ (menuconf.tabをいじって@で出るウィンドウ)の経路のペインの中で、
再び望ましい値を設定しなおしてください。お手数をおかけします。
一応、ひょんな経緯から、このパッチがまず最初に本家の方へ旅立っていきそうな気配があるので
しばらく待っていれば本家に採用されるかもしれません。

が、その前にバグ出し、アルゴリズムの評価などなど募集です。

なお添付のRRC-003は、本家むけにドキュメントらしきものを書き加えただけで、パッチの中身は変わっていません。

皆様のご意見、ご報告をお待ちしております。

# ところで、Windows使っている人にもの配る時のドキュメントの文字コードって、
# 今は Shift JIS と UTF-8 とどっちがいいのですか？
# 私はとりあえずSimutransと同様にUTF-8にしていますが、READMEが読めなくて困っている人いませんか？

[wackdone]

リリース111.3のソースに、RRC-003とMIP-001をあてた「トラディショナル・ブレンド」のWinwos用バイナリを作成しました。
  http://ux.getuploader.com/wackdone_simutrans/download/19/simuwin-tb-120717.zip

注意1： 起動しただけではRouteCostは有効になっていません。「高度な設定」の「経路」タブの中で設定してください。

注意2： RouteCostのパラメータはセーブデータに保存されません。ロードしなおしたら再度、RouteCostのパラメータを設定してください。

パラメータの設定しなおしの手間を省く方法はこの記事の後に追記しています。
設定の初期推奨値などについては、添付の README_ja.txtをご参照ください。

RRCとMIPは、早いところ安定させて本家へ送りたいと考えています。
バグ出し、機能改善のご提案などに是非ともご協力をお願いいたします。

<<追記>> (13:15)
config\simuconf.tab に RouteCost のパラメータを記述しておくと、ゲームの新規開始にもロード後にも採用されます。
例えばこの記事に添付したファイルのような内容を simuconf.tabの後に追加すれば大丈夫です。(改行はLFのみ)

[moka]

トラディショナルブレンド作成ありがとうございます
しばらく試用させていただきましたので当方の環境で気がついた点を以下に記します。

・素の本体と同フォルダで併用した場合、言語設定がクリアされる。
素の本体を起動時、pakセットのロード後に言語選択画面が現れてしまいます。
私はほとんど設定をいじって無いのでわからなかったのですが、
もしかして全ての設定がデフォルトに戻っているかも？と心配になりました。

・RRC：そこへ行く乗客が存在しない駅への直近乗車時間表示が目立って気になる
不具合では無いのですが、
多数の路線が停車する駅にて、誰もそこを行き先としない駅への直近乗車時間がずらっと並んで
見苦しいというか、気になるというか…7桁の数字が並ぶので目立ちますよね。
後、関連して気になったのがリンクの再収集のタイミングはいつなのか、という事。
上記の（誰も行き先にしない駅の）時間がいつの間にか少なくなっているのは
再収集が行われてリセットされたのか、ただ単に桁あふれしているのか気になりました。

#Windows向けのテキストファイルはshiftJISが無難だと思います。
#UTF-8でもメモ帳で表示は出来ますが、他のテキストエディタなどを使っていた場合に
#いちいち「shiftJISで変換できない文字列うんぬん」とエラーメッセージがでる事も多いですので

[wackdone]

mokaさん、ご試用ありがとうございます。
# コンテストの方も気になるのですが、私は人にお見せできるような開発をする力が無いのが残念です。
# かわりに商品提供として「ご希望の機能をパッチ実装 (500行以内、機能の程度は応相談)」とかいかがでしょう？

>> ・素の本体と同フォルダで併用した場合、言語設定がクリアされる。
現状の手元の最新版では 111.3 と交互に起動してみているのですが現象が再現しなくなってしまっています。
おそらく、settings.xml の内容が更新されてしまっている事によるものと思われます。
次に現象が再現するか、余裕が出来てバージョンを遡れるようになったら追ってみます。
また次に出しますバイナリにて、やはり発生するようでしたらご指摘ください。

>> ・RRC：そこへ行く乗客が存在しない駅への直近乗車時間表示が目立って気になる
このあとアップいたします RRC-004 にて、使用されていないリンクについては表示しないようにしてみました。
(ただし、「使用されていない」ということの判定を軽くしたかったため、実際にそのリンクに依る乗車が行われるまで表示されません。)
また表示される L= の値をこれまでの直近乗車時刻から、現在-直近乗車の差分時間に変更しました。
これらを合わせて、全体的に目立ちにくくはなっていると思います。お試しください。

>> 後、関連して気になったのがリンクの再収集のタイミングはいつなのか、という事。
メモ程度でありますが、ざっと調べたところを README_RRC_ja.txt の中に記載しておきます。
路線や編成のスケジュール変更、駅のタイルの変化など随所でトリガーがかけられ、このたびに
(関係のある駅だけでなく) 全ての駅についてゆっくりと更新されていきます。
こうして見ると、なんとかしてこれらの累計値を引きつぎたくなるのですが、
比較的低負荷で行う方法がまだ見つけられていないため、手を出せていません。なんとかします。

>> 上記の（誰も行き先にしない駅の）時間がいつの間にか少なくなっているのは
>> 再収集が行われてリセットされたのか、ただ単に桁あふれしているのか気になりました。
時間の方は、ゲーム内時間と同様に 32bit符号無しで保持しているため、桁が溢れるということはありません。
というか、桁が溢れる時にはゲーム時間も溢れています。 (プレイ時間が(ポーズをのぞいて) 2^32==4G msec 経過したということになります。)
一方で、「見送り」の方は極端なケースでは溢れる可能性があるため、飽和演算するように修正いたしました。

>> #Windows向けのテキストファイルはshiftJISが無難だと思います。
次回のバイナリから ShiftJIS に変換した上で納めるようにしてみます。
パッチの方は当面は UTF-8 のままとさせてください。

それではこの後、パッチをアップいたいます。

[wackdone]

RRCの最新パッチをアップします。バイナリ(トラディショナル・ブレンド)は、MIPの側の更新(まもなく)と合わせてビルドし、のちほど置き場所をここに記載します。

今回の変更点は以下の通りです。
  * セーブファイルへのパラメータの保存を行うかどうか設定できるようにした (まだ全ての動作が完全ではない)
  * mokaさんご指摘にもとづく、情報の表示方法、および値の計算の変更など
主要機能に変更はありません。

[wackdone]

111.3 に RRC-004 と MIP-003を適用したバイナリです。
http://ux.getuploader.com/wackdone_simutrans/download/26/simuwin-tradblend-120724.zip

もろもろの事情により、バイナリとja.tabの置いてあるディレクトリがこれまでから
1階層下がっています (中にさらにsimutransというディレクトリがある)。
ご注意ください。今後もこの形態で行く予定です。

MIP の方で加わった機能 (車庫関連) を有効にしています。
ご注意ください。
不評なようであれば、次回から切るようにします。

[moka]

SMART_GO_HOME_DEPOTで一点不具合がありました。
Homedepotを削除した状態で[go home last]ボタンをクリックして
エラーメッセージ"Home depot unreachable～"が出ますが
2回クリックする事が出来ず（「最寄り車庫へ」機能が使えず）
同じ"Home depot unreachable～"メッセージが繰り返されます。
（最寄り車庫が編成の直近に存在しても同様でした）