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, @height = width, 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 = a @cells = Array.new(@width) {Array.new(@height)} #@cells にすべてちがう値の数を与える (@width * @height).times {|i| @cells[i % @width][i / @width] = i} end def generate break_wall until finish [@yokokabe, @tatekabe] end def wall_position(num) #flag, a flag = (num < @yokokabe_num) #横壁なら true、縦壁なら false a = if flag @width else num -= @yokokabe_num @height end [flag, num % a, num / a - 1] 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, flag, x, y, a, b num = @left_wall[rand(@left_wall.size)] #残された壁から壊す壁をランダムに選択する flag, x, y = wall_position(num) #壊す壁の情報を得る @left_wall.delete(num) if flag #横壁 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 clear 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, Height = 30, 20 yokokabe, tatekabe = Maze.new(Width, Height).generate Left, Top = 20, 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 画像ファイルに落とすことも出来ます。
※追記
これで作った迷路を実際に歩いてみるプログラムを書きました。