This lab continues the random maze generator you wrote before. This time you'll need to find a solution for the maze. The kind of maze we generated always yield solutions (unless you invert it so that the part that's not "dug out" is considered passable). The idea is get from the top left corner of the maze to the lower right corner.
You were supposed to have come up with your own algorithm (with help from me when necessary). However, here's a hint if you must have one.
First, download this template from the webpage, and paste in your "digout" function. This template is just a slightly modified version from the first maze lab, and should work with your digout function (if you wrote it without making assumption you know you shouldn't make). For this problem, the maze need to have odd values for both mw (width) and mh (height).
Write a function public void solve() that solves the maze. 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
(If you used a stack to solve the maze in the first place, then you
shouldn't need this extra 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. This is another typical linked list operation. 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.