Pathfinding, oder: Alternative zu A* (A-Star) ?!
-
Good Morning Forum
Ich meditiere jetzt seit geraumer Zeit über Wegfindungs-Algorithmen.
Wie es sich gehört (und um TGGC's Kommentare zu vermeiden 
) hab
ich natürlich erst bei google gesucht und bin dort auf den A* bzw "A Star"
Algorithmus gestossen. Natürlich habe ich das Teil sofort implementiert
und getestet. Aber irgendwie ist mir das noch zu langsam. Ich
habe eine 2D Welt mit einer Größe von mindestens 100 x 100 Feldern.
Solange nur ein Weg berechnet werden soll ist alles im Rahmen, aber wenn es
darum geht, die Route für gleich mehrere (20 aufwärts) Objekte zu
berechnen, geht das ganze doch schon sehr in die Knie. Ich habe dann versucht,
den A* Algo aufzubohren. Dazu berechne ich die Route vom Start bis zum Ziel
erstmal als "Luftlinie" (was ja, ohne die Hindernisse zu betrachten, der kürzeste Weg wäre). Trifft die Linie auf ein Hindernis, kümmert sich A*
darum, dieses zu umgehen. Dazu wird der Weg vom letzten begehbaren Punkt zum nächsten Begehbaren hinter dem Hindernis berechnet. Doch leider schiesst man sich damit schnell ins Knie. Weil der Weg sich ja an der Luftlinie orientiert, kommt es öfters vor, das Hindernisse völlig uneffizient übergangen werden. Aufgrund der Hindernisse kann die Luftlinie sogar zum fiesesten Umweg werden.
Wer hat eine Idee, wie man das Problem ungehen kann ? (Ich kann zur vedeutlichung auch mal eine Skizze malen wenn ihr wollt) Oder wer kann mir
eine Alternative zu A* nennen, die schneller arbeitet ?
-
Berechnen nicht für 20 Objekte den Weg gleichzeitig.
Bye, TGGC \-/
-
Ist deine Welt statisch? Dann kannst Du evtl. den begehbaren Pfad durch ein Polygon (mit Loechern) aproximieren. Es exestiert ein Algorithmus dafuer, um in glaube ich O(n*log(n)) Zeit (n: Anzahl konkaver Eckpunkte) einen perfekten Weg zu finden.
Edit: Das Polygon koennte natuerlich "mit deinen Tiles" gerastert sein.
-
Cpp_Junky schrieb:
Doch leider schiesst man sich damit schnell ins Knie. Weil der Weg sich ja an der Luftlinie orientiert, kommt es öfters vor, das Hindernisse völlig uneffizient übergangen werden. Aufgrund der Hindernisse kann die Luftlinie sogar zum fiesesten Umweg werden.
Dann hast Du den Algorithmus nicht verstanden. A* findet Dir garantiert den besten Weg auf den ersten Anlauf - schau Dir den Algorithmus noch mal an. Die Luftlinie ist nur die Heuristik mit der der Algorithmus sucht.
Zwecks anderer Lösungen:
Du bewegst Dich halt auf dem Weg der Suchalgorithmen. Ist immer ein trade-off. Kriterien sind dann so was wie:
-Findet Dein Algo die Lösung wenn es eine gibt (Stichwort unendlicher Suchraum)
-Findet Dein Algo die beste Lösung oder nur die erste
-Laufzeit
-Speicher
...
Schau Dir die Algorithmen einfach mal an und such Dir einen raus der zu Deinem Problem passt. Es kommt eben auch einfach auf Dein Problem an.
-
meinereiner schrieb:
Dann hast Du den Algorithmus nicht verstanden. A* findet Dir garantiert den besten Weg auf den ersten Anlauf - schau Dir den Algorithmus noch mal an. Die Luftlinie ist nur die Heuristik mit der der Algorithmus sucht.
Heuristik ? Was meinst du damit ? Ich weiss nicht, wie der "Luftlinien-Trick" üblicherwiese bei A* genutzt wird, aber ich wollte es einsetzen um zu vermeiden, das einfache Strecken (geraden ohne Hindernis) mit A* berechnet werden (weil langsam).
TGGC schrieb:
Berechnen nicht für 20 Objekte den Weg gleichzeitig.
Bye, TGGC \-/
Aha, und was willst du mir jetzt damit sagen ?
Ist mir schon klar, das dies nicht "gleichzeitig" passiert (nutze ja keine Threads dafür). Aber eben aufeinanderfolgend.
-
Um nochmal drauf zurueckzukommen, falls deine Welt einigermassen statisch ist:
1. Du jagst die Tiles durch ein Polygonisierprogramm, welches aus dem "Tile-Bitmap" Polygone bastelt, die den begehbaren Weg abdecken. (oder Du machst es von Hand).
2. Du suchst dir die konkaven Ecken heraus (die, die nach innen gerichtet sind)
3. Du berechnest alle Eckenpaare, die per Luftlinie erreichbar sind
Jetzt hast Du einen Sichtbarkeitsgraphen.Wenn Du von A nach B willst, berechnest Du alle Luftlinienwege von jeweils A und B zu den konvaven Ecken und fuegst diese dem Graphen hinzu. Dann A* ueber den Graphen laufen lassen.
Wenn das Polygon nicht zu komplex ist, koennte es deutlich schneller sein. Aber ich weiss ja nicht wie deine Welt aussieht..
-
wenns darum geht,20 objekte gleichzeitig ans selbe ziel zu befördern,kannst du auch versuchen, einen nahen gemeisnamen punkt für die objekte zu suchen, und dann von diesem punkt aus einmalig eine route für alle zu suchen.
-
Cpp_Junky schrieb:
meinereiner schrieb:
Dann hast Du den Algorithmus nicht verstanden. A* findet Dir garantiert den besten Weg auf den ersten Anlauf - schau Dir den Algorithmus noch mal an. Die Luftlinie ist nur die Heuristik mit der der Algorithmus sucht.
Heuristik ? Was meinst du damit ? Ich weiss nicht, wie der "Luftlinien-Trick" üblicherwiese bei A* genutzt wird, aber ich wollte es einsetzen um zu vermeiden, das einfache Strecken (geraden ohne Hindernis) mit A* berechnet werden (weil langsam).
A* verwendet eine Heuristik (in Deinem Fall Luftlinie oder im Falle von diskreten Feldern auch oft die "Manhatten-Distanz"). Wenn man von bei der Suche eine Heuristik (heuristische Suche) verwendet sucht man nicht blind nach einer Lösung, sondern nutzt vorhandenes Wissen um effizienter zur Lösung bzw. überhaupt zu einer Lösung zu finden. Es werden noch gewisse Anforderungen an eine Heuristik gestellt; z.B. schnell und einfach zu berechenen sein und im Falle von A* muss es den verbleibenden Weg eher unterschätzen.
Bei A* setzt sich die Bewertung eines Wegs aus der Kostenfkt. (z.B. zurückgelegter Weg) und der Heuristik (z.B. Manhattan-Distanz) zusammen.
Dass der Algorithmus immer den besten Weg von dem Ausgangspunkt zum Ziel findet kannst Du recht einfach beweisen.
Aber wie gesagt, schau Dir einfach den Algorithmus nochmal genau an.
-
Cpp_Junky schrieb:
Aha, und was willst du mir jetzt damit sagen ?
Ist mir schon klar, das dies nicht "gleichzeitig" passiert (nutze ja keine Threads dafür). Aber eben aufeinanderfolgend.Das du nicht für so viele Objekte den Weg berechnen solltest. Denn mit einem Objekt geht es ja.
Bye, TGGC \-/
-
meinereiner schrieb:
...Aber wie gesagt, schau Dir einfach den Algorithmus nochmal genau an.
Ok, jetzt hab ichs einigermaßen verstanden. Diese Heuristik repräsentiert also eine geschätzte Entfernung bis zum Ziel und soll der Wegfindung eine gewisse Orientierung geben, richtig ?
Ich habe mal nach so einem "heuristik-A*" Algo gesucht. Habe auch einen gefunden und den gleich mal ausprobiert. Das Teil arbeitet schon deutlich besser, aber löst mein eigentliches Problem leider auch nicht.
Der A* Algo "scannt" im Worst-Case-Fall fast die gesamte Spielwelt. Das ist natürlich sehr Berechnungs- und Speicherintensiv. Daher meine Idee mit der Luftlinie:
Berechne die Gerade von Start bis Ziel. Gehe dabei alle Felder auf der Geraden durch und prüfe ob Hindernisse vorhanden sind. Wenn ein Feld auf der Geraden sich als Hindernis herausstellt, merke dir das letzte begehbare Feld vor, und das erste begehbare Feld hinter dem Hindernis, das auf der Geraden liegt. Jetzt berechne mit A* eine Ausweich-Route um das Hindernis und zwar so, das wir letztendlich wieder auf unserer Luftlinie landen.
Ich habe mal eine Skizze gemacht um das zu verdeutlichen:
http://home.arcor.de/cppjunky/files/ok.gif
Hier ist noch alles ok. Durch die Kombination von Luftlinie und A* ist die Berechnung Blitz-schnell. Das Ergebnis kann sich von der zurückgelegten Wegstrecke sehen lassen.Aber jetzt kommt der Problemfall. Und zwar, wenn die Hindernisse so angeordnet sind, das die Luftlinie nicht mehr der kürzeste Weg ist:
http://home.arcor.de/cppjunky/files/dreck.gif
Deutlich wird das vor allem an dem U-Förmigen Hindernis. Hier bewegt sich das Objekt dämlicherweise erst dort rein und dann wieder raus, da der Pfad sich ja an der Luftlinie orientiert
Jemand ne Idee ?
-
Deine "Luftlinien-Optimierung" ist keine Optimierung. Streiche sie. Halte dich besser an die Vorschläge hier. Erzeuge Graphen mit weniger Kanten und Knoten und frage weniger Wege ab.
Bye, TGGC \-/
-
wollt ihr auf Gunnar nicht hören, oder versteht ihr ihn nicht?
-
volkard schrieb:
wollt ihr auf Gunnar nicht hören, oder versteht ihr ihn nicht?
Ne verstehs nicht. Er meint was anderes als so ein "A* Knotensystem" oder ?
Für mich hört sich das an, wie BSP
-
Nein meint er nicht. Er meint du sollst unnötige Knoten im Graph weglassen. Der kürzeste Weg liegt immer auf dem Sichtbarkeitsgraph (exklusive erste und letzte Kante), also entferne alles andere.
Bye, TGGC \-/
-
Bin bei der Forensuche nur mal so hier vorbeigekommen. Da ich mich gerade damit beschaftige:
TGGC schrieb:
Der kürzeste Weg liegt immer auf dem Sichtbarkeitsgraph (exklusive erste und letzte Kante), also entferne alles andere.
Es sei denn, man benutzt ein Terrain, wo auf unterschiedlichem Gelände unterschiedlich schnell gelaufen werden kann (Straßen, Sümpfe etc.) dann wirds erheblich komplizierter.
Um das Problem des nicht existenten Weges vorzubeugen, kann man alle zusammenhängenden Gebiete vorberechnen und vorher überprüfen, ob Ziel und Start im selben Gebiet liegen. Wenn nicht, existiert kein Weg.
Um auch mit großen Karten klarzukommen, kann man verschiedene Schichten von Knoten mit unterschiedlicher Dichte benutzen und dann erst im gröbsten Graphen suchen und den Weg dann verfeinern. (hat nicht mehr den Anspruch, den optimalen Weg zu finden, aber gute Laufzeiteigenschaften und findet bei guter implementierung einen brauchbare Wege).
Niko
-
sirniko schrieb:
TGGC schrieb:
Der kürzeste Weg liegt immer auf dem Sichtbarkeitsgraph (exklusive erste und letzte Kante), also entferne alles andere.
Es sei denn, man benutzt ein Terrain, wo auf unterschiedlichem Gelände unterschiedlich schnell gelaufen werden kann (Straßen, Sümpfe etc.) dann wirds erheblich komplizierter.
Auch dann findet man den kürzesten Weg (ein Weg, bei dem die Weglänge minimal ist).
Bye, TGGC (Der Held lebt!)
-
Sieht mir nicht so aus, als ob das schon geklärt sei, deswegen:
Also, dein was auch immer soll von S(start) nach Z(iel)
. sind begehbare Felder
X sind HindernisseS......... .1........ ..2....... ...3XXX... ...4XXX... ...5XXX... ....6..... .....7.... ......89Z.Wenn du da deinen normalen A* drüber laufen lässt und ihn jedes begehbare Feld als Knoten anfassen lässt muss er zienlich lang suchen bis er am Ziel ist.
Dabei kommt beispielsweise die Strecke, die ich mit den Zahlen markiert, habe bei heraus.S......... .......... ...o...o.. ....XXX... ....XXX... ....XXX... ...o...o.. .......... ........Z.Wenn du jetzt aber rund um die besagten konkaven Ecken Knoten ( o ) legst kann der A* seine Aufgabe viel schneller erledigen, da er statt 10 mal 9 Knoten wie vorher nur noch 4 (oder eigentlich 6 mit S u. Z) hat. Denn über diese Knoten lässt sich jeder Punkt der Karte von jedem Punkt der Karte optimal kurz erreichen.
Das beschleunigt die Sache erheblich.Du musst dann nur noch folgendes machen:
Welche Knoten "sehen" S und Z und dann den A* drüberlaufen lassen.
-
Ich hab nach den vielen quälenden "A* zum funktionieren bringen Stunden" mal ein Tutorial dazu geschrieben. Könnts euch ja mal anschauen und ggf sagen, was noch fehlt / bzw schlecht erklärt ist.
unter Code-Section -> tutorials
