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' も使っています(参照)。メソッド Array.make と nest_loop がそれです。
maze.rb

require 'oekaki'
require 'utils'

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.make([@width, @height])
    #@cell にすべてちがう値の数を与える
    i = 0
    [@height, @width].nest_loop do |y, x|
      @cells[x][y] = i
      i += 1
    end
  end
  
  def generate
    break_wall until finish
    [@yokokabe, @tatekabe]
  end
  
  def wall_position(num)
    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, @height].nest_loop do |x, y|
      @cells[x][y] = t if @cells[x][y] == s
    end
  end
  
  def break_wall
    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, w].nest_loop do |y, 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
      [w + 1, h].nest_loop do |x, 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
      
      #save_pic(get_pic(0, 0, wi, he), "maze.png")    #画像ファイルの作成
    end
  end
end


if __FILE__ == $0
  Width = 20; 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 画像ファイルに落とすことも出来ます。

Utils

上のコードに必要な 'utils' の部分は以下だけなので、これで代用してもらって構いません。
utils.rb

class Array
  #任意の階層だけ繰り返しをネストする
  def nest_loop(arg = [], &bk)
    check = lambda do |obj|
      return 0...obj if (c = obj.class) == Bignum or c == Integer or c == Fixnum
      obj
    end
    
    ar = dup
    for i in check.call(ar.shift)
      if ar.empty?
        yield(arg + [i])
      else
        ar.nest_loop(arg.push(i), &bk)
        arg.pop
      end
    end
    self
  end

  #多重配列を簡単に生成する
  def self.make(ar, ob=nil)
    raise "Argument class Error" unless ar.class == Array
    a = ar.dup
    ar1 = []
    a.shift.times {ar1 << (a.empty? ? (ob.dup rescue ob) : Array.make(a, ob))}
    ar1
  end
end

 

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