Maze 2D Rekursiver Algorithmus Sackgassenproblem

Ich habe versucht, ein Programm zu erstellen, das ein Labyrinth rekursiv lösen kann (sollte für jedes Labyrinth funktionieren). Der Großteil der Rekursion für den Algorithmus funktioniert, aber wenn das Labyrinth nach Sackgassen und einer Möglichkeit zur Umleitung sucht, um die Lösung (Endpunkt) zu finden, funktioniert der Code nicht dafür. Ich habe mehrere Möglichkeiten zum Debuggen ausprobiert, aber es hat mich nicht weit gebracht; Ich erhalte entweder StackOverflowError oder der Algorithmus arbeitet, um eine Position zurückzuverfolgen.

Beachten Sie "Zeichenindikatoren" für das 2D-Array:

• '*' = Wände


• '#' = beginnen


• '$' = Ende


• ' ' = möglicher Weg/keine Wand


• '@' = Pfad


• '~' = Sackgasse

Gewünschte Ausgabe:

Presolved maze:
* * * * * * * * * * 
* # * * * * * * * * 
* * * * 
* * * * * 
* * * * * 
* * * * * * 
* * * * * * 
* * * * * 
* * * * * * * * 
* $ * 
* * * * * * * * * * 
Maze solution:
* * * * * * * * * * 
* # * * * * * * * * 
* @ * @ @ @ @ @ * * 
* @ * @ ~ ~ * @ * * 
* @ @ @ * ~ * @ * * 
* * * ~ ~ ~ * @ * * 
* * ~ ~ * ~ * @ * * 
* * ~ ~ * ~ * @ @ * 
* * * * * * * ~ @ * 
* ~ ~ ~ ~ ~ ~ ~ $ * 
* * * * * * * * * *

Hier ist der Code für denjenigen, der nur um eine Position zurückgeht:

In dieser Version habe ich versucht, rekursiv zu rufen, nachdem ich eine Position gefunden hatte, die zurückverfolgt werden konnte, und diese Position zurückzugeben, um sie zurückzuverfolgen und die Lösung zu finden

import java.util.*;
public class mazeOG {
 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
 
 // 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
 }
 // 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 - 1][col] == '@' && 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 - 1][col]!= '#') {// if west 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 there's no way out, that means there is no solution
  System.out.println("No Solution"); 
  return mazeArr;
 }
 
 return mazeArr;
 }
 }
}

Ausgabe für diese Version:

Presolved maze:
* * * * * * * * * * 
* # * * * * * * * * 
* * * * 
* * * * * 
* * * * * 
* * * * * * 
* * * * * * 
* * * * * 
* * * * * * * * 
* $ * 
* * * * * * * * * * 
Maze solution:
No Solution
* * * * * * * * * * 
* # * * * * * * * * 
* @ * @ @ @ @ @ * * 
* @ * @ * @ * * 
* @ @ @ * * @ * * 
* * * * @ * * 
* * * * @ * * 
* * * * @ @ * 
* * * * * * * @ @ * 
* ~ @ @ @ @ @ @ $ * 
* * * * * * * * * * 

Hier ist der Code für die Version, die StackOverflowError erhält:

In dieser Version habe ich den Abschnitt des Codes entfernt, der eine Position zurückverfolgt und rekursiv aufruft. Stattdessen gebe ich nur an, dass diese Position eine Sackgasse ist, und rufe stattdessen rekursiv den Algorithmus auf, um nach der nächsten Position zu suchen.

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
 // 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
 }
 //code from here and below is for the case of a dead end
 if (mazeArr[row][col]!= '#' && isPath == false) {
 mazeArr[row][col] = '~'; // indicates that this index is a dead end
 isPath = true;
 isSolved = false;
 return algorithm(mazeArr, row, col, isSolved);
 }
 if (isPath == false) { // if there's no way out, that means there is no solution
 System.out.println("No Solution");
 return mazeArr;
 }
 return mazeArr;
 }
 }
}

