迷路の探索

前回の迷路作成に続き、今回は探索です。

幅優先探索

迷路探索の方法は色々あるようですが、今回は幅優先探索でやってみようと思います。
スタート位置から4方向を調べ、道がある方向へ移動して毎回4方向を調べるというのを1マスずつ繰り返していき、分岐がある場合は平行して調べていくという方法。

1.迷路を作成する
2.各マスの訪問履歴を作成する
3.スタートのマスをキューに格納する
4.キューの先頭から一マス取得する
5.取り出したマスがゴールなら終了
6.手順4で取り出したマスから上下左右の何れかに移動する
7.移動先のマスが迷路外でないことを確認する(迷路外の場合は手順6に戻る)
8.移動先のマスが道またはゴールであることを確認する(道でもゴールでもない場合は手順6に戻る)
9.移動先のマスが未訪問であることを確認する(訪問済みの場合は手順6に戻る)
10.移動先のマスをキューに格納し、訪問履歴を更新する
11.4から10をキューが空になるまで繰り返す
引用：全探索アルゴリズム入門

これをJavaScriptで作成していきます。
迷路作成部分は前回の物をそのまま使用します。
迷路描画は正方形の壁の方で。
とりあえずはスタートは左上、ゴールは右下にしておきます。

グレーの線が探索してきたマスで、赤の線がゴールまでの道順です。無事にスタートからゴールまで辿り着いているのが分かります。
ほとんどのマスを探索しているようで大変そうです。
分岐地点を並行して調べていってるので、赤線は（多分）最短経路です。

キューに追加する時に、探索位置x,yの他に今までの経路rtも一緒に保存するようにしています。rtの中身もキューというかスタックのような物です。
キューから取り出したものがゴール位置だった場合、一緒に保存されているrtにはスタートから今までの経路が入っているということになります。

スタートとゴール地点のランダム化もしてみました。

注意点等

迷路と関係ないんですが、JavaScriptの2次元配列の初期化は注意が必要です。

他、経路を保存する時にもハマりました。
キューから取り出したrtですが、経路を追加する時にそのままrtに追加すると上手くいきません。
これで3日くらい悩みました（笑） そしてJavaScriptの配列は参照渡しということを思い出したのです。他の言語もそうかもしれないが。
そのまま追加だと、全て同じ配列に追加されていたのだった。
というわけで、newRouteという配列を新しく作り、そこにrtの内容をコピーしてからnewRouteに新しい経路を追加するというやり方で上手く動作しました。

---