Maze Walker
Due Dates
| Class Design and Maze Reader | Feb 22, 2005.
|
| Legal mover generator | Feb 24
|
| Interaction between the stack and the legal move generator. This version should be able to walk a simple maze | March 1
|
| Final Project | March 3, 2005
|
Task Description
In this assignment you will write a program for navigating through a maze. The program will read the maze from a file. For instance the file for a simple T maze might appear as:
6 7
1 1 1 1 1 1 1
1 3 0 0 0 0 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 2 1 1 1
1 1 1 1 1 1 1
In the file the first line will always have 2 numbers which give the size of the maze. The first number is the number of rows, the second is the number of columns. Subsequent lines will show the maze. The characters used to define the maze are:
| character | meaning
|
| 1 | Walls
|
| 0 | Hallways
|
| 2 | Starting point
|
| 3 | the goal
|
In the maze definition you may assume that the number of rows and columns is correct and that there is exactly 1 starting point and 1 ending point.
Idea
Use a stack. In particular, when you are at a point, determine all of the moves possible from that point (being careful not to back up). Add each of these possible moves to the stack. Then make a move by removing the topmost possible move from the stack. Curiously, some correct implementations of a maze wanderer will result in finding the finish but with no clue about how to get from the beginning to the end. (Of course, this is often the case in mazes.)
You maze walker may only move up, down, right or left (no diagonal movement).
You succeed iff you reach the target (the number 3). You could also determine that there is not solution for the maze.
Programming requirements:
Your program must:
- accept one command line argument, the name of file containing the maze.
- Have some method of showing the search through the maze.
- When a solution is found, print a statement that the solution has been found and the number of steps (including any backtracking) required your program to find the solution.
- If there is no path from the start to the finish, print a statement that says there is no path.
Testing
An incomplete set of mazes will be available in files of the form: /home/gtowell/cs206/mazes/mazeN where N is a number. E.g., maze1, maze2, ... That is, when I test your programs, some of the tests will involve issues that do not appear in my test examples. So, the comment "it worked on your examples" is an insufficient response. You may assume that the maze description files are correct both for development and testing.
Generally speaking, mazes have a difficult determined by their number. So maze1 is easier than maze2, etc.
Submit
| Class descriptions and maze reader | The class design should mention all of the classes you intend to create and all the public methods of those classes. In addition, mention any standard Java classes you will be using. In effect, you should be able to implement the maze walker just by programming up the interaction you show. NOTE: this need not be precisely correct; indeed I would expect that as you implement you will find mistakes. However, it needs to be plausible.
The maze reader should be a small java program that accepts one argument, the name of a maze file (as defined above). The program should read, store, and create a printed representation of the maze.
|
| Legal Move Generator | The program should accept a maze and be able to generate all legal moves from a point in the maze. It will be most useful if the legal move generator produces new copies of maze, indicating the legal moves. For example here is a maze and two legal moves:
| Initial position | legal move 1 | legal move 2
|
0 1
2 0
|
2 1
4 0
|
0 1
4 2
|
Note that this legal move generator changed the coding of the start position to 4 and assigned the value of 2 (indicating the start position) to each of possible moves in the maze.
|
|---|
| Stacking legal moves | In this version, rather than just outputting the various possible legal moves, put the legal moves onto a stack and then take them off.
|
| Completed Program |
- An electronic copy of you maze running program
- A written statement of the situations in which you know that your program does not work (if there are any).
- A statement of which extra credit (if any) you would like your program evaluated for.
|
|---|
Extra Credit
- (5 extra points) For each maze, a statement of the path from start to end.
- (10 extra points)For mazes with more than one path, the shortest path (10 extra points).
- (30 extra points)A graphical GUI showing the program's search through the maze. The GUI should include at least two buttons: "step" which causes the search to make a move, and "run" which causes the search to run to completion. ( I do not recommend trying this but if you must, you can look at my Rand program for an example of starting to build a GUI in an application.)
Grading
- 10 points each
- For the first 3 submissions.
- 55 points
- The ability of the program to find solutions to mazes (i.e., whether or not it solves all of my test mazes). The efficiency of solution finding will be considered here.
- 10 points
- Coding style. This includes appropriate use of Java classes, methods, and variables; use of descriptive names, comments, etc.
- 5 points
- Written response. (less than 200 words) For this assignment I suggested using a stack to solve the maze walking problem. Indeed, every computer maze walker uses a stack. You could use a queue instead. So, why do all maze walkers use a stack? Should one be preferred over the other for efficiency reasons? (Speculate)