DouKaku? 5304 minke: 迷路がお題を満たす(全ての場所にいける&...(必ず解ける迷路)

Comment detail

迷路がお題を満たす(全ての場所にいける&ループ無し) ための必要十分条件は
「全ての基点(マップ上で(i, j)=(偶数, 偶数)の点) が外壁と一ヶ所でだけ繋がっている」
なんじゃないかなぁと思って、
お題を満たすような迷路を全て生成し得るような方法を考えてみました。

領域量はO(mn)要ります。1024*1024で2分ぐらい。


ちなみに棒倒し法なんかだと、例えば次のようなものを生成できません。

■■■■■■■■■
■　■　　　　　■
■　■　■■■　■
■　■　■　■　■
■　■　■　■　■
■　■　　　■　■
■　■■■■■　■
■　　　　　　　■
■■■■■■■■■

class Maze
  def initialize(m, n)
    @rows = m
    @cols = n
    @field = Array.new(2*@rows+1) do |i|
      (i % 2 == 0) ? ('# ' * @cols + '#') : ('#' + ' ' * (2*@cols-1) + '#')
    end
    @field[0] = @field[-1] = '#' * (2*@cols+1)
  end

  def gen
    # number of connections to the wall
    bases = Array.new(@rows+1) do |i|
      if i == 0 || i == @rows
        Array.new(@cols+1, 1)
      else
        Array.new(@cols+1) {|j| (j == 0 || j == @cols) ? 1 : 0 }
      end
    end
    uc = []  # candidates of next selection
    (1 .. @rows-1).each {|i| uc << [i, 1] << [i, @cols-1] }
    (2 .. @cols-2).each {|j| uc << [1, j] << [@rows-1, j] }

    until uc.empty?
      y, x = uc.slice!(rand(uc.size))
      next if bases[y][x] > 0
      dirs = [[+1, 0], [-1, 0], [0, +1], [0, -1]].sort_by { rand }
      dirs.each do |mv|
        y_, x_ = y + mv[0], x + mv[1]
        if bases[y_][x_] == 1
          @field[2*y+mv[0]][2*x+mv[1]] = ?#
          bases[y][x] += 1
          break
        end
      end
      dirs.each do |mv|
        y_ , x_ = y + mv[0], x + mv[1]
        uc << [y_, x_] if bases[y_][x_] == 0
      end
    end
    self
  end

  def p
    @field.each {|row| puts row }
  end
end


M, N = 10, 10
maze = Maze.new(M, N)
#maze.p
maze.gen.p

壁伸ばし法の変種ですね。

> ちなみに棒倒し法なんかだと、例えば次のようなものを生成できません。

棒倒し法では生成方向に逆行する経路が出来ないという意味でしょうか？

棒倒し方では, 格子状に壁を生成し, それを起点に周
囲に1つ以上の壁を生成していきます. 
そのため, 必ず格子状に壁が存在し, かつその周辺に
1つ以上壁が存在することになり, 一部の構造の迷路
が生成できないということなんだと思います.

棒倒し法の問題点は以下のようです。

1. 一行目に壁が少なくなってしまう。
2. 閉じた領域が出来てしまう。
3. 全ての道と連絡する抜け道ができてしまう。
4. 隙間だらけになってしまう。
5. 生成方向に逆行する経路ができない。

1～4の問題を克服した発散棒倒し法が紹介されていますが、
放射状に迷路を作るのでO(n)で実装するのは無理かもしれません。

参考
迷路自動生成アルゴリズム「発散棒倒し法」
http://aoyzsas.hp.infoseek.co.jp/maze/maze_hpillar.html

> 壁伸ばし法の変種
やってることはグラフの最小全域木を求めるPrimのアルゴリズムと同じですね。
壁が枝に対応します。

> 棒倒し法では生成方向に逆行する経路が出来ないという意味でしょうか？
生成方向に逆行するような棒の倒し方ができないので、
4方向全てに倒す必要のある迷路は、どの方向から始めても
無理なのではないかと考えました。

>グラフの最小全域木を求めるPrimのアルゴリズムと同じ

たしかに「ループがない」「たどり着けない場所がない」という条件はまさに全域木！

えーと、木に見たててるのは壁の方なのですが、
確かに通路の全域木を作る方が素直ですね(笑)

というわけで、通路の最小全域木を作るものを実装してみました。穴掘りです。

Pentium4/2.8GHzで1分半ほど。

class Maze
  WALL, VAC = '#', ' '
  DIRS = [[+1, 0], [-1, 0], [0, +1], [0, -1]]
  def initialize(m, n)
    @rows = m
    @cols = n
    @field = Array.new(2*@rows+1) { WALL*(2*@cols+1) }
  end

  def gen
    conn = Array.new(@rows) { Array.new(@cols, false) }
    cand = [[rand(@rows), rand(@cols), 0, 0]] # (0,0) is dummy
    until cand.empty?
      y, x, dy, dx = cand.slice!(rand(cand.size))
      next if conn[y][x]
      conn[y][x] = true
      @field[2*y+1-dy][2*x+1-dx] = VAC
      @field[2*y+1][2*x+1] = VAC
      DIRS.each do |mv|
        y_, x_ = y+mv[0], x+mv[1]
        if (0...@rows) === y_ &&
           (0...@cols) === x_ &&
           !conn[y_][x_]
          cand << [y_, x_, mv[0], mv[1]]
        end
      end
    end
    self
  end

  def p
    puts @field
  end
end

M, N = 10, 10
maze = Maze.new(M, N)
maze.gen.p

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq