Homework 10

due: Thursday May 8 at 11:59pm (submit on Gradescope here).

Goals:

The main goal of this assignment is to compute the shortest path out of a maze. In doing so, you'll practice setting up your own data structures to represent the adjacency information of each location in the maze. We are assuming that each step has the same cost, so the shortest path can be computed using breadth-first search from the maze entrance to exit locations. The starter code can be downloaded here which also has files for the sample mazes below.

Part 1: Read a maze file.

Each location in the maze will be assigned an index, starting at 0 in the top-left corner of the maze, and increasing from left-to-right and top-to-bottom, as in the example images above.

Locations in the maze are considered adjacent if there is no wall between them. Our maze files contain wall information for the four directions around a particular location. These locations are oriented in clockwise order, starting with the +x direction (to the right). The first line in the file defines the maze size: # cells in horizontal direction $\times$ # cells in vertical direction. We will always have the same number of cells in the horizontal and vertical directions.

The leftmost image above is represented by the following file:

4,4
0,0,1,1,1
1,0,1,0,1
2,0,1,0,1
3,1,0,0,1
4,0,0,1,1
5,0,0,0,1
6,0,0,0,1
7,1,1,0,0
8,1,1,0,0
9,1,0,1,0
10,0,0,1,0
11,1,0,0,1
12,0,1,1,1
13,0,1,0,0
14,0,1,0,0
15,0,1,0,0

The first line indicates we are working with a 4x4 maze. The first number in every line afterwards is the cell (location) index, numbered in the order described above. The next four numbers are either 0 or 1, depending on whether there is a wall in the corresponding direction. As mentioned above, this is in clockwise order starting with the +x direction (right): the directions are right, bottom, left, top. To recap, each line (except for the first line) is:

[location index],[wall to the right?],[wall below?],[wall to the left?],[wall above?]

If there is a wall in the corresponding direction the value will be 1, otherwise it will be 0.

Your first task is to complete the Maze(String filename) constructor in order to read a maze file and set up your own data structures to represent the adjacency information between locations in the maze. We recommend you use an ArrayList of ArrayLists to store the adjacency information; add neighbors to the end of an adjacency list in clockwise order.

Recall that the starter code for Homework 8 included some code for reading from a text file.

Part 2: Determine the entrance and exit location indices.

The location of the maze entrance is always on the leftmost part of the maze, and the exit location is always on the rightmost part of the maze. All the entrances of our mazes (as in the images above) are the unique cell on the left with no wall in the left direction. Similarly, all exits of our mazes are the unique cell on the right with no wall in the right direction.

Return the indices of the entrance and exit cells in the getEntrance and getExit methods, respectively. You can either calculate these directly in getEntrance and getExit, or you can precompute and save them as you read your maze file.

Part 3: Compute the shortest path between entrance and exit locations.

In the getShortestPath method, use breadth-first search (BFS) to calculate the shortest path between the entrance and exit locations of the maze. This method should return a List<Integer> with the nodes in order from entrance to exit (you can use an ArrayList or LinkedList). For the three mazes above, this should be:

Again, the order depends on the fact that adjacencies should be traversed in clockwise order (starting with the right/east direction).

Hint: stop the BFS traversal once you reach the exit location. When adding a new (unvisited) location to the queue, keep track of the "parent" of this location (which is the parent in the tree BFS produces). The shortest path can then be obtained by starting at the exit and stepping into each parent until we reach the entrance.

Submission

You can generate additional mazes using the maze game on our course website. Click the export button to download the current maze (which is in the same format described above). You can also display the location indices and shortest path.

Upload Maze.java to Gradescope. Pre-submission check-list: