Simple maze solving algorithm

Question

I was to write a simple maze solver program that takes in an input file denoting the maze start and end points, and the structure of the maze itself. The specifications were to keep it as simple as you can, so no need to over complicate the solution. My solution is below. I think the buildMaze() method could definitely be done better. I wasn't sure how to read in a new line every time and write the input to new variables, so this solution was one I found online that worked, but I'd like to improve on it if I could.

Here were the specifications for the input file and the output:

INPUT:
<WIDTH> <HEIGHT><CR>
<START_X> <START_Y><CR> (x,y) location of the start. (0,0) is upper left and (width-1,height-1) is lower right
<END_X> <END_Y><CR> (x,y) location of the end
<HEIGHT> <WIDTH> {0,0} rows where each row has integers space delimited
OUTPUT:
 The maze with a path from start to end
 Walls marked by '#', passages marked by ' ', path marked by 'X', start/end marked by 'S'/'E'

Sample maze file input:

10 10
1 1
8 8
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 1 0 1 1 1 1 1 1
1 0 1 0 0 0 0 0 0 1
1 0 1 1 0 1 0 1 1 1
1 0 1 0 0 1 0 1 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 1 1 0 1 1 1 1
1 0 1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

1 - denotes walls

0 - traversable passage way

SAMPLE OUTPUT:
##########
#SXX #
# #X######
# #XX #
# ##X# ###
# # X# # #
# # XX #
# ###X####
# # XXXE#
##########

Code

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
public class MazeSolver {
 private char [][] maze = null;
 private BufferedReader br = null;
 private File f;
 private static int startX = 0;
 private static int startY = 0;
 private int endX = 0;
 private int endY = 0;
 private int height = 0;
 private int width = 0;
 public static void main(String[] args) {
 MazeSolver ms = new MazeSolver();
 String fileName = args[0];
 ms.buildMaze(fileName);
 ms.formatMaze();
 if(ms.solve(startX, startY)) {
 ms.printMaze();
 }
 else {
 System.out.println("The maze could not be solved");
 } 
 } 
 /**
 * Populates the 2d maze with the input from the given file
 * @param file
 */
 private void buildMaze(String file) {
 char temp;
 String line = null;
 int count = 1;
 int heightCounter = 0;
 try {
 f = new File(file);
 if(!f.exists() || f.isDirectory()) {
 throw new FileNotFoundException();
 }
 //Read each file line to populate necessary variables and maze coordinates
 br = new BufferedReader(new FileReader(file));
 while((line = br.readLine()) != null) {
 switch (count) {
 case (1):
 width = Integer.parseInt(line.substring(0, line.indexOf(' ')));
 height = Integer.parseInt((line.substring(line.indexOf(' ')+1)));
 maze = new char[height][width];
 break;
 case (2):
 temp = line.charAt(0);
 startY = Character.getNumericValue(temp);
 temp = line.charAt(2);
 startX = Character.getNumericValue(temp);
 break;
 case (3):
 endY = Integer.parseInt(line.substring(0, line.indexOf(' ')));
 endX = Integer.parseInt((line.substring(line.indexOf(' ') +1 )));
 break;
 default:
 int counter = 0;
 for (int i = 0; i < line.length(); i++){
 if(line.charAt(i) != ' '){
 maze[heightCounter][counter] = line.charAt(i);
 counter++;
 }
 }
 heightCounter++;
 break;
 }
 count++;
 }
 }
 catch(FileNotFoundException fnfe) {
 System.out.println("The file : " + f.getName() + " does not exist" );
 fnfe.printStackTrace(); 
 }
 catch(IOException ioe) {
 ioe.printStackTrace();
 }
 catch(ArrayIndexOutOfBoundsException aioob){
 aioob.printStackTrace();
 }
 }
 /**
 * Formats the maze
 * Replaces 1s with '#' and 0s with ' '
 * Also sets start and end values 'S' and 'E'
 */
 private void formatMaze() {
 maze[startX][startY] = 'S';
 maze[endX][endY] = 'E'; 
 for (int i = 0; i < height; i++) {
 for(int j = 0; j < width; j++) {
 if(maze[i][j] == '1') {
 maze[i][j] = '#';
 }
 if(maze[i][j] == '0') {
 maze[i][j] = ' ';
 }
 } 
 } 
 }
 /**
 * Finds the path to the exit by marking each visited point and
 * recursively calling the method with new coordinates until the exit
 * is reached
 * @param i - x coordinate
 * @param j - y coordinate
 * @return - true when maze is solved
 */
 private boolean solve(int i, int j) { 
 if (maze[i][j] == '#') {
 return false;
 }
 if (maze[i][j] == 'E') {
 return true;
 }
 if (maze[i][j] == 'X') {
 return false;
 }
 maze[i][j] = 'X';
 //South
 if ((solve(i + 1, j)) == true) {
 return true;
 }
 //West
 if ((solve(i, j - 1)) == true) {
 return true;
 }
 //East
 if ((solve(i , j + 1)) == true) {
 return true;
 }
 //North
 if ((solve(i - 1 , j)) == true) {
 return true;
 } 
 maze[i][j] = ' ';
 return false;
 }
 /**
 * Prints the solved maze path
 */
 private void printMaze() {
 maze[startX][startY] = 'S';
 for (int i = 0; i < maze.length; i++) {
 System.out.println(maze[i]);
 }
 }
}

