A-Star Pathfinding optimieren
-
Mahlzeit
Ist hier jemand der mit dem A* Algorithmus vertraut ist und mir Tipps geben kann ? Meine Implementierung von A* ist mir viel zu langsam
Ich habe mal testweise auf einer 100 x 100 Tile Map zwei Schikanen eingebaut.
Zwei horizontale Reihen mit Hindernissen. Am Ende ist gegenüber jeweils 5 Tiles platz zum durchkommen (Man betrachte die "Skizze" zum besseren Verständnis)S..................... ...................... XXXXXXXXXXXXXXXXX..... ...................... ...................... .....XXXXXXXXXXXXXXXXX ...................... ...................... .....................ZS = Start
Z = Ziel
. = Begehbares Feld
X = HindernisFür dieses Terrain (In der Größe 100 x 100) braucht mein Algo ~60 msec um den Pfad zu ermitteln. Bei einer 500 x 500 Map dauert es ewig.
Einige Optimierungen habe ich bereits eingebaut: Die Open-Node Liste ist nach "Bewegungskosten" sortiert und alle Nodes können durch die Verwendung von Maps (MFC) schnell aus den Listen ermittelt und zugeordnet werden. Dennoch geht der Algo bei grossen Maps in die Knie. Was kann man dagegen tun ?
Was gibt es für Alternativen zu A* ?
-
1
schneller ist es wenn man vorher nodes verteilt (viel gröber als die eigentliche auflösung des spielfeldes) und dann diese z.b. beim spielstart initialisiert.eine node ist dabei ein knoten der in nord,sued,ost,west sich merkt ob er zur dortigen nachbarnode eine verbindung hat oder nicht (es muss keine direckte verbindung sein, aber z.b. eine deren weg maximal 50% überm direckten weg ist... das ist ne frage der balance)
wenn man dann einen weg finden möchte, sucht man sich den weg zur nächersten möglichen node und von der aus dann (relativ schnell) einen zu der Node die am nachesten zum ziel liegt. dann muss sich jede einheit nurnoch von node zur node hangeln und das ist recht performant zu machen.
2
bei manchen playstation2 spielen verwendet man eine art portal-technik. dabei unterteilt man vor dem spielbeginn das spielfeld in gebiete und merkt sich die verbindungen zwischen den gebieten (die portale). um dann den weg zu finden muss man (wie bei dem node system) nur den weg zum nachesten portal suchen und hangeld sich dann zum nächsten... bis man am zielgebiet ankommt.
das ist recht fix und speichersparend. aber vielleicht nicht sooo einfach zu implementieren.rapso->greets();
-
rapso Ansätze sind schon ok. Aber eigentlich reicht auch schon der Sichtbarkeitsgraph der gesamten Welt aus, in den dann nur Start und Ziel einfügt werden. Bewiesener Massen sind alle inneren Kanten des kürzesten Weges Kanten des Sichtbarkeitsgraphen. (Ich kann mich irren, aber das hatten wir schonmal?!)
Was ist bei dir jetzt die "Open Node"-List? Bei A* brauchst du doch, wenn du eine konstante Schätzfunktion, nur eine Menge (genau wie bei Dijkstra) und die speichert man normal in einen Heap, z.b. Fibonnacci Heap.
Bye, TGGC (Der Held bei Dir!)
-
Also der Algorithmus sieht in etwa so aus:
Pseudo
Startfeld in Open-List packen Wiederholen bis Pfad gefunden: Suche das Feld aus der Open-List mit der besten Bewertung (Bewegungspunkte) Dieses ist das zu betrachtende, aktuelle Feld Pack dieses Feld in die Closed-Liste Betrachte alle anliegenden Felder Für jedes Feld wird folgendes geprüft: Auf der Closed-Liste ? Dann nächstes Feld Auf der Open-Liste ? Ist die Entfernung vom aktuellen Feld zu diesem Feld günstiger als seine aktuelle ? Dann mach das aktuelle Feld zu seinem Parent und berechne die Bewegungspunkte neu Nicht auf der Open-Liste ? Setz das Feld auf die Open-Liste, mach das aktuelle Feld zu seinem Parent und berechne die Bewegungspunkte Ist das Feld das Zielfeld, dann beende die suche Schleifen-EndeDie Suche endet, wenn das Ziel-Feld auf der Open-Liste landet, oder die Open-Liste irgendwann leer ist (Pfad nicht berechenbar)
-
Cpp_Junky schrieb:
Mahlzeit
S..................... ...................... XXXXXXXXXXXXXXXXX..... ...................... ...................... .....XXXXXXXXXXXXXXXXX ...................... ...................... .....................ZS = Start
Z = Ziel
. = Begehbares Feld
X = Hindernislass doch beim laden der map noch einen algo durchlaufen, der aus der map sowas macht:
S = Start
Z = Ziel
. = Begehbares Feld
X = Hindernis
N = NodeS..................... .................N.... XXXXXXXXXXXXXXXXX..... .................N.... ....N................. .....XXXXXXXXXXXXXXXXX ....N................. ...................... .....................Zder A* algorithmus sucht dann nichtmehr alle felder des weges, sondern nurnoch alle Ns, die ihn um die hindernisse rumführen
-
Das mit der "open" und "closed" Listen doch aber sinnlos? Wenn es einen Parent hat, und nicht in der zu untersuchenden Menge (hier "open" genannt), dann ist es "closed", warum extra verwalten?
Bye, TGGC (Der Held bei Dir!)
-
Ich brauche die Listen, damit ich nicht bei jedem mal wenn ich das Pathfinding ausführe die Nodes neu initialisieren muss. Bei einer kleinen 100 x 100 Map sind das immerhin schon 10.000 Objekte. Es ist wesentlich schneller einmal die Open/Closed Listen zu bereinigen. Wobei die Closed Liste dennoch etwas überflüssig ist. Man kann genauso gut fragen ob ein Node nicht in der Open-Liste steht. Aber das ist Performance-Technisch irrelevant und kostet höchstens ein Paar Bytes vom Speicher. Ich brauchs aber schneller :p
-
Cpp_Junky schrieb:
Ich brauche die Listen, damit ich nicht bei jedem mal wenn ich das Pathfinding ausführe die Nodes neu initialisieren muss.
Na wenn du meinst.
Bye, TGGC (Der Held bei Dir!)
