Entwicklung [Delphi/Pathfinding allgemein] Rösselsprung / Heuristik?

[schenki]

Servus Computer/Internet -Forum, ich stör mal wieder und denke, dass der Thread in diesem Teilforum am ehesten passt.

Ich habe die Aufgabe, bis Januar in Delphi(7) ein Programm zu schreiben, dass für ein quadratisches Feld den bestmöglichen Weg von einem Start- zu einem Zielpunkt berechnet. Beide sind frei wählbar. Das Problem ist jedoch, dass der Weg in Rösselsprüngen / so, wie das Pferd beim Schach, gegangen werden muss. Natürlich wird der kürzeste Weg gesucht. Zwar hab ich mich mit dem A*- Algorithmus beschäftigt, jedoch fiel mir schon schnell auf, dass man den Heuristikgedanken beim Rösselsprung wohl streichen kann (falls nicht, bitte ich um Erläuterungen). Hätte jemand nun einen passenden Algorythmus, oder andere Denkanstöße parat?

Mir fiel bis jetz nur ein, stupide alle möglichen Wege auszurechnen, und davon den kürzesten zu nehmen. Dies sorgt dann jedoch für massig Wege, und die Zeit, in der der Weg errechnet werden soll, ist nur begrenzt. Ich hoffe, ihr habt konstruktive Ideen =).

mfg

[Bananen-Joe]

Nun ich hatte früher mal einen Pathfinding-Code in Visual Basic geschrieben,
allerdings hat dieser weder Rösselsprünge genutzt noch jedesmal den kürzesten Weg gefunden.

Das Thema Pathfinding hatte ich danach erstmal auf Eis gelegt um mich um andere Themen zu kümmern.
Allerdings hatte ich (bevor ich es eingefroren hatte) eine Idee, welche möglicher weise bei deinem Problem weiterhelfen könnte.

Und zwar über Knotenpunkte.
Wenn wir davon ausgehen, dass das Pferd sich nur L-Förmig bewegen kann, dann kannst du ja, beim Beginn des Pathfinding-Algorithmus eine Knotenpunktliste erstellen, welche angibt, von welchem Knotenpunkt man zu welchen anderen Knotenpunkten gelangt.
Anschließend müsste man nur die Knotenpunktliste durchgehen und damit versuchen einen Weg zu finden.

Hierbei gibt es aber zwei Probleme: zum einen das Erstellen der Knotenpunktliste, was bei kleinen Karten (100x100 Felder) zwar noch sehr schnell ist, bei größeren Karten jedoch (1000x1000 Felder) langsam werden kann.
Eine Lösung hierfür wäre es größere Felder zusammenzufassen.
Wenn also ein 10x10 Felder Block komplett passierbar ist, dann könnte man ihn zu einen Punkt mit dem Radius 10 (ok kein echter Radius, da es quadratisch ist...) zusammenfassen.
Das zweite Problem wäre das Durchlaufen der Knotenpunktliste.
Um den kürzesten Weg zu finden könnte man natürlich einfach die Liste rekursiv durchlaufen und den kürzesten Weg speichern.
Wäre aber auch nicht sonderlich elegant, wobei es bei dem "immer den kürzesten Weg finden" wohl kaum einen anderen Weg gibt als alle auszuprobieren.

Hm, möglicher weise könnte an dieser Stelle ein Mathematiker, welcher Delphi kundig ist, weiterhelfen.
Ich glaube die Person weiß, dass ich sie meine. ^^

MfG Bananen-Joe

[derula]

Zitat von schenki

jedoch fiel mir schon schnell auf, dass man den Heuristikgedanken beim Rösselsprung wohl streichen kann

Warum das? Die Heuristik muss nur eine Abschätzung zum Abstand zum Ziel sein. Das einzige, was die Heuristik erfüllen muss, ist, dass sie nicht größer sein darf als der tatsächliche Weg zum Ziel, und wenn du als Heuristik Luftlinie (sprich euklidische Norm, also |Endvektor - Zielvektor| = Wurzel((Endpunkt.x - Zielpunkt.x)² + (Endpunkt.y - Zielpunkt.y)²)) nimmst, ist das immer erfüllt.

Edit: Hoffe das hilft dir weiter ^^

[schenki]

Zitat von derula

Warum das? Die Heuristik muss nur eine Abschätzung zum Abstand zum Ziel sein. Das einzige, was die Heuristik erfüllen muss, ist, dass sie nicht größer sein darf als der tatsächliche Weg zum Ziel, und wenn du als Heuristik Luftlinie (sprich euklidische Norm, also |Endvektor - Zielvektor| = Wurzel((Endpunkt.x - Zielpunkt.x)² + (Endpunkt.y - Zielpunkt.y)²)) nimmst, ist das immer erfüllt.

