kruskals.rb

# --------------------------------------------------------------------
# An implementation of Kruskal's algorithm for generating mazes.
# Fairly expensive, memory-wise, as it requires memory proportional
# to the size of the entire maze, and it's not the fastest of the
# algorithms (what with all the set and edge management is has to
# do). Also, the mazes it generates tend to have a lot of very short
# dead-ends, giving the maze a kind of "spiky" look.
# --------------------------------------------------------------------

# --------------------------------------------------------------------
# 1. Allow the maze to be customized via command-line parameters
# --------------------------------------------------------------------

width  = (ARGV[0] || 10).to_i
height = (ARGV[1] || width).to_i
seed   = (ARGV[2] || rand(0xFFFF_FFFF)).to_i

srand(seed)

# --------------------------------------------------------------------
# 2. Set up constants to aid with describing the passage directions
# --------------------------------------------------------------------

N, S, E, W = 1, 2, 4, 8
DX         = { E => 1, W => -1, N =>  0, S => 0 }
DY         = { E => 0, W =>  0, N => -1, S => 1 }
OPPOSITE   = { E => W, W =>  E, N =>  S, S => N }

# --------------------------------------------------------------------
# 3. Data structures to assist the algorithm
# --------------------------------------------------------------------

class Tree
  attr_accessor :parent

  def initialize
    @parent = nil
  end

  def root
    @parent ? @parent.root : self
  end

  def connected?(tree)
    root == tree.root
  end

  def connect(tree)
    tree.root.parent = self
  end
end

class Maze
  attr_reader :grid, :width, :height

  def initialize(w,h)
    @width, @height = w, h

    @grid  = Array.new(@height) { Array.new(@width, 0) }
    @cells = Array.new(@height) { Array.new(@width) { Tree.new } }

    # build the list of edges
    @edges = []
    @height.times do |y|
      @width.times do |x|
        @edges << [x, y, N] if y > 0
        @edges << [x, y, W] if x > 0
      end
    end

    @edges = @edges.sort_by{rand}
  end

  def to_s
    s = " " + "_" * (width * 2 - 1) + "\n"
    @height.times do |y|
      s << "|"
      @width.times do |x|
        s << ((@grid[y][x] & S != 0) ? " " : "_")
        if @grid[y][x] & E != 0
          s << (((@grid[y][x] | @grid[y][x+1]) & S != 0) ? " " : "_")
        else
          s << "|"
        end
      end
      s << "\n"
    end
    s
  end
end

maze = Maze.new(width, height)

# --------------------------------------------------------------------
# 4. Kruskal's algorithm
# --------------------------------------------------------------------

class Maze
  def step
    return false if @edges.empty?

    until @edges.empty?
      x, y, direction = @edges.pop
      nx, ny = x + DX[direction], y + DY[direction]

      set1, set2 = @cells[y][x], @cells[ny][nx]

      unless set1.connected?(set2)
        set1.connect(set2)
        @grid[y][x] |= direction
        @grid[ny][nx] |= OPPOSITE[direction]
        break
      end
    end

    return @edges.any?
  end
end

while maze.step
  ### uncomment these lines if you want to animate the algorithm
  # system "clear"
  # puts maze
  # sleep 0.05
end
system "clear"
puts maze

# --------------------------------------------------------------------
# 5. Show the parameters used to build this maze, for repeatability
# --------------------------------------------------------------------

puts "#{$0} #{width} #{height} #{seed}"