CS 245 Lab 10 – Maze Traversal
First, if you have checkpoints left over from last lab, get them inspected during the first 15 minutes of this lab. No credit will be awarded past these 15 minutes.
Work in pairs, where possible. Prefer working with someone that you did not work with last lab. 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. Recall that a queue is a first-in, first-out structure. The oldest item in the queue is the first to be pulled out.
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
add 1,1 as initial bookmark
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 is to implement this algorithm with two different collections used for bookmarks: Stack and Queue. We suggest completing this task in the following order:
- Create a separate class with just a main method.
- After copying the two classes below into Eclipse, construct a new
Mazeand a newMazeFrameto see what a maze actually looks like. You are trying to travel from the upper-left corner to the bottom-right. - Implement the algorithm above, making use of the following methods in
Maze:isEscaped,visitCell,getUnvisitedNeighborsCount, andisUnvisited. - Immediately after you visit a cell, call
MazeFrame.repaintNowto see the drawing update in real-time. - Try tracking the bookmarks with a
Stackfirst. Then aQueue. What differences do you see?
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());
}
}