Create a gist now

Instantly share code, notes, and snippets.

anonymous /paulmckibbin.rb Secret
Created Jan 2, 2010

Breadth first search of a maze for the exit for RPCFN quiz 5
class Maze
def initialize(map)
def build
def walk
unless start_pos.nil? || !(@m_aMap.join=~/B/) #unless no start or end
width=@m_aMap.collect {|x| x.size}.max #should have boundary wall anyway
queue=[[start_pos/width,start_pos%width,0]] #initialize stack with start x,y and depth
while !queue.empty?
visited[hash_index].nil? ? visited[hash_index]=true : next
case @m_aMap[x][y].chr
when ' ','A'
queue.push([x,y-1,depth+1]) if y>0 #checks are redundant if boundary wall completely
queue.push([x,y+1,depth+1]) if y<width #surrounds the maze, but add to flexibility if there
queue.push([x-1,y,depth+1]) if x>0 #is a start position on the boundary.
queue.push([x+1,y,depth+1]) if x<height
when 'B'
return [true,depth]
return [false,0] #fail if we got to here
def solvable?
@m_bSolvable || build
def steps
solvable? ? @m_iPathLength : 0
#There were lots of choices for this particular test, but I thought that I'd go for brevity and meeting
#the stated requirement rather than leave in all of the extra code I had (printing the final solution, by
#storing a parent in the visited and passing it to the stack, etc.) The code first converts the map to
#an array of strings and finds the start position. From this it then adds in all of the boxes bounding
#this to a stack and examines them in turn, adding other bounding squares to the stack of places to
#be examined as it goes on. If a cell has been previously visited, or doesn't contain a path, it is
#skipped and the next one in the stack is examined. In addition to the cell location, the distance from
#the starting square is passed to the stack, which means, when the final cell is reached, this variable
#(called depth) contains the shortest distance from the start to the end. The fail condition happens
#when there are no start or end squares, or when all possibilities have been traced from the start
#and have resulted in only dead ends without reaching the end point.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment