追いかけや追いかけられゲームや脱出ゲームでは迷路が必要となる場合があります。
必要に応じて迷路を作ります。
少ない数であれば手作りをすることもできるのですが、プログラミングを生かして自動生成したいものです。
迷路を作るアルゴリズムは基本的には何種類かあってそれらが使いまわされているようです。
ここでは成長木アルゴリズムというものを使って壁を自動生成することによって迷路を作るプログラムを作ってみました。
先ずは、大きさを決めるて周囲を壁で覆います（２枚目の画像）。すると必ず壁になる壁の開始点（画像で白い四角で表示したもの）が決まります。
そこから手順は次のようになります。
①ランダムに一つの開始点を選びここから壁の生成を開始する（３枚目の画像）。
②上下左右からランダムに生成方向を決め、そちらにある開始点と接続する。
その際に自分自身とぶつかる方向は避ける（４枚目の画像）。
③壁の生成が袋小路に入り込んだら一番近い生成可能な場所に戻る。
④他の壁にぶつかったらそこで壁の生成を終了する（５枚目の画像）。
この①～④を繰り返します。全ての開始点が壁になったら終了です。

迷路生成の様子をYoutube動画にしましたのでよろしければご覧ください。

美しい迷路を作るアルゴリズム
体験申し込みお待ちしております。
それでは。