穴掘り法で迷路を作ってみた

maze.rb

#!/usr/bin/env ruby
# -*- encoding: utf-8 -*-

require 'rubygems'
require 'win32console'
require 'term/ansicolor'

include Win32::Console::ANSI
include Term::ANSIColor

class Maze
  OUTSIDE = -1
  PATHWAY = 0
  WALL = 1

  def initialize(width, height)
    @console = Win32::Console.new(STD_OUTPUT_HANDLE)
    @width = width * 2 + 1
    @height = height * 2 + 1
    @data = [WALL] * @width * @height
    draw_bg
    dig
    finish
  end

  def finish
    @console.Cursor(0, 1)
    print ' '
    @console.Cursor(@width + 1, @height)
    print ' '
    @console.Cursor(0, @height + 1)
  end

  def dig
    x = rand(@width / 2) * 2
    y = rand(@height / 2) * 2
    loop do
      dig_path(x, y)
      r = select_next(x, y)
      break unless r
      set_pathway(*r[0])
      x, y = r[1]
    end
  end

  def select_next(x, y)
    r = walk(x, y)
    until r.empty?
      i = rand(r.size)
      x, y = r[i]
      r.delete_at(i)
      s = candidates(x, y)
      return s[rand(s.size)] unless s.empty?
    end
  end

  def walk(tx, ty, x = nil, y = nil, fx = nil, fy = nil, r = [])
    return if fx == tx && fy == ty
    return if PATHWAY != self[tx, ty]
    r << [tx, ty] if tx % 2 == 0 && ty % 2 == 0
    walk(tx + 1, ty, tx, ty, x, y, r)
    walk(tx - 1, ty, tx, ty, x, y, r)
    walk(tx, ty + 1, tx, ty, x, y, r)
    walk(tx, ty - 1, tx, ty, x, y, r)
    r
  end

  def dig_path(x, y)
    set_pathway(x, y)
    loop do
      s = candidates(x, y)
      break if s.empty?
      s = s[rand(s.size)]
      set_pathway(*s[0])
      set_pathway(*s[1])
      x, y = s[1]
    end
  end

  def candidates(x, y)
    r = []
    try_dig(x, y, 1, 0, r)
    try_dig(x, y, -1, 0, r)
    try_dig(x, y, 0, 1, r)
    try_dig(x, y, 0, -1, r)
    r
  end

  def try_dig(x, y, dx, dy, r)
    x += dx
    y += dy
    s = x + dx
    t = y + dy
    if WALL == self[s, t]
      r << [[x, y], [s, t]]
    end
  end

  def [](x, y)
    return OUTSIDE if x < 0 || @width <= x
    return OUTSIDE if y < 0 || @height <= y
    @data[x + y * @width]
  end

  def set_pathway(x, y)
    @data[x + y * @width] = PATHWAY
    @console.Cursor(x + 1, y + 1)
    print ' '
  end

  def draw_bg
    @console.Cls
    (@height + 2).times do
      print on_white
      print ' ' * (@width + 2)
      print reset
      puts
    end
  end
end

#Maze.new(38, 30)
Maze.new(10, 10)

参考: 自動生成迷路