# For your first assignment this semester in PRG469, you are required
# to write a standalone Python program that locates and displays the
# path to a specific character in a maze!
# The Python code that randomly generates mazes of 20 or more rows
# by 35 or more columns has already been written and provided (see below).
# Download here: mazeGen.py
import random, sys
# usage: python mazeGen.py 30 15
# modified and augmented by: danny abesdris 02/07/2019
try :
(rows, cols) = (int(sys.argv[1]), int(sys.argv[2])) # accepts 2 command line arguments
rows -= 1
cols -= 1
except (ValueError, IndexError) :
print("2 command line arguments expected...")
print("Usage: python maze.py rows cols")
print(" minimum rows >= 10 minimum cols >= 20")
quit( )
try :
assert rows >= 9 and cols >= 19
except AssertionError :
print("Error: maze dimensions must be at least 20 x 10...")
print("Usage: python maze.py rows cols")
print(" minimum rows >= 10 minimum cols >= 20")
quit( )
(blank, roof, wall, corner) = ' -|+'
M = str(roof * int(cols / 2))
n = random.randint(1, (int(cols / 2)) * (int(rows / 2) - 1))
for i in range(int(rows / 2)) :
e = s = t = ''
N = wall
if i == 0 :
t = '@' # add entry marker '@' on first row first col only
# end if
for j in range(int(cols / 2)) :
if i and(random.randint(0, 1) or j == 0) :
s += N + blank
t += wall
N = wall
M = M[1 : ] + corner
else :
s += M[0] + roof
if i or j :
t += blank # add blank to compensate for '@' on first row only
# end if
N = corner
M = M[1 : ] + roof
# end if / else
n -= 1
t += ' #' [n == 0]
# end for
if cols & 1 :
s += s[-1]
t += blank
e = roof
# end if
print(s + N + 'n' + t + wall)
# end for
if rows & 1 :
print(t + wall)
# end if
print(roof.join(M) + e + roof + corner)
# sample 35 x 20 maze:
mazeString = '''
----------------------------------+
@ |
| --+ --------+ --------+ | | | --+
| | | | | | | |
| | +-------+ | | ------+-+-+ +-+ |
| | | | | | | |
| +-----+ | | | +-------+ | | | +-+
| | | | | | | | | |
| --+ | | +-+ | ----+ --+-+ +-+ | |
| | | | | | | | | | |
| | | | | | | | | | +-+ | +---+ | |
| | | | | | | | | | | | #| | |
| | +-+ +-+ +-+-+-+ --+ | | --+-+ |
| | | | | | | | | |
| +---+ | | | --+ | --+ | +-+ --+ |
| | | | | | | | | | | |
| | --+ +-+ +-+ +-+-+ +-+ | +---+ |
| | | | | | | | | |
| | | | | | | | | |
+-+---+---+---+-----+---+-+-----+-+
'''
# Directions: (North = right, East = down)
# +-- N
# |
# E
#
# Your program is required to do the following:
# 1. Use the code above to randomly generate a maze of at least
# 35 rows by 20 columns.
# 2. Traverse through the maze starting at coordinates (1, 0) until
# the '#' is located.
# 3. Once located, display the maze's dimensions, the coordinate and
# path to the '#'. The path will be displayed as a string of
# 'N' and 'E' characters.
# 4. Display the total number of searches performed and the percentage of
# blank tiles in the maze the searches represents (see examples below).
----------------------------------+
@ |
| ----------+ | | --+ | ----+ ----+
| | | | | | | |
| | | ------+ +-+ | +-+ | --+ ----+
| | | | | | | | | |
| +-+---+ | +-+ | | | | +-+ +-+ | |
| | | | | | | | | | | |
| ------+ | --+ +-+ +-+---+ --+ +-+
| | | | | | | |
| | | --+-+-+ | | +-+ --+ | --+ --+
| | | | | |# | | | | |
| | +-+ --+ | +-+---+---+-+---+ | |
| | | | | | | |
| +-+ | --+-+ ------+ | --+ --+-+-+
| | | | | | | |
| | +-+---+ | --+ | | | --+ --+ --+
| | | | | | | | | | |
| | | | | | | | | | |
+-+-------+-+---+-+-+-+---+---+---+
maze dimensions: (30x55)
found # at coords: (11, 17) path: NNNNNNNNNNNNNEEEENNEEEENNEE
total searches: (216/327) 66.0550% of maze
------------------------------------------------------+
@ |
| --+ | | ----+ | | --+ | | | --+ | --------+ ------+ |
| | | | | | | | | | | | | | | |
| --+ +-+---+ | | | --+-+ +-+ | | | ----+ | | ------+-+
| | | | | | # | | | | | | | | |
| | | --+ --+ +-+ | ----+---+ | +-+ ----+-+-+-+ --+ | |
| | | | | | | | | | | | | |
| +-+-+ | --+ | | +---------+ +---+-----+ --+ | --+ +-+
| | | | | | | | | | | |
| | | +-+---+-+-+ ----+ | | | | ------+ +-+ +-+ --+-+ |
| | | | | | | | | | | | | |
| | +-+ | | --+ | --+ | | | +-+-+ | | | | +-+ | --+ | |
| | | | | | | | | | | | | | | | | | | | |
| +---+-+ | | | +-+ | | | | --+ | +-+ +-+ | | +-+ +-+ |
| | | | | | | | | | | | | | | | | | |
| --+ | +-+ | +-+ +-+-+ | +---+ | | +-+ +-+ +-+ | | | |
| | | | | | | | | | | | | | | | | |
| --+ +-+ | | | | | --+-+ ----+-+-+ --+ --+---+ +-+ | |
| | | | | | | | | | | | | | |
| | | | +-+ +-+ | | ----+-+ | | --+-+ | ------+ | | | |
| | | | | | | | | | | | | | | | | |
| +-+ +---+ | +-+-+ | | | | | +-+ --+-+-+ | --+-+ +-+ |
| | | | | | | | | | | | | | | |
| --+ | --+ +---+ +-+ +-+ +-+ | | | --+ | | | | | | +-+
| | | | | | | | | | | | | | | | | | |
| | | | | +-----+---+-+ | --+ | | +-+ +-+ | | | | +---+
| | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | |
+-+-+-+-+-------------+-+---+-+-+---+---+-+-+-+-+-----+
maze dimensions: (30x55)
found # at coords: (5, 21) path: NNNNNNNNNNNNNNNNNNNEEEENN
total searches: (459/791) 58.0278% of maze
This assignment will be divided into components and weighted as follows:
PART A: Using the code (above) create a user-defined Python function named 'mazeGen' that accepts 2 parameters (rows and columns) (replacing the command line arguments) and generates a random maze. However, instead of being displayed on the screen, this function stores the maze in a string and returns it once complete.
PART B: Your assignment MUST also contain a user-defined function named 'createMazeMatrix' that accepts 3 parameters:
1. the maze string returned from the 'mazeGen' function,
2. the # rows the maze contains, and
3. the # columns the maze contains.
This function uses the maze string to create a 2-dimensional array containing every character in the maze. The first character stored at (0,0) and the last at (rows-1, cols-1). This function returns the 2-dimensional array.
PART C: Your assignment also contains a user-defined function named 'traverseMaze' that accepts the 2-dimensional array returned from the 'createMazeMatrix' function as its only parameter. This function searches through the maze starting at coordinates (1, 0) (the '@' chatracter) until it finds the '#' symbol. The '@' symbol will ALWAYS at coordinates (1, 0) regardless of maze size and there will ALWAYS be a '#' within the maze. Traversing through the maze can be accomplished by moving entirely in 2 directions only (right (North) and down (east)).
NOTE: The maze generating algorithm was designed to allow traversals in 2 directions only without the need to move up or to the left (more detail in the algorithm section below) and without the need for using recursion.
The '#' symbol will always be accessible and there will only ever be 1 exact path that leads to it starting from the '@' symbol.
Traversals through the maze may only be made along blank spaces and moving to a non-blank character such as '|', '+', '-', or '@' is NOT permitted.
NOTE: Solutions which only complete a partial traversal (without finding the '#') may still qualify for partial marks for PART C.
ALGORITHM: Moving through the 2D maze simply requires either increasing variables that track row or column number repeatedly in a loop (1 iteration at a time).
Starting at the '@' symbol (1, 0), your first move can only be to move right (North) to (1, 1). From there and throughout the maze there may coordinates that allow movement in only 1 direction (either North or East) or that allow movement in 2 directions (North AND East). If you encounter a coordinate that allows movement in 2 directions, store the coordinate that allows you to move North (right) along with an integer that keeps track of the path length to that coordinate, and append it to a list (that simulates a LIFO stack). Given that you will be storing both a coordinate AND an additional integer, the data structure used could be: coord = [[0, 0], 0].
A series of 'coord' (2D arrays) can then be placed in a list (stack) with the append( ) method.
For example:
stack = [ ]
coord = [[0, 0], 0]
stack.append(coord)
However, when working with lists, you must always make sure that a copy of the list is made to avoid potentially modifying an existing list. Therefore, the proper syntax to store a COPY of a list is:
stack.append(copy.deepcopy(coord))
# which will require importing the copy module (i.e. import copy).
So, when a decision is required as to which direction to move (North or East), store the North coordinate and ALWAYS choose east over North. As you increase the row variable (because moving East means moving down), repeat the same procedure for every coordinate that allows moving in 2 directions. For coordinates that only allow movement in 1 direction, simply move in that direction (East increases row by 1) and (North increase column by 1). For each move you make, add either an 'N' or an 'E' to the end of a path string and make sure to increase the value of the path length integer being stored in last coordinate stored on the stack. Next, continue moving either until you find the '#' or until you reach a dead end.
If you encounter a dead end, retrieve the last coordinate you added to the stack variable and set your row and column variables to that coordinate. Also, use the path length integer to cut away exactly that number of characters from your 'path' string (see example below): see image.
Lastly, in order to make sure that you do not visit a square that was previously visited, consider using an entire deep copy of the 2D maze as a 'mask' and mark each blank square that you visit with a ANY non-blank character so that it can be considered inaccessible. The mask will be required to ensure that your traversal does not get trapped in a portion of the maze that contains 2 rows on blank characters!
NOTE: *** Refer to in-class demonstration for a step by step sample run through the maze.***
Your solution may use ANY Python language elements and constructs that you have learned to date.