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

11

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)

Geben Sie hier die Bildbeschreibung ein

sfphilli
quelle
Es wird immer noch nur die gleiche (Gesamt-) Distanz zurücklegen können. Bei der Frage geht es also wirklich darum herauszufinden, wie weit es sich dreht. / Wie viel muss es drehen? / Wo muss es sich drehen? Sie müssen wahrscheinlich mit der Bestimmung des regulären Pfades beginnen und dann einen Startbeginn für Winkel über einem bestimmten Betrag zurückgehen. Beachten Sie, dass der endgültige Abstand auf einem geraden Pfad (spätestens abbiegen) länger ist als bei den Kurven.
Uhrwerk-Muse
Ja, die zurückgelegte Strecke ist der Hauptbegrenzungsfaktor. Meine größte Hürde dabei ist, dass ich berücksichtigen muss, dass sich das Stück an jedem Punkt, den es erreichen kann, drehen und weiter drehen kann, solange noch Abstand vorhanden ist.
Sfphilli
Was meinst du mit der Reichweite, die eine Einheit bewegen kann? Du meinst die Punkte, zu denen es sich bewegen kann? Wie vertraut sind Sie mit linearer Algebra (Vektoren)?
BlueRaja - Danny Pflughoeft
1
Welches reale Szenario versuchen Sie zu modellieren? Ihr Problem ist in Bezug auf die Anforderungen zu vage, was dazu führt, dass zu viele Lösungsansätze vorgeschlagen werden. Es gibt bekannte Ansätze für (praktisch) jedes spezifische Problem in diesem Bereich, aber jeder ahnt, welches dieser vielen Probleme Sie tatsächlich angehen.
Pieter Geerkens
1
@PieterGeerkens Ich nehme an, weil OP keinen Code anfordert, fordern sie einen Algorithmus an. Und haben genug Details über das Szenario geliefert, dass ein Algorithmus vernünftigerweise konzipiert werden könnte. Dies ist üblich und akzeptabel.
MichaelHouse

Antworten:

4

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.

Sean Middleditch
quelle
Nicht ganz, wie ich das Konzept erklären oder umsetzen würde, aber sicherlich der richtige Ansatz.
Pieter Geerkens
Mein Verständnis des Algorithmus ist, wie er ist, dass Knoten-Traversal pfadunabhängig sein muss. Um dies zu erreichen, müssen Sie einen weiteren Freiheitsgrad (eine weitere Achse zum Erstellen Ihrer Knoten) hinzufügen, der der Ausrichtung gewidmet ist. Mit anderen Worten, Sie hätten einen Knoten für jede Kombination aus verschiedenen X, Y, möglicherweise Z und Facing. Andernfalls unterscheidet das Finden des kürzesten Pfades zum Betreten eines Knotens beim Verlassen des Knotens nicht zwischen den verschiedenen Facings. Ist das korrekt? Wenn dies der Fall ist, ist diese Methode möglicherweise zu intensiv?
TASagent
@TASagent: Guter Punkt, ich habe das nicht ganz durchdacht. Der Algorithmus ist dann vielleicht ein bisschen anders, aber der Ansatz sollte funktionieren.
Sean Middleditch
@PieterGeerkens: Ich stimme zu, es ist eine schlechte Erklärung. Sie sollten Ihre eigene Antwort geben, die alles besser erklärt.
Sean Middleditch
Dies scheint ziemlich nahe an dem zu liegen, was ich brauche, aber ich muss zugeben, dass ich noch nie von diesem Algorithmus gehört habe und daher nicht weiß, wie ich ihn auf das verallgemeinern soll, was ich brauche. Haben Sie zufällig einen Link zu guten Informationen oder Tutorials?
Sfphilli
4

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.

Geben Sie hier die Bildbeschreibung ein

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

MichaelHouse
quelle
3

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.

TASagent
quelle
1
Das ist ausgezeichnet. Ich muss ein wenig über den Algorithmus recherchieren und in meinem Spiel damit experimentieren, aber das scheint mir wirklich die perfekte Lösung zu sein, zumal ich ihn auf einige andere wichtige Teile des Spiels verallgemeinern kann.
Sfphilli
1

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.

TASagent
quelle
Ich möchte auf jeden Fall die zweite Option verwenden, um an jedem und möglicherweise jedem Punkt entlang eines Pfades bis zu (zum Beispiel) 45 Grad zu drehen. Es wird auch Hindernisse geben, die jeweils größer als die Teile sind (denken Sie an riesige Felsen). Ursprünglich dachte ich darüber nach, einen Kegel möglicher Endpunkte zu generieren und dann für jeden dieser Endpunkte einen neuen Kegel usw. für jeden möglichen Ort zu generieren, bis die maximal zurückgelegte Strecke erreicht ist. Trotzdem bin ich mir nicht ganz sicher, wie ich dies ohne verrückte Überkomplikation umsetzen soll.
Sfphilli
Hmmm, es scheint, dass ich über einige Details ein wenig unklar war / bin. Wenn ich auf die Frage zurückblicke, sehe ich, dass Sie "rundenbasiert" angegeben haben und dass die Einheiten sich in ihrem Zug "drehen oder bewegen" können. Bedeutet das dann, dass der Spieler seine Aktionen viele Runden im Voraus plant und Sie die Wegfindung durchführen möchten, während er sich bewegt? Eine weitere Klarstellung, wie Bewegung funktionieren soll, wäre hilfreich.
TASagent
Nein, ich meinte damit, dass der Spieler in einer bestimmten Runde entweder seine Figur an Ort und Stelle drehen kann, wie weit er möchte, oder sich in die Richtung bewegen kann, in die er bereits schaut. Wenn sie sich bewegen, können sie eine bestimmte Strecke entlang eines Pfades zurücklegen und sich während der Bewegung bis zu einem bestimmten Winkel (z. B. zwischen -45 und 45 Grad) drehen oder lenken. Stellen Sie sich also vor, ein gewählter Pfad würde eine Kurve beinhalten, um sich nach links oder rechts zu bewegen. Der Pfad wird dadurch bestimmt, dass der Spieler einen Punkt auswählt, zu dem er sich bewegen möchte, und zwar innerhalb des Bereichs möglicher Punkte, die ich nur schwer bestimmen kann.
Sfphilli
Ok, es hört sich tatsächlich so an, als wären Ihre gewünschten Eigenschaften möglicherweise zu restriktiv für den Dijkstra-Algorithmus, über den wir oben sprechen: - \. Möglicherweise. Ich werde später einige Dinge dafür skizzieren, wenn ich nach Hause komme.
TASagent
Möglicherweise möchten Sie einige dieser Informationen, die Sie gesammelt haben, bearbeiten, um das Problem in der ursprünglichen Frage zu klären, damit Personen, die später kommen, mit weiteren Informationen beginnen können.
TASagent