CIS 260 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
- Create this program in a new directory which only contains
code for this program.
- Modify any source code you change to include your name
and the current date.
- You need a class to represent directions. This should be done
as an enumeration. The source code needed for this is provided
and can be used without modification. It is named
Direction.java. The Direction
enumeration 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.
- 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.java.
See the Methods section for a description of
the one method you must implement.
- 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.java. See the
Methods section for a description of the
three methods you must implement.
- 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.java. See the
Methods section for a description of the
one method you must finish implementing. This will be
the code that actually creates the maze.
- When you are done implementing the code you are supposed to
implement, you can compile everything using: javac *.java.
You can then run the code using: java Maze1
- There is built-in test code to display whether or not your
code is functioning properly.
Methods
- In Cell.java: ArrayList<Direction> getNeighbors().
Create and return a new ArrayList of Direction objects. The
list should contain every Direction for which there is an
adjacent Cell. It should not contain any Direction which
leads beyond the boundaries of the maze itself.
- In Board.java: ArrayList<Direction> getConnectedNeighbors(Cell c).
Create and return a new ArrayList of Direction objects. 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).
- In Board.java: ArrayList<Direction> getUnvisitedConnectedNeighbors(Cell c).
Create and return a new ArrayList of Direction objects. The
list should contain every Direction for which there is an
adjacent Cell which exists, is unvisited, and which has no
wall between it and the Cell specified by the method argument.
- In Board.java: ArrayList<Direction> getUnvisitedNeighbors(Cell c).
Create and return a new ArrayList of Direction objects. The
list should contain every Direction for which there is an
adjacent Cell which exists and is unvisited (even if there is
a wall between the adjacent Cell and the Cell specified by the
method argument).
- In Maze1.java: public Maze1().
- Create a new stack which can contain Cell objects.
- Choose a random cell from Board b and push it on to the stack.
- While the stack is not empty
- Let cl = the top Cell popped from the stack
- Set cl to visited
- Get a list of all of cl's unvisited neighbors
- 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
that neighbor onto the stack.
Resources
- Direction.java
- Cell.java
- Board.java
- Maze1.java
Sample output
All cells on board visited: true
All boundaries correct: true
All cells reachable: true
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _| _ _ _ _ _ _ | _ _| _| | | _ | |
| _ _ _ _|_ | |_ |_ _|_ _| _| |_| _| | _ _| | | | |
| |_ _ | | |_ |_| | _ _ _ _| _| _| | | | | | | | |
|_ |_|_ |_ _|_ |_ _ _| | | _| | _ _ _| | | |_ _| | | |
| _ _ _ _| _ |_ | _ _ _|_| | | _ _| | | | |_ _ _ _| |
|_ | _ _ _| |_ | |_ _ | _ _|_ _| _ _|_ _| |_ _ | | |
| | |_ _ | _| _| | | | |_ _ _ _| _ |_ _| _ _|_| | |
| _|_ | |_ _ _ _ _|_ | |_ _ _|_ _ _| |_ | _| _ _| |
|_ _ _ |_ _ _ _ _ _ | | | | _ _ _| | _ _| | | |_ _ _ _|
| | |_ |_ _ | |_| | _| | _ | | _ _| |_ _ _ _ |
| | |_ _ _| |_| | |_ _ _| | | |_| | _| | _ |_ _ | _|
| |_ |_ _|_ _ _|_ _ _ |_ |_ | |_ _| |_| _| | |_ _| |
| |_ _ _|_ _ _ | _ _| _ _| | _ _ _| _| _| |_ _ | |
| |_| _ _ _ _ |_|_ | |_ | _| |_ | _ |_ |_ |_ _ _|
| | _ _|_ _ |_| _ _| | | | |_ | _| |_ _ _ _|_ _ |
| | | | _ _ _ _| _| _| | | | | _ _|_ |_ _| _ |_ _| |
| | | |_ _ _ _ _ _| | _ _|_ _| |_ |_ _ _ | | _| _| _ _|
| |_ _| | _ |_ _ _| | _ _| | | | _ _| | _|_ _ _ |
|_ _ | | |_ |_ _ _ | |_ _|_ |_ _| | | _ _| | _ _ _ |
| _|_ _| | _| _|_ _|_ _ _| |_ | | |_ | |_ _| | | |
| | | |_ |_|_ _ _|_ _ _ _ _| |_| _|_ _ _|_ _| |
| _| | |_ |_ _ | | | |_| _ _ _ | _| _| |_ _ _ _ _|
|_ | |_ _|_ _ _ _|_ _| | _|_ |_ _| | _| | |_ _| |
| | |_ | _ _| _ _| | _ _|_ | | | |_ | | | | _ _| |
| _| | | | |_ | |_ _ _ _|_ | _ _| | | _| | | |_ _ _ _| |
| | |_ _| |_ _| _ _ _ _ _| | _ | |_ _ _| _| _ _ _ |
|_ _| |_ _ |_| _ | | _ | |_ _| _ _| |_ | | _| _|
| _|_ _ |_ _ _| _| | | |_ _| | |_ _| _| |_ _| | | _| |
| | _ _| | _| | |_ _ _ _| | | | | | | | | | |_ |
|_|_ _ _ _ _|_ _|_ _|_ _ _ _ _ _|_ _|_ _|_ _ _|_ _|_ _ _ _|