I have tried to code a depthfirstsearch algorithm to solve a maze. This is what I have so far. I have tried to add as much detail so the logic is understandable:
//Upgraded dfs algorithm that creates an array of nodeclass objects
package depthfirstsearch;
public class DepthFirstSearch {
public static void main(String[] args) {
int[][] stateArr =
{
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 2, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0},
{0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0},
{0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0},
{0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0},
{0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0},
{0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0},
{0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
//Maze array declaration
int mazeRows = stateArr.length;
int mazeCols = stateArr[0].length;
//Creates an array of NodeClass objects
NodeClass[][] mazeArr = new NodeClass[mazeRows][mazeCols];
//Assigning values to the nodes (state, isPath, coords)
for(int i = 0; i < mazeRows; i++)
{
for(int j = 0; j < mazeCols; j++)
{
int state = stateArr[i][j];
mazeArr[i][j] = new NodeClass(i, j, state); //Assigning coordinates & state (wall, path) to the node
} //End of col for-loop
} //End of row for-loop
//Currently have an array of nodes with coordinates, state and isPath = false
NodeClass currentNode = mazeArr[1][1]; //This is the node we'll be working with. Assigned the value of the starting node at position (1;1)
while(currentNode.getState() != 3) //3 Indicates the end of the maze. While we haven't reached the end
{
//Getting the position of the current node
int row = currentNode.getNodeRow();
int col = currentNode.getNodeCol();
System.out.println("Run");
System.out.println(currentNode);
//We'll be taking the currentNode and checking every unchecked adjacent node:
//Check up
if((mazeArr[row-1][col].getState() == 1 || mazeArr[row-1][col].getState() == 3) && (mazeArr[row-1][col].haveTried() == false))
{
//Storing the parent node:
NodeClass temp = currentNode; //Stores the current node as the node temp
mazeArr[row-1][col].setParentNode(temp); //Stores the current node as the parent node the new checked node
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(true); //Considers the current node as a potential path
currentNode = mazeArr[row-1][col]; //The new current node is the node above the original node
System.out.println("Up"); //We moved up
}
//Check right
else if((mazeArr[row][col+1].getState() == 1 || mazeArr[row][col+1].getState() == 3) && (mazeArr[row][col+1].haveTried() == false))
{
//Storing the parent node:
NodeClass temp = currentNode; //Stores the current node as the node temp
mazeArr[row-1][col].setParentNode(temp); //Stores the current node as the parent node the new checked node
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(true); //Considers the current node as a potential path
currentNode = mazeArr[row][col+1]; //The new current node is the node above the original node
System.out.println("Right"); //We moved right
}
//Check down
else if((mazeArr[row-1][col].getState() == 1 || mazeArr[row-1][col].getState() == 3) && (mazeArr[row-1][col].haveTried() == false))
{
//Storing the parent node:
NodeClass temp = currentNode; //Stores the current node as the node temp
mazeArr[row-1][col].setParentNode(temp); //Stores the current node as the parent node the new checked node
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(true); //Considers the current node as a potential path
currentNode = mazeArr[row][col+1]; //The new current node is the node above the original node
System.out.println("Down"); //We moved down
}
//Check left
else if((mazeArr[row][col-1].getState() == 1 || mazeArr[row][col-1].getState() == 3) && (mazeArr[row][col-1].haveTried() == false))
{
//Storing the parent node:
NodeClass temp = currentNode; //Stores the current node as the node temp
mazeArr[row-1][col].setParentNode(temp); //Stores the current node as the parent node the new checked node
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(true); //Considers the current node as a potential path
currentNode = mazeArr[row][col+1]; //The new current node is the node above the original node
System.out.println("Left"); //We moved left
}
//If there are no paths left: we reached a dead end and need to back track
else
{
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(false); //Since it's a dead end, we remove it from the potential solution
currentNode = mazeArr[row][col].getParentNode(); //Sets the current node as the previous node
}
} //End of while-loop for fining the solution
System.out.println("Yay yay, we did it!");
} //End of main method
} //End of DepthFirstSearch Class
The issue is, I am getting an error message: Exception in thread "main" java.lang.NullPointerException: Cannot invoke "depthfirstsearch.NodeClass.getState()" because "currentNode" is null
I printed the currentNode node but I found that it was, in fact, not null. What could be the problem? I would appreciate any tips. Thank you.
First, you're debugging at the wrong spot. The error occurs in the while condition, so if you want to see that currentNode is null, you'd print it just before that condition gets evaluated, i.e. at the very end of the loop's body.
The immediate cause is that getParentNode() returns null at the first iteration of the loop. This is odd, because that part of the code -- the final else block -- is not supposed to execute that early in the search process. And yes, there is no parent when you are only starting the search from the very first node at coordinate 1, 1.
The real cause is that your blocks of code that deal with the 4 different neighbors have several errors. There is a mix of row-1, row+1, col-1 and col+1 that doesn't make sense. Only the first block (for going up) is correct, all the others have inconsistencies, and the one for going down is the worst: none of the neighbor references are pointing at the down neighbor! When you correct all those inconsistencies (really do a thorough check!) it will work.
A way to make such errors less likely, is to avoid code repetition and deal with the four directions in a loop, making the addition to row and col dynamically determined by the loop variable. Here is how that could look for your main loop:
while (currentNode.getState() != 3)
{
int row = currentNode.getNodeRow();
int col = currentNode.getNodeCol();
currentNode.setTried(true);
int side;
for (side = -1; side < 3; side++) {
int nextRow = row + side % 2;
int nextCol = col + (side - 1) % 2;
NodeClass neighbor = mazeArr[nextRow][nextCol];
int state = neighbor.getState();
if ((state == 1 || state == 3) && !neighbor.haveTried()) {
neighbor.setParentNode(currentNode);
currentNode.setIsPath(true);
currentNode = neighbor;
break;
}
}
if (side == 3) { // No neighbor available
currentNode.setIsPath(false);
currentNode = currentNode.getParentNode();
}
}
NB: I assume that your grid will always have a wall at the outer boundaries, as is the case in your example. If not, you'll need to check whether the coordinates are still in range of the grid.