こんにちはみがきこ
網戸にカメムシの卵があったので，急いで殺虫剤を買いました．
今回はUnityで迷路を自動生成したときの備忘録です． 自動生成に使用したアルゴリズムは穴掘り法です．
参考文献
完成図
サイズ: 5×5
サイズ: 51×51
サイズ: 101×101
穴掘り法
すごく簡単に言うと「穴を掘り続けて迷路を作る」アルゴリズムです．(そのまんま)
今回は下記の条件でアルゴリズムを実装しました．
・制約
1．迷路の横・縦のサイズは奇数．
2．横・縦の最小サイズは「5」．
・実装したアルゴリズム
1．奇数座標(x, y)をランダムに取得し，基準座標とする．
2．基準座標の上・下・右・左の4方向から1方向をランダムに取得．
3-1．ランダムに取得した方向の2マス先が壁ならば，そのマスまで掘る．
3-2．進めないならば，その方向を除いた他の方向をランダムに取得し，手順3-1．
3-3．全方向に進めないならば，1つ前の座標に戻り，残りの方向をランダムに取得し，手順3-1．
4．既定の回数になるまで手順2，3を繰り返す．
おそらく再帰かスタックを使用すると思います．
自分はスタックで実装しました．
ソースコード
若干無駄な処理がある かつ このままでは動かない気がします．
あくまでアルゴリズムの参考までに．
まとめ
今度はスタートからゴールまでを探索するAIを書いてみたいですね．
多分生成と同じ方法で解けると思ってます．
