A recursive backtracking maze generator made with Ruby-Processing. gem install ruby-processing rp5 run maze.rb

maze.rb

require 'rubygems'

class Array
  def random
    self[rand length]
  end
end

class Hash
  def random
    values.random
  end
end

class Graph
  attr_accessor :nodes
  
  def initialize(args = {})
    @nodes = {}
    args.each {|k, v| send "#{k}=", v}
  end
  
  class Node
    attr_accessor :x, :y, :connections, :render_calls, :renderer, :rendered, :marked
    def initialize(args = {})
      @connections = []
      @render_calls = []
      args.each {|k, v| send "#{k}=", v}
    end
    
    def add_connection(n)
      @connections << n unless @connections.include?(n)
      n.connections << self unless n.connections.include?(self)
    end
    
    def self.processing_methods(*mthds)
      mthds.each do |a|
        define_method a do |*args|
          @render_calls << [a, args]
        end
      end
    end
    
    def top?
      @y == 0
    end
    
    def bottom?
      @y == GAME[:map_size] - 1
    end
    
    def left?
      @x == 0
    end
    
    def right?
      @x == GAME[:map_size] - 1
    end
    
    def possible_moves
      t = []
      t << node_above if !top? && [email protected]?(node_above)
      t << node_below if !bottom? && [email protected]?(node_below)
      t << node_left if !left? && [email protected]?(node_left)
      t << node_right if !right? && [email protected]?(node_right)
      t
    end
    
    def node_right
      GAME[:graph].nodes["#{@x + 1}_#{@y}"]
    end
    
    def node_left
      GAME[:graph].nodes["#{@x - 1}_#{@y}"]
    end
    
    def node_above
      GAME[:graph].nodes["#{@x}_#{@y - 1}"]
    end
    
    def node_below
      GAME[:graph].nodes["#{@x}_#{@y + 1}"]
    end
    
    processing_methods :stroke, :no_stroke, :stroke_width, :fill, :ellipse, :line, :rect
    
    def draw
      @render_calls = []
      no_stroke
      rect @x * GAME[:square_size],
           @y * GAME[:square_size],
           GAME[:square_size],
           GAME[:square_size]
      
      if @marked
        fill 50, 200, 200
        ellipse @x * GAME[:square_size] + GAME[:square_size] / 2,
                @y * GAME[:square_size] + GAME[:square_size] / 2,
                GAME[:square_size] / 2,
                GAME[:square_size] / 2
        fill 255
      end
      
      stroke 0
      
      # top
      line @x * GAME[:square_size],
           @y * GAME[:square_size],
           @x * GAME[:square_size] + GAME[:square_size],
           @y * GAME[:square_size]
      
      # left
      line @x * GAME[:square_size],
           @y * GAME[:square_size],
           @x * GAME[:square_size],
           @y * GAME[:square_size] + GAME[:square_size]
      
      # right
      line @x * GAME[:square_size] + GAME[:square_size],
           @y * GAME[:square_size],
           @x * GAME[:square_size] + GAME[:square_size],
           @y * GAME[:square_size] + GAME[:square_size]
      
      # bottom
      line @x * GAME[:square_size],
           @y * GAME[:square_size] + GAME[:square_size],
           @x * GAME[:square_size] + GAME[:square_size],
           @y * GAME[:square_size] + GAME[:square_size]
      
      stroke 255
      @connections.each do |c|
        if c.y == @y && c.x < @x
          # left
          line @x * GAME[:square_size],
               @y * GAME[:square_size] + 1,
               @x * GAME[:square_size],
               @y * GAME[:square_size] + GAME[:square_size] - 1
        elsif c.y == @y
          # right
          line @x * GAME[:square_size] + GAME[:square_size],
               @y * GAME[:square_size] + 1,
               @x * GAME[:square_size] + GAME[:square_size],
               @y * GAME[:square_size] + GAME[:square_size] - 1
        elsif c.x == @x && c.y < @y
          # top
          line @x * GAME[:square_size] + 1,
               @y * GAME[:square_size],
               @x * GAME[:square_size] + GAME[:square_size] - 1,
               @y * GAME[:square_size]
        else
          # bottom
          line @x * GAME[:square_size] + 1,
               @y * GAME[:square_size] + GAME[:square_size],
               @x * GAME[:square_size] + GAME[:square_size] - 1,
               @y * GAME[:square_size] + GAME[:square_size]
        end
      end
    end
    
    def add(n)
      add_connection n
      draw
      n.alert
      render
      n.render
    end
    
    def alert
      draw
      fill 200, 200, 50
      ellipse @x * GAME[:square_size] + GAME[:square_size] / 2,
              @y * GAME[:square_size] + GAME[:square_size] / 2,
              GAME[:square_size] / 2,
              GAME[:square_size] / 2
      fill 255
    end
    
    def unalert
      draw
    end
    
    def render
      @rendered = true
      @render_calls.each {|c| @renderer.send c.first, *c.last}
    end
  end
end

GAME = {}

class MazeGenerator < Processing::App
  
  def setup
    @start_time = Time.now
    sz = 40
    GAME[:width] = sz * 20
    GAME[:height] = sz * 20
    size GAME[:width], GAME[:height]
    smooth
    frame_rate 20
    GAME[:graph] = Graph.new
    GAME[:map_size] = sz
    GAME[:square_size] = GAME[:width].to_f / GAME[:map_size]
    GAME[:map_size].times do |x|
      GAME[:map_size].times do |y|
        GAME[:graph].nodes["#{y}_#{x}"] = Graph::Node.new(:x => y, :y => x, :renderer => self, :rendered => false)
      end
    end
    
    @history = []
    @n = GAME[:graph].nodes.values[rand(GAME[:graph].nodes.values.length)]
    background 127
    fill 255
    @dont_run = false
    @last = nil
  end
  
  def backtrack
    @history.pop
    @last = @n
    @n.marked = false unless @history.include?(@n)
    @n.alert
    @n.render
    @n = @history[-1]
  end
  
  def draw
    unless @dont_run
      1.times do
        if @last
          @last.draw
          @last.render
          @last = nil
        end
        if @n
          pm = @n.possible_moves
          c = pm.select {|v| !v.rendered}.random
          if c && !c.rendered
            c.marked = true
            @n.add c
            @n = c
            @history << @n
          else
            backtrack
          end
        else
          puts Time.now - @start_time
          @dont_run = true
          break
        end
      end
    end
    
  end
end

MazeGenerator.new :title => "Maze Generator"