Java Maze Solver (DFS)

I was asked to create a Java program that will navigate through a series of mazes. I would like to know if this is the optimal way of using a DFS or is there a better way and I am doing something wrong?

Example of a Maze File:

10 10
1 1
8 8
1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 0 0 0 0 0
0 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


This file is then converted into a 2DInt array where 0 are empty spaces and 1 is a wall. The maze can wrap around itself too so you can go from one side to another if the space is 0 on either side. 10 10 is the maze size, 1 1 is starting location and 8 8 is ending location.

I have used the Depth-First-Search to solve this maze, here is the code:

MAIN CLASS

  import java.io.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
static Stack<Node> q = new Stack<Node>(); // Stack is used for Depth First Search Algorithm, Queue can be used to
// convert DFS into a Breadth-first search algorithm.

public static void main(String[] args) {
System.out.print("Enter exact maze file location: ");

ArrayList<String> mazeRaw = new ArrayList<String>();
File file = new File(fileLocation);

try {
String st;
while ((st = br.readLine()) != null)
br.close();
} catch (IOException e) {
System.out.println("Error: " + e);
}

Maze testMaze = new Maze(mazeRaw); //2D Int array maze constructor
String[][] results = new String[testMaze.maze2D.length][testMaze.maze2D[0].length];
Node p = solveMaze(testMaze, testMaze.returnStart()); //Node p contains p.parent that hold the path through the maze.

testMaze.printMazeResult(results, p, testMaze.returnStart());

}

public static Node solveMaze(Maze maze, Node start) {
q.push(new Node(start.x, start.y, null)); // Adds the starting coordinates to the stack.
while (!q.isEmpty()) // Until the stack is empty continue loop.
{
Node p = q.pop(); // Get the top element from the Stack and assign it to p

// Valid States //-------------------------------------------------------------------------------//

//If Exit found at coordinates p.x,p.y in 2Dint Array return the p Node.
if (maze.getMaze2D()[p.x][p.y] == 9) {
return p;
}

//If x,y location cannot be wrapped on either ends then check if its sparse for formatting purposes.
if (!isWrappable(maze, p) && isSparse(maze, p)) {
maze.getMaze2D()[p.x][p.y] = -1;
Node nextP = new Node(p.x + 1, p.y, p);
q.push(nextP);
continue;
}

//Check if p node is at the border and if the border wraps around the array in a valid way and make sure that the node parent is not at border to avoid loops
if (isWrappingBorder(maze, p.x, p.y, p) != null && isWrappingBorder(maze, p.parent.x, p.parent.y, p.parent) == null) {
q.push(isWrappingBorder(maze, p.x, p.y, p));
}

// 4 Directional Movements //-------------------------------------------------------------------------------//

// South
if (isFree(maze, p.x + 1, p.y)) {
maze.getMaze2D()[p.x][p.y] = -1;
Node nextP = new Node(p.x + 1, p.y, p);
q.push(nextP);
}

// North
if (isFree(maze, p.x - 1, p.y)) {
maze.getMaze2D()[p.x][p.y] = -1;
Node nextP = new Node(p.x - 1, p.y, p);
q.push(nextP);
}

// West
if (isFree(maze, p.x, p.y + 1)) {
maze.getMaze2D()[p.x][p.y] = -1;
Node nextP = new Node(p.x, p.y + 1, p);
q.push(nextP);
}

// East
if (isFree(maze, p.x, p.y - 1)) {
maze.getMaze2D()[p.x][p.y] = -1;
Node nextP = new Node(p.x, p.y - 1, p);
q.push(nextP);
}
}
return null; // If Maze cannot be solved value null is returned;
}

//This method checks if the coordinates adjacent to the Node p are empty to detect sparse input for formatting purposes
public static boolean isSparse(Maze maze, Node p) {
if (maze.getMaze2D()[p.x][p.y - 1] == 0 && maze.getMaze2D()[p.x + 1][p.y] == 0
&& maze.getMaze2D()[p.x + 1][p.y - 1] == 0 || maze.getMaze2D()[p.x + 1][p.y] == 9)
return true;
else
return false;
}

//Checks if the array can be wrapped around at either ends and direction from the current Node p.
public static boolean isWrappable(Maze maze, Node p) {
if (maze.getMaze2D()[0][p.y] == 0 || maze.getMaze2D()[p.x][0] == 0
|| maze.getMaze2D()[maze.getMaze2D().length - 1][p.y] == 0
|| maze.getMaze2D()[p.x][maze.getMaze2D()[0].length - 1] == 0)
return true;
else
return false;
}

