Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Towerdefenes: Performanceproblem mit Wegfindung(A*)

Werbeanzeige

Oberon

Treue Seele

  • »Oberon« ist der Autor dieses Themas

Beiträge: 181

Wohnort: Österreich

Beruf: Student

  • Private Nachricht senden

1

10.01.2011, 20:31

Towerdefenes: Performanceproblem mit Wegfindung(A*)

Ich programmiere an einem Mazing-Towerdefense, d.h. einem Towerdefense, wo die Creeps(Gegner) sich von ihrem Start zum Ziel an Türmen und Mauern vorbeischlängeln müssen (auf einer Tilemap).
Bis jetzt berechne ich einmal pro Gegner-Eingang den Weg vor, so dass alle Creeps die herauskommen, ohne zusätzliche Wegfindung zum Ausgang kommen. Wenn aber jetzt der Spieler etwas baut führt der Wege möglicherweise nicht mehr zum Ziel und außerdem sind alle Creeps unterschiedlich weit gekommen, haben also unterschiedliche Ausgangspositionen. Ich berechne also für jeden Creep am Spielfeld einzeln den Weg neu. Das führt zu merklichen Rucklern, wenn der Spieler einen Turm baut. Bis jetzt habe ich folgende Optimierungsmöglichkeiten in Betracht gezogen:
  • Überprüfen ob der neue Turm im Weg ist, und nur dann den Weg neu berechnen.
  • An der Wegfindungs-Funktion (A* Algorithmus) selbst optimieren (ist da noch viel Potential?).
  • Meistens laufen am Ende wieder alle Creeps am selben Pfad. Ich könnte mir also die schon gefunden Pfade merken, und wenn ich darauf stoße, die Wegfindung abbrechen (bzw. ab da am vorher berechneten Pfad weiterlaufen).
Fallen euch noch andere Optimierungsmöglichkeiten ein? Welche der obigen ist am vielversprechendsten?
Danke schon im voraus für eure Antworten!
oberon00.github.io

PCShadow

Alter Hase

Beiträge: 1 062

  • Private Nachricht senden

2

10.01.2011, 20:50

Zitat von »Oberon«

Überprüfen ob der neue Turm im Weg ist, und nur dann den Weg neu berechnen. [...]
Meistens laufen am Ende wieder alle Creeps am selben Pfad. Ich könnte mir also die schon gefunden Pfade merken, und wenn ich darauf stoße, die Wegfindung abbrechen (bzw. ab da am vorher berechneten Pfad weiterlaufen).

Das ist mit sicherheit ncith verkehrt. Man könnte auch so weit gehen, das sich ja alle creeps auf dem selben pfad befinden, und wieder für alle auf einmal rechnen, sprich, wieder den anfang als startpunkt nehmen, außerdem überprüfen, wo der bisherige pfad unterrochen wurde, und die creeps, die sich vor der unterbrechung befinden, auf den neuen pfad wechseln lassen. Das erzeugt wiederrum für die creeps die sich innerhalb des geänderten pfads befinden, einen suboptimalen pfad (und die notwendigkeit kurzer einzelpfade zweischen den beiden gruppenpfaden), aber man muss zumidnest nicht mehr für jeden über das komplette spielfeld rechnen.

Zitat von »Oberon«

An der Wegfindungs-Funktion (A* Algorithmus) selbst optimieren (ist da noch viel Potential?).

Ich hab mal irgendwo von einer abwandlung von A* gelesen, die speziell für sowas (also neu auftauchende hindernisse) gedacht ist, weiß aber leider nciht mehr, wie sie heißt, bzw. wo ich davon gelesen hab. Aber du könntest ja mal im internet danach recherschieren ;)

dispy

Treue Seele

Beiträge: 101

  • Private Nachricht senden

3

10.01.2011, 23:17

Zitat von »PCShadow«

Zitat von »Oberon«Überprüfen ob der neue Turm im Weg ist, und nur dann den Weg neu berechnen. [...]Meistens laufen am Ende wieder alle Creeps am selben Pfad. Ich könnte mir also die schon gefunden Pfade merken, und wenn ich darauf stoße, die Wegfindung abbrechen (bzw. ab da am vorher berechneten Pfad weiterlaufen).Das ist mit sicherheit ncith verkehrt. Man könnte auch so weit gehen, das sich ja alle creeps auf dem selben pfad befinden, und wieder für alle auf einmal rechnen, sprich, wieder den anfang als startpunkt nehmen, außerdem überprüfen, wo der bisherige pfad unterrochen wurde, und die creeps, die sich vor der unterbrechung befinden, auf den neuen pfad wechseln lassen. Das erzeugt wiederrum für die creeps die sich innerhalb des geänderten pfads befinden, einen suboptimalen pfad (und die notwendigkeit kurzer einzelpfade zweischen den beiden gruppenpfaden), aber man muss zumidnest nicht mehr für jeden über das komplette spielfeld rechnen. Zitat von »Oberon«An der Wegfindungs-Funktion (A* Algorithmus) selbst optimieren (ist da noch viel Potential?).Ich hab mal irgendwo von einer abwandlung von A* gelesen, die speziell für sowas (also neu auftauchende hindernisse) gedacht ist, weiß aber leider nciht mehr, wie sie heißt, bzw. wo ich davon gelesen hab. Aber du könntest ja mal im internet danach recherschieren ;)

Ich tippe mal auf den D*-Algo

MfG
dispy

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

