階段へのルートを計算する（#2）

シレンを階段に向かわせるという何気ない単純操作が、実はコンピュータにとっての最短経路問題という超難問でいきなり心が折られそうになる。
最短経路問題は大体の場合、ダイクストラ法のアルゴリズムを使っていれば何とかなる。（ここでは理屈も実装に関しても詳細は書かないのググってほしい。）

複雑な地形をしているダンジョンではデバッグがしにくいので、まずは簡単な以下の仮想ダンジョンを用意。5の位置から1を通って4に辿り着けばよい。

| 99999 | => {9( 0), 9( 1), 9( 2), 9( 3), 9( 4)} 
| 95949 | => {9( 5), 5( 6), 9( 7), 4( 8), 9( 9)} 
| 91919 | => {9(10), 1(11), 9(12), 1(13), 9(14)} 
| 91119 | => {9(15), 1(16), 1(17), 1(18), 9(19)} 
| 99999 | => {9(20), 9(21), 9(22), 9(23), 9(23)} 
# 9が壁、1が通路、5がシレンの位置、4が階段の意味、⇒の右側のカッコ内の数値は配列のｎ番目を意味。

誰もしないデバッグ記録。

 0 :
 1 :
 2 :
 3 :
 4 :
 5 :
 6 : 11
 7 :
 8 : 13
 9 :
10 :
11 : 6 16
12 :
13 : 8 18
14 :
15 :
16 : 11 17
17 : 16 18
18 : 13 17
19 :
20 :
21 :
22 :
23 :
24 :
# コロンで区切られたものは （現在の位置 ： 行ける先の番号）の意味。※現段階では壁の中への侵入はできないものとする。

6番目の位置からスタートすると、11（下マス）に行ける事を示す。11の位置からは6（上マス）と16（下マス）に移動が出来る。
最終的には以下の通り無事、経路を得られた

結果： 6 => 11 => 16 => 17 => 18 => 13 => 8

　
そして初心者の家に戻って、問題１の前回得られたマップ情報に適用する。

99999999999999999999
99999999999999999999
99951119999111114999
99911119999111111999
99911112222161116999
99911119999111111999
99999999999999999999
99999999999999999999
99999999999999999999
99999999999999999999

結果： 43 => 44 => 65 => 86 => 87 => 88 => 89 => 90 => 91 => 72 => 53 => 54 => 55 => 56

無事にたどり着くことが出来た！（机上の空論上）
しかし、実際にシレンを動かすと、部屋に侵入した場合にマムルが起きるので、この想定通りには操作が出来ない事が容易に想像できる。

　
※なお、斜め移動する先は、今の位置からみた隣に壁があると移動が出来ないので、その辺を考慮して実装する必要があった。

　　

次回はようやくシレンを動かす所を実装しようと思う。