From: "Glenn M. Lewis" <noSpam@...>
Date: 2005-05-18T14:15:14+09:00
Subject: Re: [SUMMARY] Amazing Mazes (#31)

In honor of Clifford's very clear description of his maze-generation algorithm,
here is my attempt at a solution, and an example output:
#!/usr/bin/env ruby

class Maze
   TOP  = 1
   LEFT = 2
   def initialize(w,h)
     @w = w
     @h = h
     @maze = Array.new(w*h)
     @wall = Array.new(w*h, TOP|LEFT)
     @w.times do |i|
       @h.times do |j|
	putMaze(i,j,j*@w+i)
       end
     end

     # First, break exactly one top wall
     clearWall(rand(@w),0,TOP)
     # and define the exit column at the bottom...
     @exit = rand(@w)
     # Now, randomly break walls...
     (@w*@h-1).times do |i|
       breakWall
     end
   end

   def getMaze(x,y)
     @maze[y*@w+x]
   end

   def putMaze(x,y,val)
     @maze[y*@w+x] = val
   end

   def getWall(x,y,which)
     (@wall[y*@w+x] & which == 0 ? false : true)
   end

   def clearWall(x,y,which)
     @wall[y*@w+x] = @wall[y*@w+x] & (~which)
   end

   def breakWall
     while 1
       x = rand(@w)
       y = rand(@h)
       wall = 1 + rand(2)
       # Don't break LEFT wall for x==0
       next if (x==0 && wall==LEFT)
       # Don't break TOP wall for y==0
       next if (y==0 && wall==TOP)
       x2 = wall==LEFT ? x-1 : x
       y2 = wall==TOP  ? y-1 : y
       next if getMaze(x,y)==getMaze(x2,y2)
       # Found a valid wall to break!!!
       clearWall(x,y,wall)
       # Now, change all numbers in the maze from the higher number to the lower number
       from = getMaze(x,y)
       to = getMaze(x2,y2)
       changePath(from,to)
       return
     end
   end

   def changePath(n1,n2)
     higher = (n1 > n2 ? n1 : n2)
     lower  = (n1 < n2 ? n1 : n2)
     @w.times do |w|
       @h.times do |h|
	putMaze(w,h,lower) if getMaze(w,h)==higher
       end
     end
   end

   def to_s
     @w.times do |w|
       print getWall(w,0,TOP) ? "____" : "_   "
     end
     print "\n"
     @h.times do |h|
       @w.times do |w|
	print getWall(w,h,LEFT) ? "|" : " "
	print "   "
       end
       puts "|"
       if h+1 == @h
	# last row...
	@w.times do |w|
	  print getWall(w,h,LEFT) ? "|" : "."
	  print @exit == w ? "   " : "___"
	end
       else
	@w.times do |w|
	  print getWall(w,h,LEFT) ? "|" : "."
	  print getWall(w,h+1,TOP) ? "___" : "   "
	end
       end
       puts "|"
     end
   end
end

if __FILE__ == $0
   maze = Maze.new(20,20)
   puts maze
end

_____________________________________________________________________________
|           |   |               |   |       |           |                       |
|___.   .___|   |___.   .___.___|   |   .   |   .   .   |   .___.___.   .___.___|
|       |           |           |   |   |       |   |               |           |
|   .___|   .___.   |___.   .___|   |   |   .___|   |___.   .___.   |___.___.   |
|       |   |   |                   |   |       |   |       |               |   |
|   .___|   |   |   .   .___.   .   |___|___.   |___|___.___|   .___.___.   |   |
|       |   |       |       |   |               |       |   |   |   |   |   |   |
|   .   |   |   .   |___.___|___|___.   .___.   |___.   |   |   |   |   |   |___|
|   |   |   |   |           |               |   |       |   |           |       |
|   |___|   |___|___.   .   |___.___.   .___|___|___.   |   |   .   .___|___.   |
|           |           |       |           |           |       |           |   |
|___.   .___|___.___.   |   .___|   .___.   |___.___.   |___.   |___.___.___|___|
|   |       |           |       |   |   |   |           |       |   |           |
|   |___.___|___.___.   |___.___|___|   |   |___.___.   |___.   |   |   .___.___|
|       |               |           |       |       |                           |
|___.   |___.   .___.   |___.   .___|   .___|   .___|___.   .___.   .___.   .___|
|       |           |               |       |           |       |   |       |   |
|   .   |___.   .   |___.___.   .   |___.   |___.   .   |   .   |___|   .___|   |
|   |       |   |   |           |   |       |       |   |   |   |   |       |   |
|___|___.   |___|   |___.   .   |___|___.___|___.   |   |   |___|   |   .___|   |
|           |       |       |       |   |       |   |   |   |       |       |   |
|   .___.___|   .___|___.   |___.   |   |   .___|   |___|___|___.   |   .___|   |
|       |       |   |           |   |   |               |                   |   |
|   .   |___.   |   |   .   .___|___|   |___.   .___.   |___.___.   .   .   |   |
|   |           |       |           |           |       |           |   |   |   |
|   |___.   .___|___.   |___.___.   |   .   .___|___.___|___.___.___|___|___|   |
|   |               |           |       |       |       |               |       |
|___|___.___.   .___|   .___.   |   .___|___.___|___.   |___.   .___.___|___.   |
|   |               |   |       |   |   |                   |   |       |       |
|   |___.   .___.___|___|   .   |___|   |   .___.   .___.___|   |   .___|   .___|
|   |       |       |   |   |   |               |       |           |           |
|   |___.   |___.   |   |   |   |___.___.___.___|   .___|   .___.   |   .___.   |
|   |   |           |       |           |   |               |   |   |       |   |
|   |   |   .___.   |   .___|___.   .___|   |___.___.___.   |   |___|___.   |___|
|               |   |       |               |       |                       |   |
|___.   .   .___|___|___.___|___.___.___.   |   .___|   .___.___.   .___.___|   |
|       |   |   |   |   |           |   |                       |           |   |
|   .   |___|   |   |   |   .___.   |   |   .___.   .___.   .___|___.___.   |   |
|   |   |                   |               |       |               |           |
|___|___|___.___.   .___.___|___.___.___.___|___.___|___.___.___.___|___.___.___|