開発 > プログラム
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機能のうちの乗り分け機能については
事実上無効になります。
新しいマージンアルゴリズムは、あまり十分にテストできていません。
バグ出し、ご意見、ご提案をよろしくお願いいたします。
ナビゲーション
[0] メッセージ一覧
[#] 次
フルブラウザ表示にする