CSC111 visitMaze.py
--D. Thiebaut 16:13, 28 April 2010 (UTC)
# visitmaze.py
# D. Thiebaut
# this program creates a 2-dimensional list of characters
# representing a maze, and starts in the top left corner,
# Row 1, Column 0, and explores the maze recursively in
# an attempt to find an exit.
# "bread crumbs" in the form of dots '.' are left behind
# to create a path to the exit, while 'v' characters are left
# in cells that have been visited, but have been discovered
# not to lead to an exit.
#
# The format of the maze is a collection of lines, all with the
# same length. A #-sign represents a wall, while a dot '.'
# represents an empty space. The dots are replaced by space
# characters before the program starts visiting the maze.
#
# The program can read either a maze defined in the program
# itself, in the variable called mazeText, or can read a maze
# from a text file.
#
# When refering to a location in the maze, we use [i][j] as
# indexes, i representing the row, j the column.
import time
mazeText = """
####.####################
........................#
##############.##########
#.#.#........#.#........#
#.#.#.########.########.#
#.#.#.................#.#
#.#.###.#####.#######...#
#.#.........#.#.#.#.#####
#.###########.#.#.#.....#
#.#.#.#.#.#.#.#.#######.#
#.#.........#.#.......#.#
#.###########.#########.#
#.......................#
#########################
"""
import os
STARTi = 1
STARTj = 0
def getMazeFromFile( fileName ):
"""reads the definition of the maze from a file"""
try:
lines = open( fileName, 'r' ).read()
except:
print "I/O Error: could not open", fileName
return None
return getMaze( lines )
def getMaze( mazeText ):
"""take the string representing the maze and
break it down into an array of lines"""
maze=[]
for i, line in enumerate( mazeText.split( '\n' ) ):
line = line.strip()
print "%d [%s]" % (i, line )
if len( line ) < 2:
continue
line = line.replace( '.', ' ' )
maze.append( line )
return maze
def setChar( maze, i, j, char ):
"""puts the character char at position i,
j in the maze"""
line = maze[i]
letters = []
for letter in line:
letters.append( letter )
letters[j] = char
maze[i] = ''.join( letters )
def printMaze( maze ):
""" display the maze and wait for some amount of time"""
os.system( "clear" )
for line in maze:
print line
#time.sleep( 0.1 )
def printMazeNoVs( maze ):
""" remove the V-characters before printing the maze"""
os.system( "clear" )
for line in maze:
print line.replace( 'v', ' ' )
def visitMaze( maze, i, j ):
"""recursive visit of the maze. Returns True when it
has found the exit, False otherwise"""
setChar( maze, i, j, '.' )
printMaze( maze )
if ( i != STARTi or j != STARTj ) \
and ( (i==0 or i==len( maze )-1 ) or (j==0 or j==len( maze[0] )-1 ) ):
return True
#--- try the four directions around where we are ---
#--- to the right? ---
if j+1< len( maze[0] ) and maze[i][j+1]==' ':
if visitMaze( maze, i, j+1 ) == True:
return True # found an exit by going right!
#--- down? ---
if i+1< len( maze ) and maze[i+1][j]==' ':
if visitMaze( maze, i+1, j ) == True:
return True # found an exit by going down!
#--- up? ---
if i-1>=0 and maze[i-1][j]==' ':
if visitMaze( maze, i-1, j ) == True:
return True # found an exit by going up!
#--- to the left? ---
if j-1>=0 and maze[i][j-1]==' ':
if visitMaze( maze, i, j-1) == True:
return True # found an exit by going left!
#--- if we're here, none of the 4 directions was successful ---
#--- in bringing us to an exit, we have to mark our cell with--
#--- a v, and return false to our caller, indicating that we---
#--- couldn't find a path ---
setChar( maze, i, j, 'v' )
printMaze( maze )
return False
def main():
"""gets the maze, visit and display it"""
#maze = getMazeFromFile( 'largemaze.txt' )
maze = getMaze( mazeText )
printMaze( maze )
success = visitMaze( maze, STARTi, STARTj )
#--- print the maze without the v-characters ---
printMazeNoVs( maze )
if success:
print "A path was found!"
else:
print "No path to an exit found..."
main()
