# Weg durch Labyrinth durch Rekursion



## Sumpfmaus (6. Feb 2016)

Hi  !
Ich soll als Hausaufgabe einen rekursiven Algorithmus zur zweidimensionalen Wegﬁndung programmieren. Das Array soll im Test so Aussehen

*char* [][] map = {

{'#', '#', '#', '#', '#'},

{'#', 'S', '#', ' ', ' '},

{'#', ' ', ' ', ' ', '#'},

{'#', ' ', '#', ' ', '#'},

{'#', '#', '#', 'X', '#'}};
S = Startpunkt
# = Wand
. = besucht
X = Ziel
Mein Programm sagt mir, dass kein Weg gefunden werden kann.
Wo ist der Fehler?

```
public class Pathfinder implements Simple {
     privatechar[][] map;
     staticinta,b,c,d;
     public String searchPath(char s, char g) {
          for (int i = 0; i < map.length; i++){
                    for (int j = 0; j < map.length; j++){
                               if (map[i][j] == s){
                                      a = i;
                                    b = j; 
                               }
                                if (map[i][j] == g){
                                    c = i;
                                    d = j;
                               }
                     }
            }
            booleanend = suche(map,a,b);
            if (end){
                  System.out.println(loesung(map));
                  return"Es wurde ein Weg gefunden" ;

           }else{
                    return"kein Weg gefunden";
           }
}

static String loesung (char[][] map){
           String t = "";
           for (int i = 0; i < map.length ; i++ ) {
                  for (int j = 0; j < map.length; j++){
                            t += map[i][j];
                 }
                 t += "\n"; 
          }
          return t;
}

publicstaticboolean suche(char [][] map, int i, int j){
           int rechts = j+1;
           int links = j-1;    
          int unten = i+1;
          int oben = i-1;

          if (i < 0 || i >= map.length || j < 0 || j >= map[i].length){
                return false;
         }
         if (oben < 0 || oben >= map.length || j < 0 || j >= map.length){
               return false;
        }
          if (unten < 0 || unten >= map.length || j < 0 || j >= map.length){
               return false;
         }
          if (i < 0 || i >= map.length || rechts < 0 || rechts >= map.length){
                     return false;
          }
           if (i < 0 || i >= map.length || links < 0 || links >= map.length){
                 return false;
          }
           if (i == c && j ==d){ // Stelle X
                return true;  
          }
          else{
                if (map[i][rechts]==' '){
                         map[i][rechts]= 'r';
                          if(suche(map,i,rechts)){
                                   return true;
                          }
               }
                if (map[oben][j]==' '){
                          map[oben][j]='o';
                           if(suche(map,oben,j)){
                                   return true;
                           }
                 }
                 if (map[unten][j]==' '){
                           map[unten][j]='u';
                           if(suche(map,unten,j)){
                                     returntrue;
                           }
                  }
                  if (map[i][links]==' '){
                          map[i][links]='l';
                           if(suche(map,i,links)){
                                    return true;
                          }
                 }
        }
         return false;
}

publicvoid setMap(char[][] map) {
this.map = map;
}
}
```

Wäre schön wenn mir jemand helfen könnte 
_

_


----------



## Meniskusschaden (6. Feb 2016)

Ich habe es mir nur flüchtig angesehen. Auffällig finde ich, dass du in der Methode `suche(...)` zunächst prüfst, ob eines der Nachbarfelder von (i, j) ausserhalb des Spielfelds liegt. Falls das so ist verlässt du die Methode mit `return false;`. Die Prüfung, ob (i, j) bereits das Ziel ist, kommt erst danach und wird demzufolge nie erreicht, wenn das Zielfeld ein Randfeld ist.


----------