4

11.01.2011, 00:31

Jap,
wobei ich den D* für nicht ganz einfach halte. Wobei dann das Problem bleibt ob er für alle neuberechnen soll oder nicht? Ich vermute, dass das Problem einfach daran liegt das zu viele Berechnungen durchgeführt werden und da auch der D* nicht viel weiter kommen würde. Ich würde es auch so machen, dass einmal überprüft wird, für welche Agents der geänderte Knoten überhaupt interessant ist. Am A* selbst gibts soweit ich weiß nicht so viel zu optimieren. Du könntest eine andere Heuristik verwenden, wobei du dabei wohl nicht so viel Zeit rausholen solltest. Wobei dies sich halt bei vielen Anfragen oder langen Pfaden bemerkbar machen würde. Hier gibts z.B. die Manhattan Distance Heuristic. Du könntest dir ansonsten die Time-Sliced Variante angucken, wobei nicht der komplette Pfad in einem Step berechnet wird. Ansonsten guck mal ob du dir deine Map nicht in einzelne Partitionen einteilst. Dann kannst du gucken welche Agents auf einer Partition liegen und den Weg für die ganze Partition neuberechnen. Mit vorberechneten Pfaden könntest du sicherlich auch eine Zeit rausholen, wenn du dadurch nicht mehr komplette Wege berechnest, sondern nur Teile der davon. Naja durch viele kleine Optimierungen kann man solche Probleme manchmal lösen. Vielleicht hilft dir ja was davon weiter.
„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.“

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

5

11.01.2011, 07:02

Du musst eigentlich ja nur das Stück für alle neu berechnen, welches für alle unterschiedlich ist. Ab einem gewissen Punkt ist die Strecke ja für alle gleich. Wenn du dieses gleiche Stück identifizieren kannst, dann kannst du die Wegfindung, die für jede Creep separat notwendig ist, deutlich kürzer gestalten.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

n0_0ne

1x Contest-Sieger

Beiträge: 678

  • Private Nachricht senden

6

11.01.2011, 08:07

Darf ich mal fragen, wie groß deine Tilemap ist und wie viele creeps da so sind?

Ich hätte nicht gedacht, dass sowas heutzutage noch zu performanceproblemen führt.
http://pixelscientists.com

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

7

11.01.2011, 08:26

Mir ist grad auf dem Weg zur Uni noch ne Idee gekommen. Geht in die Richtung von BlueCobold. Ich vermute dein Spiel wird in etwa so wie viele der Warcraft3 TD's. Für die Wege vom Start der Creeps zum Ziel machst zu Pfade. Beim erstellen der Creeps bekommt jeder einzelne einen der Pfade zugewiesen. Wenn jetzt was gebaut wird, wird geguckt welcher der Pfade betroffen ist. Ist ein Pfad betroffen wird dieser neu Berechnet. So haben die Creeps immer einen aktuellen Weg vom Start zum Ziel. Sollten jetzt Creeps nicht mehr direkt zum nächsten Punkt im Pfad kommen, musst du diesen Teilweg natürlich neu berechnen. Wenn du deine Map in Partitionen unterteilst, kannst du diese Teilwege dann direkt für diese Partition und die darin enthaltenen Creeps berechnen.
„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.“

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

8

11.01.2011, 09:52

Alle haben das gleiche Ziel? Dann brauchst du ueberhaupt keinen A-Stern. Mach einfach ein Floodfill vom Ziel aus und schreibe in jedes Feld die Iterationstiefe. Fuer die Wegsuche muss nun jeder nur noch auf das jeweilige Nachbarfeld wechseln, in dem die Zahl eins niedriger ist. Zusaetzlich Optimierung fuers Update beim Turmbau waere noch, das dein Turm, wenn er auf ein Feld mit x gesetzt wird, du nur die Felder neu fuellen muesstest, die eine Zahl > x haben.

Der Rest ist alles unnoetiger Aufwand, kein Wunder, das es so rumlahmt.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Oberon

Treue Seele

  • »Oberon« ist der Autor dieses Themas

Beiträge: 181

Wohnort: Österreich

Beruf: Student

  • Private Nachricht senden

9

11.01.2011, 15:57

Danke für eure zahl- und hilfreichen Antworten!
Die Map ist nicht sehr groß, maximal ~30x30 Felder.
Floodfill klingt vielversprechend, auch wenn nicht alle Creeps das selbe Ziel haben, aber auch sicher nicht mehr als ~5 verschiedene.
Ansonsten ist es nicht so leicht festzustellen, ob ein Pfad betroffen ist, da es dazu nicht reicht zu prüfen ob der neue Turm direkt auf einem Wegknoten steht, ich will ja auch bei dieser Stellung, das niemand zwischen den Türmen durchkann:

Quellcode

 
1
2

..X...
...X..

Ich muss also die vorberechneten Wege neu berechnen, und wenn sie sich verändert haben, den aller Creeps mit gleichem Ziel jeweils neu berechnen, bzw. wenn sie noch auf dem Pfad sind, ihnen diesen zuweisen. Was auch durchaus machbar ist, und ich glaube ich werde das auch so umsetzen, falls Floodfill doch nicht passt.

EDIT: Floodfill funktioniert perfekt! Danke an TGGC und auch allen anderen für eure Hilfe. :thumbsup:
oberon00.github.io

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Oberon« (11.01.2011, 18:28)

Werbeanzeige

Ähnliche Themen