A "weave" maze implementation, using the Growing Tree maze algorithm.

weave.rb

# --------------------------------------------------------------------
# An implementation of a "weave" maze (with over/under passages),
# using the Growing Tree maze generation algorithm.
# --------------------------------------------------------------------

# --------------------------------------------------------------------
# Helper data and methods
# --------------------------------------------------------------------

N, S, E, W, U = 0x01, 0x02, 0x04, 0x08, 0x10
OPP           = { N => S, S => N, E => W, W => E }
DX            = { N => 0, S => 0, E => 1, W => -1 }
DY            = { N => -1, S => 1, E => 0, W => 0 }
CROSS         = { N => E|W, S => E|W, E => N|S, W => N|S }

def can_weave?(grid, dir, x, y)
  cell = grid[y][x]
  return false unless cell == CROSS[dir]

  nx, ny = x + DX[dir], y + DY[dir]
  return ny.between?(0, grid.length-1) && nx.between?(0, grid[ny].length-1) && grid[ny][nx] == 0
end

# --------------------------------------------------------------------
# Allow the maze to be customized via the command-line
# --------------------------------------------------------------------

width = (ARGV.shift || 10).to_i
height = (ARGV.shift || width).to_i

# --------------------------------------------------------------------
# Data structures
# --------------------------------------------------------------------

grid = Array.new(height) { Array.new(width, 0) }
list = [[rand(width), rand(height)]]
carved = nil

# --------------------------------------------------------------------
# Growing tree algorithm
# --------------------------------------------------------------------

while list.any?
  ## recursive-backtracker
  index = list.length-1

  ## prim-like
  # index = rand(list.length)

  x, y = list[index]

  directions = [N, S, E, W].shuffle
  directions.unshift(carved) if carved && rand(2) > 0

  carved = nil

  directions.each do |dir|
    nx, ny = x + DX[dir], y + DY[dir]
    if nx.between?(0, width-1) && ny.between?(0, height-1)
      if grid[ny][nx] == 0
        grid[y][x] |= dir
        grid[ny][nx] |= OPP[dir]
        list << [nx, ny]

        carved = dir
      elsif can_weave?(grid, dir, nx, ny)
        grid[y][x] |= dir

        if rand(2) == 0
          grid[ny][nx] |= U
        elsif (grid[ny][nx] & N) != 0
          grid[ny][nx] = E|W|U
        else
          grid[ny][nx] = N|S|U
        end

        nx, ny = nx + DX[dir], ny + DY[dir]
        grid[ny][nx] |= OPP[dir]
        list << [nx, ny]

        carved = dir
      end

      break if carved
    end
  end

  list.delete_at(index) unless carved
end


# --------------------------------------------------------------------
# Display the maze using Unicode characters (for a more unambiguous
# representation)
# --------------------------------------------------------------------

EW, NS, SE, SW, NE, NW = [0x80, 0x82, 0x8C, 0x90, 0x94, 0x98].map { |v| "\xE2\x94#{v.chr}" }
NSE, NSW, EWS, EWN     = [0x9C, 0xA4, 0xAC, 0xB4].map { |v| "\xE2\x94#{v.chr}" }

TILES = {
  N       => ["#{NS} #{NS}", "#{NE}#{EW}#{NW}"],
  S       => ["#{SE}#{EW}#{SW}", "#{NS} #{NS}"],
  E       => ["#{SE}#{EW}#{EW}", "#{NE}#{EW}#{EW}"],
  W       => ["#{EW}#{EW}#{SW}", "#{EW}#{EW}#{NW}"],
  N|S     => ["#{NS} #{NS}", "#{NS} #{NS}"],
  N|W     => ["#{NW} #{NS}", "#{EW}#{EW}#{NW}"],
  N|E     => ["#{NS} #{NE}", "#{NE}#{EW}#{EW}"],
  S|W     => ["#{EW}#{EW}#{SW}", "#{SW} #{NS}"],
  S|E     => ["#{SE}#{EW}#{EW}", "#{NS} #{SE}"],
  E|W     => ["#{EW}#{EW}#{EW}", "#{EW}#{EW}#{EW}"],
  N|S|E   => ["#{NS} #{NE}", "#{NS} #{SE}"],
  N|S|W   => ["#{NW} #{NS}", "#{SW} #{NS}"],
  E|W|N   => ["#{NW} #{NE}", "#{EW}#{EW}#{EW}"],
  E|W|S   => ["#{EW}#{EW}#{EW}", "#{SW} #{SE}"],
  N|S|E|W => ["#{NW} #{NE}", "#{SW} #{SE}"],
  N|S|U   => ["#{NSW} #{NSE}", "#{NSW} #{NSE}"],
  E|W|U   => ["#{EWN}#{EW}#{EWN}", "#{EWS}#{EW}#{EWS}"]
}

height.times do |y|
  2.times do |row|
    width.times { |x| print TILES[grid[y][x]][row] }
    puts
  end
end