A-Stern: fährt immer wieder vor die Wand! - Hilfeeee

[data89]

Hallo,

ich versuche gerade den A-Stern-Algorithmus zu implementieren, nachdem ich heute morgen den BreathFirst-Algo implementiert habe. Doch meine Implementierung fährt immer wieder vor die Wand!

Könntet Ihr nicht einmal drüber schauen? Ich habe schon ausführlich gedebugged, aber bin den Fehler nicht so richtig auf die Schliche gekommen ...
Im Anhang findet Ihr die Source-Code-Dateien ...

Ich bitte Euch, mir zu helfen!
data89 :-(

Edit: Ich habe mich an diesem Tutorial orientiert: A* Pfadfindung für Anfänger (fast ganz unten ist ein Ablaufschema).

 

[SlaterB]

schöner Link,
wenn sich kein anderer meldet werde ich heute abend draufschauen, muss sich doch finden lassen,

ich hoffe, ein Beispiel-Netz, welches zum Fehler führt, ist dabei

 

[data89]

wenn sich kein anderer meldet werde ich heute abend draufschauen, muss sich doch finden lassen

Vielen Dank vorab, SlaterB!

ich hoffe, ein Beispiel-Netz, welches zum Fehler führt, ist dabei

Ja, aus dem Artikel das Beispielraster. Außerdem ist noch eine Debug-GUI dabei, für die Felder (orange=auf der jew. List, grün=start, rot=ziel, schwarz=hindernis).

Danke nochmals
data89

 

[SlaterB]

nur 1 Min später :

was kannst du da debuggt haben?
schau dir einfach an was dein Algorithmus tut, alles liegt klar vor dir,
da wäre z.B.

> // check if the filed is accessible or already in the closed list
> if (!this.map.isAccessible(temp) || this.isInClosedList(temp)) break;

hier brichst du die Schleife ab, zumindest die innere der doppelten Schleife,
andere Knoten mit höherem x,y werden nicht mehr überprüft,
richtig ist dagegen ein continue, der Rest muss noch dran kommen,

mit einfachen Debugging 'starte von Punkt xy aus' (hast du), 'prüfe nun Punkt xy' (hast du nicht) würde sofort auffallen,
wenn ein Punkt ohne guten Grund nicht überprüft wird,

deshalb kommst du auf der Testkarte nicht unten um die Ecke

--------

zwei weitere Fehler:

// check if this item is better
AStarNode fromOpenList = this.getNodeFromOpenList(temp);
if (n.getF() < fromOpenList.getF()) {

fromOpenList.getF() ist der alte geschätzte Gesamtweg über fromOpenList,
diesem Wert darfst du nicht n.getF() entgegen setzen, sondern ein neu berechnetes fromOpenList.getF() WENN n der Parent von fromOpenList wäre

mal ein etwas anschaulicheres Beispiel:
von Hamburg aus is Ziel München, weitere Zwischenknoten sind Berlin und Stuttgart, die Gitterstruktur dürfte ungefähr klar sein
von Hamburg aus kommten Stuttgart und Berlin in die Open-Liste,
als nächstes wird Stuttgart betrachtet, und von Stuttgart aus schauen wir mal nach dem schon sich in der Open-Liste befindlichen Berlin
nun darfst du nicht den geschätzen Weg Hamburg-Stuttgart-München mit Hamburg-Berlin-München vergleichen um Stuttgart als Parent zu setzen,
sondern du musst den geschätzen Weg Hamburg-Stuttgart-Berlin-München mit Hamburg-Berlin-München vergleichen, denn falls du Stuttgart
als neuen Parent von Berlin setzt, wäre der mögliche Endweg schließlich auch Hamburg-Stuttgart-Berlin-München

--------

> while (!this.isInClosedList(t) || !this.open.isEmpty()) {

das oder bedeutet: führe die Schleife fort, solange eine der beiden Bedingungen erfüllt ist,
solange es noch offene Knoten gibt wird also ewig weitergesucht, selbst wenn der Zielknoten schon gefunden wurde,
das muss ein 'und' rein


------

edit:
ob am Ende alles stimmt, z.B. die richtige Verknüpfung der Knoten, habe ich nicht genau angeschaut

edit2:
ich empfehle noch
for (int i = 0; i < this.map.length; i++) {
for (int j = 0; j < this.map.length; j++) {
g.drawString(""+j+"/"+i,j*80+50, i*80+50);
}
}
am Ende der paint-Methode, damit sich die Felder einfacher wiederfinden lassen

 

[data89]

Vielen, vielen Dank für Deine Antwort, SlaterB!! Hat mir wirklich sehr geholfen ...

Mittlerweile funktioniert mein Algorithmus bei manchen (!! :-() Konstellationen. Aber es gibt immer wieder solche unnötigen Pfade. Im Bild sieht man es ganz deutlich. Woran kann das liegen? Sicher doch an der Stelle, wo ich den Parent setze, oder?

Könntet Ihr - vorallem auch SlaterB - nocheinmal drüberschauen? Im Anhang habe ich nochmals eine komprimierte Version, die auf statische Methoden setzt und auch anhand des von mir erwähnten Links mit Nummerierung kommentiert ...

Schön an meiner Implementierung ist, dass die Laufzeit bis jetzt (bei ca. 500 Feldern) immer unter 15 ms (bei 5-12 ms) lag!

Danke vorab,
data89

 

[SlaterB]

diesmal nicht ausprobiert, nur geschaut

							// (2.3.3) check the g value from currentNode to
							// tempPoint is better than the g value of the 
							// parent to tempPoint
							Node fromList = get(open, tempPoint);
							
							Node test = new Node(tempPoint, n);
							test.g = Node.calculateG(test);
							
							if (fromList.g < test.g) {
							} else {
								fromList.parent = n;
							}
							
//							if (fromList.g < n.g) {
//								// the g value of the item in the list is 
//								// better; do nothing
//							} else {
//								// the g value of the new item is better
//								fromList.parent = currentNode;
//								// re-calculate g and h
//								fromList.g = Node.calculateG(fromList);
//								fromList.h = Node.calculateH(fromList, t);
//							}

tempPoint ist der betrachte Nachbarpunkt von currentNode,
n ist ein neuer Node zu diesem tempPoint
und fromList genauso, der alte aus der Open-Liste,

was soll nun test? test ist noch ein dritter Node an diesem Nachbarpunkt, mit quasi sich selber als Parent,
danach zweimal dieselbe if-else-Abfrage, nur mit verschiedenen Vergleichsknoten, kann ja auch nicht richtig sein

wenn du alles zu test schreichst, auch das erste if-else, könnte es vielleicht funktionieren, wenn nicht schaue bitte selber nach,
durch deinen Debugger siehst du doch Schritt für Schritt was passiert, wo wird erstmals Unsinn als Parent gesetzt?
genau an dieser Stelle loggen mit System.out.println(),
wenn allgemeine Ausgaben zu jeden Schritt zuviel Text erzeugen, dann filtere nach den Point, du siehst ja exakt die Stelle

if (isPoint(4,5,tempPoint) && isPoint(4,4,currentNode)) {
  System.out.println(die beiden g Werte sind .. und deshalb passiert ..);
}

edit:
gar nicht gesehen: das zweite if-else ist ja auskommentiert, na dann eher falschrum,
auf jeden Fall test weg, nur n mit fromList vergleichen

--------

Konstrukte wie
> test.g = Node.calculateG(test);
gehen gar nicht, da kann man doch locker leicht
test.g = Node.calculateG(other);
schreiben

besser ist
test.calculateGUndH();
diese Methode kann ja gerne was statisches aufrufen, wird aber sicher sich selber übergeben,
denn ein anderer Node ist ja kaum vorhanden, außer Parent

 

[data89]

Wirklich, vielen Dank für Deine Hilfe SlaterB!
Der Algorithmus funktioniert jetzt - dank Deiner Hilfe SlaterB ;-) - und auch laufzeitmäßig ziemlich gut: bei einem Test mit Map's im Größenbereich von 600-5.000 Feldern benötigt der Algorithmus durchschnittlich 0,96 ms (bei den größeren Feldern bis 2 ms). Find' ich toll!

Aber ich habe noch ein Problem: den Algorithmus will ich in meinem Tile-Map-Spiel einsetzen. Und da geht dieser Pfad definitiv nicht:

Denn wie soll die Figur durch die Hindernisse kommen? (wenn das 3D wäre, dann ist ja da kein "spalt", wo die Figur durchkommen kann).

Meine Frage nun: wie kann ich das nun ausbügeln?

Vielen Dank für Alles,
data89

P.S.: Für die Zahlen im Bild: Oben F, unten links G und oben rechts H.

 

[SlaterB]

an einer Stelle gehst du ja die Nachbarknoten durch und fragst ab
1. nicht passierbar (blau)
2. schon in closed-Liste

da musst du nun eine dritte Überprüfung machen, nämlich ob erreichbar,
waagerecht und quer geht das immer, falls 1. und 2. erfüllt sind,
für schräg entfernte Nachbarn eben prüfen, ob die beiden anderen Felder (du erkennst sicher welche) passierbar sind (nicht blau),
ob nun ein blaues schon stört oder nicht kannst du selbst festlegen, spätestens bei zweien gehts nicht