PolyHexane 六角形迷路生成のアルゴリズム

しばらく前にやねうらおさんというコンピュータ将棋ソフト「やねうら王」などを作られている方のブログで迷路生成アルゴリズムについて読んだ。

古くて新しい自動迷路生成アルゴリズム

そっからのリンクでクラスタリングによる迷路作成アルゴリズム

その後しばらくそのことも忘れていたが、ふとした時に六角形の迷路で同じアルゴリズムを使えるか考えてみた。

仮に4x4の迷路を作るとして、図のように番号を振ることとする

ルーチンcreateで横X 縦Yの迷路を作成する。

部屋の間の壁を考える(struct Wall)。部屋Aと部屋Bの間の壁で、向きは{縦・右が上・左が上}の3種類がある。すべての壁を列挙する。配列Poolに入れておく
→本当は一番ここが面倒なところ。縦棒の壁はすごくわかりやすいが、斜めの壁はYが奇数・偶数で変わってくるなどあり、多少の場合分けが必要。ソースをご参照ください。

初めはすべての部屋が別のクラスタに属するので、部屋一つずつに対応する配列を作って別々のクラスタ番号を割り振る。

最終的な迷路に残る壁を入れる配列としてwalls
各部屋から隣接して移動できる部屋の配列としてlink という配列の配列を用意する

配列Poolが空になるまでループ:
ランダムにPoolから壁を一つ取り出す この壁は部屋Aと部屋Bの間にあるとする
部屋A,Bのクラスタ番号を比較
同じクラスタ:この壁は残す 配列wallsに追加
違うクラスタ:この壁は取り払う 両側の部屋のクラスタ番号を同じにする
部屋A,Bが繋がったのでlink[A]にBを追加、link[B]にAを追加

これで迷路は完成しているが、スタート地点からの距離を調べておくと便利なのでここで計算しておく distanceという各部屋に対応した配列を作り-1で初期化
部屋pについて link[p]で隣接している部屋のうち、distanceが-1のものは自分の距離+1に設定した上で、その部屋について再帰的に適用する。
部屋0からスタート

というアルゴリズムをSwiftで書いたのが以下のソースです。PolyHexaneの内部では対戦モード向けに反転した迷路を作らなければいけないのでもうちょっと余計な処理が増えています。


class Maze{

  enum WallDirection{
    case None
    case StraightUp
    case RightUp
    case LeftUp
  }

  struct Wall {
    var A:Int
    var B:Int
    var Direction:WallDirection
    init(a:Int, b:Int, dir:WallDirection){
      A = a
      B = b
      Direction = dir
    }
  }

  private var Pool = [Wall]()
  private var clusterNumber = [Int]()

  var walls = [Wall]()
  var link = [[Int]]()
  var distance = [Int]()

  func create(X:Int, Y :Int){
    walls = []
    Pool = []
    clusterNumber = []
    for i in 0...X*Y-1{
      clusterNumber.append(i)
    }
    link = Array(repeating: [], count: X*Y)

    for y in 0...Y-1{
      for x in 0...X-2 {
        Pool.append(Wall(a: y*X+x, b: y*X+x+1, dir: .StraightUp))
      }
      if y > 0{
        if y % 2 == 1{
          for x in 0...X-1 {
            Pool.append(Wall(a: y*X-X + x, b: y*X + x, dir: .RightUp))
          }
          for x in 0...X-2 {
            Pool.append(Wall(a: y*X-X + x+1, b: y*X + x, dir: .LeftUp))
          }
        }else{
          for x in 0...X-1 {
            Pool.append(Wall(a: y*X-X + x, b: y*X + x, dir: .LeftUp))
          }
          for x in 1...X-1 {
            Pool.append(Wall(a: y*X-X + x-1, b: y*X + x, dir: .RightUp))
          }
        }
      }
    }

    while !Pool.isEmpty {
      var n = Int(drand48() * Double(Pool.count))
      let a = clusterNumber[Pool[n].A]
      let b = clusterNumber[Pool[n].B]
      if a == b {
        // this wall stands within a cluster so add it to remaining 'walls'
        walls.append(Pool[n])
      }else{
        // cluster B is merged to A
        link[Pool[n].A].append(Pool[n].B)
        link[Pool[n].B].append(Pool[n].A)
        for i in 0...X*Y-1{
          if clusterNumber[i] == b {
            clusterNumber[i] = a
          }
        }
      }
      Pool.remove(at: n)
    }

    distance = Array(repeating: -1, count: X*Y)
    func dig(_ p:Int){
      for i in link[p]{
        if distance[i] == -1{
          distance[i] = distance[p]+1
          dig(i)
        }
      }
    }
    distance[0] = 0
    dig(0)
  }
}
広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中