CSC111 visitMaze.py

--D. Thiebaut 16:13, 28 April 2010 (UTC)

---

Python Version 3, Graphics

This version uses Zelle's graphics.py library.

# graphicsVisitMaze.py
# D. Thiebaut
# Generates a maze and displays it in a graphics window.
# The maze is defined as a collection of lines of text.
# MazeText is the variable containing the raw definition.
# MazeText is split into lines and the list of lines is kept
# in the variable maze.
# Each line in mazeText contains # or . characters.  A #-character
# indicates a wall, while a . indicates an empty space.
# MazeText is cleaned up and all the dots are replaced by spaces.
# Then the maze is displayed in the graphic window.
# The program maintains the status of the visit in the variable
# maze.  A '.' will represent a breadcrumb, i.e. a place that has
# been visited and that is potentially on the path to the exit.  An
# 'i' character indicates a visited place that leads to an impass.
# The program starts by visiting location STARTi (line number)
# and STARTj (column number).
# 
import time
import os
from graphics import *


# Dimensions of the graphics window
WIDTH  = 800
HEIGHT = 600

mazeText = """
#########################
........................#
##############.##########
..#.#........#.#........#
#.#.#.########.########.#
#.#.#.................#.#
#.#.###.#####.#####.#...#
#...........#.#.#.#.#####
#.#########.#.#.#.#.....#
#.#.#.#.#.#.#.#.#######.#
#.#.........#.#.......#.#
#.###############.#####.#
#...............#.......#
#.###########.#########.#
#........#..............#
#########################
"""

mazeText1 = """
#########################
........................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#........................
#.......................#
#########################
"""

mazeText2 = """
#########################
........................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#######################.#
#.......................#
#.......................#
#.......................#
#.......................#
#.#######################
#.......................#
#.......................#
#........................
#.......................#
#########################
""" 

#
STARTi = 1   # line number
STARTj = 0   # column number

NOLINES = len( mazeText.strip().split("\n") )
NOCHARS = len( mazeText.strip().split("\n")[1] )
BLOCKWIDTH  = WIDTH // NOCHARS
BLOCKHEIGHT = HEIGHT / NOLINES

 
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 setBreakCrumb( i, j, win ):
    global BLOCKWIDTH
    global BLOCKHEIGHT
    radius = BLOCKWIDTH // 4
    brd = Circle( Point( (j+0.5)*BLOCKWIDTH, (i+0.5)*BLOCKHEIGHT ), radius )
    brd.setFill( "red" )
    brd.draw( win )
    
    # rest a tiny bit to slow down the program
    time.sleep( 0.1 )

def setImpass( i, j, win ):
    global BLOCKWIDTH
    global BLOCKHEIGHT
    radius = BLOCKWIDTH // 4
    blk = Rectangle( Point( j*BLOCKWIDTH, i*BLOCKHEIGHT ),
                  Point( (j+1)*BLOCKWIDTH, (i+1)*BLOCKHEIGHT ) )
    blk.setFill( "lightgrey" )
    blk.setOutline( "lightgrey" )
    blk.draw( win )
    
    # rest a tiny bit to slow down the program
    time.sleep( 0.1 )


def displayMaze( maze, win ):
    """ display the maze and wait for some amount of time"""
    global BLOCKWIDTH
    global BLOCKHEIGHT
    global NOLINES
    global NOCHARS
    
    blocks = []
    for i in range (NOLINES ):
       for j in range( NOCHARS ):
          if maze[i][j]=="#":
             r = Rectangle( Point( j*BLOCKWIDTH, i*BLOCKHEIGHT ),
                        Point( (j+1)*BLOCKWIDTH, (i+1)*BLOCKHEIGHT ) )
             r.setFill( "blue" )
             r.setOutline( "blue" )
             r.draw( win )
             blocks.append( r )
    
    return blocks

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 visitMaze( maze, i, j, win ):
    """recursive visit of the maze.  Returns True when it
    has found the exit, False otherwise"""
 
    setBreakCrumb( i, j, win )
    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, win ) == 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, win ) == 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, win ) == 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, win ) == 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                                   ---

    setImpass( i, j, win )
    setChar( maze, i, j, 'v' )
    #printMaze( maze )
    return False
 
 
def main():
    """gets the maze, visit and display it"""
    #maze = getMazeFromFile( 'largemaze.txt' )
    win = GraphWin("Maze", WIDTH, HEIGHT )
    
    maze = getMaze( mazeText )

    #printMaze( maze )
    blocks = displayMaze( maze, win )
    
    success = visitMaze( maze, STARTi, STARTj, win )
 
    #--- print the maze without the v-characters ---
    #printMazeNoVs( maze )
 
    if success:
        print( "A path was found!" )
    else:
        print( "No path to an exit found..." )

    win.getMouse()
    win.close()
    
main()

Python Verison 3

import time
import os

mazeText = """
#########################
........................#
##############.##########
#.#.#........#.#........#
#.#.#.########.########.#
#.#.#.................#.#
#.#.###.#####.#####.#...#
#...........#.#.#.#######
#.###########.#.#.#......
#.#.#.#.#.#.#.#.#######.#
#.#.........#.#.......#.#
#.#####################.#
#.......................#
#########################
"""

mazeText = """
#########################
........................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#.......................#
#........................
#.......................#
#########################
""" 
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" )
    os.system( "cls" )
    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()

Python Version 2

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