Problem mit Pathfinden (nicht der kürzte Weg)

Liste der Anhänge anzeigen (Anzahl: 1)

Hi,

kann mir jemand einen Tip geben, wo ich suchen
muss, wenn mir mein A* Verfahren den folgenden Weg gibt.

Im unteren Bildbereich sieht man plötzlich einen Hacken in dem Pfad.
Ebenso läuft es manchmal auf ein Hindernis zu um dann fast den gleichen
Weg wieder zurück zu laufen und einen neuen Weg einzuschlagen.
(Verstehe ich überhaupt nicht). Dieses Verhalten ist eingetreten, seit dem
ich die Randbedingung eingefügt habe. (Felder die dieses Bedingung nicht
erfüllen sind als nicht begehbar eingestuft.)

Randbedingung: Es muessen immer 2 Kästchen rund um
den Robby frei sein. (Es würde sonst nicht durchkommen).

Ich vermute eine falsche Kostenberechnung/Schätzung .

Hat hier jemand schon oder mehr Erfahrung damit, wo ich ansetzen muss.

Ich verwende im Prinzip diesen Code.
http://www.generation5.org/content/2000/cpathfinder.asp

Gruss
Ritchie[/img]

Hi,
Wie hast du denn die Randbedingung ausprogrammiert???
so, ganz ohne Sourcecodes kann man das nicht so ganz einfach sagen, was du da falsch gemacht hast!

Falls du eine gute (sehr einfach beschriebene) Anleitung zu A* suchst kann ich dir folgende empfehlen:
http://www.policyalmanac.org/games/a...torial_de.html

Um zu erreichen, dass der Roboter min. 2 Kästchen um die Hindernisse freilasst, würde ich vielleicht die Hindernisse einfach größer in dein Raster einzeichnen.

Hi,

hier die Routine, welche prüft, ob das Feld betreten werden darf.

Code:

int Navigation::FeldFrei(int x, int y, void *p) { int i; unsigned long lngOffset; // Daten offset in der Karten char *pointer; // Daten pointer if (x > KARTENGROESSE-2) return false; // Bereichskontrolle x if (y > KARTENGROESSE-2) return false; // Bereichskontrolle y if (x < 2 ) return false; // Zu nah am Rand if (y < 2 ) return false; // Zu nah am Rand pointer = (char*)p; // Pointer von Basisadresse legen lngOffset= x + (y * KARTENGROESSE); // Y Adresse in der Karten ermitteln pointer += lngOffset; // Adresse berechnen if (*pointer > 20) return false; // Mit groesser Sicherheit ein Hindernis ! // Pruefe inneren Roboterbereich / aesserer Bereich erster Teil for(i=0;i<8;i++) { if( *(pointer + InnerArray[i]) > 20 ) // Ist eine Schwellwert überschritten return false; // Ist ein Hindernis im Inneren Kreis if( *(pointer + OuterArray[i]) > 20 ) // Ist eine Schwellwert überschritten return false; // Ist ein Hindernis im aeusseren Kreis } // Pruefe auesseren Roboterbereich for(i=8;i<16;i++) { if( *(pointer + OuterArray[i]) > 20 ) // Ist eine Schwellwert überschritten return false; // Ist ein Hindernis im Aeusseren Kreis } return true; // Feld kann betreten werden }

Diese Routine wird innerhalb des A* hier aufgerufen (via udValid()):

Code:

void CPathFinder::CreateChildren(_asNode *node) { int x = node->x; // X / Y Werte aus performancegruenden int y = node->y; // in lokale Variablen for (int i=-1;i<2;i++) // Durchsuche alle umgebenen Knoten fuer den Weg { for (int j=-1;j<2;j++) // in alle Richtungen { if (i == 0 && j == 0 || // Ist der aktuelle Knoten aktiv ! !udValid(x+i, y+j, m_pCBData)) // oder darf dieses Feld nicht betreten werden { continue; // Dann Schleife hier abbrechen (kein Linkchild) } LinkChild(node, x+i, y+j); } } }

Die Seite von "Patrick Leste" ist mir bekannt und sie war schon eine gute Hilfe:
Leider sind die Links für eine "falsche Heuristik" für mich nicht klar genug.
Leider kann ich seine Implemetierung nicht mit der meinigen vergleichen.

Gruss Ritchie

P.S: Fehler in der KostenRoutine gefunden . Überbewertet.