迷路作成アルゴリズム（２）穴掘り法
棒倒し法と比べると、ちょっと複雑だけど再帰さえ使えれば簡単。
１．奇数のマスを用意する（２５＊２５等）
２．起点を決める（座標は奇数にする）
（起点は道にする）
３．ルーチン（ａ）をコール
※ ってことで、マスはポインタで、座標は値で渡す。
ａ−１．座標から左右上下を調べ、全て道か座標空間外ならリターン
ａ−２．乱数で左右上下を決める。
ａ−３．２歩先を調べて道か座標空間外ならａ−２に戻る
ａ−４．２歩先まで掘り進む
ａ−５．２歩先の座標を起点にして自身を再帰する
ａ−６．ａ−１に戻る
問題点としては、最初の起点を中心に放射状に迷路が出来る事。
ループの無い迷路になること。（左手法とかで、必ずゴール出来る迷路になってしまう・・・）
あと、まっすぐな道が作られにくく、くねくね道になる事。
乱数で左右上下を選択する際に、前回の方向をベースに確率を変動させることで、この辺は対応出来るでしょうけど・・・。
致命的なのは、必ず奇数の点で曲がり道になること。これは・・・ちょっとツマラナイです。
再帰を使わなくても、スタックを使えばそれなりに書けそう。座標だけスタックに積んでおけば良いから。（スタックすら使えない時は、スタックをシミュレートすれば良いか？）
コメント