Java Backtracking Irrgarten Lösung kürzester Weg

[Darlis]

Ok, es hapert an den Grundlagen von Java: else if
http://docs.oracle.com/javase/tutorial/java/nutsandbolts/if.html

Edit: Vielleicht solltest du das Programm anders strukturieren, damit es übersichtlicher wird: Fang mit den den Abbruchkriterien an. Gehe auch davon aus, dass du in eine Wand laufen kannst. Damit hast du 3 Abbruchkriterien. Trifft keines dieser Kriterien zu, sucht du blind in alle Richtungen weiter.

 

[lynxx]

... und Du sollest das Ergebnis eines rekursiven Aufrufs auch übernehmen, also z.B:
gefunden = suche(x,y+1);

 

[convexus]

ich habe mal die bisherigen Empfehlungen in die Source eingebaut. Ich gehe davon aus, dass das Feld von einen Rahmen mit den Zeichen # umgeben ist. Damit spart man sich die Bereichsabfragen. Der initiale Aufruf setzt zudem voraus, dass feld[x][y] == ' ' gilt. Die Source ist nicht getestet.

private boolean ist_frei(char c) {
    return c != '*' && c != '#';
}

private boolean suche(int x, int y) {
    boolean gefunden = x == zielx && y==ziely;
    feld[x][y] = '*';
    if(!gefunden){ 
      if(ist_frei(feld[x][y+1])){
         gefunden = suche(x,y+1);
      }
      else if(ist_frei(feld[x][y-1])){
         gefunden = suche(x,y-1);
      }
      else if(ist_frei(feld[x+1][y])){
        gefunden = suche(x+1,y);
      }
      else if(ist_frei(feld[x-1][y])){
        gefunden = suche(x-1,y);
    }
    if(!gefunden) {
        // backtracking
        feld[x][y] = ' ';
    }
    return gefunden;
  }

 

[Darlis]

Der initiale Aufruf setzt zudem voraus, dass feld[x][y] == ' ' gilt.

Ob dies in der Aufgabenstellung vorausgesetzt ist oder nicht, es ist eine schlechte Strategie. Wenn du bereits auf dem Ziel sitzt, wird das Programm es nicht finden.
Außerdem durchsuchst du auch nur den erstbesten Weg und nicht alle.

Mal das Grundgerüst von meinem Vorschlag:

  private boolean suche(int x, int y) {
  {
    if(x == zielx && y==ziely) {
      // Ziel gefunden
      return true;
    } else if (feld[x][y] == '#') {
      // Autsch, eine Wand
      return false;
    } else if (...) {
      // Hier bin ich auch  nicht richtig
      return false;
    } else {
      // Weitersuchen...

      // ALLE Wege durchsuchen
      // einer wird schon der Richtige sein...
      ...

    }
  }

 

[lynxx]

private boolean suche(int x, int y) {
    boolean gefunden = x == zielx && y==ziely;
    feld[x][y] = '*';
    if(!gefunden){ 
      if(ist_frei(feld[x][y+1])){
         gefunden = suche(x,y+1);
      }
      else if(ist_frei(feld[x][y-1])){
...

Wenn aber feld x, y+1 frei ist wird er ja NIEMALS bei x, y-1 suchen ..

Soweit ich das verstanden habe:
# = Wände
* = Markierter Weg
Leerzeichen = Begehbarer Weg
???

Dann würde ich das so schreiben:

private boolean suche(int x, int y) {
  boolean gefunden = x == zielx && y==ziely;
  if(!gefunden && feld[x][y] == ' ') {
    feld[x][y] = '*';

    gefunden = suche(x,y+1);

    if(!gefunden)
      gefunden = suche(x,y-1);

    if(!gefunden)
      gefunden = suche(x+1,y);

    if(!gefunden)
      gefunden = suche(x-1,y);

    if(!gefunden)
      feld[x][y] = ' ';  // backtracking
  }
  
  return gefunden;
}

Edit: Die Lösung findet aber nicht unbedingt den kürzesten Weg, sondern nur irgendeinen Weg zum Ziel ...

 

[Zerstoerer]

Also bei mir klappt es jetzt. Das Programm war eigentlich schon fertig, das einzigste was geändert werden musste, waren die else if Schleifen zu einer if Abfrage zu schreiben und am Anfang die Start-Ziel Abfrage von && zu || zu ändern.
Nun klappt es.

Trotzdem danke für eure Mühe.

Doch habt ihr noch welche Ideen wie man das mit dem kürzesten Weg machen könnte?

 

[Tumbleweed]

Naja, das Problem ist ja kein Neues.

Stichworte zur Wegfindung, falls du dich weiter damit beschäftigen willst:

http://de.wikipedia.org/wiki/Greedy-Algorithmus
http://de.wikipedia.org/wiki/Bestensuche
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
http://de.wikipedia.org/wiki/A*-Algorithmus

Gerade A* ist da sehr populär.

 

[Zerstoerer]

Ok, ich habe jetzt einen Ansatz. Doch nun eine neue Frage zu Strings:

Wenn ich einen String s habe, wie kann dann den ersten Buchstabe aus diesem String abfragen und dann löschen?

 

[dcobra]

Den debugger wolltest du nicht weshalb ich vermute, dass du folgendes auch überlesen wirst, schade eigentlich

http://docs.oracle.com/javase/6/docs/api/java/lang/String.html
edit: @ drunter: eigentlich dachte ich eher an substring, ist sonst etwas umständlich..

 

[Shagg]

hmm denke mal, wenn es um wege geht, sind standart algorithmen wie hillclimbing oder A* ganz gut geeignet. zb: http://de.wikipedia.org/wiki/Pathfinding

wenn du da genauer suchst, wirst du glaube auch ne fertige implementierung finden.

wegen deiner frage: du kannst den string in ein chararray umwandeln, und dir das erste element angucken, löschen und den rest wieder zu nem string machen. die funktion ist standartmäßig auf strings definiert und heißt toCharArray().