//Detect the point where Array wraps around itself and return a Node that comes out on the other side of the wrapped array
public static Node isWrappingBorder(Maze maze, int x, int y, Node parent) {
Node nextNode;

if (x == 0 && maze.getMaze2D()[x][y] != 1) {
if (maze.getMaze2D()[maze.getMaze2D().length - 1][y] != 1)
return nextNode = new Node(maze.getMaze2D().length - 1, y, parent);
}

if (x == maze.getMaze2D().length - 1 && maze.getMaze2D()[x][y] != 1) {
if (maze.getMaze2D()[0][y] != 1)
return nextNode = new Node(0, y, parent);
}

if (y == 0 && maze.getMaze2D()[x][y] != 1) {
if (maze.getMaze2D()[x][maze.getMaze2D().length - 1] != 1)
return nextNode = new Node(x, maze.getMaze2D().length - 1, parent);
}

if (y == maze.getMaze2D()[0].length - 1 && maze.getMaze2D()[x][y] != 1) {
if (maze.getMaze2D()[x][0] != 1)
return nextNode = new Node(x, 0, parent);
}
return null;
}

//Checks if int x, and int y which are passed from Node.x and Node.y values are valid coordinates
public static boolean isFree(Maze maze, int x, int y) {
if ((x >= 0 && x < maze.getMaze2D().length) && (y >= 0 && y < maze.getMaze2D()[x].length)
&& (maze.getMaze2D()[x][y] == 0 || maze.getMaze2D()[x][y] == 9))
return true;
else
return false;
}

}


MAZE CLASS

 import java.util.ArrayList;
import java.util.Arrays;

public class Maze {
int[][] maze2D; //
private Node start;
private Node end;

public Maze(ArrayList<String> mazeString) {
this.maze2D = new int[(Integer.valueOf(mazeString.get(0).split(" ")[1]))][(Integer
.valueOf(mazeString.get(0).split(" ")[0]))]; // Assign maze size from the file.
start = new Node(Integer.valueOf(mazeString.get(1).split(" ")[1]), Integer.valueOf(mazeString.get(1).split(" ")[0]), null);
end = new Node(Integer.valueOf(mazeString.get(2).split(" ")[1]), Integer.valueOf(mazeString.get(2).split(" ")[0]), null);

for (int i = 0; i < this.maze2D.length; i++) {
for (int n = 0; n < this.maze2D[i].length; n++) {
this.maze2D[i][n] = Integer.valueOf(mazeString.get(i + 3).split(" ")[n]); // i + 3 to offset first 3 lines of text file.
}
}
this.maze2D[start.x][start.y] = 8; // Assign maze start from the file.
this.maze2D[end.x][end.y] = 9; // Assign maze end from the file.
}

@Override
public String toString() {
System.out.println(Arrays.deepToString(this.maze2D));
return (this.maze2D.toString());
}

public Node returnStart()
{
return start;
}

public Node returnEnd() {
return end;
}

public int[][] getMaze2D() {
return maze2D;
}

public void setMaze2D(int[][] maze2d) {
maze2D = maze2d;
}

public void printMazeResult(String[][] results, Node p, Node start) {
Boolean mazeState = false;

for (int i = 0; i < getMaze2D().length; i++) {
for (int j = 0; j < getMaze2D()[i].length; j++) {
switch (maze2D[i][j]) {
case 0:
results[i][j] = " ";
break;
case 1:
results[i][j] = "#";
break;
case -1:
results[i][j] = " ";
break;
case 9:
results[i][j] = "E";
break;
}
}
}

try {
while (p.getParent() != null) {
p = p.getParent();
if (maze2D[p.x][p.y] == 9)
continue;
results[p.x][p.y] = "X";
}
results[start.y][start.x] = "S";
mazeState = true;
} catch (java.lang.NullPointerException e) {
mazeState = false;
}

for (int i = 0; i < results.length; i++) {
for (int j = 0; j < results[i].length; j++) {
System.out.print(results[i][j]);
}
System.out.println();
}

if (mazeState == true)
System.out.println("- Maze has been solved :) -");
else
System.out.println("- Maze is unsolvable -");

}

}


NODE CLASS

import java.util.ArrayList;

public class Node
{
int x;
int y;
Node parent;

public Node(int x, int y, Node parent) {
this.x = x;
this.y = y;
this.parent = parent;
}

public Node() {
this.x = 0;
this.y = 0;
this.parent = null;
}

public Node getParent() {
return this.parent;
}

public String toString() {
return "x = " + x + " y = " + y;
}

}


