Difference between revisions of "Python - Maze Generation Assignment"
From WLCS
(16 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | = | + | = Objectives = |
* You will create a maze generation program | * You will create a maze generation program | ||
* You will create Python classes that represent a MazeRoom and a Maze | * 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 | * You will implement a depth-first search maze algorithm using a stack as a backtracker | ||
− | + | = Resources = | |
* [[Media:Stacks.ppt]] | * [[Media:Stacks.ppt]] | ||
* [http://www.csanimated.com/animation.php?t=Stack Stack - CS Animated] | * [http://www.csanimated.com/animation.php?t=Stack Stack - CS Animated] | ||
Line 11: | Line 11: | ||
* [http://gwydir.demon.co.uk/jo/maze/makemaze/index.htm Maze Designer] | * [http://gwydir.demon.co.uk/jo/maze/makemaze/index.htm Maze Designer] | ||
− | + | = MazeRoom class = | |
* Create a file named '''MazeRoom.py''' for the MazeRoom class | * Create a file named '''MazeRoom.py''' for the MazeRoom class | ||
− | == | + | == MazeRoom Attributes == |
* MazeRoom should have the following attributes with default values: | * 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 | ** roomToNorth - references the a doorway to the north. A None value means that there is wall | ||
Line 29: | Line 29: | ||
** visited - a Boolean that keeps track of whether or not the room has been visited in the maze algorithm | ** visited - a Boolean that keeps track of whether or not the room has been visited in the maze algorithm | ||
*** Default: False | *** Default: False | ||
− | == | + | == MazeRoom Methods == |
* MazeRoom should have the following method: | * 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 | ** '''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]''' | ||
− | == Testing == | + | == Maze Methods == |
+ | * '''__init__(self, height=10, width=10):'''' | ||
+ | *# initializes the dimensions of the Maze and creates the 2-dimensional matrix of MazeRooms | ||
+ | * '''connectRooms(self, r1, r2):''' | ||
+ | *# Takes 2 MazeRooms as input parameters. | ||
+ | *# Compares their row and column numbers to figure out their adjacency (relative locations) | ||
+ | *# 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):''' | ||
+ | *# Using 2 nested loops, traverse every room in the matrix and check if its visited attribute is False. | ||
+ | *# Count all the unvisited Rooms and return the count | ||
+ | * '''generate(self):''' | ||
+ | # Create an empty list named '''stack''' | ||
+ | # Make a '''currentRoom''' variable reference '''rooms[0][0]''' and mark it as visited | ||
+ | # While there are unvisited rooms (Hint: Use the countUnvisited() method) | ||
+ | ## If the '''currentRoom''' has any neighbours which have not been visited (Hint: Use the getUnvisitedNeighbors() method) | ||
+ | ### Choose randomly one of the unvisited neighbours | ||
+ | ### Push the '''currentRoom''' on to the stack | ||
+ | ### Remove the wall between the current cell and the chosen cell (Hint: Use the connectRooms() method) | ||
+ | ### Make the randomly chosen room as the current cell and mark it as visited | ||
+ | ## Else if stack is not empty | ||
+ | ### Pop a room from the stack and make it the current cell | ||
+ | <!-- | ||
+ | ## Else | ||
+ | ### Pick a random unvisited neighbor, make it the current cell and mark it as visit | ||
+ | * '''print(self):''' - prints the maze to the screen using characters | ||
+ | --> | ||
+ | = Testing = | ||
+ | * Create a new file named '''MazeTest.py''' and execute the following code: | ||
+ | <syntaxhighlight lang="Python"> | ||
+ | from Maze import * | ||
+ | |||
+ | maze = Maze() | ||
+ | maze.generate() | ||
+ | maze.print() | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | == 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 |
Latest revision as of 13:40, 31 May 2013
Contents
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
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
- roomToNorth - references the a doorway to the north. A None value means that there is wall
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):'
- initializes the dimensions of the Maze and creates the 2-dimensional matrix of MazeRooms
- connectRooms(self, r1, r2):
- Takes 2 MazeRooms as input parameters.
- Compares their row and column numbers to figure out their adjacency (relative locations)
- 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):
- Using 2 nested loops, traverse every room in the matrix and check if its visited attribute is False.
- Count all the unvisited Rooms and return the count
- generate(self):
- Create an empty list named stack
- Make a currentRoom variable reference rooms[0][0] and mark it as visited
- While there are unvisited rooms (Hint: Use the countUnvisited() method)
- If the currentRoom has any neighbours which have not been visited (Hint: Use the getUnvisitedNeighbors() method)
- Choose randomly one of the unvisited neighbours
- Push the currentRoom on to the stack
- Remove the wall between the current cell and the chosen cell (Hint: Use the connectRooms() method)
- Make the randomly chosen room as the current cell and mark it as visited
- Else if stack is not empty
- Pop a room from the stack and make it the current cell
- If the currentRoom has any neighbours which have not been visited (Hint: Use the getUnvisitedNeighbors() method)
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