unknown
5/18/2005 5:12:00 AM
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
_____________________________________________________________________________
| | | | | | | |
|___. .___| |___. .___.___| | . | . . | .___.___. .___.___|
| | | | | | | | | |
| .___| .___. |___. .___| | | .___| |___. .___. |___.___. |
| | | | | | | | | | |
| .___| | | . .___. . |___|___. |___|___.___| .___.___. | |
| | | | | | | | | | | | | |
| . | | . |___.___|___|___. .___. |___. | | | | | |___|
| | | | | | | | | | | |
| |___| |___|___. . |___.___. .___|___|___. | | . .___|___. |
| | | | | | | | |
|___. .___|___.___. | .___| .___. |___.___. |___. |___.___.___|___|
| | | | | | | | | | | |
| |___.___|___.___. |___.___|___| | |___.___. |___. | | .___.___|
| | | | | | |
|___. |___. .___. |___. .___| .___| .___|___. .___. .___. .___|
| | | | | | | | | |
| . |___. . |___.___. . |___. |___. . | . |___| .___| |
| | | | | | | | | | | | | | |
|___|___. |___| |___. . |___|___.___|___. | | |___| | .___| |
| | | | | | | | | | | | |
| .___.___| .___|___. |___. | | .___| |___|___|___. | .___| |
| | | | | | | | | |
| . |___. | | . .___|___| |___. .___. |___.___. . . | |
| | | | | | | | | | |
| |___. .___|___. |___.___. | . .___|___.___|___.___.___|___|___| |
| | | | | | | | |
|___|___.___. .___| .___. | .___|___.___|___. |___. .___.___|___. |
| | | | | | | | | | |
| |___. .___.___|___| . |___| | .___. .___.___| | .___| .___|
| | | | | | | | | | |
| |___. |___. | | | |___.___.___.___| .___| .___. | .___. |
| | | | | | | | | | | |
| | | .___. | .___|___. .___| |___.___.___. | |___|___. |___|
| | | | | | | |
|___. . .___|___|___.___|___.___.___. | .___| .___.___. .___.___| |
| | | | | | | | | | |
| . |___| | | | .___. | | .___. .___. .___|___.___. | |
| | | | | | | |
|___|___|___.___. .___.___|___.___.___.___|___.___|___.___.___.___|___.___.___|