This assignment asks you to write a program that will find a path through a maze. You will need to implement two approaches: a depth-first approach using a stack and a breadth-first solution using a queue. You should save your programs in your cs35/homework/04 directory. You may work with one partner on this assignment. If you work with a partner, be sure to put both names on your assignment when submitting.
To create a new maze, your program should prompt the user for the maze dimension (number of rows and columns) and then ask the user to enter the grid locations of all internal walls as a set of (row, column) coordinates. Your maze class should be able to create a new maze from user input, print the maze to the terminal, find a path through the maze, and display the path if a solution exists. If no solution exists, your program should inform the user without crashing.
Below is a sample 6x6 maze with blue 1's indicating the location of walls and black 0's indicating open cells:
START--> 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 0 0 0 1 0 <--ENDA sample solution path from START to END is:
The red asterisks below show the path.
START--> * * * * * 0 1 1 1 1 * 1 1 * * * * 1 1 * 1 1 1 1 1 * 1 * * * 1 * * * 1 * <--END
This program will attempt to find a path through an m by n maze The program will first ask you for the dimensions of the maze and the location of the walls in the maze. It will then attempt to find a path in the maze and display the path if found. If no path exists, the program will inform the user. Enter number of rows: 5 Enter number of columns: 5 Enter the location of the maze walls as a list of row col pairs. Each pair should appear on a single line and be separated by a space. Type -1 on a line by itself to indicate the end of the list. The row value must be between 0 and 4 and the col value must be between 0 and 4 Enter your pairs now: 0 1 1 1 3 1 4 1 3 2 3 0 -1 Initial Maze: ---------- 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 Using a stack Path through maze: [(0,0),(1,0),(2,0),(2,1),(2,2),(2,3),(2,4),(3,4),(4,4)] Length: 9 Maze with path -------------- * 1 0 0 0 * 1 0 0 0 * * * * * 1 1 1 0 * 0 1 0 0 * Using a queue Path through maze: [(0,0),(1,0),(2,0),(2,1),(2,2),(2,3),(3,3),(4,3),(4,4)] Length: 9 Maze with path -------------- * 1 0 0 0 * 1 0 0 0 * * * * 0 1 1 1 * 0 0 1 0 * *
The search list can be implemented using either a stack or a queue. Each list will store PathPosition objects. You will need to think about what to store in the PathPosition class. You should be able to reconstruct a complete maze path given one or more PathPosition objects. Once you implement one version of the search algorithm, the other version can be implemented by modifying the first algorithm and replacing push/pops with enqueues/dequeues.
cd ~/cs35/homework/04 cp ~/cs35/labs/w04-StacksQueues/* .And yes, that is not a typo, there is a real "." at the end of the last line. The "." means to place the files in the current directory, which in this case is your cs35/homework/04 folder.
If you did not finish implementing the NodeQueue in class, or are stuck and cannot finish it, you can get a working copy by copying the file NodeQueue_sol.java to NodeQueue.java.
update35 cd ~/cs35/labs/w04-StacksQueues cp NodeQueue_sol.java NodeQueue.javaIf your Queue class works, you do not need to do this step.
Develop your code incrementally first. Design a Maze class on paper or the whiteboard first. Then implement your maze class by first declaring instance variables, writing a constructor that sets the instance variables, and then writing a very small main method to test that you class compiles. Fix the bugs in these few methods first and then incrementally add methods, testing each new method before adding the next. If you get more than 10 errors the first time you try to compile, you waited too long to compile. Write fewer lines before the next time you try to compile. When fixing errors, fix the first error first. Sometimes this makes the others go away. As you gain experience you will get a feel for common errors and their fixes.
This project can be finished by writing only three new classes: Maze, PathPosition, and TestMaze. You may add more if you wish, but if you end up with twenty new classes, you are probably over-designing things. Keep your maze constructor short. Knowing the number of rows and columns for a new maze is sufficient. You can add walls incrementally using another method.
java TestMaze < test_inputThis will read the maze data from test_input instead of from the terminal. This can save you a lot of typing. You can make your own test files in your favorite text editor (vim?).
For the adventurous, you can use gimp and the python script pgm2maze.py to create maze text files graphically. The gimp is a free Photoshop-like application. Running gimp from the command line will get you started. If this is the first time running the gimp, it might ask you to set up a few things. Just hit continue a few times. Create a small image (no bigger than 80x80), zoom in, and use the pencil tool with a 1x1 brush size to create a black and white image. Black squares indicate walls, and white squares indicate open paths. Be sure to make the upper left and lower right corners white. Save you image with a .pgm extension in ASCII mode. Then use python pgm2maze.py yourimage.pgm > yourtest_input to convert the image to a mazefile yourtest_input. Then use the input redirection above to run on your maze. I'll give a demo of this in class, or you can stop by and ask for a quick demo.