CSCI 151 - Project 2
Maze Algorithms
Overview
In this project, you will write complete two algorithms related to the Maze implementation
from Lab 4.
Materials
Setup
- Use the code from Lab 4 for this project.
Description
Now that you have a working computational model of a maze, we can implement
two algorithms using Stacks to create and solve mazes.
Step 1 - Update Cell
Uncomment code labeled for this portion in
- Trail
- PuzzleTest
- MazeController
- MazeTest
Add a VISITED element to the Cell class.
This will be used to record where the search algorithm
below makes a trail and backtracks after finding
a dead end. The Color is AQUA, flipped should return CLOSED,
and canEnter will return true.
Step 2 - 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 3 - Generic Stack
Implement a generic stack that hold any type of Object in java. This stack should
be based on either your ListIntStack or your ArrayIntStack. You should name your stack
without the Int portion, so you should have either a ListStack or an ArrayStack.
Step 4 - Creating Random Mazes
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 5 - Solving Mazes
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 updated Maze.java and Puzzle.java files along with
any additional files you created such as the Stack.
Grading
Your grade will be determined by the number of tests you pass.
© Mark Goadrich, Hendrix College