Assignment 9: Spampede!
Due Monday, November 8 by 11:59 PM

Please read the following carefully. There is a lot here!  

1. All parts of the assignment are individual or pair.  If you work with a partner, you must work with the same partner on all three parts.
   
2. You will be submitting several files for this assignment. Please submit every file that you used for your assignment. We will look for SpamMaze.py (Parts 1 and 2), and Spampede.py (Part 3). If you define any other files as part of your project, please submit those too as support files.


3. This week, we ask that you also submit a file that is typically submitted in any large software project: A text file called README. We have provided a basic README file below on this page. You should edit this file and submit it. The README file constitutes part of your score on this assignment.

This assignment has three parts, which ultimately build to the Spampede game! In Part 1, you will extend the capabilities of your maze solver from HW8 (though you may use our solution code for that assignment if you prefer). In Part 2, you will use the results of Part 1 to build some of the primary functionality of the Spampede game. In Part 3, you will use Part 2 in a graphical application that you (and your friends) can play!

What is the final product?

• You might want to try out the basic game (with required functionality, but no extras), which is available here:  SpampedeCompiled.zip.  Unzip this file and then doubleclick the SpampedeSolution.pyc file. 


• If you want to see the game with some bells and whistles, you can check out  http://www.cs.hmc.edu/~dodds/Applets/SpampedePlus/Spampede.html.  This applet demonstrates some additional functionality, but more is certainly possible (see the extra credit options, below).

Provided Files and Setup

• SpamMaze.py   The starting point for parts 1 and 2
• Spampede.py    The starting point for part 3 
• README.txt          The starter readme file, as described above.  

Notes about Spampede.py

Overview

• Maze: Responsible for storing the walls and spam in the maze, and for searching for spam and returning the path to the nearest spam can.  You will extend the Maze class to incorporate more of the game's functionality.
• SpamMaze: A subclass of Maze that does everything a Maze does AND keeps track of the spam that populates the board and location of the centepede.  This is the class that has all of the functionality for playing the game including moving the pede, populating the board with spam, determining whether the pede has hit a wall, etc.
• Spampede: A class that controls the functionality of the game application.  This class is responsible for displaying the board to the user, handling the user's key strokes, and controlling the timesteps that move the pede forward.

Part 1:     Improving Maze [20 points], submit in a file named SpamMaze.py (with Part 2)

The first part of this assignment is to improve the Maze class in which you wrote breadth-first search for assignment 8. In particular, you may start with either your own Maze.py file from last week or you may use our solution to that problem provided with the starter files. 

The first thing to do is modify the constructor so that it optionally takes 0 arguments.  This is already in the solution file, or you can copy it from here:

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)

A more flexible breadth-first-search

The final method to write in the Maze class is

multiBFS(start, destination)

What should multiBFS do?

This method should have the following behavior:

• Printing, but not changing, the Maze:    That is, when multiBFS finds a path from start to destination, it should mark it with the 'o' characters, as before, and then print out the Maze if a DEBUG flag is set. Afterwards -- before returning -- it should remove the 'o' characters and then return the next MazeCell on the path to the destination. If the Maze was not solvable, it should print that message and still return a valid MazeCell neighboring start. (See next point...)
• Returning the next MazeCell on the path:    This method should return the MazeCell that is adjacent to the start along the path that it found to the destination. If there was no path from start to any cell containing destination, then the multiBFS method should return any empty MazeCell that neighbors start to the N, E, W, or S. If there are no empty neighbors, then multiBFS should return an arbitrary MazeCell that neighbors start (and the centipede will crash!)
• REALLY not changing the Maze!    Regardless of whether a path is found or not, this method should reset all visited flags and parent data members of every MazeCell in the Maze. Unlike the previous assignment, where a Maze was solved only once, here your code will be solving a Maze repeatedly, so multiBFS must be really sure to leave the maze as it was before running breadth-first search. There is an empty method private void clearFlags() to write for just this purpose.

Testing your code

Be sure to test your code thoroughly before heading to part 2 of this assignment... there is a test in main for this purpose, and you should try editing the mazeStrings in order to make sure it works in a variety of conditions!  You do not need to submit any testing this week, though.

Part 2:     Writing SpamMaze [40 points].  Submit in the same SpamMaze.py file as Part 1

The overview

In this part of the assignment you will create a derived class named SpamMaze that handles the model for the game, which is part 3. A derived class is simply an extension of the data and capabilities (methods) available in the base class. Thus, by starting the code as in the provided SpamMaze file:

class SpamMaze(Maze)
   ''' The SpamMaze class that you will write '''

The data

Because a SpamMaze object represents the model for the Spampede applet, it needs to keep track of (1) the maze, (2), the centipede, and (3) the spam in the environment. Remember that (1) is already taken care of because your SpamMaze is a derived class of Maze. To keep track of (2) and (3), you should use deques of MazeCells. In particular, you will use two data members:

  # The data members representing the spam and the centipede
  self.spamCells = collections.deque()
  self.pedeCells = collections.deque()

The methods

You should, in essence, implement all of the functionality, but not the graphics front end, for the Spampede game inside SpamMaze. At a minimum, you should implement the following methods. You may choose to add more methods - either private helper methods (to help these public methods) - or other public methods for your game to use.

• __init__(self, filename=None)    the constructor. This should call the base class's zero-argument constructor (to create the Maze, this is already done) and then it should do additional initializion of the data members that are part of only the SpamMaze class (see above, this is for you to do). Note that the initial state of the centipede is that its head is at maze[1][2] and that it has only one body segment, at location maze[1][1]. Thus, the centipede is initially facing east. It's initial direction is east as well. This may be set here in the constructor or elsewhere in the game - that's a design choice that is up to you.


• addSpam(self)    adds one can of spam to the environment. You can choose the method used to add spam but the following properties are required:
  • An inserted can of spam may not be placed anywhere on the current location of the centipede's body nor on a wall or existing can of spam.
  • The reference to the new can of spam must be inserted in the spamCells deque.
  You may wish to use random numbers to generate the locations of new spam cans. To do so, include the line import random at the top of the file. Then, you can use the random module.  Remeber that dir(random) will tell you what functions are available (after you have imported the random module).  We recommend you check out random.choice (use help for more info).  
  
  
• removeSpam(self)    removes one can of spam from the environment when it's time for the spam to disappear. Notice that this function will simply be called periodically in order to make the game more interesting. It will not be called when the centipede consumes a can of spam. That event will be handled in the advancePede function described below. You can choose the method used to remove spam, but the following property is required: When this function is called, a can of spam is eliminated from the spamCells deque. This can be done at random or (perhaps more reasonably) the oldest spam can in the list is removed.
  
  
• advancePede(self, direction)    this is the fundamental update method for the entire game! This is where the "smarts" go. In particular, a character indicating the direction to move is passed in as a character. The characters 'N', 'S', 'E', 'W', 'A' should represent the directions north, south, east, west, and automatic ("automatic" will be described below). Be sure to define good names for these symbols to avoid magic values in your code! For example, you might have a value such as NORTH = 'N'; So, here's what this method does:
  • Based on the direction that is passed in, the pedeCells deque is updated to have the centipede move in that direction. That is, the head advances and the tail retracts in the given direction.
    
  • If the centipede's head moves to a MazeCell that contains a wall or another part of the centipede, the centipede dies, and the centipede should be reset to its initial state. This function need not necessarily do the resetting. Notice that this function returns an integer value (or you can change it to a char if you prefer). That value may be used to help with the resetting elsewhere in the program. This is described next...
    
  • So what exacty is the return value? It can be very handy for this function to return an integer or a character informing us (more likely the function that called this function) what happened. For example, if there was a collision with a wall, the calling function might appreciate knowing that so that. You can come back to this later - when doing part 3 - to decide what, if anything, you would like the function to return.
    
  • If the centipede's head lands on a can of spam, the centipede grows by one MazeCell. That is, when the centipede next moves, its head advances one square, but its tail does not retract. Importantly, the can of spam that was just consumed must be removed from the spamCells deque. What command will be used to do this? Check out remove command in the deque class (use help of course!).
    
  • Finally, the automatic direction. If this function is passed in the value 'A' then we are in AI mode. That is, the spampede should navigate by itself, also heading for the nearest can of spam. To do this, it will call the multiBFS method that you wrote in Part 1. multiBFS will return a reference to the MazeCell that the spampede should move to. The spampede will then be updated to move to that cell.
  
  
• reversePede(self)    this method reverses the centipede so that it has the opposite orientation and moves in the appropriate "opposite direction". Note that if the centipede was previously moving west, it is not necessarily going to move east upon reversal. Instead, the new direction is the opposite of the direction of the tail of the centipede. That is, if the last two cells of the centipede's body indicate that the centipede is moving north, then the new direction for the reversed centipede will be south. In addition to modifying the pedeCells linked list to perform the reversal, this function returns the new direction.

