For this lab you need to find a path through a randomly generated maze. Download the skeleton program mazedfs.java. "dfs" stands for depth-first search, which is the base algorithmic strategy of this exercise. You first need to copy the code for maze generation into the digout function (marked toward end of program). Other aspects of the program are very similar to the maze-generation assignment:
The file contains a single class called mazedfs. The maze is represented by the two dimensional array byte[][] M;. A "byte" in Java is just an 8-bit signed integer. The height and width of the array are represented by the variables mh and mw respectively. These values should be odd, but for this exercise you can leave them at the defaults.
Like C/C++, Java stores 2D arrays in "row-major order", which means that to visualize the maze consistently, you should provide the y-coordinate first: that is, use M[y][x] instead of M[x][y].
Initially, each value M[y][x] is either 0 (blocked/green) or 1 (dugout/black).
Write a function public void solve() that solves the maze using the depth-first search algorithm described in class. This function will be called automatically from the "actionPerformed" method of the template. You are to represent the current position of the player by drawing a red dot. The initial position (in the maze matrix) of the red dot should be y=1, x=1. The maze is solved when your dot reaches coordinates y==mh-2, x==mw-2.
You are of course only allowed to go where the maze have been "dug out", i.e., M[y][x]!=0, and you cannot skip any spaces. I'm giving you the following functions. You'll have to figure out how to make use of them:
// draws a red dot at location corresponding to M[y][x], includes animation // delay: public void drawdot(int y, int x) // see code in template program // draws a black rectangle at M[y][x], with option to display value: public void drawblock(int y, int x)You need to call drawblock to erase the previous red dot as you move to a new position.
class stackcell
{
int x;
int y;
stackcell tail;
public stackcell(int a, int b, stackcell t) {y=a; x=b; tail=t;}
} // stack class
You need to modify the code you just wrote so that each time you
visit a coordinate y,x in the maze, push it onto the stack:
yourstack = new stackcell(y,x,yourstack); When you've
solved the maze, you can then just "pop" the stackcells one by one
and follow the coordinates to go back to the starting point. To pop
the stack all you have to do is set yourstack=yourstack.tail.
Now, to eliminate the redundant paths recorded on the stack, you need to write a procedure (within the stack class) public void cut(), that looks down the stack to find the next cell that have the same y,x values as "this" cell, and "cut out" everything in between (there may be several such cells and you need to find the one farthest down the stack). Draw a diagram to help you picture what needs to be done. You then need to call this function at the appropriate points in your backwards simulation (this backwards simulation code should also be inside the solve() method).
Your program should look more or less as the professor's when you're done. You can display text messages on the graphical window with statements such as:
g.setFont(new Font("Serif",Font.BOLD,24));
g.drawString("You Made It!",(aw/2)-60,60);
and insert delays into the simulation with
try{Thread.sleep(3000);} catch(Exception e) {} // 3 second delay
The Graphics object "g" is already defined in the template
program, and is what allows you to draw to the graphical display.