OUTPUT:

##########
XS#XXXXXXX
#X######
# #XXXX  #
# ## #X###
# #  #X# #
# #  XX  #
# ###X####
# #  XXXE#
##########


API and Reusability

solveMaze takes both a Maze maze and Node start, even though Maze defines a start position already.

The use of the static q Stack means it is not reusable: if a solution is found, then it will remain populated, and interfere with the next run. You can also not reuse Mazes, because solveMaze replaces the empty spaces with -1: it would be much nicer if it did not modify the Maze it is given or, at the very least, reset the Maze once it has finished.

Given you don't use q outside of solveMaze, there is no sense in making it a member of the class, when it could be a local variable, created on demand. It would be nice to see the maze-solving logic in its own class, rather than mixed up with the calling code.

Magic numbers

0, 9, 8, -1... these are all meaningless to anyone who might be trying to use your classes and methods without having first inspected your code. They are a maintainability concern, because changing a 9 in one place has no effect in any of the others, and a find-and-replace for 9 is a nightmare waiting to happen. Much better to use meaningful constant values:

public static final int EmptyCell = 0;
public static final int StartCell = 8;
public static final int EndCell = 9;
public static final int VisitedCell = -1;


You could also hide the implementation details as best as possible. isFree, for example, could be a member of maze. setVisited could be added as a member, so that you can do away with maze.getMaze2D()[p.x][p.y] = -1;.

try ... catch

The try ... catch in main pretty much swallows any exception that might occur while reading the file, and then proceeds to allow the rest of the code to run, as though nothing has gone wrong. I'd prefer that this code printed the exception and stack-trace and then exited cleanly; otherwise, the code that follows after it is likely to fail on the invalid input it will receive, and the original source of the problem will be less apparent.

You should also close the BufferedReader in a finally block, to ensure this unmanaged resource is freed as soon as possible; or, better, use a try-with-resources statement, which make it difficult to misuse the BufferedReader (e.g. by forgetting to close it, or by using it when it has already been closed)

The try ... catch in printMazeResult is rather concerning: it seems that it's purpose is to deal with the case where p is null because solveMaze returned null. This, however, is wholly unclear from the code itself, and the try ... catch is liable to obscure bugs inside the code which are unrelated to whether the maze was or was note solved. You should use an explicit check to determine whether the maze was solved:

Boolean mazeIsSolved = p != null


(this is a better name than mazeState, which sounds like a transient concern)

Wrapping

The 'wrapping' code looks needlessly complicated. I'd be strongly inclined to remove it completely, and instead perform 'wrapping' in the NESW checks (see below).

The wrapping code itself would be much nicer if maze exposed the width and height of the maze, as the code is currently dotted with maze.getMaze2D()[maze.getMaze2D().length - 1], which is just a distraction from its real purpose. Many other places in the code would benefit from such methods also.

I don't think isWrappingBorder is a very good name, since it does a lot more than determine whether it is a wrapping border. It's comment (which would ideally be JavaDoc) also fails to mention that it will return null if it is not a wrapping Border. More importantly, I think it is deficient in the cases where you are against both borders, as it can only return a single value.

The return nextNode = ... theme is confusing: you assign a local variable only to return it immediately. There is no value in the local variable, and you can safely remove it.

NESW movement

Your have basically the same piece of code here four times, just with a different +/- 1: put this in a method, so that there is one reusable version to maintain, and it is easier to follow the logic in solveMaze without worrying about the details. Something like this would work:

static void tryMove(Maze maze, Node p, Stack<Node> q, int dx, int dy) {
// offset and wrap
int x = (p.x + dx + maze.getWidth()) % maze.getWidth();
int y = (p.x + dy + maze.getHeight()) % maze.getHeight();

if (isFree(maze, x, y)) {
maze.getMaze2D()[p.x][p.y] = -1;
Node nextP = new Node(x, y, p);
q.push(nextP);
}
}


Using it is then just a case of:

tryMove(maze, p, q, -1, 0);
tryMove(maze, p, q, +1, 0);
tryMove(maze, p, q, 0, -1);
tryMove(maze, p, q, 0, +1);


The following line appears once for each direction; it should presumably be run even if no move can be made, and doesn't need to be run for each in turn.

maze.getMaze2D()[p.x][p.y] = -1;


Naming

Your naming could be better. q, for example, is pretty meaningless. I guess that Node p stands for 'point'. It's also odd to see x and y as the row and column indices, rather than the other way round (e.g. normally the x-axis is east-west, not north-south).

