読者です 読者をやめる 読者になる 読者になる

真面目に、強く、上品に

逆境に負けないブログ

迷路自動生成

先日リリースしたアプリで迷路自動生成を実装してみたので、 まとめてみます。

迷路自動生成の仕様としては、

  • 2次元平面の対角をスタートとゴールとする
  • スタートは必ず一つ
  • ゴールは必ずしも、一本の道で終わってなくても良い

以上の3点となります。

これらを踏まえた上で以下のようにステップ実行してみました。

ステップ実行してみると、1ステップごとに以下の点を考えるだけで、 全ての処理が終了するように思いました。

  1. 行き止まりではない場合、ランダムで分岐を選択
  2. 行き止まりだった場合、選択していない分岐まで戻る
  3. もし全ての点を走査したら処理を終了

データ構造としては、

  • X座標、Y座標、前の点、探索済みフラグを保持しておく
  • 再帰を使って前の点への参照を作っていく

以上で、迷路を単純な木構造として表現出来そうです。

このよう方針にてPythonで実装してみました。

実際の動作としては、既にiPhoneで実装したものをリリースしていますので、 それで確認してみてください。

minosound

このアルゴリズムの問題点としては、

  • ゴールの深さが迷路が生成されるたびに変わる。
  • 分岐が浅くなりやすい。

といったことがあるため、 今後何かしらのアルゴリズムの修正が入るかもしれません。