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