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. For this assignment, you should work by yourself.

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, and your LinkedList code. 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.

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

Along with your java source code, you should hand in a file named README and your Makefile if you used one. These files will be imported automatically via handin35. 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. Also include any known problems/bugs in your code.

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:42 PM