TEG Railway

これはなに？

DMMのブラウザゲーム『TOKYO EXE GIRLS』（以下TEG）向けの支援アプリです。

TEG の2018年4月末のイベント『東京百景』で、スゴロク的なゲームが行われています。
東京の鉄道路線図を模した地図上、ランダムに設定されたゴール駅に向かって移動→到着するとボーナス、というようなものです

で、このスゴロク的地図が、ですね。
実際の鉄道路線とは似てもって異なる構成になっており、東京在住者でも迷うような感じです。

そこでこのアプリです：このアプリは『出発駅』と『到着駅』を指定すると、TEGのスゴロク地図上での最短ルートを検索・表示することができるのです。

配布物

ブラウザ動作版と、Windowsアプリ版とがあります。

ブラウザ版: ブラウザ上で動くバージョンです。JavaScriptを使用しています。
Windows版(Ver.0.3 + MapData5/12版): .net 4.6 上で動くデスクトップアプリケーションです。ラウザ版より少し多機能です。
ダウンロードしてzip解凍、TEGRail.exeを実行してください。

経路検索アルゴリズム

ちょっと質問もあったので、メモ公開しておきます。

使用しているアルゴリズムは「ダイクストラ法」の簡易版のような感じ：「すべてのオブジェクトの間の距離を１とする」ようにしているだけです。

例があったほうがわかりやすいと思うので。下記のようなごく狭い範囲の数駅の範囲：『御徒町出発→東京到着』の場合を例にして、路線検索する仕組みを説明します。

今回の検索は、オブジェクト指向での再帰的な検索を行う方法で作りました。まず前提として、「駅」というオブジェクトを作って、各駅は「自分の隣の駅オブジェクトを知っている」ようなオブジェクト網を作ります。
そして、「駅オブジェクト」には「お前の位置はｘ番目だ」という指定メソッドを持たせました。

検索は、大きく2段階を踏みます。

第一段階：『ゴールとなる駅から見て、各駅がｘ番目にたどり着ける駅である』というマッピングを作る処理。
第二段階は、第一段階のマッピングを前提に、『スタートとなる駅からゴールに近づく駅を選ぶ』処理。

第一段階

今回、ゴールを『東京駅』にしたので、「東京駅、お前は０番目だ」と指定します：青文字数字が「東京からの距離」です。

それを受けた（東京）駅オブジェクトは、自分が隣接する他の駅オブジェクトに対して「お前は（０＋１）番目だ」と指定します。
この場合、東京に隣接している「有楽町」と「神田」ですね。

で、この指定された有楽町駅および神田駅は、同じように・再帰的に、自分が隣接する他の駅オブジェクトに対して「お前は（１＋１）番目だ」と指定します。
今回の例（範囲）では、有楽町には『東京』しか隣接駅はなく、神田には『東京・御茶ノ水・秋葉原』の3駅があります。

ここで注意することは1点だけ。
「すでに一度ｘ番目」と指定された駅は、それ以降の「ｙ番目」指定を受けた際、その指定が「ｘ＞ｙ」でない限り捨てる、ということ。
そのため・・・

例えば「神田」は、「東京」「御茶ノ水」「秋葉原」に隣接しています。

神田は自分が「１番目」と指定されているので、自分の隣接する上記3駅に「お前は2番目だ」と指定しますが。
東京はすでに自分が「0番目」と知っているので、この指定を無視します。

つまりこれによって、「逆走」するようなことはおきません。

秋葉原は、神田と御茶ノ水（と御徒町）に隣接しています。その位置関係上、神田から「お前は2番目だ」と指定され、また御茶ノ水からは「お前は３番目だ」と指定されます。
こういう場合はより小さい「2番目」として動作します。

これによって、迂回ルートがある場合も「より近い」側だけを記録します。

これ以降も、各駅は自分が隣接する他の駅オブジェクトに対して「お前は（俺の位置＋１）番目だ」と指定。これをどんどん繰り返していきます。そしてその結果、全ての駅オブジェクトが「隣をｘ番目だ」と指定し終わったら、第一段階は終了です。
できたマップはこちら。

第二段階

・・・説明するまでもないですよね。

出発駅から開始して、出発駅からみて「より番号が小さい駅」を拾い。
その「より小さい駅」から、再帰的にさらに「より小さい駅」を拾う。
これを繰り返すことで、必ず最後には「0番目」の駅にたどり着けます。

その他、考察。

上記アルゴリズム、正直なところごり押しもいいところでもありまして。
上記の例では駅を『有楽町～御徒町近辺』だけに絞りましたが、実際には山手線は環状線です。ですから今回のような「3駅隣」の駅へのルート検索であっても、アルゴリズム的には『再帰的』に有楽町の向こう側も『新橋→浜松町・・・』というように調べていき、最終的には山手線一周すべての駅について距離作成してしまいます。
今回のTEGでの路線頭上にある駅は、山手圏近郊のたかだか160駅(!)くらいだったので、上記のやりかたで問題なかったですが、もっと大きい場合演算時間が無視できなくなる恐れもあるわけです。

マッピングの「隣に聞く」順番をチューニングすれば、もっと無駄なく==高速に計算できるでしょう。
マッピングの過程で一度（迂回かもしれない）最短距離を見つけたら、それより遠くなるような検索は無条件に無視させるとか。
スタートとゴール、両方から少しずつ検索することで、無駄な方向への発散を少なくするとか、ね。

また、今回のTEGでは「ｘ駅」という駅数しか勘定していませんでしたが。「実走行距離で一番近いコースは」みたいなのも、これに似たような感じで検索できます。
今回は駅数だったので、「次」を呼ぶときに「駅数を＋１」して勘定していたところを。
例えば「東京～神田間はｘｘｘkm」「神田～お茶の水はｙｙｙkm」というような情報を持たせておいて、それを積み上げればいいだけです。

『TOKYO EXE GIRLS』は DMM によるものです。