Implementierung der kooperativen Wegfindung von David Silver in Echtzeit

Ich implementiere derzeit den Silver Cooperative Pathfinding-Algorithmus von David Silver für ein 2D-Spiel mit gitterbasierter Bewegung (alle acht Richtungen).

Das Problem, um das ich mich nicht kümmern kann, ist die Reservierungstabelle in Bezug auf Echtzeit. Ich habe den Algorithmus vollständig in einem eigenen Testfeld implementiert. Meine Implementierung ist jedoch rundenbasiert, wobei sich alle mit der gleichen Geschwindigkeit bewegen.

Das Spiel, in das ich die Gruppenpfadfindung integrieren möchte, hat Echtzeitbewegungen mit Einheiten mit unterschiedlichen Geschwindigkeiten.

Ich habe einige Überlegungen zusammengestellt, die ich berücksichtigen muss, und einige, die mir bei der Umsetzung helfen könnten:

1. Feinde suchen nicht den Charakter des Spielers
2. Einige feindliche Einheiten werden jedoch wandern
3. Gegner haben je nach Feindtyp eine unterschiedliche Bewegungsgeschwindigkeit
4. Der Spieler bewegt den Avatar durch Klicken auf das Ziel (dies leitet einen Spaziergang ein).
5. Der Spieler kann durch Doppelklicken auf ein Ziel mit dem Laufen beginnen (dies kann zwischen Gitterknoten geschehen).
6. Der Spieler hat Verbündete, die dem Avatar folgen
7. Verbündete rennen, um mit dem Avatar Schritt zu halten, wenn er zu weit entfernt ist, und beginnen erneut zu laufen, wenn sie nah genug sind (dies kann auch zwischen Gitterknoten geschehen).
8. Geschwindigkeiten sind keine perfekten Vielfachen voneinander

Unter Berücksichtigung dieser Faktoren besteht meine derzeitige Teillösung aus Folgendem:

• Aufgrund der Überlegungen 1 und 2 teilen sich die Feinde Reservierungstabellen, da ich sie in denselben Intervallen bewegen kann, damit ihre Zeiten übereinstimmen
• Aufgrund der Überlegungen 3 und 8 unterscheiden sich die Reservierungstabellen der Feinde durch die Bewegungsgeschwindigkeit. Ich denke darüber nach, weil ich nicht sicher bin, wie ich eine Reservierungstabelle für alle verwenden soll, wenn ihre Geschwindigkeiten nicht perfekte Vielfache voneinander sind.
• Aufgrund der Überlegungen zur Geschwindigkeitsänderung von 4, 5, 7 und 8 werden die Pfade der Spieler und Verbündeten neu berechnet, wenn sie zu laufen oder zu laufen beginnen, da dies die Pfadkoordination beeinflusst.
• Da Pfade für den Spieler-Avatar im laufenden Betrieb neu berechnet werden können, muss ich zwei Reservierungstabellen speziell für den Spieler haben (eine für den Spaziergang, eine für den Lauf). Möglicherweise müsste ich auch zwei Reservierungstische haben, die die Verbündeten teilen können (einen für den Spaziergang, einen für den Lauf).
• Aufgrund der Tatsache, dass Pfade zwischen Knoten neu berechnet werden können, muss ich meiner Meinung nach Geschwindigkeitsänderungen so begrenzen, dass sie nur dann auftreten, wenn sich eine Einheit direkt auf einem Knoten befindet, anstatt die Geschwindigkeit zwischen Knoten so ändern zu können, wie sie derzeit funktioniert . Andernfalls müsste ich wohl die Zeit berechnen, die benötigt wird, um den nächsten Knoten zu erreichen, und diese dann auch irgendwie in der Reservierungstabelle nachverfolgen.

Schließlich sind hier Dinge, über die ich mich wundere:

• Ich muss die Reservierungstabelle nicht vollständig verstehen, wenn die Koordinierung der Einheiten so schwierig ist. Wie definiere ich die Zeit eines Knotens in der Raum-Zeit-Karte, wenn nicht um wie lange es dauert, bis eine Einheit von einem Knoten zum anderen gelangt?
• Wird die diagonale Bewegung ein Problem bei der Definition der Zeit eines Knotens in der Raum-Zeit-Karte sein?
• Gibt es eine einfachere Möglichkeit, diese Implementierung zu implementieren, als einen anderen Algorithmus zur Pfadfindung für Gruppen zu implementieren?
• Wenn es einen anderen Pfadfindungsalgorithmus gibt, den Sie empfehlen, bin ich ganz Ohr, aber zu diesem Zeitpunkt in der Entwicklung gibt es höchstwahrscheinlich keine Zeit, etwas Neues zu implementieren, es sei denn, das Codieren und Integrieren in das Spiel würde weniger Zeit in Anspruch nehmen als das Jammen der bereits codierte Algorithmus ins Spiel.

