CIS 250 Maze part I - Maze Generation

Objective

The objective of this assignment is to create a Maze which contains no loops, no large open areas, and no unreachable areas. A lot of code is provided to start you out. Check the resources section of this page for that code. The requirements section specifies the details of what must be done to finish this project.

Requirements

1. Create this program in a new directory which only contains code for this program.
2. Modify any source code you change to include your name and the current date.
3. You need a class and an enumeration to represent and deal with directions. The source code needed for this is provided and can be used without modification. The files are named Direction.h and Direction.cpp. The Direction source code specifies four directions, has information of the x and y displacement if moving in a particular direction, provides a name for each direction, and provides a method for getting the opposite direction.
4. You need a class to represent the individual cells of the maze. The Cell class keeps track of its own walls, its row and column position within the maze, stores a few pieces of information for algorithms to use, keeps track of any sides that are exterior boundaries of the maze, and can assemble a list of neighboring cells. Most of the Cell class has already been implemented for you. It is available as Cell.h and Cell.cpp. See the Methods section for a description of the one method you must implement for the Cell class.
5. You need a class to represent the maze as a whole. The Board class creates and initializes grids of Cell objects from 1 by 1 up through 100 by 100, keeps track of all of the individual cells, provides access to the individual cells, keeps track of a starting and an ending cell, and provides some convenience methods to facilitate maze creation and solving. A lot of the code has already been written for you. It is available as Board.h and Board.cpp. See the Methods section for a description of the three methods you must implement.
6. You need a class to actually create and display the maze. This is what the Maze1 class does. Some of the code has already been written for you. It is available as Maze1.cpp. See the Methods section for a description of the code you must finish implementing. This will be the code that actually creates the maze.
7. When you are done implementing the code you are supposed to implement, you can compile everything using:
   • g++ -Wall -o maze *.cpp (if all the code is in its own directory)
   • g++ -Wall -o maze Board.cpp Cell.cpp Direction.cpp Maze1.cpp (if other code is also in the directory)
   • You can then run the code using: ./maze
8. There is built-in test code to display whether or not your code is functioning properly.

Methods

1. In Cell.cpp: vector<direction>& getNeighbors(vector<direction>&).
   Populate the passed-in vector with every direction for which there is an adjacent Cell. It should not contain any direction which leads beyond the boundaries of the maze itself. You probably want to clear any vector that is passed in as an argument before you start to populate it.
2. In Board.cpp: void getConnectedNeighbors(Cell* c, vector<direction>& v).
   Populate the passed-in vector with every direction for which there is an adjacent cell which is connected to the cell passed in as an argument. The list should contain every direction for which there is an adjacent Cell which exists and is connected (has no wall between it and the Cell specified by the method argument). You probably want to clear any vector that is passed in as an argument before you start to populate it.
3. In Board.cpp: void getUnvisitedConnectedNeighbors(Cell* c, vector<direction>& v).
   Populate the passed-in vector with every direction for which there is an adjacent cell which is connected to the cell passed in as an argument and which is unvisited. The list should contain every direction for which there is an adjacent Cell which exists, is connected (has no wall between it and the Cell specified by the method argument), and is unvisited. You probably want to clear any vector that is passed in as an argument before you start to populate it.
4. In Board.cpp: void getUnvisitedNeighbors(Cell* c, vector<direction>& v).
   Populate the passed-in vector with every direction for which there is an adjacent cell which is unvisited. The adjacent cells do not have to be connected to the cell passed in as an argument. The list should contain every direction for which there is an adjacent Cell which is unvisited. You probably want to clear any vector that is passed in as an argument before you start to populate it.
5. In Maze1.cpp: int main(int argc, char* argv[])
   
   1. Create a new stack which can contain pointers to Cell objects
   2. Choose a random cell from Board b and push it on to the stack.
   3. While the stack is not empty
      1. Let cl = the top Cell pointer popped from the stack
      2. Set cl to visited
      3. Get a list of all of cl's unvisited neighbors
      4. If there are any items in cl's unvisited list, then push cl back onto the stack and choose one of its unvisited neighbors at random. Connect cl to that randomly chosen neighbor, and then push a pointer to that neighbor onto the stack.

