maze.rb

# Constructing a maze with a clustering algorithm
# (C) Copyright H. Watanabe 2015
# Distributed under the Boost Software License, Version 1.0.
# (See copy at http://www.boost.org/LICENSE_1_0.txt)
class Maze
  def initialize(s)
    @lx = s
    @ly = @lx*297/210
    @bond_h = Array.new((@lx+1)*@ly) { false}
    @bond_v = Array.new(@lx*(@ly+1)) { false}
    @point = Array.new(@lx*@ly*2) {|i| i}
    @GridSize = (600.0-30)/(@lx+4)
    @LeftMargin = @GridSize*3
    @TopMargin = @GridSize*2
    makeMaze
  end
  
  def getClasterIndex(x, y)
    index = @lx*y+x
    while(index != @point[index])
      index = @point[index]
    end
    return index
  end
  
  def connect(ix1, iy1, ix2, iy2)
    i1 = getClasterIndex(ix1,iy1)
    i2 = getClasterIndex(ix2,iy2)
    if i1<i2
      @point[i2] = i1
    else
      @point[i1] = i2
    end
  end
  
  def makeMazeSub
    rate = 0.8
    for ix in 0..@lx-2
      for iy in 0..@ly-1
        next if rand <rate
        next if getClasterIndex(ix,iy) == getClasterIndex(ix+1,iy)
        @bond_h[(@lx+1)*iy+ix+1] = true
        connect(ix,iy,ix+1,iy)
      end
    end
    for ix in 0..@lx-1
      for iy in 0..@ly-2
        next if rand <rate
        next if getClasterIndex(ix,iy) == getClasterIndex(ix,iy+1)
        @bond_v[(iy+1)*@lx+ix] = true
        connect(ix,iy,ix,iy+1)
      end
    end
  end
  
  def makeMazeFinal
    for ix in 1..@lx-2
      for iy in 1..@ly-1
        next if getClasterIndex(ix,iy) == getClasterIndex(ix+1,iy)
        @bond_h[iy*(@lx+1)+ix+1] = true
        connect(ix,iy,ix+1,iy)
      end
    end
  end
  
  def makeMaze
    for i in 0..10
      makeMazeSub
    end
    makeMazeFinal
    @bond_h[0] = true
    @bond_h[(@lx+1)*@ly-1] = true
  end
  
  def exportEPS (filename)
    f = open(filename,"w")
    f.print "%!PS-Adobe-2.0\n"
    f.print "%%BoundingBox: 0 0 600 850\n"
    f.print "%%EndComments\n"
    f.print "/mydict 120 dict def\n"
    f.print "mydict begin\n"
    f.print "gsave\n"

    g = @GridSize
    h = @GridSize*0.5
    f.print "/arrow {gsave translate "
    f.print "0 0 moveto "
    f.print g.to_s + " 0 lineto stroke\n"
    f.print g.to_s + " 0  moveto "
    f.print h.to_s + " -" + h.to_s + " lineto "
    f.print h.to_s + " " + h.to_s + " lineto "
    f.print "closepath fill stroke grestore} def\n"

    f.print @LeftMargin.to_s + " " + @TopMargin.to_s + " translate \n"
    f.print "-" + g.to_s + " " + (g*0.5).to_s + " arrow \n"
    f.print "" + (g*@lx).to_s + " " + (g*(@ly-0.5)).to_s + " arrow \n"

    for ix in 0..@lx
      for iy in 0..@ly-1
        x = ix * @GridSize
        y = iy * @GridSize
        next if @bond_h[iy*(@lx+1)+ix]
        f.print x.to_s + " " + y.to_s + " moveto "
        f.print x.to_s + " " + (y+@GridSize).to_s + " lineto stroke\n"
      end
    end
    for ix in 0..@lx-1
      for iy in 0..@ly
        x = ix * @GridSize
        y = iy * @GridSize
        next if @bond_v[iy*@lx+ix]
        f.print x.to_s + " " + y.to_s + " moveto "
        f.print ""+(x+@GridSize).to_s + " " + y.to_s + " lineto stroke\n"
      end
    end
    f.print "grestore\n"
    f.print "end\n"
    
  end
end

s = 50
if(ARGV.size > 0)
  s = ARGV[0].to_i
end 

m = Maze.new(s).exportEPS("maze.eps")
puts "A maze is constructed. The filename is maze.eps."