CISC 3115 — Lab #5

Lab 5.1 — Basic `Maze` Class: Representing, Reading, `toString`

The Maze representation

Here is a visual representation of a maze, both as it would appear in the input file as well as when output:

..........
.S****** .
.   *  * .
.  **  * .
.   *  F .
. ***    .
..........

Here is a table of the various characters used in the representation:

.	border
(blank)	wall
*	path
S	start
F	finish

The above can be represented via a two-dimensional String array.
For readability and convenience, I created static final variables in the class for these characters, e.g. START = 'S', etc

The `Maze` Class

Create a class named Maze that has the following instance variables:

a 2-D char array,
integers startRow and startCol.
- These will represent the location of the starting point in the maze … we will use this information in the solver method
A static read method that follows the same logic as the other read methods we have been writing:
- Check if there's any data; if not return null
- Read in the data into a local variable (a char [][] array), create a Maze object and return it
  - the size of the array is obtained by first reading in the rows and columns meta-=data (i.e., the header values)
A constructor that accepts a char [][] array, assigns the refeence to the instace variable, then iterates (traverses) the array looking for the Start location and assigning it row/col co-ordinates to the startRow and startCol instance variables.
A toString method that constructs the String representation of the maze; i.e, the representation shown above (but without the need for the header).

Notes

