Overview
In this lab, we will write classes encapsulating a 2D array, write Enums, testing them with JUnit, and use a Stack to
create and solve mazes.
Materials
Setup
- Download the skeleton for this project.
- Unpack the code into a new Eclipse Java project.
Description
The puzzles inherent in
generating a maze
and solving a maze
lie at the heart of some very interesting problems
in computer science. Most obvious might be using Google Maps to find directions from
one location to another.
In this lab, you will create the necessary data structures to represent a maze
computationally, allowing a user to wander through the maze toward a goal,
and then later implement algorithms to generate and solve
mazes.
To start, run the code in MazeApp. After you click on "Reset Maze", you should see the
GUI layout here.
The Clear/Fill selection allows a user to manually create a maze on the screen. This will
be completed by you in steps 1 and 2 of this lab, and augmented in step 3. The Place
Explorer and Place Goal selections will be implemented in step 4, which will
also incorporate the movement buttons Left, Forward and Right, found on the bottom
of the screen. Steps 5 and 6 will implement code for the Randomize and Solve buttons.
There are two important elements already present in the code for this project
Cell
This enum records the state of a Cell in the Maze. A cell can be OPEN, CLOSED, or VISITED. Each
cell knows its color, what state of the cell should occur when the cell is flipped,
and if it can be entered by an Explorer.
Position
This class keeps track of an x and y coordinate. It has an accessor method for each of these
two variables, and can determine if it is adjacent or equal to another Position.
Step 1 - Maze
The core storage of the pathways and walls in the maze is in the Maze class.
It holds a 2D array of Cells as the only field.
Step 1.1 - Implementation
You will need to write code for the
following methods.
public Maze(int width, int height)
This constructor brings in a width and height, and initializes the 2D array to be
of this size. All Cells are initially CLOSED.
public int getWidth()
Returns the width of the grid of cells.
public int getHeight()
Returns the height of the grid of cells.
public boolean inMaze(Position p)
A method to determine if a Position within the bounds of the grid of cells.
public Cell getStateFor(Position p)
If the requested Position is in the maze, this method will return the corresponding Cell.
Otherwise, it will always return the CLOSED Cell.
public void setStateFor(Position p, Cell state)
If the given Position is in the maze, this method will set the corresponding
location to the given Cell.
Step 1.2 - Testing
Run the MazeTest suite, and ensure your above methods are passing these tests.
Step 2 - Puzzle
The Puzzle class is our central model for this program. It will hold a Maze, an Explorer,
and a Position to represent the Goal in our maze. In this step, you will complete the
code for interacting with the Maze.
Step 2.1 - Implementation
You will need to write code for the
following methods.
public Puzzle(int width, int height)
The constructor should make a Maze of the specified width and height. It should
leave the Explorer and Goal null.
public int getWidth()
Returns the width of the maze.
public int getHeight()
Returns the height of the maze.
public Color getColorFor(Position p)
Returns the color of the Cell at the requested Position in the maze.
public boolean canEnter(Position p)
Determines if the Cell at the Position given in the maze can be entered, i.e. is it an OPEN pathway.
public void fill(Position p)
Sets the Cell in the maze at the given Position to be CLOSED up as a wall.
public boolean clear(Position p)
Sets the Cell in the maze at the given Position to be OPEN for a pathway. This will
return true if it was successful, and false otherwise. Positions outside the Maze
can never be cleared.
Step 2.2 - Testing
Run the PuzzleTest suite, and ensure your above methods are passing these tests.
Step 2.3 - GUI
Now, run the MazeApp class, and test out your code with the GUI. You should be
able to select squares and open and close pathways in the maze.
Step 3 - Avoiding Rooms
We can add a restriction on the ability of the user to create mazes with large rooms.
A room is defined as any four OPEN Cells that form a 2x2 square.
Uncomment code labeled for this step in
Step 3.1 - Maze Updates
In the Maze class,
implement the following method
public boolean inRoom(Position p)
This method will return true if the requested Position is part of a room, as defined above.
Step 3.2 - Puzzle Updates
You will need to update your clear method of the Puzzle. It should
now be the case that the only Cells that can be cleared are those in the Maze that
will not cause a room to be formed.
Step 3.3 - Testing
Test out your code with the MazeTest and PuzzleTest suite.
Step 3.4 - GUI
Run the GUI to interact with
your code.
Step 4 - Explorer and Goal
Uncomment code labeled for this step in
- MoveTest
- MazeTest
- PuzzleTest
- Explorer
- MazeController
The Explorer code is completed for you, and an Explorer can move around the
maze an look ahead according to their internal Position and Direction.
There are three pieces of code we will need to complete for the Explorer and Goal
portions of the Puzzle class.
Step 4.1 - Direction
You will add the implementations for the getClockwise, getCounterClockwise and
getRotation methods of the Direction enum. Use the standard compass rose to map
each Direction to its clockwise and counterclockwise neighbor. For the rotation, you
should return the angle in degrees for each orientation, where SOUTH is at 0 degrees,
WEST is 90, NORTH is 180, and EAST is -90.
Step 4.2 - Direction Testing
Verify that your Direction is working with the DirectionTest suite.
Step 4.3 - Update Maze
Write a new method for Maze.
public int numOpenNeighbors(Position p)
This method returns the number of neighbors for a given position that are open. This
does not include the given position, only its four neighbors, one in each Direction.
Step 4.4 - Move
Fill in the code for the Move enum. Create three elements, FORWARD, LEFT and
RIGHT. Add two abstract methods for newPosition and newDirection
as shown below, and then provide an implementation for each of the three directions.
public Position newPosition(Position p, Direction d)
Given a Position and a Direction, return the new Position found by going in the Direction.
When going FORWARD, this should make use of the getNeighbor method found
in Direction, otherwise the Position should remain the same.
public Direction newDirection(Direction d)
Given a Direction, return a new Direction. LEFT should rotate counterclockwise,
while RIGHT rotates clockwise, and FORWARD does not change the direction.
Step 4.5 - Move Testing
Verify that your Move is working with the MoveTest suite.
Step 4.6 - Puzzle Explorer
More methods are now required in the Puzzle class. Complete the implementation
of the following methods.
public boolean hasExplorer()
Returns false if the hero is null, otherwise returns true.
public void placeExplorer(Position p)
Creates a new Explorer at the given Position and saves it in the
hero field.
public void moveExplorer(Move m)
Calls the move method on the hero if the Puzzle has an Explorer.
public Position getExplorerPosition()
Returns the Position of the Explorer.
public Direction getExplorerHeading()
Returns the Direction of the Explorer.
Step 4.7 - Puzzle Goal
Finally, add two more methods to Puzzle to allow for a Goal Position to
be placed in the Puzzle.
public void placeGoal(Position p)
Saves the given Position as the Goal position.
public Position getGoal()
Returns the Goal position.
Step 4.8 - Puzzle Testing
Verify that your Puzzle is working with the PuzzleTest suite.
Step 4.9 - GUI
Run the GUI to interact with
your code.
Step 5 - Creating Random Mazes
Uncomment code labeled for this portion in
First, you will be creating random mazes by implementing the tunnelRandomly function.
You will use the randomDirections method of Direction.
public void tunnelRandomly()
Create a stack of Positions, and push (0,0) onto the stack.
While the stack still
has Positions:
- Pop the top Position from the stack.
- If this Position is in the maze and is filled, and by clearing this cell you will not create a cycle
- Clear this position
- Add the neighbors to the stack in a random order.
Step 6 - Solving Mazes
Uncomment code labeled for this portion in
- Trail
- PuzzleTest
- MazeController
Finally, you will write an algorithm to solve a maze with the solve method.
public Trail solve()
If there is no Explorer in the maze or no Goal in the maze, then return null.
Create a stack of Trails, and push the Trail starting at the Explorer's position onto the stack.
While the stack still has potential Trails, and you have not reached the goal:
- Pop the top Trail from the stack.
- If the Trail end is the goal Position, return this Trail
- If the Cell in the Maze at the Trail end is OPEN
- Mark it as a VISITED Cell
- Add new Trails based on this Trail for each of the neighbors to the stack.
What to Hand In
Submit your Maze.java, Puzzle.java, Direction.java and Move.java implementations, along with
any additional files you created for your implementations.
Grading
- To earn a D, finish Step 1
- To earn a C, finish the above and Step 2, 3.
- To earn a B, finish the above and Step 4.
- To earn a A, finish the above and Step 5, 6.
- To earn a 100, finish the above and submit a screenshot of a
20x20 maze you have created.
© Mark Goadrich, Hendrix College