こんにちは、クリエイティブSecの長谷川です。
本日は表題の通り、迷路の生成と自動探索するプログラムを作ってみました。

作ったもの

早速ですが下記が今回作成したものとなります。

迷路の生成方法については、今回3種類を実装しました。

• 壁伸ばし法
• 棒倒し法
• 穴掘り法

そして、探索方法に関しては、下記の2種類を実装しています。

• 深さ優先探索
• 幅優先探索

ロジックの説明については割愛

生成方法や探索方法の細かい説明はAlgofulというサイトにて公開されていますので、そちらを読んでみてください。

読むの面倒くさいよという人向けに簡単に説明すると以下のような感じです。

探索方法については簡単に説明すると、深さ優先探索の場合はスタートしてから分岐があった場合
とりあえず行き止まりになるまではひたすら進み、行き止まりに突き当たれば
1つ前の分岐点まで戻り、違う道を再度探索するという形になります。
人間が迷路を解こうとするときの方法と一緒ですね。

一方、幅優先探索の場合は、分岐があった場合は、すべての分岐した方向を同時に探索していくという方法になります。
イメージするなら、迷路のスタート地点から水を流し込んでいくイメージかなと思います。

感想

実際に迷路の生成法と探索方法を変えてやってみるとわかるのですが
幅優先探索の場合は、ゴールへの道が複数通りあったとしても最短ルートを求めることが出来ます。
一方、深さ優先探索は、すんなりゴールにたどり着けられれば・・・というところはありますが
今回作った規模の迷路だと、幅優先探索に比べて早い時間でゴールを見つけることが出来ます。

しかし今回の深さ優先探索の実装では、ゴールが右下にあることが前提のため
分岐したときに探索する方向の優先度合いは右→下→左→上の順番になっているので
ゴールを左下や右上に設置すると、時間がかかってしまうことがあります。
その場合は、幅優先探索のほうが早いですね。

また、深さ優先探索の特徴として、あくまでもゴールへのルートを一番最初に見つけたものが結果として表示されるため
それが最短ルートだとは限りません。

他にも探索方法はいろいろあったり、もっと高度なものを応用して
たとえばナビゲーションシステムが作られたりしているわけですが
そういうものを開発してきた人たちの凄さがわかりますね。