Wie kann man die Reichweite möglicher Bewegungen in einem rundenbasierten, entfernungsbasierten Strategiespiel bestimmen?

Ich erstelle ein zweidimensionales, rundenbasiertes Strategiespiel mit C ++ und SFML-2.0. Die Bewegung ist eher entfernungsbasiert als gitterbasiert, mit mehreren unterschiedlichen dreieckigen Teilen, die sich in einer bestimmten Umdrehung entweder an Ort und Stelle drehen oder vorwärts bewegen können.

Die Bewegung funktioniert so, dass der Spieler einen Ort auswählt, an den sich das Stück bewegen soll, wodurch ein potenzieller Pfad für das Stück generiert wird. Sobald der Spieler seine Entscheidung bestätigt hat, bewegt sich das Stück auf diesem Weg zum gewünschten Ort. Die Wege sind durch zwei Faktoren begrenzt: Entfernung, wie weit ein Stück gehen kann, unter Berücksichtigung von Kurven (wenn es also eine Kurve gibt, ist dies die Länge entlang der Kurve und nicht direkt von Punkt zu Punkt); und Lenkwinkel, wie weit sich das Teil an einem beliebigen (und bis zu jedem) Punkt drehen kann, während es sich bewegt (z. B. von -30 bis 30 Grad).

Meine Frage ist, wie ich vorgehen soll, um den Bereich potenzieller Orte zu bestimmen, an die der Spieler das Stück bewegen kann.

Ich bin mir nicht ganz sicher, welche Gleichungen und / oder Algorithmen ich hier verwenden soll. Mein ursprünglicher Plan war extrem überkompliziert, bis zu einem Punkt, an dem es nahezu unmöglich war, ihn umzusetzen, geschweige denn zu erklären, und ich bin an diesem Punkt völlig verloren, als das Projekt ins Stocken geriet.

Wie kann ich die Reichweite einer Einheit unter Berücksichtigung ihres Wenderadius bestimmen?

Zum Beispiel im folgenden Bild. Die roten, blauen und grünen Linien wären alle gleich lang. Der violette Kreis kennzeichnet den Bewegungsbereich, den das Gerät bewegen kann. (Die Form ist wahrscheinlich ungenau und die Linien sind wahrscheinlich nicht wirklich die gleiche Länge, aber Sie erhalten die Idee)

Generieren Sie mit Dijsktra ein Fluss- oder Distanzfeld.

Füllen Sie im Wesentlichen ein Raster mit dem Dijkstra-Algorithmus ohne Ziel aus (wahrscheinlich ein anderer Name dafür; weiß es nicht). Nehmen Sie einfach jeden offenen Knoten, berechnen Sie erreichbare Nachbarn, verschieben Sie sie in die offene Liste, setzen Sie sie in die geschlossene Liste, aktualisieren Sie den "nächsten" Pfad des übergeordneten Knotens entsprechend usw. Berücksichtigen Sie bei der Ermittlung der Kosten für das Erreichen eines neuen Knotens die Abbiegebeschränkungen.

Das Ergebnis ist nun, dass Sie ein Netzwerk aller Ihrer Knoten haben, um zum Start zurückzukehren. Knoten, die nicht erreicht werden können, wurden vom ersten Schritt nicht berührt. Für Knoten, die erreicht werden können, wird das Element "Nächster Knoten auf dem bestmöglichen Pfad zum übergeordneten Pfad" berechnet, sodass Sie sowohl alle Knoten hervorheben als auch diese Informationen verwenden können, um den Bewegungspfad anzuzeigen oder auszuführen, wenn der Benutzer über markierte Bereiche schwebt oder darauf klickt.

Eine Brute-Force-Lösung wäre:

1. Erstellen Sie einen Kreis von Eckpunkten um die Einheit, wobei sich die Einheit in der Mitte befindet. Der Radius des Kreises ist die maximale Bewegungsentfernung. Die Dichte der Scheitelpunkte kann sich ändern, je nachdem, wie detailliert das Endergebnis sein soll.
2. Simulieren Sie für jede Scheitelpunktposition die Bewegung der Lenkeinheit in Richtung dieser Position. Dies erfolgt in einer engen Schleife ohne Rendern.
3. Wenn der maximale Abstand in der Lenksimulation erreicht ist, bewegen Sie den Scheitelpunkt zum Punkt der simulierten Einheit. Dieser Punkt ist der Punkt, an dem die Einheit diesem Scheitelpunkt am nächsten kommen kann, bevor die aktuelle Kurve beendet ist. Dies hat den Effekt, dass der Kreis auf die Größe der tatsächlichen Bewegung verkleinert wird.
4. Verwenden Sie diese Scheitelpunkte zusammen mit einem auf der Einheit zentrierten Scheitelpunkt, um einen gerenderten Kreis zum Zeichnen der möglichen Bewegungsentfernungen zu erstellen.

Wenn Sie also mit dem blauen Kreis beginnen, verarbeiten Sie Ihre Pfade und erhalten den lila Kreis. Anschließend können Sie diese Punkte mit einem Mittelpunkt auf der Einheit verwenden, um die roten Dreiecke zu erstellen, die für die Anzeige der Form erforderlich sind. (Wenn ich nur dieses Bild mache, wird mir klar, dass diese Form nicht korrekt ist, aber es wird interessant sein zu sehen, was tatsächlich korrekt ist.)

