CS 245 Lab 11 – Maze Traversal
First, if you have checkpoints left over from last lab, get them inspected during the first 15 minutes of this lab.
Don’t forget to work in pairs! Where possible, please work with someone that you did not work with last week. The exchange of new ideas and perspectives is not an opportunity you want to rob yourself of.
Synopsis
In this lab, you will look at two methods of collecting items for later processing: Stack and Queue. You will apply these two classes to the problem of finding a path through a maze.
Checkpoint 1
Person A types.
Copy the Stack class from lecture and paste it in your package for this lab.
Now, write a Queue class with methods isEmpty, size, enqueue(T), and T dequeue. Feel free to steal ideas from the Stack class.
Do some quick testing to make sure Queue behaves properly.
Checkpoint 2
Person B types.
Suppose you are navigating a mine-avoiding robot through a terrain. Or a survivor-smelling mechanical dog through a disaster site. How might you systematically get from one location to another, given that you cannot just barge through the danger and debris? Randomly choosing directions is certainly possible, but you are likely to waste time without a more systematic approach.
Instead, every time we reach a branch in the road, let’s make record of its location. If we hit a dead end, let’s return back to a previous fork in the road and try another path. We repeat this process until we’ve found our way through.
This leads us to the following algorithm:
bookmarks = new collection
while we haven't escaped and a bookmark remains
grab bookmark from collection
mark the cell as visited
if this cell still has more than 1 unvisited neighbor
throw cell back into bookmarks
// only visit cells we haven't yet visited
if left cell is unvisited
throw left cell into bookmarks
else if right cell is unvisited
throw right cell into bookmarks
else if bottom cell is unvisited
throw bottom cell into bookmarks
else if top cell is unvisited
throw top cell into bookmarks
Your task will be to implement this algorithm with two different collections used for bookmarks: Stack and Queue. We provide a Maze and MazeFrame class to manage the state of the maze and its GUI. Paste these two classes into your package:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class Maze {
private int[][] waymap;
private int[][] grid;
private Random generator;
private boolean isEscaped;
public static final int EAST = 0;
public static final int WEST = 1;
public static final int SOUTH = 2;
public static final int NORTH = 3;
public static final int VISITED = 2;
public static final int UNVISITED = 1;
public static final int WALL = 0;
private static int[] DX;
private static int[] DY;
private static int[] OPPOSITES;
static {
DX = new int[4];
DX[EAST] = 1;
DX[WEST] = -1;
DX[NORTH] = 0;
DX[SOUTH] = 0;
DY = new int[4];
DY[EAST] = 0;
DY[WEST] = 0;
DY[NORTH] = -1;
DY[SOUTH] = 1;
OPPOSITES = new int[4];
OPPOSITES[EAST] = WEST;
OPPOSITES[WEST] = EAST;
OPPOSITES[NORTH] = SOUTH;
OPPOSITES[SOUTH] = NORTH;
};
public Maze(int width,
int height,
long seed) {
waymap = new int[height][width];
generator = new Random(seed);
isEscaped = false;
carveFrom(0, 0);
}
public boolean isEscaped() {
return isEscaped;
}
private void carveFrom(int x,
int y) {
ArrayList<Integer> directions = new ArrayList<Integer>();
directions.add(EAST);
directions.add(WEST);
directions.add(SOUTH);
directions.add(NORTH);
Collections.shuffle(directions, generator);
for (Integer direction : directions) {
int newX = x + DX[direction];
int newY = y + DY[direction];
if (newX >= 0 && newX < waymap[0].length &&
newY >= 0 && newY < waymap.length &&
waymap[newY][newX] == 0) {
waymap[y][x] |= (1 << direction);
waymap[newY][newX] |= (1 << OPPOSITES[direction]);
carveFrom(newX, newY);
}
}
grid = getGrid();
}
public int getWidth() {
return waymap[0].length * 2 + 1;
}
public int getHeight() {
return waymap.length * 2 + 1;
}
public boolean isWall(int c,
int r) {
return grid[r][c] == 0;
}
public boolean isUnvisited(int c,
int r) {
return grid[r][c] == 1;
}
public boolean isVisited(int c,
int r) {
return grid[r][c] == 2;
}
public int[][] getGrid() {
int[][] grid = new int[getHeight()][getWidth()];
for (int r = 0; r < waymap.length; ++r) {
int pr = r * 2 + 1;
for (int c = 0; c < waymap[r].length; ++c) {
int pc = c * 2 + 1;
grid[pr][pc] = UNVISITED;
if ((waymap[r][c] & (1 << EAST)) != 0) {
grid[pr][pc + 1] = UNVISITED;
}
if ((waymap[r][c] & (1 << SOUTH)) != 0) {
grid[pr + 1][pc] = UNVISITED;
}
}
}
return grid;
}
public void visitCell(int c,
int r) {
if (grid[r][c] != WALL) {
if (r == getHeight() - 2 && c == getWidth() - 2) {
isEscaped = true;
}
grid[r][c] = VISITED;
} else {
throw new RuntimeException("You can't visit the wall at " + c + "," + r + "!");
}
}
public int getUnvisitedNeighborsCount(int c,
int r) {
int nUnvisited = 0;
if (r > 0 && isUnvisited(c, r - 1)) {
++nUnvisited;
}
if (r < getHeight() - 1 && isUnvisited(c, r + 1)) {
++nUnvisited;
}
if (c > 0 && isUnvisited(c - 1, r)) {
++nUnvisited;
}
if (c < getWidth() - 1 && isUnvisited(c + 1, r)) {
++nUnvisited;
}
return nUnvisited;
}
public String toString() {
StringBuilder sb = new StringBuilder();
int[][] pixels = getGrid();
for (int r = 0; r < pixels.length; ++r) {
for (int c = 0; c < pixels[r].length; ++c) {
sb.append(pixels[r][c] == 0 ? "*" : " ");
}
sb.append("\n");
}
return sb.toString();
}
}
import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class MazeFrame extends JFrame {
private Maze maze;
private MazePanel panel;
public MazeFrame(Maze maze) {
super("Maze");
this.maze = maze;
panel = new MazePanel();
add(panel);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setSize(1000, 800);
setVisible(true);
}
private class MazePanel extends JPanel {
@Override
public void paintComponent(Graphics g) {
int width = getWidth() / maze.getWidth();
int height = getHeight() / maze.getHeight();
for (int r = 0; r < maze.getHeight(); ++r) {
for (int c = 0; c < maze.getWidth(); ++c) {
if (r == maze.getHeight() - 2 &&
c == maze.getWidth() - 2) {
g.setColor(Color.RED);
} else if (maze.isUnvisited(c, r)) {
g.setColor(Color.WHITE);
} else if (maze.isVisited(c, r)) {
g.setColor(Color.GRAY);
} else {
g.setColor(Color.BLUE);
}
g.fillRect(c * width, r * height, width, height);
}
}
}
}
public void repaintNow() {
panel.paintImmediately(0, 0, panel.getWidth(), panel.getHeight());
}
}
Consider the following as you implement your traversal algorithm:
- Put your code in a separate class with just a main method.
- Before doing anything with the algorithm above, construct a new maze and a new frame to see what your task actually looks like.
- To implement the algorithm above, you can make use of the following methods in Maze: isEscaped, visitCell, getUnvisitedNeighborsCount, and isUnvisited.
- Immediately after you visit a cell, call frame.repaintNow to see the drawing update in real-time.
- Try tracking the bookmarks with a Stack first. Then a Queue. What differences do you see?