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
  • Access the individual elements of rooms: rooms[row][col]

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.
• getUnvisitedNeighbors(self, room): - Returns a list of unvisited neighbors of the room parameter
• countUnvisited(self):
  1. Using 2 nested loops, traverse every room in the matrix and check if its visited attribute is False.
  2. Count all the unvisited Rooms and return the count
• generate(self):

1. Create an empty list named stack
2. Make a currentRoom variable reference rooms[0][0] and mark it as visited
3. While there are unvisited rooms (Hint: Use the countUnvisited() method)
   1. If the currentRoom has any neighbours which have not been visited (Hint: Use the getUnvisitedNeighbors() method)
      1. Choose randomly one of the unvisited neighbours
      2. Push the currentRoom on to the stack
      3. Remove the wall between the current cell and the chosen cell (Hint: Use the connectRooms() method)
      4. Make the randomly chosen room as the current cell and mark it as visited
   2. Else if stack is not empty
      1. Pop a room from the stack and make it the current cell

Testing

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

from Maze import *

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

Advanced Challenges

• Add a writeToFile(filename) method that outputs the maze to a file using the input function parameter
• Add a load(filename) method that loads a maze from the file name function parameter