先日リリースしたアプリで迷路自動生成を実装してみたので、 まとめてみます。
迷路自動生成の仕様としては、
- ２次元平面の対角をスタートとゴールとする
- スタートは必ず一つ
- ゴールは必ずしも、一本の道で終わってなくても良い
以上の3点となります。
これらを踏まえた上で以下のようにステップ実行してみました。
ステップ実行してみると、１ステップごとに以下の点を考えるだけで、 全ての処理が終了するように思いました。
- 行き止まりではない場合、ランダムで分岐を選択
- 行き止まりだった場合、選択していない分岐まで戻る
- もし全ての点を走査したら処理を終了
データ構造としては、
- X座標、Y座標、前の点、探索済みフラグを保持しておく
- 再帰を使って前の点への参照を作っていく
以上で、迷路を単純な木構造として表現出来そうです。
このよう方針にてPythonで実装してみました。
実際の動作としては、既にiPhoneで実装したものをリリースしていますので、 それで確認してみてください。
このアルゴリズムの問題点としては、
- ゴールの深さが迷路が生成されるたびに変わる。
- 分岐が浅くなりやすい。
といったことがあるため、 今後何かしらのアルゴリズムの修正が入るかもしれません。
