ガチホコシミュレータ#

ガチホコシミュレータとはステージ上の任意の位置をクリック（または何かしらのアイコンをドラッグアンドドロップ等で移動させれば）その地点でのガチホコのカウントの値を表示してくれるシステムである。

あると便利だなと思いつつ、そのようなシステムは実際にはない。何故ないのだろうか？

ガチホコのカウント計算式#

ガチホコのカウントの正式な計算式は内部解析でしかわからないが、概ね以下のようになっているのではないかと推測される。

まず、ゴール地点を 0 とし、初期のガチホコの位置を 100 とする。更に、ステージ上に Graph Node という両方向（一部は一方向かもしれない）のノードを用意して通行可能であれば互いを連結する。そして、ノード自体はメッシュ構造に配置されているとする。

そして、ゴール位置から初期位置までの最短経路を求め、経路長が仮に 50 だとすれば 1 つの経路の重みは $100÷50=2$ がノード間の距離となる。つまり、ノードを 1 つ移動するごとにカウントが 2 減るということである。

あとは初期位置から各ノードの最短距離を計算する。これは簡単そうに見えるがやってみると実は少し難しかったりする。考え方としては接続しているノード（隣接ノードと呼ぶことにする）の中で最小の値を持つものにノード距離を加えたものが自身のノードの距離となる。

この付近の考え方はエルデシュ数そのままなのであるが、話がそれるのでそれは置いておこう。

隣接ノードの値がちゃんと最小化されていないと自身のノードの値もまた計算ミスを起こしてしまうという点だ。

最短ルートの計算法#

一般的に最短ルートはダイクストラ法と呼ばれるアルゴリズムで求めることができるのですが、これは各ノード間の距離がわかっている場合にしか使えません。今回はノード間の距離自体はわからないのですが「接続していれば距離 1」とみなすことで使うことができます。

実際の距離はスタートからゴールまでのノード数で 100 を割れば求められます。ダイクストラ法自体は移動するとコストが減る場合には機能しません。何故なら、ダイクストラ法は「ループは避けて移動するほうが効率が良い」ということが前提となっているアルゴリズムだからです。

もしも負のコストを含むようなグラフが与えられた場合にはループすることでいくらでもコストを下げることが可能になるグラフが存在します。そうなってしまってはダイクストラ法は機能しないわけです。が、ガチホコにおいてある特定の位置でぐるぐる回っていればカウントがいくらでも減るようなバグ・仕様はないので今回は無視できます。

他の探索法について#

ダイクストラ法以外にもさまざまな探索アルゴリズムがあり、実は今回のように非負数かつ全てのノード間の距離（重み）が等しい場合には幅優先探索が最も効果を発揮します。

なので別にダイクストラ法でなくてもいいのですが、気が向いたらダイクストラ法と幅優先探索の二つのアルゴリズムを実装してみようと思います。

どうやってシミュレータを提供するか#

ブラウザベースでやろうかとも思ったのですが、せっかく Swift を勉強しているので Swift で実装するのもいいかなと思っています。

ステージの画像自体はかなり大きいものになるのですが、16:9 なのでスマートフォンの画面サイズと近く、またステージの半分の画像さえあれば機能としては問題ないので表示に関してはそこまで心配していません。

拡大・縮小機能などがあればよいのではないかと思っています。また、ステージごとの勝率のデータなども載せたいと思います。リリースは、まあ今月中にできればいいかなあと思っていたりいなかったり。

画像のライブラリやチャートのライブラリを駆使して面白いアプリに仕上げたいですね。

ちなみに#

いろいろな探索法について述べたが、仮にノードがメッシュになっているのであればゴール位置とスタート位置さえわかっていれば $(i+j)×cost$ で簡単に計算できてしまう。

が、それでは面白くないのでここでは解説を省略した。