I've been trying to make a program that could solve a maze recursively. But I have an issue with my recursion in my algorithm method. The algorithm can only solve as far as one position for the solution.
Here's it on console:
Note "char indicators" for the 2D array:
- '*' = walls
- '#' = start
- '$' = end
- ' ' = possible path/not a wall
- '@' = path
- '~' = deadend
Desired output:
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ ~ ~ * @ * *
* @ @ @ * ~ * @ * *
* * * ~ ~ ~ * @ * *
* * ~ ~ * ~ * @ * *
* * ~ ~ * ~ * @ ~ *
* * * * * * * @ ~ *
* ~ ~ ~ ~ ~ ~ @ $ *
* * * * * * * * * *
Output I get:
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
* * * * * * * * * *
* # * * * * * * * *
* @ * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
I've tried other solutions such as removing the recursion within the recursion within my general case but that just regressed the minor progress that my algorithm could do (which is find one position). I was wondering what else I could do instead to fix this problem? The other methods work but the method "algorithm" doesn't work like how I would like it to work.
import java.util.*;
public class maze {
public static void main(String[] args) {
allocateMaze();
}
public static void allocateMaze() {
char[][] mazeArr = {{'*','*','*','*','*','*','*','*','*','*'},//0
{'*','#','*','*','*','*','*','*','*','*'},//1
{'*',' ','*',' ',' ',' ',' ',' ','*','*'},//2
{'*',' ','*',' ',' ',' ','*',' ','*','*'},//3
{'*',' ',' ',' ','*',' ','*',' ','*','*'},//4
{'*','*','*',' ',' ',' ','*',' ','*','*'},//5
{'*','*',' ',' ','*',' ','*',' ','*','*'},//6
{'*','*',' ',' ','*',' ','*',' ',' ','*'},//7
{'*','*','*','*','*','*','*',' ',' ','*'},//8
{'*',' ',' ',' ',' ',' ',' ',' ','$','*'},//9
{'*','*','*','*','*','*','*','*','*','*'}};//10
//setting row and col to 0 for display method
int row = 0;
int col = 0;
System.out.println("Presolved maze:");
displayMaze(mazeArr, row, col); //displays presolved maze
row = 1;
col = 1;
boolean isSolved = false;
System.out.println("\nMaze solution:");
algorithm(mazeArr, row, col, isSolved); //create variable for solved maze, sends maze allocation to method that solves the maze
System.out.println();
row = 0;
col = 0;
displayMaze(mazeArr, row, col); //displays traced solved maze
}
public static void displayMaze(char[][] mazeArr, int row, int col) {
if (row < mazeArr.length) { //iterate through all (11) rows
if (col < mazeArr[row].length) { //iterate through all (11) columns
System.out.print(mazeArr[row][col] " "); //displays the current index in the array
displayMaze(mazeArr, row, col 1); //repeats this method by iterating through the columns first
return;
}
System.out.println(); //enters the line after each row for display purposes
displayMaze(mazeArr, row 1, col=0); //repeats this method by iterating through the rows
}
}
public static char[][] algorithm(char[][] mazeArr, int row, int col, boolean isSolved){
boolean isPath = false; // assume there is no path
if (mazeArr[row][col] == '$' && isSolved == true) { // IF MAZE IS COMPLETELY SOLVED
return mazeArr;
} else { // IF MAZE IS NOT COMPLETELY SOLVED
if (isSolved == false && isPath == false) { // start searching thru the maze, assume there is no path
// THERE IS NO DEAD END
if (mazeArr[row - 1][col] == ' ') { // if north has a path
mazeArr[row - 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row--, col, isSolved); // repeat process going to next north spot
}
if (mazeArr[row][col 1] == ' ') { // if east has a path
mazeArr[row][col 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, col , isSolved); // repeat process going to next east spot
}
if (mazeArr[row 1][col] == ' ') { // if south has a path
mazeArr[row 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row , col, isSolved); // repeat process going to next south spot
}
if (mazeArr[row][col - 1] == ' ') { // if west has a path
mazeArr[row][col - 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, col--, isSolved); // repeat process going to next west spot
}
if (mazeArr[row][col] == '$') { // if you have reached the end of the maze
isSolved = true; // maze has been solved
return algorithm(mazeArr, row, col, isSolved); // algorithm will recognize
}
} else { // finds alternate path if there's a dead end
if (mazeArr[row][col] != '#') {
mazeArr[row][col] = '~'; //indicates that this index is a dead end
}
if (isPath == false) {
if (mazeArr[row - 1][col] == '@' && mazeArr[row - 1][col] != '#') { // if north was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, row--, col, isSolved); //returns to initial position before hitting dead end
}
}
if (isPath == false) {
if (mazeArr[row][col 1] == '@' && mazeArr[row][col 1] != '#') { // if east was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, row, col , isSolved); //returns to initial position before hitting dead end
}
}
if (isPath == false) {
if (mazeArr[row 1][col] == '@' && mazeArr[row 1][col] != '#') { // if south was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, row , col, isSolved); //returns to initial position before hitting dead end
}
}
if (isPath == false) {
if (mazeArr[row][col-1] == '@' && mazeArr[row][col-1] != '#') { // if west was a path
isPath = true;
return algorithm(mazeArr, row, col--, isSolved); //returns to initial position before hitting dead end
}
}
if (isPath == false) { // if there's no way out, that means there is no solution
System.out.println("No Solution");
return mazeArr;
}
}
return mazeArr;
}
}
}
CodePudding user response：
You need to put the or -- before row or col on when you recall algorithm(). When one of these comes after a variable, the variable gets incremented, but not the value that comes out:
public class Test {
public static void main(String[] args) {
int x = 5;
int y = x ;
System.out.println(x " " y);
}
}
gives
6 5
Above x incremented x, but y was set to value of x before. To fix it put the increment before the variable, like row:
public class Test {
public static void main(String[] args) {
int x = 5;
int y = x;
System.out.println(x " " y);
}
}
output:
6 6