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()