Edit: Hoffe das hilft dir weiter ^^

Okay, der Post war für mich zu hoch, hier mal meine Gründe, warum ich innerlich Heuristik von meiner Liste gestrichen hatte:

Unter Heuristik verstand ich bis jetz die direkte Luftlinie zwischen Punkt und Ziel. Ähnlich wie hier beschrieben. Das Problem daran, die Heuristik als Faktor, bzw. als einzigen Faktor, für die Bestimmung des nächsten Zwischenschrittes, zu benutzen, ist, bei Rösselsprüngen, dass man sich auch wieder vom Ziel entfernt, um dieses zu erreichen (afair).

Edit:

(Das rote Feld ist der Startpunkt, das Grüne das Ziel, und die blauen Felder sind ein Hinderniss / eine Wand.)

Hier mal ein Beispiel, bei allen Wegen beinhaltet der Weg, dass man sich vom Endziel entfernt. Deswegen habe ich Heuristik gleich gestrichen. Das Grüne Zeug links kann man ignorieren.

mfg

[derula]

Zitat von schenki

Das Problem daran, die Heuristik als Faktor, bzw. als einzigen Faktor, für die Bestimmung des nächsten Zwischenschrittes, zu benutzen

Falsch. Die Heuristik wird benutzt, um bestimmte Wege als wahrscheinlicher zu kennzeichnen. Sprich, wenn du näher am Ziel bist, ist es wahrscheinlicher, dass von dort aus der kürzeste Weg zum Ziel führt.

Aber auch wenn du nochmal weiter weg musst, das spielt keine Rolle. A* findet immer einen kürzesten Weg (einen, denn es kann ja mehrere kürzeste Wege geben, die also gleich lang sind). Wenn wir nur von 8*8 Feldern sprechen, und Zeitaufwand eh nicht wesentlich ist, kannst du getrost die Heuristik weglassen und kommst nach (eventuell etwas längerer Zeit, wird aber auf halbwegs neuen Computern nicht merkbar sein) auf dieselbe Lösung. Die Heuristik wird für A* nicht benötigt, dient nur zur Beschleunigung ohne Verschlechterung des Ergebnisses.

Ich hoffe das war hilfreicher ^^

Edit: Bei normalem Pathfinding hat man übrigens dasselbe Problem, dass man sich eventuell vom Ziel entfernen muss. Ansonsten wäre ja das Move Toward Hero vom Maker schon Pathfinding ^^

[Scar]

Wie lange darf das Ding denn am Pfad rumrechnen? Ist die Größe des "Spielbretts" variabel?
Sonst würde ich es echt mit der haudrauf Methode "Ich berechne alle Pfade und suche den kürzesten aus" machen. Ist zwar unelegant, aber funktioniert.
Hatte letztes Semester an der Uni für nen Tetris-autobot auch funktioniert.
Naja... der hatte gleich 2 Züge im vorraus berechnet was dann SEHR lange gedauert hat. Aber wird hatten da keine Begrenzung *GG*

[schenki]

Hatte gestern Abend noch ein hilfreiches und ausführliches Gespräch mit Derula via ICQ, das sehr weitergeholfen hat (danke nochmal ).
Die Feldgröße ist festgelegt auf 24² Felder, wobei da auch noch nicht begehbare Felder und eine bestimmte Anzahl weiterer Hindernisse eingerechnet ist. Und zur Zeitbegrenzung, da bin ich mir grad nicht sicher, irgendwas mit 2 afair, nur die Einheit weiss ich grad nicht mehr, muss ich nochmal nachfragen.

mfg

[derula]

Zitat von Scar

"Ich berechne alle Pfade und suche den kürzesten aus" machen.

Hm? Ähm imho gibt es unendlich viele Pfade, das könnte das ganze etwas beeinträchtigen. ^^' Ansonsten verstehe ich nicht ganz wie du das meinst.

Aber Dijkstra bzw A* machen ja im Prinzip nichts anderes, außer, dass sie immer den Pfad fortsetzen, der im Moment noch der kürzeste ist... sobald sie beim Ziel sind wissen sie, dass garantiert ein kürzester Weg gefunden wurde. Und mit Pseudo-Code von Wikipedia dürfte das relativ einfach zu implementieren sein...

Meine Meinung.

[Scar]

Natürlich alle Pfade die halbwegs direkt ins Ziel führen 0o

[derula]

Zitat von Scar

Natürlich alle Pfade die halbwegs direkt ins Ziel führen 0o

Und woher weißt du das vorher? Oo Sorry will mich wirklich nicht aufspielen oder so, aber das ist doch genau das Problem beim PathFinding, dass du vorher genau nicht weißt, welcher Weg am schnellsten ins Ziel führt... kann sein, du kannst direkt gehen, kann sein, du musst in die andere Richtung loslaufen. Effizient helfen kann hier nur Backtracking, bzw. eine Prioritätenliste wie sie von A* und Dijkstra verwendet werden. Oder verstehe ich dich falsch?