In some places you use i and j as loop variables, in other i and n: n usually means a count, j is a better choice; however, i and j do not convey all that much; (r)ow and (c)ol would be more meaningful.

Maze constructor

The parameter ArrayList<String> mazeString is not a String, but rather a collection of lines. You might also consider taking the abstract List<String>, rather than requiring the particular derived typed, so that your interface is easier to use.

The following is pretty unreadable, and the line-break is not in a very nice place:

this.maze2D = new int[(Integer.valueOf(mazeString.get(0).split(" ")[1]))][(Integer
.valueOf(mazeString.get(0).split(" ")[0]))];


Instead of trying to squeeze all of that onto one line, break it up:

string[] dimensionData = mazeString.get(0).split(" ");
int width = Integer.valueOf(dimensionData[0]);
int height = Integer.valueOf(dimensionData[1]);

this.maze2D = new int[width][height];


Now it is instantly recognisable what the code is meant to do, and the details are laid out plainly, and without repetition (repeated code is a maintainability concern, as all instances have to kept consistent).

Performance shouldn't be an issue here, but little things like re-splitting whole lines of input for each entry should be avoided, as they can (as in this instance) turn a simple quadratic-complexity operation into a cubic cost, potentially creating problems in seemingly unlikely places:

for (int i = 0; i < this.maze2D.length; i++) {
String[] lineData = mazeString.get(i + 3).split(" "); // i + 3 to offset first 3 lines of text file.

for (int j = 0; j < this.maze2D[i].length; j++) {
this.maze2D[i][j] = Integer.valueOf(lineData[j]);
}
}


More Maze

toString should not be writing out to standard output!

@Override
public String toString() {
System.out.println(Arrays.deepToString(this.maze2D)); // no!
return (this.maze2D.toString());
}


Your setMaze method doesn't make much sense, as it could well disagree with the start and end fields, hopefully leading to a crash down-the-line, but just as likely leading to incorrect operation of the class and a meaningless result.

I also don't like maze2D = maze2d: it's far too easy get wrong. You are also inconsistent with your use of this.maze2D, which would be a better solution here.

Accessibility

You specify private accessors in some places and not in others; generally it's nice to see them everywhere, because it is then unambiguous to the reader that this was the intention (as opposed to 'forgetting' the access modifier, and leaving it as the default), and is nice for people who may not use the language every-day, or may use many languages with different defaults (I, for example - coming from C# - had forgotten the default field accessibility was package (or whatever it is) and not private, which is a very important difference, e.g. in Node...).

Node

x, y, and parent are not private: indeed, you depend on being able to access x and y from outside the class, while you provide a public getter for parent. I would be strongly inclined to make Node immutable, by making all of these fields final. Then you can choose whether to keep x and y as (genuinely) public fields, or make them private (like parent should be) and provide an appropriate getter.

I don't like the repurposing of Node as a Point or Coordinates structure; it's carrying around a null Parent everywhere, which is completely meaningless.

Why does Node() have a default constructor? It is never used, and doesn't look like it produces a meaningful node: I would remove it.

Misc

• Why all the empty-lines in Node?

• Why are returnStart and returnEnd not called getStart and getEnd?

• Why is results a parameter to printMazeResult instead of creating it itself?

• I have no idea what isSparse is meant to achieve.

• Thanks a lot for the advice I will dissect it in full soon I did fix a couple of the stuff you mentioned earlier today. Mar 22, 2019 at 0:48
• I have a problem I don't really know how to go around solving which is what isSparse is suppose to achieve because in an event I get a maze that has a section of it which is empty my code runs through the entire maze instead of taking just 1 path as a result when I print out the result every single node is printed which is useless because its not a path at all it just visits every node possible. isSparse checks if elements around a point are empty and then forces it to run down. Mar 22, 2019 at 0:52
• @MasterChiff that sounds like classic DFS; BFS won't have that problem (it will always find the optimal path), and it won't cost anything more since you are using graph search (e.g. use Queue instead of a Stack as per your comment to that effect) Mar 22, 2019 at 11:30
• I tried but when I used BFS on large mazes It would just go on for hours and I need it to resolve in seconds. Mar 22, 2019 at 12:59
• @MasterChiff if you have implemented it correctly, then the maximum run-time of a graph-search BFS and DFS should be the same (i.e. they only look at each empty cell once; you are setting the visited cell to -1 only after expanding it, which might be creating a situation where you expand outer nodes and exponential number of times, but I've not looked at it too hard). Mar 22, 2019 at 13:24