下記を見ながらrubyで実際にやってみたメモです。
http://qiita.com/2dgames_jp/items/037dc62afb268759d16d

気にしたこと

4方向ランダムな順で一通り舐める。
終了条件
- 再帰処理になるので終了条件が必要。
- 条件を満たす方向が見つからなくなるまでやる。

ランダムに4方向を選んで、それぞれに処理を行う

array.combinationは順序なし、重複なし、だから、今回の用途としては使えない。
array.permutationは順序あり、重複なし、だから今回の用途に使える。
参考
- http://manapedia.jp/text/1421?page=2

ソース

# !/usr/bin/env ruby
# coding: utf-8

# ２次元ベクトルクラス
class Vector2d
  attr_accessor :x, :y
  def initialize(x, y)
    @x = x
    @y = y
  end

  def +(other)
    return Vector2d.new(x + other.x, y + other.y)
  end
end

class Map

  def initialize(size_x, size_y)
    @size_x = size_x
    @size_y = size_y

    @map = Array.new(@size_y) do |i|
      Array.new(@size_x) do |j|
        :wall
      end
    end
  end

  # 壁かどうか
  def is_wall(x, y)
    if 0 <= x && x < @size_x &&
       0 <= y && y < @size_y

      return @map[y][x] == :wall
    else
      return false
    end
  end

  # ランダムダンジョンを生成する
  def shuffle!(current_pos_x, current_pos_y)
    # 3. 開始地点を決める
    current_pos = Vector2d.new(current_pos_x, current_pos_y)
    # 4. 穴掘り開始
    #  ⅰ. 開始基準地点を「通路」に設定する
    @map[current_pos.y][current_pos.x] = :passage

    #  ⅱ. 4方向をランダムな順番にチェックする
    check_orders = []
    [0, 1, 2, 3].permutation(4).each do |order|
      check_orders.push(order)
    end
    check_order_index = rand(check_orders.length).to_i
    check_order = check_orders[ check_order_index ]

    direction_offsets = [
      Vector2d.new(1, 0),
      Vector2d.new(0, 1),
      Vector2d.new(-1, 0),
      Vector2d.new(0, -1),
    ]
    check_order.each_with_index do |check_dir_index, index|

      check_dir = direction_offsets[ check_dir_index ]

      #  ⅲ. チェックする方向の2マス先が「壁」であれば以下の処理を行う
      check_pos_offset = Vector2d.new( check_dir.x * 2, check_dir.y * 2)
      check_pos = current_pos + check_pos_offset
      if( is_wall(check_pos.x, check_pos.y) )
        #    a. チェックした方向の1マス先を「通路」に設定する
        dig_pos = current_pos + check_dir
        @map[dig_pos.y][dig_pos.x] = :passage
        #    b. 2マス先を開始基準点として 『4. 穴掘り開始』を呼び出す
        p "=="
        p dig_pos
        p check_pos
        dump
        shuffle!(check_pos.x, check_pos.y)
      end
    end
  end

  def dump
    print "--\n"
    @map.each do |row|
      row.each do |element|
        if element == :passage
          print " "
        else
          print "o"
        end
      end
      print "\n"
    end
  end
  
  def draw(screen)
  end
end

map = Map.new(11, 11)
# map.dump
map.shuffle!(2, 2)
map.dump