Exercise 4

This is a programming exercise. The goal is to implement breadth-first search to solve a three-dimensional (3D) maze.

Let's start with two important points:

• Download the latest algtest.jar and use this latest version. It has been compiled with JDK-20.0.1 (which means, if you have an earlier JDK installed, you'll need to re-install Java).
• Bonus-points opportunity. You can submit this Exercise along with Exercise-5 (giving you extra time). However, you can get bonus points by submitting this by the Exercise-4 deadline.

Next, let's first examine what a 2D version of the problem looks like:

• Think of a 2D maze as a 2D array of 0's and 1's. A cell containing 0 is a "forbidden" cell, while a cell containing a 1 is a cell you can enter. So, a valid path in a 2D maze is a sequence of contiguous cells containing 1's.
• In a maze problem, you are given a maze (as an 2D array of 0's and 1's), a starting point (a cell in the maze) and an ending point (another cell in the maze). The goal is to get from the start to the end.
• Consider this 2D example, a 5 x 5 maze with the start=(0,0) and end=(4,4):

                       columns
                    0  1  2  3  4
                    -------------
  	row 0:    1  1  1  1  1 
  	    1:    1  0  0  1  1 
  	    2:    1  1  1  0  1 
  	    3:    1  0  1  0  0
  	    4:    1  0  1  1  1
    

  Here, we can see a path from maze[0][0] to maze[4][4] consisting only of 1's.
• Important: we will only allow horizontal or vertical "moves", and not diagonal moves. Thus if you are in a cell, you can only move to one of four potential cells (north, south, east, west) and only if that neighboring cell has a 1.
• So, an algorithm is given three pieces of information:
  • The maze itself (a 2D array for a 2D problem)
  • The start point
  • The end point
• What must an algorithm compute?
  • A valid path from start to end, if one exists. In the above example, this is the sequence of cell coordinates (row, column numbers): (0,0), (1,0), (2,0), (2,1), (2,2), (3,2), (4,2), (4,3), (4,4).
  • If no such path exists from start-to-end, then the algorithm should return null

Now let's turn to a 3D maze, which is the problem you will solve:

• Your algorithm will need to implement the Maze3DAlgorithm interface, which itself extends the Algorithm interface.
• This interface has only one method:

      public ArrayList<IntTriple> findPath (int[][][] maze, IntTriple start, IntTriple end);
    

• Your file will also need to have the following import statements:

  import edu.gwu.algtest.*;
  import edu.gwu.util.*;
  import edu.gwu.geometry.*;
  import java.util.*;
    

• In a 3D maze, you are given a 3D array of 0's and 1's. Think of a 3D maze as a bunch of 2D mazes stacked on top of each other. Thus, for example, maze[1][2][3] refers to the cell in the 2nd level (level 1), 3rd row (row 2), and 4th column (column 3).
• Note: algtest will test your code with both 2D and 3D examples. When a 2D maze is given as a test, it will be given as a 3D maze with only one level, i.e., maze.length==1. Which means the cells are referenced using maze[0][j][k].
• What is an IntTriple? A 3D maze requires working with three indices as in maze[i][j][k] (level i, row j, column k). To make it convenient to store such "triplets", we use instances of IntTriple. For example:

       IntTriple t = new IntTriple(1,2,3);   // Store the indices i=1, j=2, k=3
       System.out.println(t);                // Print
       if (t.i==1) && (t.j==2) && (t.k==3) { // Notice how to access each int
           // ...
       }
       if (t.equals(end)) {
           // Assumes "end" is an IntTriple
           // ...
       }
    

• Since a path is a sequence of 3D coordinates, it is really a sequences of IntTriple's. You need to put these in an arraylist when returning the path (if one exists).
• Note: in a 3D maze, neighboring cells are those to the north, south, east, west, as well as "above" (next higher layer) and "below" (one layer below). Of course, a valid move is one that moves to a neighboring cell that contains a 1. Of course, some cells are at the edge and won't have as many neighbors as interior cells.

Next, let's outline a few key issues:

• You are to use breadth-first search (BFS). Essentially, you are to see whether the "end" node is in the BFS tree of the "start" node, and if so, to return the path (sequence of nodes that'll go from start to end, including both start and end).
• In BFS, when processing a node (that's just been pulled from the queue), you look at its neighbors. When a neighbor node is placed on the queue for the first time, then the edge from node to neighbor is in the BFS tree.
• You need to think about how to construct the path going from start to end (if one exists). This is actually the hardest part of the exercise.
• You also need to think about how to mark nodes as visited, as well as how to find neighboring nodes.
• Call your algorithm MyMaze3DAlgorithm and make sure that it implements the Maze3DAlgorithm interface.
• Use the maze3d.props properties file when running algtest.

Submission:

• For this exercise and others, you will need to follow the usual submission instructions carefully.
• As usual, you are expected to implement your own copious testing of your algorithms.