Testing!!

As with Maze, be sure to test your SpamMaze thoroughly in main before worrying about the graphical front-end of the applet in part 3. Below is a main method, which you should feel free to adapt to your implementation and add to the main function provided. Remember that you do not need to write __repr__ -- the version that's already in Maze will work perfectly well!  Again, you do not need to submit this testing this week.

  def main(args=None):
    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)

    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

Part 3:     Putting it all together: Spampede.py [40 points].  Submit in a file named Spampede.py

The overview

The Spampede program gives a user control over a spam-seeking centipede. Key presses from the keyboard change the direction of the centipede's movement in order to intersect snacks (spam) that appear at random places on the screen. For each snack consumed, the centipede grows by one segment (a segment is simply one MazeCell). Variations are welcome (see the extra credit section below)! 

Writing the application

• Be sure to create, in __init__ and/or in _reset, a SpamMaze and make sure it is in a suitable starting configuration. There is already a data member named self.theMaze to hold the created object. This may already be done for you in the code, if you are using the zero-argument constructor for SpamMaze.


• Draw the contents of the SpamMaze within the _drawEnvironment method already provided. This will require writing a nested loop to create the 2d array of rows x columns pixel squares that represent the maze. This drawEnvironment method will be called every so often by the _cycle method to show the latest state of the maze. You should use different colors of your choice representing walls, empty space, the head of the centipede and the body of the centipede. You will want to use the create_rectangle command on the canvas to accomplish this.  Take a look at the starter file provided for an example.


• Update the spam within the SpamMaze named self.theMaze. Within updateSpam you can add (and/or remove) spam every so often -- though doing so every cycle will probably be too fast!. You can also add spam as needed (e.g., when one is eaten). But, you should make sure to have at least one spam on the board at all times.


• Keep track of the centipede (i.e., the "spampede"). The _updatePede method is provided as a placeholder for where you would do this. You might want a data member that keeps track of the centipede's current direction so that advancePede can be called appropriately.  In this case, key presses would simply change this internally-stored self.dir.
  
  Keep in mind that no MazeCells are moving as the centipede crawls through the maze! Rather, it's the data member named pedeCells of type deque that's snaking its way through the 2d array of MazeCellss by changing the cells to which it refers.


• Handle key presses. You will see a method that prints out certain characters when the user presses them. You will use these character presses to modify the pede's direction.  When the user presses the following keys, the centipede should change direction as indicated:
  • r : reverse, switching its head's position to its tail
  • i : turn north
  • j : turn west
  • l : turn east
  • k : turn south
  • a : go into autonomous, spam-seeking mode ("AI")
  If the centipede is already heading in the direction that the user chooses, nothing changes. If the user changes the centipede's direction so that it is moving back on itself (from South to North, say, or West to East), you may reverse direction, ignore the command, or "terminate" the centipede.

As you write your code, please compile and rerun the applet often to make sure you're on the right path. 

A Reminder On What to Submit

I want more!

If you haven't had enough of the Spampede.py file at the end of this assignment, there are a couple of specific items and an open-ended invitation to improve on the applet for optional bonus credit. (Up to 25 points in total.)

If you add optional features, please explain them carefully in the README file.

• Enemy Pedes!: Allow there to be one or more "enemy" pedes that use the multiBFS and/or other heuristics to play against your pede. (This is worth extra bonus points since it is a bit more challenging.)


• Speed up: You might want to have the rate at which the centipede is moving to increase as the game progresses.


• Scoring: You might want to have a system of scoring with a running total displayed as a label or text field or simply drawn to the applet panel.


• Lives: Rather than resetting or stopping the game after a single Spampede crash, keep a text field (or label) with the number of lives remaining and decrement it after each crash. When there are no lives left, stop the game (though you might want to consider a "start over" button.)
  


• Levels: Rather than maintaining a single, static maze, you may want to have the centipede advance to different mazes after consuming enough spam.
  


• Wrapping: Allow the centipede to wrap around the game board -- either in an unlimited fashion or through small tunnels in the walls. Or you might consider a "hyperspace" square, that "sends" cells to another spot on the board.


• General improvements: Feel free to add additional features you think would enhance the Spampede applet: different kinds of spam, sounds, images, other graphical widgets like pull-down menus or text boxes, etc.
  

.