レンタルSNS
simutransで行こう 中継点をうまく使おう
プロフィール

空間軌道×箱積駅舎

中の人:128な人
うにゅー

最新記事
カテゴリ



最新コメント
めも.txt
リンク&RSS
時計&カウンター
おまけ

中継点をうまく使おう

あんまり使いどころの分からない「中継点」ですが、うまく使えばルート検索の負荷を抑えられます。
特に長距離ノンストップなルートに有効です

ルート検索は2点間の移動の繰り返しであり、移動方向が縦と横に限られるので簡単に言ってしまえば格子の移動と同じことです。
中学だか高校で習うやつですね。
細かい意味は教科書でも見て下さい

route.png

10マス四方自由に動けるとすると最短距離で1024通りのルート候補がありますが、中継点を1つ入れるだけで64通りまで減ります。4ケタ→2ケタの減量です。
実際は地形や通れるルートが限られるのでもっと複雑でしょうが減ることは確かです。
100マス移動の長距離系統だと中継点の威力がよく分かります。


特に有効なもの
 長距離船 水タイルのほぼすべてが検索対象になるので格子の計算と同程度の効果はあるかと思います。
 長距離バス 中継点代わりに高速道路入口にICを設置、それを停車駅にすると違和感なく&高速通らずにずっと下道走行なルート発生を防止することもできます。

それなりに有効
 長距離列車 バスに比べれば本数も少なく、線路にルートが限られるので目に見えるほどの効果はありません。

おまけ
 「車庫に送る」コマンドが重い時があるのはつながっている全線の全車庫へのルートを見比べているためです。
 そのため短絡線で幹線同士をあちこちつなぐと重くなります。
 スケジュールや経路編集で車庫を自分で追加した方がスムーズに車庫送りできます。


※飛行機は地形の影響を受けないのでむしろ設定しない方がいいです。
中継点にしている所の線路を撤去してしまったりするとルートなしでorzするのでマーカーを置いておくといいです。
特に複数人プレイの場合は必須

関連記事

コメント

非公開コメント

ルート検索アルゴリズム

記事のルート検索アルゴリズムは、非効率的です。

(1) 1ますで行ける範囲を求める
(2) Nますで行ける範囲から、N+1ますで行ける範囲を求め、これを繰り返す
(3) 終点が行ける範囲内に収まったところで検索を打ち切る
とすると、各ますごとに始点からの距離が求まります。

経路は、終点から1ます進むごとに、始点からの距離が1少なくなる場所を進むようにします。候補は複数ありますが、どれでもかまいません。

この方法では、計算量は距離の2乗です。

No title

書きそびれたため、連続で失礼します。
先程の①の計算方法についての詳細はここには書きませんが、「場合の数 道順」でググるといっぱい出てきますので、詳細はそちらをご覧ください。

No title

意図してることはわかるし、大体合っていると思いますが、計算は本当にあっているのでしょうか。
10×10マス、海洋上、障害物なし、(ナナメ無し)の場合、
①最短ルートのみを検索する。総数は20C10=184756通り
②「東西南北4方向のどれかに進む」×20回
 (20回目を計算した時点で目的地に着くルートが見つかり、探索が打ち切られる)
 総数は4の20乗=約1兆通り(1E+12、13ケタ)
②が正しいのではないかと思っていますが、よくわからないです。

どれにしても、中継点を設定することで総数は大幅に減らせます。
①→中継点までの計算、中継点からの計算それぞれ252通り
②→それぞれ約100万通り