Problem mit Pathfinden (nicht der kürzte Weg)

[Ritchie]

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]

[skillii]

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/aStarTutorial_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.

[Ritchie]

Hi,

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


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()):



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.