Search A Maze For Any Path

Once we model a maze as a graph where each node can have up to 4 edges, we can search for a path in a maze using depth first or breadth first search.

Table of Contents

Code Sample

/*
Authorship: All credit for the code in this file goes to the authors of the
book "Elements of Programming Interviews" by Adnan Aziz, Amit Prakash, and
Tsung-Hsien Lee.
I have just added explanatory comments, reformatted the code, & changed
variable names for understanding.
The video to explain this code is here: https://www.youtube.com/watch?v=W9F8fDQj7Ok
*/
/*
Black cells are walls. We cannot "walk" on them.
White cells are traversable. We can "walk" on white cells.
*/
public static enum Color { WHITE, BLACK }
/*
A standard coordinate to represent a cell in the maze with
an row and col position.
*/
public static class Coordinate {
public int row, col;
public Coordinate (int row, int col) {
this.row = row;
this.col = col;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Coordinate that = (Coordinate) o;
if (row != that.row || col != that.col) {
return false;
}
return true;
}
@Override
public int hashCode() {
return Objects.hash(row, col);
}
}
/*
This is the driver function. It will return the path that we find as
a list of Coordinate objects.
*/
public static List<Coordinate> searchMaze(List<List<Color>> maze,
Coordinate start, Coordinate end) {
/*
This will hold the path.
*/
List<Coordinate> path = new ArrayList<>();
/*
Flip the item start position to black. We will start the search
from here.
Add the coordinate to the start of the path. It is our literal start
*/
maze.get(start.row).set(start.col, Color.BLACK);
path.add(start);
/*
If we do not find a path then remove the start node we added to the
path and return an empty list down below
*/
if (!hasPathToEnd(maze, start, end, path)) {
path.remove(path.size() - 1);
}
/*
If we DO find a path, the 'path' variable will have all nodes in the
path from start to end, otherwise it will be an empty list
*/
return path;
}
/*
A standard DFS for the path that we want to find.
*/
private static boolean hasPathToEnd(
List<List<Color>> maze,
Coordinate node,
Coordinate end,
List<Coordinate> path
) {
if (node.equals(end)) {
return true;
}
/*
SHIFTS codifies different shifts.
Indexes:
0 1
{rowDelta, colDelta}
*/
final int[][] SHIFTS = {
{0 , 1}, // going right
{1, 0}, // going down
{0, -1}, // going left
{-1, 0} // going up`
};
/*
We:
1.) Apply each shift. next is the coordinate that is next to process according
to the shift we are on
*/
for (int[] shift : SHIFTS) {
/*
The next item to possibly add to our path and search
*/
Coordinate next = new Coordinate(node.row + shift[0], node.col + shift[1]);
/*
Can this item be walked on?
*/
if (canTraverse(next , maze)) {
// Yes. Set it to black and add it to the path
maze.get(next.row).set(next.col, Color.BLACK);
path.add(next);
/*
Can we finish a path from here now, recurse and find out. If we can
we will bubble up the result and this Coordinate will be in the path.
*/
if (hasPathToEnd(maze, next, end, path)) {
return true;
}
/*
Sadly...things didn't work out, walking from this cell we cannot complete
a path. We remove the Coordinate from the path and continue the loop trying
to root ourselves at a new "next" position in the path
*/
path.remove(path.size() - 1);
}
}
/*
No 'next' Coordinates worked from this Coordinate. Return false to our
caller. Path not possible, caller will have to keep searching.
*/
return false;
}
/*
Validates a given cell, it ensures it is in the maze and is white (can
be "walked on")
*/
private static boolean canTraverse(Coordinate node, List<List<Color>> maze) {
return node.row >= 0 && node.row < maze.size() &&
node.col >= 0 && node.col < maze.get(node.row).size() &&
maze.get(node.row).get(node.col) == Color.WHITE;
}
view raw SearchAMaze.java hosted with ❤ by GitHub