Ich werde Seans Lösung in einer separaten Antwort näher erläutern, da sie einen anderen Ansatz darstellt als den, den ich ursprünglich vorgeschlagen hatte.

Diese Lösung ist wahrscheinlich die am besten zugängliche Methode. Es erfordert die Partitionierung Ihrer Umgebung in Knoten. Ja, dies führt einen gitterbasierten Ansatz wieder ein, aber er kann relativ gut gemacht oder für eine breite Pfadfindung mit einer feineren Positionierung innerhalb des Knotens verwendet werden. Je gröber die Knotenstruktur ist, desto schneller ist die Pfadfindung.

Das große Problem hierbei ist, dass Sie sich tatsächlich mit Schiffsverkleidungen befassen, sodass viele herkömmliche Pfadfindungslösungen nicht ohne Änderungen verwendet werden können. Diese sind normalerweise pfadunabhängig, da es ihnen egal ist, wie Sie zu dem Knoten gekommen sind, in dem Sie sich befinden. Dies funktioniert einwandfrei, wenn Beschleunigung, Verzögerung und Drehung sofort und kostenlos sind. Leider ist das Wenden für Sie nicht kostenlos. Da es jedoch wirklich eine zusätzliche Information gibt, die in dieser Vereinfachung gelöscht wird, können wir sie als eine andere Variable codieren. In der Physik wäre dies als Phasenraum bekannt.

Unter der Annahme von 2 Dimensionen können Sie für 3 extrapolieren:

Normalerweise benötigen Sie einen Knoten für jede zulässige diskrete Koordinatenposition. Beispielsweise:

(0,0) - (1,0) - (2,0)
  | \  /  |  \  / |
(0,1) - (1,1) - (2,1)

Sie würden einen Knotengraphen benachbarter Punkte erstellen und diese durch räumliche Nachbarschaft verbinden. Dann würden Sie den Dijkstra-Algorithmus verwenden und Knoten töten, die den für den Zug zulässigen Bewegungswert überschreiten, bis keine unerforschten lebenden Knoten mehr mit erkundeten Knoten verbunden sind. Jeder Knoten verfolgt die kleinste Entfernung, die erforderlich ist, um ihn zu erreichen.

Stellen Sie sich denselben Knotengraphen in drei Dimensionen vor, um diese Methode für die Verwendung mit Rotation zu erweitern. Die Z-Richtung entspricht der Drehung / Ausrichtung und ist zyklisch. Wenn Sie also weiter in + Z-Richtung fahren, kehren Sie zu Ihrem Ausgangspunkt zurück. Jetzt werden Knoten, die benachbarten Positionen entsprechen, nur über die dieser Richtung entsprechende Ausrichtung verbunden. Sie iterieren wie gewohnt über die Knoten, die mit bereits erkundeten Knoten verbunden sind. Ich würde empfehlen, in diesem Schema auf N, NE, E, SE, S, SW, W, NW zu beschränken.

Diese Lösung kann Ihnen alle zugänglichen Regionen des Weltraums sowie den besten Weg, um dorthin zu gelangen, wie viel Rotation Sie haben, wenn Sie dort ankommen, und alle Orientierungen, die Sie haben könnten, wenn Sie dort ankommen.

Wenn Sie das Pathing dann tatsächlich ausführen, können Sie es interpolieren / kubisch spulen, damit es authentischer aussieht.

Es hört sich so an, als müssten Sie möglicherweise zuerst entscheiden, wie genau das Einschalten unterwegs funktionieren soll. Optionen wie:

• Wenn sie sich innerhalb des Kegels bewegen, drehen Sie sich zuerst und beginnen Sie dann, sich zu bewegen. Dies ist die einfachere Implementierung und der einfachere Pfad. Es ist auch weniger interessant, deshalb würde ich es nicht verwenden wollen.

• Kontinuierliches Drehen während der Bewegung bis zu insgesamt 45 Grad. Dieser ist viel kniffliger und hoffentlich der, nach dem Sie suchen. Die numerische Integration über den Pfad mit einem festen Zeitschritt ist wahrscheinlich der einfachste Weg, sich diesem zu nähern. Ihr Kegel wird durch die maximale (+ X Grad pro Schritt) und minimale (-X Grad pro Schritt) Drehung begrenzt.

Wie man mit der zweiten dieser Anforderungen am besten durch den Weltraum fährt, hängt weitgehend von der Umgebung ab, in der sie sich bewegen. Wenn es viele Hindernisse gibt, die man überwinden muss, kann es sehr schwierig und sehr teuer werden. Wenn dies nicht der Fall ist, können Sie die Drehung von vorne laden (und sogar verjüngen), um an der gewünschten Stelle zu landen.

Ich habe das Gefühl, dass ich die Themen, zu denen Sie eine Frage hatten, möglicherweise nur teilweise behandelt habe. Sie können also gerne weitere Kommentare hinzufügen, und ich kann die Diskussion erweitern.