Python - Maze Generation Assignment

Objectives

• You will create a maze generation program
• You will create Python classes that represent a MazeRoom and a Maze
• You will implement a depth-first search maze algorithm using a stack as a backtracker

Resources

• Media:Stacks.ppt
• Stack - CS Animated
• Depth-first Search
• Recursive backtracker
• Maze Designer

MazeRoom class

• Create a file named MazeRoom.py for the MazeRoom class

MazeRoom Attributes

• MazeRoom should have the following attributes with default values:
  • roomToNorth - references the a doorway to the north. A None value means that there is wall
    • Default: None
  • roomToSouth - references the a doorway to the south. A None value means that there is wall
    • Default: None
  • roomToEast - references the a doorway to the east. A None value means that there is wall
    • Default: None
  • roomToWest - references the a doorway to the west. A None value means that there is wall
    • Default: None
  • row - the row number for the Room
    • Default: -1
  • col - the column number for the Room
    • Default: -1
  • visited - a Boolean that keeps track of whether or not the room has been visited in the maze algorithm
    • Default: False

MazeRoom Methods

• MazeRoom should have the following method:
  • def __init__(self, row = -1, col = -1) - set the internal row and col attributes to be the same as the input parameters

Maze class

• Download the partially completed Maze.py for the Maze class

Maze Attributes

• numRows - an int that stores the total number of rows in your maze
• numCols - an int that stores the total number of cols in your maze
• rooms - a 2-dimensional list of Rooms

Maze Methods

• __init__(self, height=10, width=10):'
  1. initializes the dimensions of the Maze and creates the 2-dimensional matrix of MazeRooms
• connectRooms(self, r1, r2):
  1. Takes 2 MazeRooms as input parameters.
  2. Compares their row and column numbers to figure out their adjacency (relative locations)
  3. Sets the roomToNorth, roomToSouth, roomToEast, or roomToWest variables accordingly to connect the rooms together.
• isValidRoom(self, row, col):
  1. Returns True if the row and col numbers are valid and all of the following are True:
     • row is non-negative
     • col is non-negative
     • row is less than numRows
     • col is less than numCols
  2. Returns False otherwise

• getUnvisitedNeighbors(self, room): - Returns a list of unvisited neighbors of the room parameter
  1. Create an empty list named neighbors

• countUnvisited(self):

• generate(self):
• print(self): - prints the maze to the screen using characters

Testing

• Create a new file named MazeTest.py and execute the following code:

from Maze import *

maze = Maze()
maze.generate()
maze.print()