DouKaku? 5321 minke: > 壁伸ばし法の変種やってるこ...(必ず解ける迷路)

Comment detail

This comment is reply for 5307 squld: 壁伸ばし法の変種ですね。 >...(必ず解ける迷路). Go to thread root.

> 壁伸ばし法の変種
やってることはグラフの最小全域木を求める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