Aber gut, ist ja im Prinzip auch egal... Die Sache ist, A* und Dijkstra garantieren auf sehr simple Weise einen wirklich kürzesten Weg und sind nicht besonders schwer zu implementieren, wenn man sie mal verstanden hat. Also wozu das Rad neu erfinden?

[Bananen-Joe]

Zitat von derula

Und woher weißt du das vorher? Oo Sorry will mich wirklich nicht aufspielen oder so, aber das ist doch genau das Problem beim PathFinding, dass du vorher genau nicht weißt, welcher Weg am schnellsten ins Ziel führt... kann sein, du kannst direkt gehen, kann sein, du musst in die andere Richtung loslaufen. Effizient helfen kann hier nur Backtracking, bzw. eine Prioritätenliste wie sie von A* und Dijkstra verwendet werden. Oder verstehe ich dich falsch?

Aber gut, ist ja im Prinzip auch egal... Die Sache ist, A* und Dijkstra garantieren auf sehr simple Weise einen wirklich kürzesten Weg und sind nicht besonders schwer zu implementieren, wenn man sie mal verstanden hat. Also wozu das Rad neu erfinden?

Also ich erzähl' dir mal wie ich das früher gelöst habe:
Ich hatte ein Array (z.B. 10x10 Felder).
0 bedeutet Feld ist frei.
-1 bedeutet Feld ist belegt.
1 bedeutet das Feld wird gerade durchprobiert.

Nun habe ich die Ziel- und die Start-Koordinaten.
Danach werden (vorzugsweise in Richtung des Ziels) die Felder durchprobiert.
Jedes durchprobierte Feld wird anschließend als "bereits probiert" markiert (Wert 1).
Der Code läuft rekursiv ab. Führte ein Weg ins Nichts, dann werden die Marker stückchenweise entfernt und neu durchprobiert.
Die Probierreihenfolge ist folgende (wenn z.B. das Ziel oberhalb ist):

1. Feld oben
2. Feld oben-links
3. Feld oben-rechts
4. Feld links
5. Feld rechts
6. Feld unten-link
7. Feld unten-rechts
8. Feld zurück

(Ok, hier bei den Rösselsprüngen müsste das anders aufgebaut sein...)

Jedesmal, wenn das Ziel erreicht wurde, kann man den Weg in eine Liste übernehmen.
Anschließend muss man nur den Weg raussuchen, welcher die wenigsten Felder benötigt hat.

Dauert aber halt sehr lange der Code.

MfG Bananen-Joe

[derula]

Zitat von Bananen-Joe

[...]
Jedesmal, wenn das Ziel erreicht wurde, kann man den Weg in eine Liste übernehmen.
Anschließend muss man nur den Weg raussuchen, welcher die wenigsten Felder benötigt hat.

Sagen wir so, du hast damit eine garantierte Laufzeit von O(n²), bei den oben genannten Algorithmen wird das nur im Worts-Case-Fall erreicht^^. Aber beide geben einen kürzesten Weg zurück.

Zitat von Bananen-Joe

Danach werden (vorzugsweise in Richtung des Ziels) die Felder durchprobiert.

Also auch mit Heuristik, nur,... wie sinnvoll ist die, wenn eh alle Wege durchprobiert werden?^^'

[Scar]

Genau sowas meinte ich doch wie Joe es erklärt hat -.-

[anti-freak]

ich versteh das problem nicht... oder ich bin zu unwissend xD
ich mein, der A* algorythmus sucht doch den weg nach einer gewissen vorgabe.
gibst du ihm vor, das er jedes feld untersuchen soll, macht er das, gibste ihm vor, das er alle 2 felder untersuchen soll, macht er das doch auch o.O
zu mindest denke ich mir das so.
bei total danebener aussage (xD xD xD) bitte ich um berichtigung und dazugehöriger erklärung xD

mfg

[Bananen-Joe]

Zitat von derula

Also auch mit Heuristik, nur,... wie sinnvoll ist die, wenn eh alle Wege durchprobiert werden?^^'

Der Sinn dahinter war der, dass der Code damals nur das erste Ziel finden musste.
Anschließend hatte ich zwei Optimierungsfilter drüber gehetzt.
So hat ein Filter z.B. versucht Wege linear zu machen, was am Ende ganz nett aussah.

Problem hierbei war halt, dass eben nicht immer der kürzeste Weg gewählt wurde. ^^


Zum A*-Algo kann ich leider nicht viel sagen, da ich ihn mir bisher nicht angeschaut habe. ^^
Aber sowie das erledigt ist, kann ich da vielleicht auch meinen Senf hinzugeben.

MfG Bananen-Joe