A*: Wieviele Knotenpunkte sind sinnvoll bei einem Echtzeitstrategiespiel
-
Hallo
Ich habe mir gestern ein wenig was zu A* durchgelesen, jetzt frage ich mich wieviele Knoten ich nehmen sollte damit ich nicht zuviele habe (die CPU hätte viel zu tun) bzw. zu wenig (Einheiten bewegen sich sehr unnatürlich).
Es geht dabei um ein 2D Strategiespiel, mein erste Gedanke wäre das ich die Knoten mit einem Abstand in der Größe des Durchmessers der kleinsten Einheiten anlege.
Ist das schon zu viel? Hat hier jemand Erfahrungen damit?
-
Hängt von deinem System ab. Ich lege Knoten an den Ecken von Hindernissen an. Wenn du ein Gridbasiertes System hast, wirst wohl auf jedem Feld einen anlegen.
Viele Knoten sind selten schlimm, entscheidender ist die Arbeit, die du dir mit jedem Knoten machst. Wenn du sehr aufwändig prüfen musst, ob zwei Knoten verbunden sind, dann tut das auch bei wenigen weh.
-
Optimizer schrieb:
Hängt von deinem System ab. Ich lege Knoten an den Ecken von Hindernissen an. Wenn du ein Gridbasiertes System hast, wirst wohl auf jedem Feld einen anlegen.
Meine Überlegungen wären jetzt in Richtung gridbasiertes System gegangen, ich hätte die Karte in viele Quadrate aufgeteilt und in der Mitte oder an den Eckpunkten die Knoten gelegt, so das ich keine dynamischen Knoten habe.
Hast du evt. etwas zum lesen wie man ein System aufbaut wo Knoten an Hindernissen angelegt werden? Dann wäre doch praktisch jede Einheit ein Knoten (Edit Jede Einheit hätte 4 Knoten), jeder Baum, jedes Gebäude. Was passiert wenn es wenig Hindernisse gibt? Dann ist die Wegfindung doch arg eingeschränkt?
Optimizer schrieb:
Viele Knoten sind selten schlimm, entscheidender ist die Arbeit, die du dir mit jedem Knoten machst. Wenn du sehr aufwändig prüfen musst, ob zwei Knoten verbunden sind, dann tut das auch bei wenigen weh.
Die Prüfung würde imho nicht aufwändig werden
-
Delryn schrieb:
Meine Überlegungen wären jetzt in Richtung gridbasiertes System gegangen, ich hätte die Karte in viele Quadrate aufgeteilt und in der Mitte oder an den Eckpunkten die Knoten gelegt, so das ich keine dynamischen Knoten habe.
Gut. Dann leg einfach auf jedes Feld einen Knoten.
Hast du evt. etwas zum lesen wie man ein System aufbaut wo Knoten an Hindernissen angelegt werden? Dann wäre doch praktisch jede Einheit ein Knoten (Edit Jede Einheit hätte 4 Knoten), jeder Baum, jedes Gebäude. Was passiert wenn es wenig Hindernisse gibt? Dann ist die Wegfindung doch arg eingeschränkt?
Nein. Den idealen Weg gibt's auf jeden Fall, wenn du kein Hinderniss auslässt. Ist doch auch logisch. Am meisten ist die Wegfindung "eingeschränkt", wenn es gar keine Hindernisse gibt.
Die Prüfung würde imho nicht aufwändig werden
Bei so einem freien System? Da brauchst du schon eine ausgeklügelte Prüfung, damit du dabei nicht drauf gehst. Für ein Gridbasiertes System ist sie natürlich trivial.
-
Optimizer schrieb:
Delryn schrieb:
Meine Überlegungen wären jetzt in Richtung gridbasiertes System gegangen, ich hätte die Karte in viele Quadrate aufgeteilt und in der Mitte oder an den Eckpunkten die Knoten gelegt, so das ich keine dynamischen Knoten habe.
Gut. Dann leg einfach auf jedes Feld einen Knoten.
Das klingt so als ob mit dieser Lösung etwas nicht stimmt
?
Fragen wir mal so; warum hast du dich für die dynamische Version entschieden? Warst du nicht auch der der dieses Stonage Spiel programmiert hatte? Gibt es das evt. noch irgendwo?Nein. Den idealen Weg gibt's auf jeden Fall, wenn du kein Hinderniss auslässt. Ist doch auch logisch. Am meisten ist die Wegfindung "eingeschränkt", wenn es gar keine Hindernisse gibt.
Wäre es bei deinem System dann noch möglich wenn es nur eine Einheit gibt sie von a nach b zu schicken, da es dann ja nur die 4 Punkte der Einheit gibt? Irgendwie muss das ja gelöst werden.
Die Prüfung würde imho nicht aufwändig werden
Bei so einem freien System? Da brauchst du schon eine ausgeklügelte Prüfung, damit du dabei nicht drauf gehst. Für ein Gridbasiertes System ist sie natürlich trivial.
War auf auf ein Gatter bezogen
-
Delryn schrieb:
Das klingt so als ob mit dieser Lösung etwas nicht stimmt
?
Fragen wir mal so; warum hast du dich für die dynamische Version entschieden? Warst du nicht auch der der dieses Stonage Spiel programmiert hatte? Gibt es das evt. noch irgendwo?Weil ich wollte, dass meine Figuren überall stehen könen und in beliebige Richtung gehen können. Alternativ könnte man auch ein ganz feines Grid machen und nur auf jedem 10ten einen Knoten legen. Oder ein grobes Grid, und in jede Zelle einen Knoten. Wie auch immer, ich wollte es frei haben.
Das hat auch nicht nur Vorteile, Kollision und solche Sachen sind ungleich schwieriger.
Das Spiel wird's bald wieder geben... es hat ne größere Umstellung hinter sich.Wäre es bei deinem System dann noch möglich wenn es nur eine Einheit gibt sie von a nach b zu schicken, da es dann ja nur die 4 Punkte der Einheit gibt? Irgendwie muss das ja gelöst werden.
Es gibt ja noch die Punkte A und B.
-
Danke für deine Antworten, kann man die neueste alte Version noch herunterladen? Ich würde mir das gerne anschauen
-
Die hab ich leider nicht mehr lauffähig. Ich denke, das wird noch etwas dauern, bis da wieder was geht - ich hab einfach zu wenig Zeit.
-
Wenn du dich gut in komplexe Algos reindenken kannst, dann guck dir auf jeden Fall das Pathfinding mit Hilfe von Binary Heaps an. Die Open-List wird dabei mit einem Quicksort-Ähnlichen Algorithmus organisiert. Meine A* Implementierung ist dadurch je nach Dichte der Hindernisse bis zu drei mal schneller geworden. Ein Tutorial dazu gibts auf www.aiguru.com