Du bist nicht angemeldet.

Werbeanzeige

1

24.04.2017, 16:50

Welche Pfadfindung sollte ich nutzen?

Hallo

Der Teil meines Spieles wofür ich die Wegfindung brauche lässt sich am ehesten so beschreiben: es ist eine Art Mount&Blade Schlachtfeld in 2D, indem man seine Truppen aus der Vogelperspektive wie bei Total War steuert. Jeder Soldat ist einzeln wählbar und ich würde mich freuen weit über 1.000 Einheiten pro Schlacht in Echtzeit ohne FPS Verlust zu befehligen. Wenn es am Ende aus Performance Gründen nur maximal 200 werden ist das halt so, aber erst mal die Ziele hoch stecken. :-)

Also A* ist direkt raus. Performance Killer.
Flowfield Pathfinding ist vielleicht mein Kandidat, ich habe gelesen das bis zu 500 Einheiten damit gleichzeitig Ihren Weg finden können UND sie umliegende Einheiten berücksichtigen, um nicht gleichzeitig über dasselbe Feld zu laufen.

Aber brauche ich überhaupt eine Wegfindung? Die Einheiten sollten sich lediglich nicht ineinander befinden... den Weg gebe ich ja sowieso vor, ein Schlachtfeld ist ja kein Labyrinth.

Morgen mache ich mich ans programmieren ... wäre cool noch ein wenig Input vorher zu bekommen :-)

2

24.04.2017, 17:37

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.

3

24.04.2017, 19:26

Das ganze auf der Grafikkarte berechnen zu lassen hat den Vorteil, dass diese normalerweise bei einem 2D Spiel sowieso nicht ausgelastet wird, richtig?

NachoMan

Community-Fossil

Beiträge: 3 907

Wohnort: Berlin

Beruf: (Nachhilfe)Lehrer (Mathematik, C++, Java, C#)

  • Private Nachricht senden

4

24.04.2017, 20:16

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.
"Der erste Trunk aus dem Becher der Erkenntnis macht einem zum Atheist, doch auf dem Grund des Bechers wartet Gott." - Werner Heisenberg
Biete Privatunterricht in Berlin und Online.
Kommt jemand mit Nach oMan?

5

05.05.2017, 01:19

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?

6

05.05.2017, 20:05

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.

Schorsch

Supermoderator

Beiträge: 5 185

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

7

05.05.2017, 20:43

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.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Renegade

Alter Hase

Beiträge: 477

Wohnort: Berlin

Beruf: Certified Unity Developer

  • Private Nachricht senden

8

05.05.2017, 21:15

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/
Liebe Grüße,
René

9

15.05.2019, 18:08

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

TGGC

1x Rätselkönig

Beiträge: 1 809

Beruf: Software Entwickler

  • Private Nachricht senden

10

16.05.2019, 08:30

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.

Werbeanzeige