Sie können gerne Vorschläge machen, wie Sie die Bewegung von Feinden, Spielern und Verbündeten geringfügig ändern können, wenn dies die Implementierung erheblich erleichtert. Ich freue mich über jede Hilfe, die Sie anbieten möchten. Vielen Dank für Ihre Zeit!

Da Sie mit diesem Ansatz vor dem Lesen des verknüpften Dokuments nicht vertraut sind, scheint die Verwirrung durch die Verwendung mehrerer Reservierungstabellen zu entstehen. Das würde den Sinn einer Reservierungstabelle verfehlen. Sie könnten Kollisionen zwischen Einheiten desselben Typs verhindern, aber eine schnelle Einheit und eine langsame Einheit, die versuchen, denselben Raum zu durchqueren, könnten immer noch in einem Kollisionsreaktionstanz enden, wenn sie versuchen, sich durcheinander zu bewegen. Außerdem wird auf Seite 11 des verknüpften PDF-Dokuments das spezifische Problem behandelt, das besagt, dass erwartet wird, dass sie eine Reservierungstabelle gemeinsam nutzen.

Wenn Ihr Entwurf eine freundliche Einheit erfordert, die an einer Gruppe feindlicher Einheiten vorbeirennen kann, teilen sich Verbündete und Feinde ebenfalls eine Reservierungstabelle. Wenn Sie speziell möchten, dass sie einen Kollisionstanz machen, wenn sie nahe beieinander liegen, könnten Sie vielleicht separate Tabellen für jede Gruppe verwenden, aber ich würde trotzdem denken, dass es vorzuziehen ist, alle Pfade auf derselben Reservierungstabelle zu belassen und sich auf Verhaltenslogik zu verlassen Bestimmen Sie, ob sie aufhören zu interagieren oder sich weiter bewegen. Womit ich meine, Sie könnten einen Teil Ihrer Logik hacken, indem Sie absichtlich die Wegfindung versuchen, aber ich empfehle sehr dringend dagegen.

Ich denke, ich sehe, wo die Unsicherheit für diagonale Bewegungen oder unterschiedliche Geschwindigkeitsmultiplikatoren eintritt, aber auch hier würde das PDF anzeigen, dass weiterhin dieselbe Reservierungstabelle verwendet wird und ein größerer Platz für Einheiten reserviert wird, deren Bewegungsgeschwindigkeiten nicht sauber in das Intervall passen durch die Tabelle festgelegt. Wenn sich eine Einheit diagonal bewegt und während eines Teils der Reservierungstabelle teilweise mehrere Kacheln belegt, reservieren Sie alle diese Kacheln für dieses Intervall. Wenn sich in x Sekunden eine schnellere oder langsamere Einheit teilweise in einer Kachel und teilweise in einer anderen befindet, weil sie sich mit einer Geschwindigkeit bewegt, die nicht ein sauberes Vielfaches des in der Tabelle verwendeten Intervalls ist, reservieren Sie beide Kacheln.

Schließlich sollte eine Änderung der Einheitsgeschwindigkeit vom Laufen zum Gehen keine zweite Reservierungstabelle erzeugen, sondern den Pfad dieser Einheit entlang der einen Reservierungstabelle aktualisieren, die alle Einheiten gemeinsam nutzen.

Der einzige Fall, in dem ich es für angemessen halte, mehrere Reservierungstabellen zu haben, ist, wenn Sie unterschiedliche Bewegungshöhen haben (in einem 2D-Spiel oder einem 3D-gerenderten Spiel, in dem die Bewegung auf 2D-Ebenen beschränkt ist), in denen fliegende Einheiten über die Köpfe von fliegen können Bodeneinheiten ohne Kollision. In einem vollständigen 3D-Spiel würden Sie eine 4D-Reservierungstabelle verwenden.

Es kann hilfreich sein, etwas in die Animation zu lesen. Konzeptionell teilt die Reservierungstabelle (meiner Meinung nach) einige Elemente mit der Animation eines Scheitelpunkts, von dem erwartet wird, dass er sich von diesem Punkt zu diesem Punkt bewegt, beginnend zu diesem Zeitpunkt und endend zu diesem Zeitpunkt, während die Spieluhr so ​​gut wie garantiert nicht perfekt aktualisiert wird im Takt der Keyframe-Intervalle des Modells.