We will assume the maze is rectangular;
- the 'size' of the maze (rows and columns) is provided in a header value above the visual representation (12 in this case).
```
7 x 10
..........
.S****** .
.   *  * .
.  **  * .
.   *  F .
. ***    .
..........
				
```
- Note the border is included within the dimensions of the maze
We will also assume the representation is correct (i.e. there is a border of '.'s, the lines are all of the proper format, there is a start and finish, and no characters other than the ones specified in the above table.
While the header should be read in using nextInt, the visual representation is best read in using nextLine. As we've discussed in class, these two methods do not interact well. To avoid any issues, please do a dummy nextLine right after reading inthe header, i.e.:
```
int rows = scanner.nextInt();
scanner.next();			// skips the 'x'
int cols = scanner.nextInt();
nextLine();				// positions to the next line
		
```
that will get everything in 'synch' and enable you to perform the nextLine for reading the visual rep.

Developing and Testing

Here is a sample maze file for you to develop with.

7 x 10
..........
.S****** .
.   *  * .
.  **  * .
.   *  F .
. ***    .
..........

Here is an app to read in the maze and print it:

import java.util.*;
import java.io.*;

class MazeApp {
	public static void main(String [] args) throws Exception {
		Maze maze = Maze.read(new Scanner(new File(args[0])));
		System.out.println(maze);
	}
}

..........
.S****** .
.   *  * .
.  **  * .
.   *  F .
. ***    .
..........

Lab 5.2 — Solving the Maze

In this step we will simply test and report whether the maze has a solution, i.e., there is a path from the start location to the finish location.

An Explanation of the Algorithm

We will refer to locations as (row, col). Here is an overview of the recursive definition of how to solve a maze:

If you are currently at a location where there's nowhere to go, i.e., every direction is either a border, a wall, or you've visited it already, there's no solution path from this location
If you're currently at the finish location, you've solved the maze
Otherwise, try solving the maze from the current location, try solving it by going in all directions from the current location: up, down, left, or right
- This is the recursive step — given a solution path from a particular location, a path from any position adjacent to the particular location that is a path location (i.e., not a wall or border) is also a solution (one step longer than the existing solution).
- You can only move up (row-1), down (row+1), left (col+1), or right (col-1) (i.e., no diagonal moves)
  - In addition, you can only move in a direction if the destination is not a wall or a border
- You also don't want to move in a direction you've already visited
  - Doing so could lead you into an endless loop of repeatedly visiting the same locations
  - In addition, there's no point in going to a location that you've already visited
  - This implies that you should have a 'visited' array … i.e. an 2-D boolean array that is the same size as the maze array. Initially, all entries are false (not visited); whenever you land (visit) at a location in the maze, set the corresponding visited array location to true

Some more details

The initial current location is the start location.
Check the current position, if it's the finish position, the maze has been solved
Mark the current position as visited
Try to solve the maze in all legal (non-wall/border) and non-visited directions from the current position. If a direction reports success, return success, otherwise, return failure.

Add an instance variable visited — a 2-D boolean array of the same size as the 2-D char instance variable holding the maze.
Add logic to the constructor to initialize all entries in to false.
The solver algorithm proper should be defined as a boolean-returning method that accepts the current row and column value of the current location; the algorithm will recurse on these two parameters in the manner described above:
- If the current position is a wall, or border, or we've visited it already, return false
  - the first two cannot be moved to
  - in the case of visited, this is to avoid endlessly looping around the same positions; in addition, there's no reason to explore in that direction if we've already been there
  Add a wrapper method, solve(), that sets up the recursive parameters, and calls the recursive method. Conceptually speaking, before we move to a new position (i.e., make a recursive call in that direction), we should make sure it's not a wall or border. However, the logic is a bit simpler if we first 'move' to that location and if it's an invalid position we immediately return false.
```
boolean solve(row, col) {…}


	If location (row, col) is a wall, or border, or we've visited it already, return false
		
			you cannot move into a wall or border location
			
there's no point in moving to a location you've already visited
		
	
If our current position is the finish position, we've solved the maze! … return true
	
mark the location (row, col) to true in the visited array
	
try to solve the maze by moving in all directions (up, down, left, and right)
		and see if any are successful (i.e. return true). If any returns true, we can return true; otherwise, return false..
		
			We can do this by making four recursive calls … one to each direction and OR'ing the results
		


	Let's call this new position our current position; assign its i and j to instance variables currentI and currentJ.
	
If our current position is the finish position, we've solved the maze! … return true
	
Otherwise, we still have work to do; we'll try to solve the maze by moving in all directions (up, down, left, and right)
		and see if any are successful (i.e. return true). If any returns true, we can return true.
		
			We can do this by making four recursive calls … one to each direction and OR'ing the results
		
```
Here is a seomwhat more fleshed-out algorithm: boolean solve(row, col) if location (row, col) is a wall or border return false // not a legitimate loocation if location (row, col) has been visited return false // been here, not getting anything new now if location (row, col) is the finish location return true // solved the maze! mark location (row.col) as true in the visited array // try to solve the maze by moving forward in every direction: if solve(i, j-1) return true // going one location up in the maze //same for down //same for left //same for right return false // no direction solves the maze
Notes
- the first three conditionals are escape clauses; the last four are the recursive calls
- strictly speaking, we should check for walls and borders BEFORE we move into a location (i.e., in in the last four conditionals); we defer the check until we actually are at the location (the first conditional)
Tracking the Solver's Progress
The above algorithm simply returns whether the maze is solvable; we want two other things:
- First to be able to trace the algorithm to make sure it is working correctly and not simply returning some arbitrary true/false that may or may not be correct
- Second to be able to show the actual solution path
We will incorporate the first item into this initial 'solving' step to help us check whether the algorithm is doing what we think it is; we will defer the solution path to the next step.
- Add a pair of instance variables named currentRow and currentCol to your class — they will represent the current position in the maze during the solution (think of a mouse running the maze; the current position represents the mouse's position).
- When you enter the solve method, after determining you belong there (i,.e., it's not a wall/border, and has never been visited) set currentRow and currentCol to the row and col parameters respectively.
- display the maze, but now include the current location on the display; i.e. modifiy your toString method to include the current location. To achieve,add another character (I used capital O) to represent the current position, and add logic to toString print that character when you are at the current position.
The result of the above will be a step-by-step illustration of your solve algorithm. For example, given the small maze example supplied above, you should get:
```
..........	..........	..........	..........	..........	..........	..........
.S****** .	.O****** .	.SO***** .	.S*O**** .	.S**O*** .	.S****** .	.S****** .
.   *  * .	.   *  * .	.   *  * .	.   *  * .	.   *  * .	.   O  * .	.   *  * .
.  **  * . 	.  **  * .	.  **  * .	.  **  * .	.  **  * .	.  **  * .	.  *O  * .
.   *  F .	.   *  F .	.   *  F .	.   *  F .	.   *  F .	.   *  F .	.   *  F .
. ***    .	. ***    .	. ***    .	. ***    .	. ***    .	. ***    .	. ***    .
..........	..........	..........	..........	..........	..........	..........

..........	..........	..........	..........	..........	..........	..........
.S****** .	.S****** .	.S****** .	.S****** .	.S****** .	.S***O** .	.S****O* .
.   *  * .	.   *  * .	.   *  * .	.   *  * .	.   *  * .	.   *  * .	.   *  * .
.  **  * .	.  **  * .	.  **  * .	.  **  * .	.  O*  * .	.  **  * .	.  **  * .
.   O  F .	.   *  F .	.   *  F .	.   *  F .	.   *  F .	.   *  F .	.   *  F .
. ***    .	. **O    .	. *O*    .	. O**    .	. ***    .	. ***    .	. ***    .
..........	..........	..........	..........	..........	..........	..........

..........	..........	..........	..........	
.S*****O .	.S****** .	.S****** .	.S****** .	
.   *  * .	.   *  O .	.   *  * .	.   *  * .	
.  **  * .	.  **  * .	.  **  O .	.  **  * .	
.   *  F .	.   *  F .	.   *  F .	.   *  O .	
. ***    .	. ***    .	. ***    .	. ***    .	
..........	..........	..........	..........	
```

Lab 5.3 — Constructing and Displaying the Solution Path

Here is a solution path for the above example (the O's represents the path of the solution): ............ .S** * . .O * . .O * OOOF. .OO** O . . O O * . . OOOOOO * . . * *** . . * * . . *** *** . . * * . ............ Recall that when we reach the finish location, we return true. That location is the last one on the path. We then unwind the recursion passing true up the chain of recursive calls. That means that each of those recursive calls is on the path that leads from Start to Finish.

Add yet one more boolean array, solutionPath, of the same dimensions as the maze, initialized to false.
In the main solver method, whenever you return true, set the (row, col) of the solution method to true.
Add a method, getSolutionPath that displays the maze just like toString but uses a different chaaracter (my O above) for any location that is true in the SolutionPath array.

CISC 3115
Introduction to Modern Programming Techniques
Lab #5
Recursion — Maze Solving

How to Develop and Submit your Labs

Lab 5 — Maze Solving

Overview

Two-Dimensional Arrays

Declaring and Creating

Accessing Individual Elements

Traversing

Lab 5.1 — Basic `Maze` Class: Representing, Reading, `toString`

The Maze representation

The `Maze` Class

Developing and Testing

Lab 5.2 — Solving the Maze

An Explanation of the Algorithm

Some more details

Tracking the Solver's Progress

Lab 5.3 — Constructing and Displaying the Solution Path

CISC 3115 Introduction to Modern Programming Techniques Lab #5 Recursion — Maze Solving

How to Develop and Submit your Labs

Lab 5 — Maze Solving

Overview

Two-Dimensional Arrays

Declaring and Creating

Accessing Individual Elements

Traversing

Lab 5.1 — Basic Maze Class: Representing, Reading, toString

The Maze representation

The Maze Class

Developing and Testing

Lab 5.2 — Solving the Maze

An Explanation of the Algorithm

Some more details

Tracking the Solver's Progress

Lab 5.3 — Constructing and Displaying the Solution Path

CISC 3115
Introduction to Modern Programming Techniques
Lab #5
Recursion — Maze Solving

Lab 5.1 — Basic `Maze` Class: Representing, Reading, `toString`

The `Maze` Class