user3390133
Reputation: 21
Maze Solver problems in Java
I have now got it to stop repeating infinitely, but it just keeps trying the same wrong path over and over again. Does anyone know of a way to get it to try different paths?
Key for the numbers: 0 is open 1 is a wall 2 is part of the path 3 is the end of the maze
public class Maze{
public static void main(String[] args){
int[][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
{1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1},
{1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
{1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1},
{1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1},
{1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
{1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1},
{1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1},
{1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
{1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
{1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
{1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1},
{1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1},
{1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1},
{1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1},
{1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1},
{1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
{1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1},
{1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1},
{1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1},
{1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
{1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1},
{1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
{1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1},
{1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1},
{1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1},
{1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
{1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}};
boolean[][] posCheck = new boolean[maze.length][maze[0].length];
int r = 0;
int c = 0;
for(int row = 0; row < maze.length; row++){
for(int col = 0; col < maze[row].length; col++){
if(maze[row][col]==0){
r = row;
c = col;
}
}
}
maze[r][c] = 3;
mazeSolver(1, 0, maze, posCheck);
}
public static boolean mazeSolver(int r, int c, int[][]maze, boolean[][] posCheck){
posCheck[r][c] = true;
maze[r][c] = 2;
if(maze[r][c] == 3){
print(maze);
return true;
}
if((c+1 < maze.length) && maze[r][c+1]==0 && !posCheck[r][c+1] && (mazeSolver(r, c + 1, maze, posCheck))){
maze[r][c] = 2;
return true;
}
if((r-1 >= 0) && maze[r-1][c]==0 && !posCheck[r-1][c] && (mazeSolver(r - 1, c, maze, posCheck))){
maze[r][c] = 2;
return true;
}
if((c-1 >= 0) && maze[r][c-1]==0 && !posCheck[r][c-1] && (mazeSolver(r, c - 1, maze, posCheck))){
maze[r][c] = 2;
return true;
}
if((r+1 < maze.length) && maze[r+1][c]==0 && !posCheck[r+1][c] && (mazeSolver(r + 1, c, maze, posCheck))){
maze[r][c] = 2;
return true;
}
print(maze);
return false;
}
public static void print(int[][] maze){
for(int row = 0; row<maze.length; row++){
for(int col = 0; col<maze[row].length; col++)
System.out.print(maze[row][col]);
System.out.println();
}
}
}
Upvotes: 0
Views: 358
Answers (3)
onesixtyfourth
Reputation: 866
http://www.astrolog.org/labyrnth/algrithm.htm http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap
I have recently been writing a maze application and found the above sites extremely useful in gaining an understanding of the concepts. I created classes to represent Maze, Cell & edge to the graph as a collection of Cells (nodes) & Edges. At one point I also had a problem with not completing a search for a path & required better management of which cells had already been visited. I was repeatedly going back into a dead end as my algorithm didn't track that the Cell had already been visited. This sounds very similar to your problem.
Upvotes: 1
aliteralmind
Reputation: 20163
I have added debugging output to every branch in your mazeSolver function. As you can see, no branch is ever being called, because the recursive call in the third if-block never finishes evaluating. It therefore is an infinite recursion, which is the cause of the StackOverflowError. It also shows that it is bouncing back and forth between only two different values, which is likely a problem.
You need to determine what your mazeSolver is actually doing--why that infinite recursion is never unrolling, and change it so one of the other conditions are met.
In other words, you need to fix your "recursion terminator", and figure out why no values other than [1, 1] and [0, 1] are being passed.
public static boolean mazeSolver(int r, int c, int[][] maze){
System.out.println("mazeSolver(" + r + ", " + c + ", maze)");
if(maze[r][c] == 3) {
System.out.println(" Equals 3 -- return true");
return true;
} else if((c+1 < maze.length) && maze[r][c+1]==0 && (mazeSolver(r, c + 1, maze))) {
maze[r][c] = 2;
System.out.println(" Set to 2 (a) -- return true");
return true;
} else if((r-1 >= 0) && maze[r-1][c]==0 && (mazeSolver(r - 1, c, maze))) {
maze[r][c] = 2;
System.out.println(" Set to 2 (b) -- return true");
return true;
}
System.out.println(" Between first and second if-block");
if((c-1 >= 0 && maze[r][c-1]==0) && (mazeSolver(r, c - 1, maze))) {
maze[r][c] = 2;
System.out.println(" Set to 2 (c) -- return true");
return true;
}
System.out.println(" Between second and third if-block");
if((r+1 < maze.length) && maze[r+1][c]==0 && (mazeSolver(r + 1, c, maze))){
maze[r][c] = 2;
System.out.println(" Set to 2 (d) -- return true");
return true;
}
System.out.println(" return false");
return false;
}
}
Output:
[R:\jeffy\programming\sandbox\xbnjava]java Maze
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
...and on and on...
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
Between first and second if-block
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.SingleByte.withResult(Unknown Source)
at sun.nio.cs.SingleByte.access$000(Unknown Source)
at sun.nio.cs.SingleByte$Encoder.encodeArrayLoop(Unknown Source)
at sun.nio.cs.SingleByte$Encoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
at sun.nio.cs.StreamEncoder.write(Unknown Source)
at java.io.OutputStreamWriter.write(Unknown Source)
at java.io.BufferedWriter.flushBuffer(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at java.io.PrintStream.print(Unknown Source)
at java.io.PrintStream.println(Unknown Source)
at Maze.mazeSolver(Maze.java:64)
at Maze.mazeSolver(Maze.java:82)
at Maze.mazeSolver(Maze.java:69)
at Maze.mazeSolver(Maze.java:82)
at Maze.mazeSolver(Maze.java:69)
at Maze.mazeSolver(Maze.java:82)
at Maze.mazeSolver(Maze.java:69)
at Maze.mazeSolver(Maze.java:82)
at Maze.mazeSolver(Maze.java:69)
at Maze.mazeSolver(Maze.java:82)
at Maze.mazeSolver(Maze.java:69)
at Maze.mazeSolver(Maze.java:82)
at Maze.mazeSolver(Maze.java:69)
at Maze.mazeSolver(Maze.java:82)
...and on and on...
Upvotes: 3
Marsh
Reputation: 8125
You need to keep track of which positions you have already visited. A simple method would be to have a 2d boolean array of the same size as your maze, and to mark a position as true when your recursive method first hits it. In addition to your wall check, you'll want to add an wasVisited check.
Upvotes: 1
Related Questions
- Maze Recursion Code Finishes Maze but Returns Errors
- Recursive Maze Solver method Issue
- Java Recursive Maze Solver problems
- Java maze solving issue
- maze solver using recursion
- Recursive Maze Solving Method
- Solving Maze with Recursion java
- Solving a maze recursively
- Recursion with maze solver
- Java solving a maze with recursion problem