Answer 1

Since you specifically talked about the buildMaze method, I'll start there.

While the following test may seem useful : if(!f.exists() || f.isDirectory()) { it's actually already implied by the FileReader so you should skip it.

Don't catch exceptions in the MazeSolver to simply use printStackTrace on them. Let them bubble up until you have a layer that can "deal with them"... in your case, you can deal with them in the main method.

You should also control the validity of the user input as soon as possible, if, for example, the starting position is out of bound you won't detect it before the solve method. Same goes for a starting/ending position that is within a wall.

Also the second case in your switch will give a bad starting position if one of the value is>= 10.

There is multiple pattern in the input. IMO the Scanner (https://docs.oracle.com/javase/8/docs/api/java/util/Scanner.html) class better fits your use case than a loop with a switch as I'll show below.

Lastly, the reader (now a Scanner) must be closed in the code as, otherwise, resources may leak (well, tbh, the file will automatically be closed upon program termination but it's better to use the "clean" way from the start).

There is basically 2 ways to close the reader :

1. by calling explicitly the close method
2. by using a try-with-resource

We won't use the first solution, it's verbose, unpractical when dealing with exceptions and... just booooring ^^

So in the end the code should look like this :

int heightCounter = 0;
try (Scanner sc = new Scanner(file)) {
 width = sc.nextInt(); // this will throw an exception if the next token cannot be parsed as an int
 height = sc.nextInt();
 maze = new char[width][height];
 startX = sc.nextInt();
 startY = sc.nextInt();
 endX = sc.nextInt();
 endY = sc.nextInt();
 sc.nextLine(); // necessary to get rid of the final line-feed
 while (sc.hasNext()) {
 String line = sc.nextLine();
 // same logic than your default case here
 }
 // don't forget to control the start and end position
}

---

Well, let's move to other parts of your code :

You shouldn't set startX and startY to be static. You only use this to be able to call ms.solve(startX, startY)... to avoid this problem, you could give a solve method that takes no parameters and delegates to your "true" solve like this :

public boolean solve() {
 return solve(startX, startY);
}

It's pretty neat because this new solve give a better abstraction ; two birds with one stone basically ^^

Doing your conditions like this : if ((solve(XXXX, YYYY)) == true) { is not useful, you should prefer to simply write if (solve(i + 1, j)) { ;)

On a more general note, there is something that bothers me with your architecture :
the MazeSolver is much more than a simple solver : it actually stores the maze it's trying to solve and it's also responsible with the printing.
It's doing way too much.

For the first part, you should consider moving the grid into it's own Maze class, the buildMaze method can be a static method that returns a new Maze from a given file. The MazeSolver will now solve a given maze like this :

MazeSolver solver = new MazeSolver(Maze.buildFrom(filename));
if (solver.solve()) {
 // print something here....

The Maze may look like this :

public class Maze {
 private char[][] maze;
 private int startX;
 private int startY;
 private int endX;
 private int endY;
 public Maze(final char[][] maze, final int startX, final int startY, final int endX, final int endY) {
 // set the fields here and validates the data
 }
 // getter, setters...
 public static Maze buildFrom(final String filename) throws IOException {
 int heightCounter = 0;
 try (Scanner sc = new Scanner(new File(filename))) {
 int width = sc.nextInt();
 int height = sc.nextInt();
 char[][] maze = new char[width][height];
 int startX = sc.nextInt();
 int startY = sc.nextInt();
 int endX = sc.nextInt();
 int endY = sc.nextInt();
 sc.nextLine(); // necessary to get rid of the final line-feed
 while (sc.hasNext()) {
 String line = sc.nextLine();
 // same logic than your default case here
 }
 return new Maze(maze, startX, startY, endX, endY);
 } catch (InputMismatchException e) {
 throw new IOException("Input cannot be parsed", e);
 }
 }
}

About the second point, the printMaze method also have a problem IMO. MazeSolver shouldn't know about the console... nor it should know anything about printing actually... same goes for the new Mazeobject(s) if you decided to add it.
As such, you should replace this method with a method that gives you a String and it'll be the caller's responsability to do something with the returned string... either printing it to the console as you are already doing (so with a System.out.println) or maybe putting it into a file... or even send it to twitter :P

---

Hope it helps. If you want you can provide an upgraded version of your code in a new question ;)

• Eoin: Thanks for the very detailed response! Some really good stuff in here! I agree with the class being a bit too cluttered. I'll refactor it into something cleaner shortly!