In this lab, we will write classes encapsulating a 2D array, write Enums, and test them with JUnit.
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. In later labs, we will 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.
There are two important elements already present in the code for this project
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.
Cell
Maze
OPEN
CLOSED
VISITED
Explorer
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.
Position
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.
Cells
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. Also, you need to set each individual Cell to be 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 grid location to the given Cell.
Run the MazeTest suite, and ensure your above methods are passing these tests.
MazeTest
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.
Puzzle
goal
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.
Returns the width of the maze.
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.
true
false
Run the PuzzleTest suite, and ensure your above methods are passing these tests.
PuzzleTest
Now, run the MazeApp class, and test out your code with the GUI.
MazeApp
Click Reset Maze to see a maze with all closed (red) Cells. Now, you should be able to click on squares to open and close pathways in the maze.
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.
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.
getClockwise
getCounterClockwise
getRotation
Direction
Verify that your Direction is working with the DirectionTest suite.
DirectionTest
In the Maze class, implement the following method:
public boolean inRoom(Position p).
public boolean inRoom(Position p)
This method will return true if the requested Position is part of a room, as defined above.
getNeighbor(Position p)
values()
Uncomment code labeled for this step in
Test out your code with the MazeTest suite.
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.
clear
Test out your code with the PuzzleTest suite.
Run the GUI to interact with your code.
The Explorer code is completed for you, and an Explorer can move around the maze and 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.
In the Move enum, you will need to create three elements, FORWARD, LEFT and RIGHT.
Move
FORWARD
LEFT
RIGHT
Add two abstract methods for newPosition and newDirection as shown below, and then provide an implementation for each of the three directions.
newPosition
newDirection
public abstract 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.
getNeighbor
public abstract 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.
MoveTest
Verify that your Move is working with the MoveTest suite.
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.
hero
null
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.
move
public Position getExplorerPosition()
Returns the Position of the Explorer.
public Direction getExplorerHeading()
Returns the Direction of the Explorer.
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.
Verify that your Puzzle and Explorer are working with the PuzzleTest suite.
MazeController