チワ裏

とあるゲーム作りたい人のチラシの裏

開発日記 その6 自作迷路生成アルゴリズム step3

第6回です。
1週間ほど体調が悪かったので久しぶりの更新です。

こんかいはアルゴリズムのstep3について書いていきます。

step3

このステップでは迷路を作っていきます。
これまで、step1で不定形な領域をつくり、step2で、生成した領域ができるだけ長くなるような接続関係をつくりました。

迷路を作るまえの最後の前準備として、領域の境界に壁を作っていきます。
さらに、step2で連結が定義された領域同士は、壁に穴を開けて移動が可能にしていきます。


こんな感じになります。いまのところstep2ではジグザグな経路になりやすいので赤線のような経路になります。

次にようやく迷路生成にはいります。

迷路生成アルゴリズム

最後のシメとして、各領域に迷路を作っていきます。
適当に作っても、これまでの前準備によって、ある程度長い迷路が作られます。

注意点として、迷路の領域が不定形なので既存のアルゴリズムは工夫しないと使えません。
今回は迷路の幅に依存しないバックトラック法を用いました。
参考リンク
Buckblog: Maze Generation: Recursive Backtracking

↑のサイトのプログラムをそのまま使ったところ、何故か迷路ができなかったので、考え方だけ借りて自作しました。また、再帰アルゴリズムを非再帰に直しています。

迷路の生成結果

いままでのステップのまとめ動画

経路探索にはAstarアルゴリズムを使っています。
参考リンク
よくわかるA*(A-star)アルゴリズム (Unity2Dのサンプルコードつき) - Qiita

おわり

以上で自作迷路生成アルゴリズムの記事は終了です。
まだ処理速度とか安定性に難があって、改良すべきところがいくつかありますが、一応このアルゴリズムを今回作るゲームの中核にすえていきたいと思います。

次回からはゲームデザインとか、グラフィックの進捗なんかを記事にしていきます。

アルゴリズム部分だけは別プロジェクトで作っているので、もうちょっとコードを改良したらプロジェクトごと公開する予定です。
それと解説もかなり適当な感じになってしまっているので、後でもっと分かりやすく解説できるようにします。