Resources

These files are also available on the server at ~dklick/examples/cis250/maze/

1. Direction.h
2. Direction.cpp
3. Cell.h
4. Cell.cpp
5. Board.h
6. Board.cpp
7. Maze1.cpp

Sample output

All cells on board visited: true
All boundaries correct: true
All cells reachable: true
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   _ _ _ _ _ _ _ _ _ _ _ _ _
|  _ _ _|  _ _ _ _   _ _  |  _   _|      _|   | |  _    |   |
|  _ _ _ _|_  |   |_    |_ _|_ _|  _| |_|  _| |  _ _| | | | |
| |_     _  | | |_  |_| |  _ _ _ _|  _|  _| | | |   | | | | |
|_  |_|_  |_ _|_  |_ _ _| |   |  _| |  _ _ _| | | |_ _| | | |
|  _ _ _ _|  _  |_  |  _ _ _|_| | |  _ _|   | | | |_ _ _ _| |
|_  |  _ _ _| |_  | |_ _  |  _ _|_ _|  _ _|_ _| |_ _  |   | |
| | |_ _  |  _|  _|   | | | |_   _ _ _|  _  |_ _|  _ _|_| | |
|  _|_  | |_ _ _ _ _|_  | |_ _ _|_ _   _| |_  |  _|    _ _| |
|_ _ _  |_ _ _ _ _ _  | | | |    _ _ _| |  _ _| | | |_ _ _ _|
| |   |_  |_ _      | |_| |  _| |    _  | |  _ _| |_ _ _ _  |
| | |_ _ _|   |_| | |_ _ _| | | |_| |  _| |  _  |_ _    |  _|
| |_  |_   _|_ _ _|_ _ _  |_  |_  | |_ _| |_|  _|   | |_ _| |
|   |_ _ _|_ _ _    |  _ _|  _ _| |  _ _ _|  _|  _| |_ _  | |
| |_|  _ _   _ _  |_|_  | |_  |  _| |_  |  _  |_  |_  |_ _ _|
|   |  _ _|_ _  |_|  _ _|   | | | |_  |  _| |_ _ _ _|_   _  |
| | | |  _ _ _ _|  _|  _| | | | |  _ _|_  |_   _|  _  |_ _| |
| | | |_ _ _ _ _ _| |  _ _|_ _| |_  |_ _ _  | |  _|  _|  _ _|
| |_ _|   |  _  |_ _ _|   |  _ _| | |   |  _ _| |  _|_ _ _  |
|_ _  | | |_  |_ _ _  | |_ _|_    |_ _| | |  _ _| |  _ _ _  |
|  _|_ _| |  _|    _|_ _|_   _ _| |_  | | |_  | |_ _|   | | |
| |     | |_  |_|_   _     _|_ _ _ _ _| |_|  _|_   _ _|_ _| |
|  _| | |_  |_ _  | | | |_|  _ _ _  |  _|  _|   |_ _   _ _ _|
|_  | |_ _|_ _ _ _|_ _| |  _|_    |_ _|   |  _| |   |_ _|   |
| | |_  |  _   _|    _ _| |  _ _|_  | | | |_  | | | |  _ _| |
|  _| | | | |_  | |_ _ _ _|_  |  _ _| | |  _| | | |_ _ _ _| |
| |   |_ _|   |_ _|  _ _ _ _ _| |  _  | |_ _ _|  _|  _ _ _  |
|_ _| |_ _  |_|  _  | |    _  | |_ _|  _ _|   |_  | |  _|  _|
|  _|_ _  |_ _ _|  _| | | |_ _| |   |_ _|  _| |_ _| | |  _| |
|   |  _ _|   |  _|   | |_ _ _ _| | |   | | | |   | | | |_  |
|_|_ _ _ _ _|_ _|_ _|_ _ _ _ _   _|_ _|_ _|_ _ _|_ _|_ _ _ _|