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.

Write a Maze class for creating, displaying, and solving mazes. All our mazes will be two-dimensional arrays of n rows and m columns. Each row, column cell is either open, or blocked by an internal wall. From any open cell, you may move left, right, up, or down to an adjacent empty cell. To solve a maze, you must find a path of open cells from a given start cell to a specified end cell. By default, you should assume that the start cell is in position (0,0) and the end cell is at position (n-1, m-1).

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 <--END

A sample solution path from START to END is:
[(0,0),(0,1),(0,2),(0,3),(0,4), (1,4),(2,4),(2,3), (2,2),(2,1),(3,1), (4,1),(5,1),(5,2),(5,3),(4,3),(4,4), (4,5),(5,5)]

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

Your program must have the following features:

1. Prompt the user for maze dimensions and locations of walls
2. Print the maze to the terminal (stdout)
3. Search for a path in the maze using a stack
4. Search for a path in the maze using a queue
5. If no path exists, display an appropriate message
6. If a path exists, display the following
   • The coordinates of the path from START to END
   • The total length of the path
   • A graphical (ASCII art) representation of the path

A full run of the program might look like this:

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 * *

You may use any of the code discussed in class, including the Queue and Stack implementations. You will likely need to finish your Queue class, and implement Maze, TestMaze, and PathPosition classes. You may find the Scanner class in java.util.Scanner helpful for reading in input from the user. An example of how to use a Scanner object is in RandomDays.java in the w01-intro folder. Other examples can be found in the textbook. Looking at old code is a great way to learn how to write new code. To find paths in the maze, you should use the following algorithm. Some details have been omitted and you will need to think about how to fill them in.

1. Initialize the search list with the start position (0,0).
2. while the search list is not empty
   1. remove the next element from search list
   2. if the next element is the end position (m-1, n-1), then you have found a path
   3. otherwise, add any valid moves to a unvisited neighbor of this element to the search list
3. If list is empty, and no path was found, no path exists

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.

For much of this assignment you will be writing code from scratch. Working with a partner can make this much easier for the both of you. If you are interested in finding a partner, email me and I can try to connect interested parties. However, you do not need to write everything from scratch. You can use the Stack and Queue code we discussed in class to implement your search lists. To copy this data into your lab folder, you can run the following sequence of commands:

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.java

If 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.

You grade depends on how well your code solves mazes, not on whether or not your code compiles (compiling in necessary, but not sufficient). Please test your code. You worked hard on writing your code, so show it off with some cool tests. Try to come up with tricky cases that might break your code (for example a maze with no solution) and see if your program recovers gracefully or crashes in flames. I have included some test cases you may want to try in the test_* files. To use one of these files as input, you can use the input redirection operator in linux (the < symbol). Here is an example from class:

java TestMaze < test_input

This 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.

Along with your java source code, you should hand in a file named README. Your README should include a brief summary of your results, including a discussion of the advantages/disadvantages of using a stack or queue to solve this problem. Give a brief explanation of the big-Oh run-time of your methods in terms of the number of rows and columns of the maze. Also include any known problems/bugs in your code. Does any particular method (stack or queue) find a solution faster? Does any particular method find a shorter (or shortest possible) solution? Explain briefly in your README. Do not include lengthy technical discussions about the details of your code in the README. That's what the code is for. Imagine you are explaining what you did to someone who might be interested in taking cs35 but does not know Java. What would you tell her/him? Put that in your README. You can include a few small test runs as well.

Home Page

Last updated: Tuesday, September 22, 2020 at 09:07:42 AM