spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Flowfield pathfinding ist denke ich genau was du suchst. Aber du solltest das auf der Grafikkarte alles berechnen lassen und nicht auf der cpu.

Kannst natürlich auch old school gehen und ein waypoint system verwenden.

Ich glaube die Grafikkarte kann das ganze parallel berechnen. Die CPU nur sequenziell bzw. mit der Anzahl der Kerne die sie hat(viel weniger als eine GPU). Das dürfte der Hauptgrund sein.

Warum ist a Stern ein performancekiller?

Mal abgesehen davon dass der pfad nicht für jede einzelne Einheit berechnet wird, zumindest. macht das in meinen Augen keinen Sinn. Oder steuert man jede einzelne Einheit manuell?

Zitat von »Hades85«

Warum ist a Stern ein performancekiller?

Mal abgesehen davon dass der pfad nicht für jede einzelne Einheit berechnet wird, zumindest. macht das in meinen Augen keinen Sinn. Oder steuert man jede einzelne Einheit manuell?

Ich glaub das hat was mit der Zeitkomplexität des Algorithmus es zu tun. Da müsste auch die verwendete heuristic mit Einflüssen jnd auch die Anzahl der nodes. Und es gibt natürlich auch worst case scenarien. Bzw bei einem algo der ein optimales Ergebnis (immer den besten weg findet) auch dazu führen dass erst fast das gesamte Spielfeld durchsucht wird bevor der optimalste weg gefunden wurde. Heuristiken helfen zwar dass es da nicht alszu sehr ausartet aber passiert halt.

Zitat von »TypeOverride«

Ich glaub das hat was mit der Zeitkomplexität des Algorithmus es zu tun. Da müsste auch die verwendete heuristic mit Einflüssen jnd auch die Anzahl der nodes. Und es gibt natürlich auch worst case scenarien. Bzw bei einem algo der ein optimales Ergebnis (immer den besten weg findet) auch dazu führen dass erst fast das gesamte Spielfeld durchsucht wird bevor der optimalste weg gefunden wurde. Heuristiken helfen zwar dass es da nicht alszu sehr ausartet aber passiert halt.

Da stellt sich jetzt aber die Frage ob hier nicht rum optimiert wird bevor überhaupt ein konkretes Problem auftritt. Werden mehrere Einheiten zusammen bewegt so kann reicht es aus den Weg ein einziges mal zu berechnen. Ob jetzt hier Worstcase Szenarien auftreten können hängt ganz stark von dem Graphen ab. Ist die Welt eher offen findet A* ziemlich direkt den kürzesten Weg. Man kann sich jetzt hier unglaublich viel Arbeit machen und nach irgendwelchen tollen anderen Lösungen suchen, oder man setzt das ganze einfach mal um und guckt ob es zu einem Problem führt.
Oft arbeitet man bei der Wegfindung auf verschiedenen Ebenen. Das bedeutet ich suche zunächst einen Weg in einem recht groben Graphen. Hier werden zum Beispiel nur statische Objekte der Umgebung berücksichtigt. Der Weg den ich hier finde könnte dann theoretisch weiter unterteilt werden. Als Beispiel suchst du den kürzesten Weg durch eine Stadt bei der alle Häuser betretbar sind. Zuerst möchtest du nur einen groben Weg mit Straßen und Häusern durch die du gehst. Danach guckst du wie du dich durch die Häuser selbst bewegen kannst. Danach guckst du wie du dich durch einen einzelnen Raum bewegen kannst. Das kann an sich alles noch mit der statischen Welt berechnet werden. Die dynamischen Objekte könnten dann im letzten Schritt oder sogar erst bei der Durchführung der Bewegung betrachtet werden. Durch so einen Ansatz kann es mir jetzt natürlich passieren dass ein Weg nicht mehr zu 100% optimal ist, wobei man sich vorher fragen sollte was am Ende das eigentliche Ziel ist. In einem Spiel geht es darum dass sich Einheiten plausibel und nicht dass sich diese unschlagbar intelligent und effizient verhalten. Sollte das alles nicht reichen dann kannst du die gefundenen Wege theoretisch auch noch irgendwo zwischen speichern.


tldr: A* ist nicht ineffizient. Du kannst mehrere Einheiten zusammenfassen um einen Weg nicht doppelt berechnen zu müssen. Du kannst die Wegfindung auf verschiedenen Genauigkeitsebenen berechnen. Du kannst gefundene Wege cachen.

Hier gibt es eine sehr schöne Artikel über die Möglichkeiten A* mittels Jump Point Search zu erweitern. Kann ich nur empfehlen.
https://harablog.wordpress.com/2011/09/07/jump-point-search/

Hi, ich versuche ähnliches zu implementieren tue mich sehr hart damit, vor allem mit sauberen gruppenbewegung en zum beispiel um ein Hindernis herum oder gar Formationen der Einheiten.

Hier noch ein Artikel dazu:
http://www.gamasutra.com/view/feature/33…ent.php?print=1

Hier hat der AgeOfEmpires Programmierer Dave pottinger was dazu veröffentlicht.

Vielleicht hilft auch das noch

A* vs Flow Field. Häh? Macht doch gar keinen Sinn! A* berechnet doch ein Flowfield und findet dann mit Backtracking den optimalen Weg. Zudem ist A* die optimalste Variante ein Flowfield von A nach B zu erstellen (optimal im Sinne von möglichst wenige Knoten angeschaut um eine zusammenhängenden Pfad von A nach B zu haben). Wo willst du denn dein Flowfield herbekommen? Das muss sich ja bei jedem Klick ändern. Und wenn ich jeden der 1000 Soldaten manuell wähle und irgendwo hinklicke, musst du dann 1000 Flowfields speichern? Und wie gibst du den Weg vor, woher kennst du den? Ist einfach alles leer, so das du die kürzeste Verbindungslinie laufen kannst? Dann brauchst du aber auch kein Flowfield? Ich glaube ich muss ertsmal ein bisschen genauer wissen, was du machen willst.