Jede Hilfe wäre wirklich toll! Danke:)

Lösung des Problems

Es gibt mehrere Probleme, darunter:

• Eine Sackgasse sollte keinen neuen rekursiven Aufruf auslösen. Die Sackgassenmarkierung sollte beim Zurückverfolgen von der Rekursion erfolgen und sollte dem Aufrufer anzeigen, dass es keinen Erfolg gab.




• Jede der ifAnweisungen, die eine bestimmte Richtung prüfen (Norden usw.), führt ein returnin ihrem Block aus, was bedeutet, dass, wenn es eine solche Richtung gibt, keine der anderen Richtungen versucht wird.




• Da der rekursive Aufruf nicht zurückgibt, ob es erfolgreich war oder nicht, hat der Aufrufer keine Möglichkeit zu wissen, ob er es in einer anderen Richtung versuchen sollte

Nicht das Problem, aber:

• Es gibt auch einige Codewiederholungen, die Sie vermeiden sollten.


• Es gibt keinen guten Grund, die Anzeigefunktion rekursiv zu machen. Iterieren Sie einfach mit zwei forSchleifen über die Zellen


• Vermeiden Sie rowund colVariablen in Ihrem Hauptprogramm: Diese sollten dort nichts zu suchen haben.


• Wenn Sie das Labyrinth mutieren, sollte es nicht notwendig sein, dieses Labyrinth auch zurückzugeben. Der Anrufer hat nach dem Anruf auf jeden Fall Zugang zu dem bevölkerten Labyrinth.


• Der Code wird einfacher, wenn Sie die Suche nach dem Startpunkt ( #) vom Rest des Algorithmus trennen.

Einer der Schlüssel zu einer erfolgreichen Funktion ist, dass sie einen booleschen Wert zurückgibt, der angibt, ob der Pfad gefunden wurde oder nicht. Auf diese Weise kann der Algorithmus entscheiden, ob er es noch einmal in einer anderen Richtung versuchen soll oder nicht.

Hier ist die Änderung Ihres Codes:

import java.util.*;
public class Main {
 public static void main(String[] args) {
 char[][] mazeArr = { 
 { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
 { '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
 { '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
 { '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
 { '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
 { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
 { '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
 { '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
 { '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
 { '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
 { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
 System.out.println("Input maze:");
 displayMaze(mazeArr);
 
 System.out.println("\nMaze solution:");
 boolean isSolved = algorithm(mazeArr);
 if (isSolved) {
 displayMaze(mazeArr);
 } else {
 System.out.println("No Solution");
 }
 }
 public static void displayMaze(char[][] mazeArr) {
 for (char[] row: mazeArr) {
 for (char cell: row) {
 System.out.print(cell + " ");
 }
 System.out.println();
 }
 }
 public static boolean algorithm(char[][] mazeArr) {
 // Look for starting point
 for (int row = 0; row < mazeArr.length; row++) {
 for (int col = 0; col < mazeArr[0].length; col++) {
 if (mazeArr[row][col] == '#') {
  return algorithm(mazeArr, row, col);
 }
 }
 }
 return false; // No starting point found
 }
 public static boolean algorithm(char[][] mazeArr, int row, int col) {
 if (mazeArr[row][col] == '$') { // Found the target
 return true;
 }
 if (mazeArr[row][col] == ' ') {
 mazeArr[row][col] = '@'; // Mark as visited
 } else if (mazeArr[row][col]!= '#') { // Not allowed
 return false;
 }
 // The core of the algorithm: try each direction until true is returned
 if (algorithm(mazeArr, row, col - 1) // west
 || algorithm(mazeArr, row - 1, col) // north
 || algorithm(mazeArr, row, col + 1) // east
 || algorithm(mazeArr, row + 1, col) // south
 ) {
 return true; // Path found
 }
 if (mazeArr[row][col] == '@') { // mark backtracking
 mazeArr[row][col] = '~';
 }
 return false;
 }
}