# File: SpamMaze.py # CS 42 HW9, problems 1 and 2 # Author: # Date: # Time Spent: import sys # for getting command line arguments import collections # for the deque class import random # For adding Spam mazeStrings = ["**************************************************", "*PS D *", "* *", "* *", "* *", "* *", "* *", "* *", "* *", "* *", "* *", "* *", "* ** *", "* ** *", "* ** *", "* ** *", "* *", "* *", "* *", "* *", "* *", "* *", "* *", "* *", "* *", "* D *", "* *", "* *", "* *", "**************************************************"] # MazeCell - a class supporting Maze # # The following convention is used in mazes: # Walls are represented by '*' # Empty area is represented by the blank symbol ' ' # Starting point is represented by 'S' # Destination (SPAM!) is represented by 'D' class MazeCell(object): ''' A class to support Maze containing one cell of the maze ''' def __init__(self, row, col, contents): self.row = row self.col = col self.contents = contents self.visited = False self.parent = None def __repr__(self): return "[" + str(self.row) + "," + str(self.col) + "," + self.contents + "]" def isWall(self): return self.contents == Maze.WALL class Maze(object): # USE THESE RATHER THAN MAGIC VALUES! WALL = '*' EMPTY = ' ' START = 'S' DESTINATION = 'D' FOOTSTEP = 'o' def __init__(self, filename=None): ''' Initialize a new Maze from a File or from the string above ''' if filename is None: self.rows = len(mazeStrings) self.columns = len(mazeStrings[0]) self.maze = [] for r in range(self.rows): self.maze.append([]) for c in range(self.columns): self.maze[r].append(MazeCell(r,c,mazeStrings[r][c])) else: self.maze = None self.rows = 0 self.columns = 0 self.loadMazeFromFile(filename) def findMazeCell(self, charToFind): ''' Takes a char token (either 'S' or 'D') and returns the MazeCell containing the location of the token in the maze''' for r in range(self.rows): for c in range(self.columns): if self.maze[r][c].contents == charToFind: return self.maze[r][c] def multiBFS(self, start, dest): ''' Breadth-first search from start to ANY cell containing the character in destination, which will typically be a 'D', representing spam. Input: The start cell and destination character Output: a Maze Cell next to the start cell next on the path. If there is no path, return a (empty if possible) cell next to start. If DEBUG is set to true, it will print the path. ''' return None def BFS(self, start, dest): ''' BFS method takes the start MazeCell and the destination char as input and performs the breadth-first search algorithm in the maze beginning at location start. When the method ends, each reachable empty (' ') MazeCell should have its "parent" data member set to the MazeCell from which it was visited. Returns the destination cell.''' toExplore = collections.deque() toExplore.append(start) start.visited = True foundDest = False toReturn = None while len(toExplore) > 0: current = toExplore.popleft() if current.contents == dest: foundDest = True destCell = current break # now enqueue each neighbor if it's not yet visited neighbors = self.getNeighborsOf( current ) for n in neighbors: if not n.visited and (n.contents == self.EMPTY or n.contents == self.DESTINATION): n.visited = True n.parent = current toExplore.append(n) # Finally put the footsteps on the path, if there was one if foundDest: pathcell = destCell pathcell = pathcell.parent while not (pathcell == None) and not (pathcell == start): pathcell.contents = self.FOOTSTEP pathcell = pathcell.parent else: print "Maze not solvable!" def getNeighborsOf( self, cell ): ''' get the neighbors of a maze cell and returns them as a list ''' ret = [] if cell.row-1 >= 0: ret.append(self.maze[cell.row-1][cell.col]) if cell.col+1 < self.columns: ret.append(self.maze[cell.row][cell.col+1]) if cell.row+1 < self.rows: ret.append(self.maze[cell.row+1][cell.col]) if cell.col-1 >= 0: ret.append(self.maze[cell.row][cell.col-1]) return ret def __repr__(self): ''' Return a string representation of the maze, for printing''' result = "\n"; for r in range(self.rows): for c in range(self.columns): result += self.maze[r][c].contents result += "\n" result += "\n" return result ## PROVIDED METHOD. NO NEED TO ALTER (unless you want to change ## the file format or something to support multiple levels or ## other extensions...) def loadMazeFromFile(self, filename): ''' loadMaze method takes the maze and a String with the name of the 10 by 10 maze file to open and loads that file into the maze array.''' try: # in case the file isn't there or misnamed f = open(filename, 'r') fileline = f.readline() # The first line should have two integers... dimensions = fileline.strip().split() #split on whitespace self.rows = int(dimensions[0]) self.columns = int(dimensions[1]) # create the maze cell references ... but not the MazeCells themselves self.maze = [] for r in range(self.rows): fileline = f.readline() self.maze.append([]) for c in range(self.columns): ch = fileline[c] self.maze[r].append(MazeCell(r,c,ch)) except IOError as (errno, strerror): print "I/O error({0}): {1}".format(errno, strerror) except ValueError: print "Could not convert data to an integer." except: print "Unexpected error:", sys.exc_info()[0] raise else: f.close() ### The SpamMaze class class SpamMaze(Maze): ''' The SpamMaze class that you will write. This class provides all of the functionality of the Spampede game. ''' SPAM = 'D' PEDEHEAD = 'S' PEDEBODY = 'P' # Define more constants here def __init__(self, filename=None): ''' Initialize a SpamMaze. Currently a SpamMaze is just a Maze, but you will change this. ''' self.filename = filename # hang on to the filename in case we need it later super(SpamMaze, self).__init__(self.filename) # Call the superclass constructor # Add more code here def main(args=None): ''' main function, for testing. ''' SM = None if args is None or len(args) != 2: SM = SpamMaze() else: #The filename comes from the command line filename = args[1] SM = SpamMaze(filename) # this creates the maze start = SM.findMazeCell('S') # get the Source print "Start at", start # Test multiBFS print SM.multiBFS(start, 'D') # Make sure the maze didn't change print "M is\n" + str(SM) #some testing code provided below '''for i in range(10): SM.addSpam() print "M is\n" + str(SM) for i in range(5): SM.removeSpam() print "M is\n" + str(SM) # Now test the SpamMaze functionality nextSpot = SM.multiBFS(SM.pedeCells[0], SpamMaze.SPAM) print "nextSpot is\n", nextSpot print "SM is\n", SM SM.advancePede(SpamMaze.EAST) print "SM is\n", SM print "pedeCells is ", SM.pedeCells SM.advancePede(SpamMaze.EAST) print "SM is\n", SM print "pedeCells is ", SM.pedeCells SM.advancePede(SpamMaze.EAST) print "SM is\n", SM print "pedeCells is ", SM.pedeCells SM.advancePede(SpamMaze.SOUTH) print "SM is\n", SM print "pedeCells is ", SM.pedeCells SM.advancePede(SpamMaze.SOUTH) print "SM is\n", SM print "pedeCells is ", SM.pedeCells direction = SM.reversePede() print "SM is\n", SM print "direction is", direction ''' if __name__ == "__main__" : main(sys.argv)