Invertierte Rekursion???

[nik.stffrs]

Moin,
Ich habe weiß nicht so recht ob mein Titel stimmt aber mir fällt echt keine bessere Überschrift für mein Problem ein (schlagt gerne was vor, dann ändere ich sie dementsprechend). So jetzt zu meinem Problem. Ich habe Letztens (gestern) ein Pathfindingprogramm geschrieben. Dieses wollte ich noch weiter verbessern und mir wurde empfohlen mir mal den A* Algorithmus anzugucken. Also gut Wikipedia-Artikel gelesen erstmal nichts verstanden, nochmal gelesen und nochmal und nochmal... Also es hat nen Weilchen gedauert aber jetzt versteh ich wie der funktionieren soll (ich meine es zumindest). Erstmal für die, die den Algorithmus nicht kennen. Dieser dient dazu den schnellsten Weg zu einem Ziel zu finden. In meinem Fall habe ich mit einem kleinen 2 dimensionalem Array eine kleine Map erstellt. Für die Koordinaten habe ich eine Klasse erzeugt, die Coordinate Klasse. "Der Algorithmus schreibt vor" , dass die einzelnen Koordinaten des Weges einen Verweis auf die Koordinate haben, von der der Algorithmus kommt (Ist schwer zu erklären, wen's näher interessiert, kann den Wikipedia-Artikel nur empfehlen). So jedenfalls hat wie gesagt jede Koordinate einen Verweis auf die vorige Koordinate. Jetzt habe ich eine Start Koordinate. Das was jetzt kommt ist echt schwer zu erklären aber ich gebe mein Bestes. Angenommen ich habe eine Koordinate c. Der beste Weg zu dieser Koordinate ist dem Algorithmus bereits bekannt. Das heißt sozusagen, dass die vorherige Koordinate von c bekannt ist und die vorherige Koordinate der vorherigen Koordinate von c auch, usw. Jetzt möchte ich diesen Spaß solange betreiben bis meine vorherige Koordinate der Startposition entspricht. Zum besseren Verständniss:

c.getPreviousCoordinate().getPreviousCoordinate().getPreviousCoordinate…….

Dieses getPreviousCoordinate() möchte ich solange ausführen bis die previousCoordinate der Start Koordinate entspricht. Die Frage ist nur wie krieg ich das hin ?? Ich muss das ganze ja sozusagen in einen loop packen bis die previousCoordinate der previousCoordinate der previousCoordinate blablabla der Startposition entspricht. Warum jetzt der Titel "invertierte Rekursion"? Also als ich an so einen loop gedacht habe ist mir aus irgendeinem Grund sofort dieser Begriff ins Hirn geschossen. Da mir kein besserer Titel eingefallen ist habe ich jetzt einfach den genommen. Ich stehe momentan komplett aufm Schlauch und vielleicht denke ich auch einfach nur viel zu kompliziert und merkwürdig??
Ich hoffe Ich habs hingekriegt das Problem halbwegs zu beschreiben.
Vielen Dank für eure Hilfe!

 

[Xyz1]

Der beste Weg zu dieser Koordinate ist dem Algorithmus bereits bekannt

Neee der kennt erstmal nur naiv die Luftlinie....

 

[mihe7]

@nik.stffrs Schau Dir mal in AStar.java (s. Verbesserungsvorschläge zu Wegfinder Programm) die Methode path() an.

Ansonsten mal ganz allgemein, mit Rekursion:

public void visit(Coordinate c) {
    if (c == null) {
        return;
    }
    doSomething(c); // ggf. auch erst nach dem visit...
    visit(c.previous());
}

oder iterativ:

public void visit(Coordinate c) {
    while (c != null) {
        doSomething(c);
        c = c.previous();
    }
}

Varianten nach Gusto.

 

[nik.stffrs]

Neee der kennt erstmal nur naiv die Luftlinie....

Stimmt nicht ganz. Am Anfang hast du Recht. Aber wenn der Algorithmus schon am laufen ist, und sich die ersten Koordinaten schon auf der Closed List (die Liste für Koordinaten zu denen der kürzeste Weg bekannt ist) befindet, dann kennt der Algorithmus wie schon gesagt den besten Weg zu dieser Koordinate schon. Wenn du dann den weiteren Weg von der Koordinate zum Ziel haben willst nimmt man erstmal Luftlinie.

 

[mihe7]

Genau so ist das

 

[nik.stffrs]

public void visit(Coordinate c) {
    if (c == null) {
        return;
    }
    doSomething(c); // ggf. auch erst nach dem visit...
    visit(c.previous());
}

Mensch hatte ich ein Brett vorm Kopf. Im Nachhinein fragt man sich immer warum man nicht selbst draufgekommen ist.