Ruby-Processing 迷路生成

クラスタリングによる迷路作成アルゴリズム を Ruby-Processing で実装してみました。

アルゴリズムがとてもシンプルでわかりやすいです。
上記リンク先の迷路作成アルゴリズムにある「ループを作らない保証」「死に領域ができない保証」が直感的に理解できます。

gen-ruby.rb

load_library :vecmath

# クラスタリングによる迷路作成アルゴリズム
# http://apollon.issp.u-tokyo.ac.jp/~watanabe/tips/maze.html

# 迷路生成
def gen_maze(rows, cols)
  maze = [] # クラスタ番号を格納
  for i in 0..rows-1
    maze << (0..cols-1).map {|j| cols*i + j }
  end

  # 隣り合うペア
  pairs = []
  for i in 0..rows-1
    for j in 0..cols-1
      pairs << [[i, j], [i, j+1]] if j < cols-1
      pairs << [[i, j], [i+1, j]] if i < rows-1
    end
  end

  # 隣合うペアをランダムに選択する。
  # 選択されたペアのクラスタ番号が異なるなら、そのペアの間の壁を壊す。
  break_walls = []
  pairs.shuffle.each {|a, b|
    # クラスタ番号が異なるなら、壁を壊す
    x = maze[a[0]][a[1]]
    y = maze[b[0]][b[1]]
    if x != y
      # puts "BREAK WALL #{a} - #{b}"
      break_walls << [a, b]
      fill(x, y, maze)
    end
  }

  print_maze(break_walls, maze)
  # draw_maze(break_walls, maze)
  @break_walls = break_walls
  @maze = maze
end

# クラスタ番号 fm を to に書き換える
def fill(fm, to, maze)
  rows = maze.size
  cols = maze[0].size
  for i in 0..rows-1
    for j in 0..cols-1
      if maze[i][j] == fm
        maze[i][j] = to
      end
    end
  end
end

# コンソールに迷路を出力する
def print_maze(break_walls, maze)
  rows = maze.size
  cols = maze[0].size

  printf " %s \n", (['_'] * cols).join(' ') # 上部の壁
  for i in 0..rows-1
    printf '|' # 左端の壁
    for j in 0..cols-1
      # (i, j) - (i+1, j) に壁があるか
      if break_walls.any? {|a, b| a == [i, j] && b == [i+1, j] }
        printf ' '
      else
        printf '_'
      end

      # (i, j) - (i, j+1) に壁があるか
      if break_walls.any? {|a, b| a == [i, j] && b == [i, j+1] }
        printf ' '
      else
        printf '|'
      end
    end
    puts
  end
end

# Processing キャンパスに迷路を描画する
def draw_maze(break_walls, maze)
  rows = maze.size
  cols = maze[0].size
  size = 15 # セル一つ分のサイズ

  translate (width - size * cols) / 2, (height - size * rows) / 2

  line(0, 0, size * cols, 0) # 上端の壁
  line(0, 0, 0, size * rows) # 左端の壁
  for i in 0..rows-1
    for j in 0..cols-1
      # (i, j) - (i+1, j) に壁があるか
      if !break_walls.any? {|a, b| a == [i, j] && b == [i+1, j] }
        line(j * size, (i+1) * size, (j+1) * size, (i+1) * size)
      end

      # (i, j) - (i, j+1) に壁があるか
      if !break_walls.any? {|a, b| a == [i, j] && b == [i, j+1] }
        line((j+1) * size, i * size, (j+1) * size, (i+1) * size)
      end
    end
  end
end

def setup
  size 400, 400

  gen_maze(20, 20)
end

def draw
  background 255

  if @break_walls && @maze
    draw_maze(@break_walls, @maze)
  end
end

def key_pressed
  if key == ' ' # スペースキーで迷路を作り直し
    puts 'gen maze'
    gen_maze(20, 20)
  end
end

コマンドラインから次のように実行します。

$ rp5 run gen-maze.rb

参考

• クラスタリングによる迷路作成アルゴリズム