Ruby で迷路作成

http://apollon.issp.u-tokyo.ac.jp/~watanabe/tips/maze.html
ここのリンク先のアルゴリズムを使って、迷路のジェネレーターを Ruby で書いてみました。リンク先でも Ruby での実装がありますが、自分でやってみました。


20×20の迷路です。

 

コードは以下です。迷路の作成と描画は別にしてあります。描画は自作の Gem 'oekaki' を使っています。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた(Ruby) - Camera Obscura
(※追記 以前は下のコードは自作のライブラリ 'utils' に依存していましたが、それを使わないように変更しました。(10/9))
maze.rb

require 'oekaki'

class Maze
  def initialize(width, height)
    @width = width
    @height = height
    
    @yokokabe = Array.new(@width  * (@height + 1), 1)
    @tatekabe = Array.new(@height * (@width  + 1), 1)
    
    @left_wall = (@width..((a = @yokokabe.size) - @width - 1)).to_a
    @left_wall += ((a + @height)..(a + @tatekabe.size - @height - 1)).to_a
    @yokokabe_num = @yokokabe.size
    
    @cells = Array.new(@width) {Array.new(@height)}
    #@cell にすべてちがう値の数を与える
    i = 0
    @height.times do |y|
      @width.times {|x| @cells[x][y] = i; i += 1}
    end
  end
  
  def generate
    break_wall until finish
    [@yokokabe, @tatekabe]
  end
  
  def wall_position(num)
    #po, a
    po = []
    po[0] = (num < @yokokabe_num)    #横壁なら true、縦壁なら false
    if po[0]
      a = @width
    else
      num -= @yokokabe_num
      a = @height
    end
    po[1] = num % a
    po[2] = num / a
    po
  end
  
  def replace(s, t)
    @width.times do |x|
      @height.times {|y| @cells[x][y] = t if @cells[x][y] == s}
    end
  end
  
  def break_wall
    #num, po, x, y, a, b
    num = @left_wall[rand(@left_wall.size)]    #残された壁から壊す壁をランダムに選択する
    po = wall_position(num)                    #壊す壁の情報を得る
    x = po[1]; y = po[2] - 1
    @left_wall.delete(num)
    if po[0]
      #横壁
      return if (a = @cells[x][y]) == (b = @cells[x][y + 1])
      @yokokabe[num] = 0                       #実際に壁を壊す
    else
      #縦壁
      return if (a = @cells[y][x]) == (b = @cells[y + 1][x])
      @tatekabe[num - @yokokabe_num] = 0       #実際に壁を壊す
    end
    a, b = b, a if a < b
    replace(a, b)                              #壁を壊したあとに通路をつなげる
  end
  
  def finish    #@cell の値がすべて等しくなれば終了
    a = @cells[0][0]
    @cells.flatten.each {|b| return false if b != a}
    true
  end
end


def show_maze(w, h, yokokabe, tatekabe)
  wi = Left * 2 + w * (CellWidth + 1)
  he = Top  * 2 + h * (CellWidth + 1)
  
  Oekaki.app width: wi, height: he, title: "maze" do
    draw do
      color(0, 0, 0)
      rectangle(true, 0, 0, wi, he)
      
      color(65535, 65535, 65535)
      (h + 1).times do |y|
        w.times do |x|
          next if yokokabe[x + y * w].zero?
          x1 = Left + x * (CellWidth + 1)
          y1 = Top  + y * (CellWidth + 1)
          line(x1, y1, x1 + CellWidth + 1, y1)
        end
      end
      (w + 1).times do |x|
        h.times do |y|
          next if tatekabe[y + x * h].zero?
          x1 = Left + x * (CellWidth + 1)
          y1 = Top  + y * (CellWidth + 1)
          line(x1, y1, x1, y1 + CellWidth + 1)
        end
      end
      
      #save_pic(get_pic(0, 0, wi, he), "maze.png")    #画像ファイルの作成
    end
  end
end


if __FILE__ == $0
  Width = 30; Height = 20
  
  yokokabe, tatekabe = Maze.new(Width, Height).generate
  
  Left = 20; Top = 20
  CellWidth = 20
  
  show_maze(Width, Height, yokokabe, tatekabe)
end

メソッド Maze#generate で迷路を生成します。返り値は yokokabe と tatekabe で、それぞれ横方向と縦方向の壁をあらわす配列です(1 なら壁が存在し、0 なら存在しない。初期値はすべて 1)。メソッド Maze#break_wall は、壁をランダムにひとつ選んで、壊してもよい壁なら壊します。メソッド show_maze で迷路を表示します。ここで自家製の Gem 'oekaki' を使っています。png 画像ファイルに落とすことも出来ます。

 
 
※追記
これで作った迷路を実際に歩いてみるプログラムを書きました。