From: Markus Koenig <markus@...>
Date: 2005-05-10T07:04:28+09:00
Subject: Re: [QUIZ] Amazing Mazes (#31)

Hello,

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