[QUIZ] Amazing Mazes (#31)
Ruby Quiz
1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
3. Enjoy!
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
by Matt Linnell
We've had crosswords, cryptograms, chess puzzles, madlibs ... so why don't we
try our hand at mazes? We can define the two basic components of this problem
as:
- Generating the maze
- Solving the maze
* Generating the maze *
The maze is to be rectangular in shape, with the height and width determined at
run time. All nodes of the maze must be reachable from any point. In other
words, if one were to randomly pick a start/stop, the maze is always solvable.
Furthermore, let us enforce that only 1 viable solution for the maze exists for
any given start/stop (you cannot reach the same destination from 2 different
routes). Generate an ASCII output representing the maze.
* Solving the Maze *
Given a maze produced from your above code, find the solution. Produce ASCII
output to demonstrate/visualize solution.
* Bonus Points *
1) Calculate which pair of start/stop points in the maze which gives
you the longest possible path.
2) Calculate which pair of start/stop points in the maze which gives
the most complicated path (involves the most turns)
Example command line execution:
$> ruby maze.rb {height} {width} [ {start} {stop} ]
James Edward Gray II
> Thank you for the quiz,
>
> I took great pleasure in this quiz...
Brian, simply amazing. You're work is always a pleasure to look
through and you're write-ups always help me get right to the good stuff.
Thanks!
James Edward Gray II
Dominik Bathon
here is my solution. First of all thanks for this nice quiz. After
Knight's Travails and Barrel of Monkeys another "search the shortest path"
quiz, so once again a nice solution to this quiz is Dijkstra's shortest
path algorithm.
I have to admit, that I cheated a bit: I googled for the maze generation
part and found the following page:
http://www.mazeworks.com/mazegen/mazetut/
It explains the perfect maze generation algorithm quite nice.
I solved the 1st bonus part, I didn't try the 2nd part, but I think
searching for the most turns might be quite expensive.
Dominik
Usage:
ruby maze.rb [-l] width height [from [to]]
if -l is given, it will search for the longest shortest path and print it.
if form or to are ommitted then random positions will be used.
Examples:
$ ruby maze.rb 10 10
$ ruby maze.rb -l 10 10
$ ruby maze.rb 10 10 0,0 9,9
$ ruby maze.rb 10 10 _ 5,5 # random "from"
Complete Example:
$ ruby maze.rb -l 8 8 0,0 7,7
Maze:
+---+---+---+---+---+---+---+---+
| | |
+---+---+ + +---+---+---+ +
| | | | |
+ +---+---+ +---+ + +---+
| | | | |
+---+---+ +---+ + +---+ +
| | | | | | |
+ + +---+ + + + + +
| | | | | |
+ + +---+---+---+---+ + +
| | | | |
+ +---+ +---+ + +---+ +
| | | | | | | |
+---+ + + + + + + +
| | | |
+---+---+---+---+---+---+---+---+
Shortest path from [0, 0] to [7, 7]:
+---+---+---+---+---+---+---+---+
| X X X | |
+---+---+ + +---+---+---+ +
| X X X | | | |
+ +---+---+ +---+ + +---+
| X X X | | | |
+---+---+ +---+ + +---+ +
| | X X | | | | X X |
+ + +---+ + + + + +
| | X | | X | X |
+ + +---+---+---+---+ + +
| X X | X X X | X X | X |
+ +---+ +---+ + +---+ +
| X X | X | | X | X | | X |
+---+ + + + + + + +
| X X | X X | X |
+---+---+---+---+---+---+---+---+
Longest shortest path (from [0, 0] to [4, 1]:
+---+---+---+---+---+---+---+---+
| X X X | X X X X X |
+---+---+ + +---+---+---+ +
| X X X | X | X X | X X |
+ +---+---+ +---+ + +---+
| X X X | X X | X | X X |
+---+---+ +---+ + +---+ +
| | X X | | X | X | X X |
+ + +---+ + + + + +
| | X | X X | X | |
+ + +---+---+---+---+ + +
| X X | X X X | X X | |
+ +---+ +---+ + +---+ +
| X X | X | | X | X | | |
+---+ + + + + + + +
| X X | X X | |
+---+---+---+---+---+---+---+---+
The performance is quite well:
$ time ruby maze.rb 30 30 > /dev/null
real 0m0.214s
user 0m0.179s
sys 0m0.008s
$ time ruby maze.rb -l 30 30 > /dev/null
real 0m4.068s
user 0m3.946s
sys 0m0.022s
$ time ruby maze.rb 100 100 > /dev/null
real 0m1.033s
user 0m0.992s
sys 0m0.011s
==============================================
maze.rb:
class Hash
# find the key for with the smallest value, delete it and return it
def delete_min_value
return nil if empty?
minkey=min=nil
each { |k, v|
min, minkey=v, k if !min || v<min
}
delete(minkey)
minkey
end
end
# Maze represents the maze ;-)
#
# Cells/positions in the maze are represented by Numbers (from 0 to w*h-1),
# each position corresponds to x/y coordinates, you can convert between
# positions and coordinates by coord2pos and pos2coord.
#
# The walls for each position are stored in the String @data. The walls for
# position p are stored in the first two bits of @data[p], the other bits
are
# unused. If bit one is set then p has a north wall, if bit two is set
then p
# has a west wall.
#
# Maze#generate generates a (random) maze using the method described at
# http://www.mazeworks.com/mazegen/mazetut/
#
# Maze#shortest_path uses Dijkstra's shortest path algorithm, so it can not
# anly find shortest pathes in perfect mazes, but also in mazes where
different
# pathes between two position exist.
class Maze
attr_reader :w, :h # width, height
def initialize(w, h)
@w, @h=[w, 1].max, [h, 1].max
@wh=@w*@h
@neighbors_cache={}
set_all_walls
end
def set_all_walls
# set all bits
@data=3.chr * (@wh)
nil
end
def clear_all_walls
# all except outer border
@data=0.chr * (@wh)
# set north walls of row 0
w.times { |i| @data[i] |= 1 }
# set west walls of col 0
h.times { |i| @data[i*w] |= 2 }
nil
end
# positions in path will be printed as "X"
def to_s(path=[])
ph={}
path.each { |i| ph[i]=true }
res=""
h.times { |y|
w.times { |x|
res << "+" << ((@data[y*w+x] & 1 > 0) ? "---" :
" ")
}
res << "+\n"
w.times { |x|
res << ((@data[y*w+x] & 2 > 0) ? "|" : " ")
res << (ph[y*w+x] ? " X " : " ")
}
res << "|\n"
}
res << ("+---"*w) << "+"
end
def inspect
"#<#{self.class.name} #{w}x#{h}>"
end
# maze positions are cell indices from 0 to w*h-1
# the following functions do conversions to and from coordinates
def coord2pos(x, y)
(y%h)*w+(x%w)
end
def pos2coord(p)
[p%w, (p/w)%h]
end
# returns valid neighbors to p, doesn't care about walls
def neighbors(p)
if ce=@neighbors_cache[p]; return ce; end
res=[p-w, p+w]
res << p-1 if p%w > 0
res << p+1 if p%w < w-1
@neighbors_cache[p] = res.find_all { |t| t>=0 && t<@wh }
end
def wall_between?(p1, p2)
p1, p2=[p1, p2].sort
if p2-p1==w # check north wall of p2
@data[p2] & 1 > 0
elsif p2-p1==1 # check west wall of p2
@data[p2] & 2 > 0
else
false
end
end
def set_wall(p1, p2)
p1, p2=[p1, p2].sort
if p2-p1==w # set north wall of p2
@data[p2] |= 1
elsif p2-p1==1 # set west wall of p2
@data[p2] |= 2
end
nil
end
def unset_wall(p1, p2)
p1, p2=[p1, p2].sort
if p2-p1==w # unset north wall of p2
@data[p2] &= ~1
elsif p2-p1==1 # unset west wall of p2
@data[p2] &= ~2
end
nil
end
# generate a (random) perfect maze
def generate(random=true)
set_all_walls
# (random) depth first search method
visited={0 => true}
stack=[0]
until stack.empty?
n=neighbors(stack.last).reject { |p| visited[p] }
if n.empty?
stack.pop
else
# choose one unvisited neighbor
np=n[random ? rand(n.size) : 0]
unset_wall(stack.last, np)
visited[np]=true
# if all neighbors are visited then here is
# nothing left to do
stack.pop if n.size==1
stack.push np
end
end
self
end
# central part of Dijkstra's shortest path algorithm:
# returns a hash that associates each reachable (from start) position
# p, with the previous position on the shortest path from start to p
# and the length of that path.
# example: if the shortest path from 0 to 2 is [0, 1, 2], then
# prev[2]==[1, 2], prev[1]==[0, 1] and prev[0]==[nil, 0].
# so you can get all shortest paths from start to each reachable
# position out of the returned hash.
# if stop_at!=nil the method stops when the previous cell on the
# shortest path from start to stop_at is found.
def build_prev_hash(start, stop_at=nil)
prev={start=>[nil, 0]} # hash to be returned
return prev if stop_at==start
# positions which we have seen, but we are not yet sure about
# the shortest path to them (the value is length of the path,
# for delete_min_value):
active={start=>0}
until active.empty?
# get the position with the shortest path from the
# active list
cur=active.delete_min_value
return prev if cur==stop_at
newlength=prev[cur][1]+1 # path to cur length + 1
# for all reachable neighbors of cur, check if we found
# a shorter path to them
neighbors(cur).each { |n|
# ignore unreachable
next if wall_between?(cur, n)
if old=prev[n] # was n already visited
# if we found a longer path, ignore it
next if newlength>=old[1]
end
# (re)add new position to active list
active[n]=newlength
# set new prev and length
prev[n]=[cur, newlength]
}
end
prev
end
def shortest_path(from, to)
prev=build_prev_hash(from, to)
if prev[to]
# path found, build it by following the prev hash from
# "to" to "from"
path=[to]
path.unshift(to) while to=prev[to][0]
path
else
nil
end
end
# finds the longest shortest path in this maze, only works if there
is
# at least one position that can only reach one neighbor, because we
# search only starting at those positions.
def longest_shortest_path
startp=endp=nil
max=-1
@wh.times { |p|
# if current p can only reach 1 neighbor
if neighbors(p).reject { |n| wall_between?(p, n)
}.size==1
prev=build_prev_hash(p)
# search longest path from p
tend, tmax=nil, -1
prev.each { |k, v|
if v[1]>tmax
tend=k
tmax=v[1]
end
}
if tmax>max
max=tmax
startp, endp=p, tend
end
end
}
if startp # path found
shortest_path(startp, endp)
else
nil
end
end
end
if $0 == __FILE__
ARGV.shift if search_longest=ARGV[0]=="-l"
w, h, from, to=ARGV
m=Maze.new(w.to_i, h.to_i)
m.generate
puts "Maze:", m.to_s
if from=~/(\d+),(\d+)/
p1=m.coord2pos($1.to_i, $2.to_i)
else
p1=rand(m.w*m.h)
end
if to=~/(\d+),(\d+)/
p2=m.coord2pos($1.to_i, $2.to_i)
else
p2=rand(m.w*m.h)
end
path=m.shortest_path(p1, p2)
puts "\nShortest path from #{m.pos2coord(p1).inspect} to " \
"#{m.pos2coord(p2).inspect}:", m.to_s(path)
if search_longest
path=m.longest_shortest_path
puts "\nLongest shortest path (from " \
"#{m.pos2coord(path[0]).inspect} to " \
"#{m.pos2coord(path[-1]).inspect}:",
m.to_s(path)
end
end
Markus Koenig
here is another solution. The maze generation part really took me a
while, but I finally got it, although my solution performs very badly
compared to the others. Maybe I should just go and read the page
Dominik suggested ...
Again, this taught me that one should just use Hashes to get better
performance, as I have done in the Visit class.
Thanks for this quiz which prevented my lessons from being boring :)
Markus
#!/usr/bin/env ruby
# This is an ugly hack to redeem us from checking indices all the time
def nil.[](i)
nil
end
# Visit encapsulates a selection of fields
class Visit < Array
attr_accessor :turns
def initialize
@included = {}
end
def [](x, y)
@included[y][x]
end
def add(x, y)
if (@included[y] ||= {})[x]
false
else
self << [x, y]
@included[y][x] = true
end
end
# from Latin "pons", bridge
# select a random bridge
def pons(other)
xarr = []
yarr = []
dirarr = []
each do |x, y|
if other[x - 1, y]
xarr << x
yarr << y
dirarr << :left
end
if other[x, y - 1]
xarr << x
yarr << y
dirarr << :up
end
if other[x + 1, y]
xarr << x
yarr << y
dirarr << :right
end
if other[x, y + 1]
xarr << x
yarr << y
dirarr << :down
end
end
# yield a bridge if there is at least one
if dirarr.empty?
return false
else
i = rand(dirarr.length)
yield xarr[i], yarr[i], dirarr[i]
return true
end
end
end
# Obviously encapsulates a maze
class Maze
attr_reader :width, :height
attr_accessor :selection
def initialize(width, height)
# initialize instance variables
@width = width
@height = height
@go_right = Array.new(height) {Array.new(width, false)}
@go_down = Array.new(height) {Array.new(width, false)}
# generate the maze
combs = combinations.sort_by{rand}
until combs.empty?
cur_comb = combs.shift
unless add_path(*cur_comb)
combs.push cur_comb
end
end
end
def add_path(x0, y0, x1, y1)
neigh0 = neighbors(x0, y0)
# return true if one can go from x0|y0 to x1|y1
if neigh0[x1, y1]
true
else
# remove the wall if we can
neigh0.pons(neighbors(x1, y1)) do |x, y, dir|
case dir
when :left
@go_right[y][x - 1] = true
when :up
@go_down[y - 1][x] = true
when :right
@go_right[y][x] = true
when :down
@go_down[y][x] = true
end
end
end
end
def combinations
max_index = @width * @height - 1
arr = []
max_index.times do |i0|
x0 = i0 % @width
y0 = i0 / @width
(i0+1).upto(max_index) do |i1|
x1 = i1 % @width
y1 = i1 / @width
arr << [x0, y0, x1, y1]
end
end
return arr
end
def display
curses = MazeCurses.new(5 * @width + 1, 3 * @height + 1)
# draw the stipples
if @selection
@selection.each do |x, y|
curses.stipple 5 * x, 3 * y, 6, 4
end
end
# draw the outer border
curses.box
# draw the inner borders
@height.times do |y|
@width.times do |x|
unless @go_right[y][x]
curses.mvvline 5 * (x + 1), 3 * y, 4
end
unless @go_down[y][x]
curses.mvhline 5 * x, 3 * (y + 1), 6
end
end
end
# throw the thing at stdout
curses.wnoutrefresh
end
def go(x, y, direction)
# try to go into a direction
case direction
when :left
yield x - 1, y if @go_right[y][x - 1]
when :up
yield x, y - 1 if @go_down[y - 1][x]
when :right
yield x + 1, y if @go_right[y][x]
when :down
yield x, y + 1 if @go_down[y][x]
end
end
def neighbors(x, y)
neigh = Visit.new
neigh.add x, y
# add all neighbors
done = false
until done
done = true
neigh.each do |x, y|
# try to go left
if @go_right[y][x - 1] and neigh.add(x - 1, y)
done = false
end
# try to go up
if @go_down[y - 1][x] and neigh.add(x, y - 1)
done = false
end
# try to go right
if @go_right[y][x] and neigh.add(x + 1, y)
done = false
end
# try to go down
if @go_down[y][x] and neigh.add(x, y + 1)
done = false
end
end
end
# the neighborhood is complete
return neigh
end
def path(x0, y0, x1, y1, curdir = nil)
# find a way from x0|y0 to x1|y1
# this uses depth-first search
if x0 == x1 and y0 == y1
way = Visit.new
way.add x0, y0
way.turns = 0
return way
end
case curdir
when :left
directions = [:left, :up, :down]
when :up
directions = [:left, :up, :right]
when :right
directions = [:up, :right, :down]
when :down
directions = [:left, :right, :down]
else
directions = [:left, :up, :right, :down]
end
directions.each do |direction|
go x0, y0, direction do |x2, y2|
way = path(x2, y2, x1, y1, direction)
if way
way.add x0, y0
unless direction == curdir
way.turns += 1
end
return way
end
end
end
return nil
end
end
# A way to draw fancy or sludgy ASCII graphics
class MazeCurses
# This has *nothing* to do with the curses library!
def initialize(width, height)
@width = width
@height = height
@matrix = Array.new(height) {' ' * width}
end
def box
# draw a box around the edges of the matrix
mvhline 0, 0, @width
mvhline 0, @height-1, @width
mvvline 0, 0, @height
mvvline @width-1, 0, @height
end
def mvaddch(x, y, ch)
case ch
when ?-
if @matrix[y][x] == ?|
@matrix[y][x] = ?+
elsif @matrix[y][x] != ?+
@matrix[y][x] = ?-
end
when ?|
if @matrix[y][x] == ?-
@matrix[y][x] = ?+
elsif @matrix[y][x] != ?+
@matrix[y][x] = ?|
end
else
@matrix[y][x] = ch
end
end
def mvhline(x, y, n)
n.times do |i|
mvaddch x + i, y, ?-
end
end
def mvvline(x, y, n)
n.times do |i|
mvaddch x, y + i, ?|
end
end
def stipple(left, top, width, height)
top.upto(top+height-1) do |y|
left.upto(left+width-1) do |x|
@matrix[y][x] = ?:
end
end
end
def wnoutrefresh
puts @matrix
puts
end
end
if ARGV.length != 2
puts 'usage: ruby maze.rb {height} {width}'
exit
end
maze = Maze.new(ARGV[1].to_i, ARGV[0].to_i)
all_paths = maze.combinations.map{|x| maze.path(*x)}
puts "== Upper left to lower right =="
maze.selection = maze.path(0, 0, maze.width - 1, maze.height - 1)
maze.display
puts "== Longest path =="
maze.selection = all_paths.sort_by{|x| x.length}.last
maze.display
puts "== Most complicated path =="
maze.selection = all_paths.sort_by{|x| x.turns}.last
maze.display
Dave Burt
I have 2 maze creation algorithms, and 2 maze solving algorithms.
I didn't implement a command-line options interface, but that would be
trivial to do. I think it's a decent enough API.
I don't like my solution because it has too many capital letters, due to the
fact that methods are not first-class objects and I wanted to pass around
the building and solving algorithms.
http://www.dave.burt.id.au/ruby/maze.rb
Cheers,
Dave
Ruby Quiz
to give me a little man icon and some controls! Throw in some doors, some keys,
and little critters to chase me around and there's simply no chance at all I
would get a summary written next week. Hmm, maybe it's not such a good idea.
Jokes aside, do run the solutions a few times each this week. It's fun to see
what they build. Then peek inside the code and read the comments. Good stuff
in there.
Below, I want to look into Dominik Bathon's code. It is a nice search and
lightning quick! On my machine, it makes and solves quizzes faster than the
other solutions can just make them. Even better, it uses a complex internal
representation (mainly for speed), yet still comes out with clean algorithms. I
was quite impressed by that.
Let's get to the code. Dominik starts off by defining a helper method in Hash:
class Hash
# find the key for with the smallest value, delete it and return it
def delete_min_value
return nil if empty?
minkey=min=nil
each { |k, v|
min, minkey=v, k if !min || v<min
}
delete(minkey)
minkey
end
end
# ...
The comment pretty much explains what's going on there. Each pair of the Hash
is compared by value. The pair with the lowest value is deleted and the key for
that value is returned.
On to the interesting parts. Here's the start of the main class used by the
solution:
# Maze represents the maze ;-)
#
# Cells/positions in the maze are represented by Numbers
# (from 0 to w*h-1), each position corresponds to x/y coordinates,
# you can convert between positions and coordinates by coord2pos
# and pos2coord.
#
# The walls for each position are stored in the String @data. The walls
# for position p are stored in the first two bits of @data[p], the
# other bits are unused. If bit one is set then p has a north wall, if
# bit two is set then p has a west wall.
#
# Maze#generate generates a (random) maze using the method described at
# http://www.mazeworks.com/mazegen/mazetut/
#
# Maze#shortest_path uses Dijkstra's shortest path algorithm, so it can
# not anly find shortest pathes in perfect mazes, but also in mazes
# where different pathes between two position exist.
class Maze
attr_reader :w, :h # width, height
def initialize(w, h)
@w, @h=[w, 1].max, [h, 1].max
@wh=@w*@h
@neighbors_cache={}
set_all_walls
end
# ...
I know that section is mostly a comment, but you'll want to read through it.
It's interesting information and it introduces you to the internal format the
code uses.
After that, we see some readers defined and some simple initialization work.
Set a width and height, ensuring they are both at least 1. Nice use of max()
there. Calculate width times height or the total number of cells, initialize a
cache and call set_all_walls().
That means we need some more code:
# ...
def set_all_walls
# set all bits
@data=3.chr * (@wh)
nil
end
def clear_all_walls
# all except outer border
@data=0.chr * (@wh)
# set north walls of row 0
w.times { |i| @data[i] |= 1 }
# set west walls of col 0
h.times { |i| @data[i*w] |= 2 }
nil
end
# ...
Okay, now we start to get tricky. Remember the initial comment about using bits
for the walls. We're only tracking two walls here, north and west. Of course
cells can still have up to four walls, but your east wall is just your
neighbor's west wall and your south wall is the north wall for the cell below
you.
Now, what do you get if you turn two bits on? 3. The set_all_walls() method
just translates that to a character and duplicates it for every cell. That
gives us a String representing the entire maze with all the walls turned on.
That should make clear_all_walls() more obvious. This time we want no walls so
we don't set any bits. Translate 0 to a character and duplicate. However, we
still need the edges of the maze. All cells in the top row need a north wall
(set the 1 bit). Then all the cells in the first column need a west wall (set
the 2 bit). That makes up the rest of the method.
Ready for the next chunk?
# ...
# positions in path will be printed as "X"
def to_s(path=[])
ph={}
path.each { |i| ph[i]=true }
res=""
h.times { |y|
w.times { |x|
res << "+" << ( (@data[y*w+x] & 1 > 0) ? "---" :
" " )
}
res << "+\n"
w.times { |x|
res << ((@data[y*w+x] & 2 > 0) ? "|" : " ")
res << (ph[y*w+x] ? " X " : " ")
}
res << "|\n"
}
res << ("+---"*w) << "+"
end
def inspect
"#<#{self.class.name} #{w}x#{h}>"
end
# ...
The to_s() method draws mazes. The first two lines fill a Hash with the
solution path, if one is given. The Hash is indexed identically as the maze
String and values can be true (if it's on the path) or the default nil, (when
it's not).
The rest of that method does the drawing. It walks row by row with h.times(),
down the maze drawing cells. The first w.times() call handles the north walls.
First it adds a "+", then it adds "---" if the 1 bit is set or " " if it's
not. Next we need another "+" and a "\n". Now the second w.times() block
handles the west wall and path. First it checks to see if the 2 bit is set for
the current cell, outputting "|" if it is and " " if it's not. Then the path is
checked. If this cell is on the path, it's filled with " X " and if it's not,
the code adds a " ".
The last two lines of the method are important. They ensure a final "|" is
always added to the end of a row and a final "+---" is placed at the end each
column of the maze. This handles the east and south borders of the maze, which
are not covered by the bits.
The other method, inspect(), just returns a class name, width and height.
# ...
# maze positions are cell indices from 0 to w*h-1
# the following functions do conversions to and from coordinates
def coord2pos(x, y)
(y % h)*w+(x % w)
end
def pos2coord(p)
[p % w, (p/w) % h]
end
# ...
These convertors were explained in the initial comment and they are explained
again here. No surprises there.
# returns valid neighbors to p, doesn't care about walls
def neighbors(p)
if ce=@neighbors_cache[p]; return ce; end
res=[p-w, p+w]
res << p-1 if p%w > 0
res << p+1 if p%w < w-1
@neighbors_cache[p] = res.find_all { |t| t>=0 && t<@wh }
end
This returns the indices of the up to four neighboring cells. It caches this
lookup the first time it does it, since it will never change. The first line
just uses the cache if it has already been figured. The second line adds the
cell above and the cell below. Note that these numbers are found by simple math
and could be outside the bounds of the maze. The next two lines add the left
and right cells. We're more careful with our math here, because a wrong answer
could look right: The last cell of the first row is "left" of the first cell of
the second row, in our one dimensional String that holds the maze data. The
final line, stores the indices to the cache and returns them, after using
find_all() to eliminate any bogus number that crept in.
# ...
# ...
These three methods are all very similar. Given two cells, the first checks if
there is a wall between them, the second sets the wall between them, and the
third unsets it. The if's just figure out if we are talking about a north wall
or a west wall. The rest is bit testing or setting.
On to maze generation:
# ...
# generate a (random) perfect maze
def generate(random=true)
set_all_walls
# (random) depth first search method
visited={0 => true}
stack=[0]
until stack.empty?
n=neighbors(stack.last).reject { |p| visited[p] }
if n.empty?
stack.pop
else
# choose one unvisited neighbor
np=n[random ? rand(n.size) : 0]
unset_wall(stack.last, np)
visited[np]=true
# if all neighbors are visited then here is
# nothing left to do
stack.pop if n.size==1
stack.push np
end
end
self
end
# ...
This algorithm came out very clean, I think. Not a bit operation in sight.
First it turns all the walls on. Then it sets up an Array for tracking visited
cells and another as a stack to drive the process. While there is something on
the stack, the code looks at each not-yet-visited neighbor. If there are no
neighbors in that set, the stack is popped and the routine moves on. However,
if there are, one is chosen at random and the wall is knocked out between them.
If that neighbor was the last unvisited one for this cell, the code pops the
current cell off the stack. The neighbor cell is set to visited and pushed onto
the stack, moving the build process to that location for the next iteration.
That covers creation. Now we need a solver:
# ...
# central part of Dijkstra's shortest path algorithm:
# returns a hash that associates each reachable (from start)
# position p, with the previous position on the shortest path
# from start to p and the length of that path.
# ...
I really don't think I need to launch into too deep an explanation here as the
comments guide you right through it. The short story is that this method
branches out from a starting cell, walking to each neighbor and always counting
its steps. While doing this, it is building the Hash described in the first
comment, which points to the cell that came before on the shortest path. Using
that Hash, returned by this method, you can easily construct the shortest path
to any cell the algorithm visited. Handy stuff! Let's see how it gets put to
use:
# ...
def shortest_path(from, to)
prev=build_prev_hash(from, to)
if prev[to]
# path found, build it by following the prev hash from
# "to" to "from"
path=[to]
path.unshift(to) while to=prev[to][0]
path
else
nil
end
end
# ...
Given a starting and ending cell, this returns just what the name implies. It
builds the magic Hash we just looked at on the first line, then just walks the
path in reverse until it reaches the start (nil in the Hash). Again, clean and
simple. Nice coding Dominik.
Let's look at the other search the code provides:
# ...
# finds the longest shortest path in this maze, only works if
# there is at least one position that can only reach one
# neighbor, because we search only starting at those positions.
# ...
This method walks the maze, looking for cells that are dead-ends. From each of
those, it builds the path Hash and checks the lengths of each path found. In
the end, it will return the longest path it saw.
Just a little more code is needed for human interface:
# ...
This is just option parsing and display. The code checks for a special first
"-l" option, which just sets a flag to add the long search.
The next chunk reads a width and height then builds and displays a maze of the
indicated size. The code next reads from and to cells for a solution search,
if they where provided. Random coordinates are used when from or to cells are
absent. Note the use of the coord2pos() convertor in here.
Finally, the shortest path is displayed. The longer search is also added, if
requested. Dominik uses an unusual Ruby idiom here, "string" "string". Ruby
will concatenate these, even without the + between them. (I didn't know this!)
However, the rumor is that this feature may vanish in a future version of Ruby,
so it's probably not a good habit to get into.
My thanks to those who braved the mazes this week. Really interesting (and
fun!) solutions were given by all.
Tomorrow's quiz is a little client and server fun, care of Pat Eyler's
children...
Dominik Bathon
One other point I found out today:
We don't really need Dijkstra's algorithm for the mazes, because all edges
have weight 1. In this case a simple breadth-first search is sufficient.
So build_prev_hash can be simplified to the following:
def build_prev_hash(start, stop_at=nil)
prev={start=>[nil, 0]} # hash to be returned
# positions which we have seen, but we are not yet sure about
# the shortest path to them (the value is length of the path,
# for delete_min_value):
active=[start]
until active.empty?
# get the position with the shortest path from the
# active list
cur=active.shift
return prev if cur==stop_at
newlength=prev[cur][1]+1 # path to cur length + 1
neighbors(cur).each { |n|
# ignore unreachable
next if wall_between?(cur, n)
# was n already visited
next if prev[n]
# add new position to active list
active << n
# set prev and length
prev[n]=[cur, newlength]
}
end
prev
end
The active list is now an Array instead of a Hash and we just use it as
fifo, because the positions/paths that were found first are the shortest.
So there is also no more need for Hash#delete_min_value. And it gets even
faster ;-)
Dominik
Clifford Heath
> Below, I want to look into Dominik Bathon's code.
Nicely coded, I enjoyed learning some Ruby tricks.
Unfortunately if you look at the mazes this algorithm generates,
you'll see a serious flaw. They always seem to "fan out" from
the start position - in other words there is not a random nature
to the shape of the paths away from the start position. It makes
the mazes much easier to solve. I made the same mistake when I
first wrote a maze generator.
The commonly accepted alternative method (which produces *random*
mazes) is to number every square with a distinct number 0..N, then
choose a random wall which divides two cells having different
numbers. Throughout the maze, change the higher number to the
lower number, and repeat until the whole maze is numbered 0. This
takes exactly N cycles.
The search for a random wall requires a circular search around the
maze from a randomly-chosen start position, until a suitable wall
is found.
Clifford Heath.
Martin DeMello
>
> Let's get to the code. Dominik starts off by defining a helper method
> in Hash:
>
> class Hash
> # find the key for with the smallest value, delete it and return it
> def delete_min_value
Wonder if
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/133202 would
be an optimisation.
martin
Dominik Bathon
Yes, I know about rbtree, but it isn't in the stdlib, so I didn't want to
use it for the quiz. Ruby really lacks a nice sorted set out of the box
(SortedSet in set.rb uses rbtree, if it is installed, otherwise it just
resorts the elements, when they changed and it has no accessor for the
min/max elements).
And as I said in my other reply, for this special problem the priority
queue isn't necessary at all.
Dominik
Martin DeMello
>
> Yes, I know about rbtree, but it isn't in the stdlib, so I didn't want to
> use it for the quiz. Ruby really lacks a nice sorted set out of the box
> (SortedSet in set.rb uses rbtree, if it is installed, otherwise it just
> resorts the elements, when they changed and it has no accessor for the
> min/max elements).
Ah - yes, good point. But rbtree really ought to make it into the
stdlib, IMO. Having it in there would promote good algorithmic
practices.
martin
Ara.T....@noaa.gov
i've reccomended this many times - an RCR?
-a
--
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| renunciation is not getting rid of the things of this world, but accepting
| that they pass away. --aitken roshi
===============================================================================
Glenn M. Lewis
Could you please elaborate? This sounds fascinating,
but I don't quite grok it. For example, when/how do you decide
to place or destroy a wall?
Do you have a pointer that goes into more detail?
Thanks!
-- Glenn
Clifford Heath
> Could you please elaborate?
It's been quite a while since I did this stuff, but I do recall
solving the problem, and only afterwards finding some other
work that reflected the same solution.
It'd be very cool to do this again in Ruby with OpenGL :-))).
The idea is to start as Dominik did, with a maze having all
walls intact - every cell has two intact walls so it's closed
from every other cell. Every cell is numbered, say top-left
to bottom-right, 0..(W*H-1). This number is known as the
domain number, and every cell bearing a certain number is
defined to be reachable from any cell in that domain.
Whenever you break a wall separating two distinct domains,
you join them into one domain, because any cell in either
domain can now reach any cell in the other domain. So to keep
things intact, you must eliminate one domain by changing all
occurrences of that number to the other one. I always eliminate
the higher numbered one, so the maze ends up as one domain
numbered zero.
Whenever you consider a wall you might want to break, check
the domain numbers on either side. If they're the same, there
is already a path between the two cells, and breaking this wall
will make a duplicate path - which is not what you want. If
they're different however, there is no path between the two
cells and it's ok to break this wall, eliminating one of the
two domains.
The only remaining task is to find an efficient and random
search for a wall to break. The easiest way is to choose a
cell at random, check both walls (in random order), and if
that wall divides two domains, break it. If not, consider
the next cell (circular search) until you find a wall you can
break.
Because you have W*H cells, there are initially that many domains,
and because every break reduces the domain count by one, you must
break exactly W*H-1 walls to get to a maze where every cell is
reachable from every other.
I set my son the challenge of doing this in three dimensions,
and we arranged things so the ladders (=broken floors) were
much less numerous than the horizontal connections. You can
do this simply by skewing the random number generator that
chooses which wall to break. If it tries the north wall 45%
of the time, the east wall 45%, and the floor only 10%, you
get the desired outcome.
Similarly in a 2-D maze, you can skew the generation so that
more of the paths are E-W rather than N-S.
Then we created a 3-D perspective view looking in from near one
corner between two layers, so you can see all the passages, the
ladders climbing up to the layer above, and the manholes where
ladders appear from below, so you can wander around the maze at
will. We even animated the ladder climbing using double
buffering, moving the camera up past the floor to the next floor.
All in Turbo-Pascal for a year 10 assignment :-). My son solved
a 20x20x20 maze in about 10 minutes, much to his teacher's
astonishment - he has an amazing visual memory.
I used to print him 2-D mazes with a 1/8" cell size, full page on
letter paper - perhaps 60x80 in size. When he was four years old,
he complained that he needed some new ones, and my wife pointed
out that he had a stack of sixty that were unmarked. He quickly
went through the stack, pointing to the solution on each one. He
had not only solved them all by eye, but he recognised each one
and remembered its solution! Scary...
Clifford Heath.
Glenn M. Lewis
> [... description removed ...]
Excellent! That makes perfect sense! Thank you very
much for explaining it!!!
> Then we created a 3-D perspective view looking in from near one
> corner between two layers, so you can see all the passages, the
> ladders climbing up to the layer above, and the manholes where
> ladders appear from below, so you can wander around the maze at
> will. We even animated the ladder climbing using double
> buffering, moving the camera up past the floor to the next floor.
> All in Turbo-Pascal for a year 10 assignment :-). My son solved
> a 20x20x20 maze in about 10 minutes, much to his teacher's
> astonishment - he has an amazing visual memory.
That's incredible!
> I used to print him 2-D mazes with a 1/8" cell size, full page on
> letter paper - perhaps 60x80 in size. When he was four years old,
> he complained that he needed some new ones, and my wife pointed
> out that he had a stack of sixty that were unmarked. He quickly
> went through the stack, pointing to the solution on each one. He
> had not only solved them all by eye, but he recognised each one
> and remembered its solution! Scary...
>
> Clifford Heath.
Wow... very impressive!!! Looks like you've got a genius
on your hands! Very cool.
Thanks again!
-- Glenn
Glenn M. Lewis
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
_____________________________________________________________________________
| | | | | | | |
|___. .___| |___. .___.___| | . | . . | .___.___. .___.___|
| | | | | | | | | |
| .___| .___. |___. .___| | | .___| |___. .___. |___.___. |
| | | | | | | | | | |
| .___| | | . .___. . |___|___. |___|___.___| .___.___. | |
| | | | | | | | | | | | | |
| . | | . |___.___|___|___. .___. |___. | | | | | |___|
| | | | | | | | | | | |
| |___| |___|___. . |___.___. .___|___|___. | | . .___|___. |
| | | | | | | | |
|___. .___|___.___. | .___| .___. |___.___. |___. |___.___.___|___|
| | | | | | | | | | | |
| |___.___|___.___. |___.___|___| | |___.___. |___. | | .___.___|
| | | | | | |
|___. |___. .___. |___. .___| .___| .___|___. .___. .___. .___|
| | | | | | | | | |
| . |___. . |___.___. . |___. |___. . | . |___| .___| |
| | | | | | | | | | | | | | |
|___|___. |___| |___. . |___|___.___|___. | | |___| | .___| |
| | | | | | | | | | | | |
| .___.___| .___|___. |___. | | .___| |___|___|___. | .___| |
| | | | | | | | | |
| . |___. | | . .___|___| |___. .___. |___.___. . . | |
| | | | | | | | | | |
| |___. .___|___. |___.___. | . .___|___.___|___.___.___|___|___| |
| | | | | | | | |
|___|___.___. .___| .___. | .___|___.___|___. |___. .___.___|___. |
| | | | | | | | | | |
| |___. .___.___|___| . |___| | .___. .___.___| | .___| .___|
| | | | | | | | | | |
| |___. |___. | | | |___.___.___.___| .___| .___. | .___. |
| | | | | | | | | | | |
| | | .___. | .___|___. .___| |___.___.___. | |___|___. |___|
| | | | | | | |
|___. . .___|___|___.___|___.___.___. | .___| .___.___. .___.___| |
| | | | | | | | | | |
| . |___| | | | .___. | | .___. .___. .___|___.___. | |
| | | | | | | |
|___|___|___.___. .___.___|___.___.___.___|___.___|___.___.___.___|___.___.___|
Clifford Heath
> In honor of Clifford's very clear description of his maze-generation
> algorithm, here is my attempt at a solution, and an example output:
That's even cuter than I expected it to be - well done!
Note that you don't use a circular search, so especially
with large mazes, your random choice is going to take
longer and longer to find a valid wall. You should choose
a starting position, then choose an order in which to
check the two walls, check them both, and if that fails,
don't choose a new random starting position but step to
the very next cell and check the walls again (same or
different random order is ok). Otherwise there's a real
possibility of *very* long runtimes. For example, to break
the last wall in a 20x20x20 maze, your random algorithm
has to loop until it finds one of 167200 candidate walls
out of a field that might be as small as three walls.
Thanks for your kind comments. Let's hope my son is as good
at relationships! He announced his engagement yesterday, at
the age of 19... I can't complain, I married at 21 and still
am now... ;-).
Clifford.
Glenn M. Lewis
for big mazes. I was actually pleasantly surprised by how fast this one
cranked out a small maze. I thought I would be waiting and waiting for
it to find a valid wall to break.
Congratulations to you and your son!
I married at 22 and am still married 16 years later with 4 kiddies, and
the first one just got her learner's permit! Time flies!
-- Glenn
Greg Millam
> Could you please elaborate? This sounds fascinating,
> but I don't quite grok it. For example, when/how do you decide
> to place or destroy a wall?
>
> Do you have a pointer that goes into more detail?
I know I'm coming into this thread a bit late, but I just looked into
it. I wrote a little lesson on this kind of thing about a year or so ago
to help a co-developer understand something I was doing. (I'm making a
game that, while not a maze, does use the same wall-breaking concept and
using regions as such).
http://walker.deafcode.com/lessons/perfect_maze.txt
In the other solutions provided here, a wall is chosen by randomly
selecting cells until one is found with an unbroken wall. In my given
solution above, the walls themselves are listed, shuffled (perhaps even
a weighted shuffle) and then broken in order they are in the list,
unless the rooms on either side of the wall are in the same area.
Just some input of mine. Hope it helps.
- Greg Millam
Glenn M. Lewis
>...
> Note that you don't use a circular search, so especially
> with large mazes, your random choice is going to take
> longer and longer to find a valid wall. You should choose
> a starting position, then choose an order in which to
> check the two walls, check them both, and if that fails,
> don't choose a new random starting position but step to
> the very next cell and check the walls again (same or
> different random order is ok). Otherwise there's a real
> possibility of *very* long runtimes. For example, to break
> the last wall in a 20x20x20 maze, your random algorithm
> has to loop until it finds one of 167200 candidate walls
> out of a field that might be as small as three walls.
> Clifford.
Excellent point! Here's my revised version that should not have this problem.
#!/usr/bin/env ruby
$debug = nil
#
# The algorithm is extracted from:
# <http://www.rubygarden.org/ruby?OneLiners>
#
class Array
def shuffle!
each_index {|j|
i = rand(size-j);
self[j], self[j+i] = self[j+i], self[j]
}
end
end
class Maze
TOP = 1
LEFT = 2
def initialize(w,h)
@w = w
@h = h
@size = @w*@h
@maze = Array.new(@size)
@wall = Array.new(@size, TOP|LEFT)
@w.times do |i|
@h.times do |j|
putMaze(i,j,j*@w+i)
end
end
@order = @maze.dup
# First, break exactly one top wall
clearWall(rand(@w),0,TOP)
# and define the exit column at the bottom...
@exit = rand(@w)
# Define the order in which cells and their walls get checked...
@order.shuffle!
# Now, randomly break the walls...
breakWalls
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 breakWalls
breakCount = @size-1
i = 0
while breakCount > 0
val = @order[i%@size]
y = val/@w
x = val-@w*y
puts "i=#{i}, val=#{val}, breakCount=#{breakCount}, calling: breakCell(#{x},#{y})..." if $debug
breakCount -= breakCell(x,y)
i += 1
end
end
def breakCell(x,y)
wall = 1 + rand(2)
count = breakWall(x,y,wall)
# Better mazes (longer runs) result if both walls are not checked at the same time.
# wall = (TOP+LEFT)-wall
# count += breakWall(x,y,wall)
return count
end
def breakWall(x,y,wall)
# Don't break LEFT wall for x==0
return 0 if (x==0 && wall==LEFT)
# Don't break TOP wall for y==0
return 0 if (y==0 && wall==TOP)
x2 = wall==LEFT ? x-1 : x
y2 = wall==TOP ? y-1 : y
return 0 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 1
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) ? "|" : " "
$debug ? printf("%3d", getMaze(w,h)) : (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(37,28)
puts maze
end
C:\src>gmlmaze2.rb
_________ ________________________________________________________________________________________________________________________________________
| | | | | | | | | | | | | |
| | .___| .___|___. |___.___. .___.___. .___.___. . .___| | .___. |___. .___| | . | . | . .___| .___.___. |
| | | | | | | | | | | | | | | | | | |
| | . | . .___| . .___| . . |___. . |___|___.___. | . | .___|___. .___.___|___| | | |___.___| .___.___|___|
| | | | | | | | | | | | | | | | | | |
| . | |___| . | |___.___| | | . | |___.___.___.___| | | | .___.___|___.___.___. |___| .___. .___. . . .___|
| | | | | | | | | | | | | | | | | | | | | |
|___|___| . | | |___. . | |___|___|___| .___. .___.___|___| | |___.___. . . . | . |___. |___. |___|___|___.___|
| | | | | | | | | | | | | | | | | | | |
|___. | | . | .___| | |___.___.___. |___.___|___.___.___. | |___.___. |___| | |___|___|___. | . |___.___. .___. |
| | | | | | | | | | | | | | | | | | |
| |___.___|___|___| . |___| .___.___.___| .___.___.___. . | | . .___|___.___| | . .___.___| |___| .___.___| . | |
| | | | | | | | | | | | | | | | | |
| . .___.___.___| | .___|___.___. . . .___.___. |___|___|___|___|___. .___. | | |___. . |___. | .___. | |___| |
| | | | | | | | | | | | | | | | | | | |
|___| . . . | |___.___.___. |___|___|___.___. | .___. .___.___.___| .___| | | . | |___. | |___.___| |___. | |
| | | | | | | | | | | | | | | | | | | | | |
| | |___|___|___| . .___. |___. . .___. |___| .___|___. . .___| . |___| | |___|___. | | . . | . |___|___|
| | | | | | | | | | | | | | | | | | | | | |
| . .___. . |___| .___| . | | . |___. |___.___. |___|___. |___|___. |___| .___.___|___|___|___| | | | . . |
| | | | | | | | | | | | | | | | | | | | |
|___| .___|___| .___|___. |___|___| | | .___|___. . | .___.___|___.___. |___.___|___.___. .___. .___|___|___.___|___| | |
| | | | | | | | | | | | | |
| |___. . |___. . | .___. |___| | .___.___|___| |___.___. .___.___|___.___. . .___. . | .___. . .___.___. |___|
| | | | | | | | | | | | | | | | | | | |
|___. | | . | | | .___|___.___| | .___. . |___.___. | .___.___.___. | |___. |___| | .___|___|___.___.___| .___|
| | | | | | | | | | | | | | | | | | | |
|___. |___|___|___| |___|___. .___. |___|___.___|___| .___.___|___|___. .___.___|___|___. | .___|___|___. . . . .___| . |
| | | | | | | | | | | | | | |
| . .___.___.___|___. .___| .___|___. . . .___| . . . .___| .___.___. . |___| . . . |___|___|___| .___| |___|
| | | | | | | | | | | | | | | | | | | | |
|___|___. . .___. | . | .___. | | |___. |___|___|___| .___|___.___.___|___|___. | | | |___. . .___|___. |___. |
| | | | | | | | | | | | | | | | | | | | |
|___. | | .___|___| |___|___. | |___|___.___|___.___.___. |___.___. .___.___. .___| |___|___| . |___|___.___. |___.___| |
| | | | | | | | | | | | | |
| |___.___| .___.___| .___.___. | . .___. .___.___. | . .___|___.___. | . |___.___. |___|___. .___.___| . . |___|
| | | | | | | | | | | | | | | | | | |
|___.___. |___. .___|___. . |___| | . | . .___| |___|___.___. .___| |___| . .___|___.___. | .___.___|___|___|___. |
| | | | | | | | | | | | | | | | | | |
|___. | . |___.___. |___| . |___|___| | | . |___.___. .___|___. | . |___| . . . |___|___. . . .___. |___|
| | | | | | | | | | | | | | | | | | | | | | |
| |___.___| .___. |___. |___|___.___. | | |___|___.___.___| .___. | | | . | | | | . .___| | | . | .___|
| | | | | | | | | | | | | | | | | | | | | |
| . .___| .___| .___.___. .___.___. |___|___.___.___.___.___| . | |___| | |___|___| |___|___| . | |___| |___| .___|
| | | | | | | | | | | | | | | | | |
|___|___. | . |___. .___| .___. |___.___. .___. .___.___| | |___.___| | .___.___|___.___.___|___| | .___|___. | . |
| | | | | | | | | | | | | | | | |
|___.___.___.___|___. | .___| . |___.___.___|___.___| .___.___| | .___.___|___| .___. .___. . . | |___. . | |___|___|
| | | | | | | | | | | | | | | | | |
|___.___.___. . | | .___| | .___. .___.___. | . . | |___. . . | .___| . |___|___| |___.___| |___|___.___.___|
| | | | | | | | | | | | | | | | | | | | |
|___. .___. |___| | . |___| .___|___.___.___| | |___|___| .___|___|___|___| .___| |___. .___| .___. |___.___.___. . |
| | | | | | | | | | | | | | |
|___.___.___| . . | |___. | . .___. .___|___| . .___| .___.___. .___| .___|___. | . |___. |___.___.___.___.___|___|
| | | | | | | | | | | | | | | | | |
|___.___.___.___|___|___|___.___|___|___|___.___|___.___.___|___|___.___|___.___.___|___.___|___.___. |___|___|___.___|___.___.___.___.___.___.___|
Belorion
Great stuff.
> Glen said:
> Excellent point! Here's my revised version that should not have this problem.
*snips maze output*
I don't know if this is just coincidence, or that I might being seeing
something that really isn't there ... but looking at your output in
the proper fixed-width font makes me wonder if your algorithm is truly
random. I can't help but look at that maze and see a very heavy
presence of diagonal paths ... ie. a high occurance of being able to
travel right, down, right, down, right, down, right, down, etc. Or is
it just me?
I took a look at your source, and nothing jumped out at me as to why
this might be the case...
Matt