Finden möglicher Züge für eine Entität in einem 2D-Kachelspiel

10

Ich habe Probleme mit einem bestimmten Suchbegriff dafür, aber wie würde man die möglichen Bewegungen in einem rundenbasierten 2D-Strategiespiel finden (dh FF: Taktik, Feueremblem, Advance Wars).

Geben Sie hier die Bildbeschreibung ein

Ich denke an dieser Stelle nicht so sehr über Gelände (oder gar Kollision) nach. Ich frage mich nur, mit welchem ​​Algorithmus ich herausfinden kann, dass eine X-Entität 5 Kacheln bewegen und 2 weitere Kacheln angreifen kann.

Ich weiß, dass ich so etwas wie Dijkstra verwenden kann, um den Abstand zwischen zwei Punkten zu ermitteln. Eine mögliche Implementierung besteht darin, am Standort des Spielers zu beginnen und von dort abzweigen, bis die von Dijkstra zurückgegebene Entfernung größer ist als die Anzahl der Züge.

Ich frage mich nur, ob mich jemand in die richtige Richtung weisen könnte (dh Name der Algorithmen, Techniken, Artikel usw.).

NRaf
quelle
Ich denke, es heißt Pfadfindung für einen Suchbegriff? Wenn Sie die Pfadfindung verwenden, könnten Sie Zähler haben, um das zu handhaben, was Sie brauchen
Exikle
Dies ist im Wesentlichen Teil der Pfadfindung (Berechnung von Metadaten für Bewegungskosten). Sie bestimmen nur Orte, die sich in Reichweite befinden, aber Sie bestimmen nicht unbedingt auch die Route, die Sie nehmen würden.
Mario
1
Es ist keine Echtzeit (RTS), wenn es rundenbasiert à la FFTactics ist. : p
Alayric
In 2d könnten Sie Taxicab / Manhattan-Berechnung en.wikipedia.org/wiki/Taxicab_geometry
Gerben Jacobs

Antworten:

5

Ich denke, eine begrenzte Dijkstra ist genau das, was Sie verwenden möchten. Die Art und Weise, wie Dijkstra die Entfernung zwischen zwei Punkten ermittelt, besteht darin, die Entfernung zu jedem Knoten von einem Ursprungsknoten abzubilden und dann den kürzesten Pfad aus dieser Entfernungskarte auszuwählen. Sie möchten praktisch dasselbe tun, außer dass Sie das von ihm erstellte Entfernungsknotendiagramm als Ausgabe und nicht als Pfad zu einem bestimmten Punkt verwenden möchten.

Die einzige Änderung, die Sie vornehmen möchten, besteht darin, die Berechnung der Entfernung von Knoten zu überspringen, die Ihren maximalen Bewegungsbereich bereits überschritten haben. Dann haben Sie ein Knotendiagramm aller Knoten, zu denen die Einheit fahren kann, sowie einen Rand. Schneiden Sie also einfach die Knoten aus, deren Abstand größer als die zulässige Bewegung ist.

Viola.

Mit anderen Worten, so ziemlich das, was Sie in Ihrer Frage beschrieben haben, ist das, was Sie tun müssen. Es hat auch den Vorteil, dass die Ausgabe für die Pfadfindung verwendet werden kann, ohne dass weitere Berechnungen erforderlich sind.

TASagent
quelle
Ich denke, Dijkstra ist in diesem Fall übertrieben. Das OP benötigt keinen Pfad zu allen möglichen Bewegungszielen, nur eine Ja / Nein-Antwort darauf, ob ein Agent dorthin gelangen kann. Er kann einen Pfad später berechnen, sobald der Benutzer einen ausgewählt hat.
Michael Kristofik
Die Kosten für die Verwendung des Dijkstra-Algorithmus zur Berechnung des Pfads nach der Festlegung eines Ziels sind fast genau die gleichen wie für die Verwendung im Voraus (es sei denn, Sie verwenden einen heuristischen Ansatz wie A * für die Pfadfindung). Wenn Sie dies nicht im Voraus tun, entsteht einfach überflüssige Arbeit, da Dijkstra sowohl die Fragen "Wohin kann ich gehen" als auch "Wie komme ich dorthin?" Beantworten würde. Es ermöglicht auch das Hinzufügen von Komplikationen zur Umgebung, die die Bewegungskosten ändern, obwohl dies für die Anwendung möglicherweise nicht erforderlich ist. Darüber hinaus ist der Ansatz gut dokumentiert, was für den Implementierer hilfreich ist.
TASagent
1
Beim Betrachten von Marios Antwort beschreibt er tatsächlich den Algorithmus von Dijkstra, außer dass er die Entfernung invertiert und nicht erwähnt, dass es sich um Dijkstra handelt.
TASagent
1
Ich würde nicht sagen, dass es Dijkstra ist, weil Sie nicht wirklich nach einer kürzesten Route suchen oder versuchen, einen bestimmten Punkt zu erreichen. Es ist im Wesentlichen der erste Teil von Dijkstras Algorithmus, das stimmt jedoch. Das Problem mit Ihrer Formulierung, Dijkstra zu verwenden, kann irreführend sein, und ich denke, das hat Michael auch verwirrt. Er dachte wahrscheinlich, Sie hätten vorgeschlagen, Dijkstra einmal für jedes Feld / jede Zelle zu verwenden.
Mario
1
Verwenden Sie diesen Ansatz, da er gut funktioniert und sehr einfach zu erweitern ist, um Hindernisse zu bewältigen.
NRaf
12

Der einfachste (und wahrscheinlich naivste) Ansatz, den ich mir derzeit vorstellen kann:

  • Beginnen Sie bei Ihrem Charakter und markieren Sie alle umliegenden Felder als steps - 1.
  • Iterate alle über neu gekennzeichneten Felder aus und wieder ihre umliegenden Felder wie markieren , steps - 1wo stepsdas aktuelle Feld der Schrittzahl sein würde, es sei denn , das neue Feld eine bereits höhere Nummer hat.
  • Wiederholen Sie den letzten Schritt, bis Ihnen die Schritte ausgehen.
Mario
quelle
1
Dieser Algorithmus hat einen Namen: Flood Fill .
Michael Kristofik
6
@ MichaelKristofik: Ich würde es Breite erste Suche nennen . Die Flutfüllung erfasst keine Entfernungen.
BlueRaja - Danny Pflughoeft
2

Ich denke, was Sie suchen, könnte Manhattan Distance sein . Wenn Sie keine Hindernisse annehmen, können Sie sagen, dass ein Quadrat einfach erreichbar ist, wenn:

| toX-fromX | + | toY-fromY | <maxMoveDistance

Dieser Algorithmus ist möglicherweise nicht die richtige Richtung, wenn Sie später auf Hindernisse stoßen. Eine Möglichkeit zur Anpassung könnte darin bestehen, Hindernisse „Schatten“ werfen zu lassen und vom nächsten Punkt aus neu zu bewerten.

BEARBEITEN (weil ich jetzt etwas mehr Freizeit habe):

Mit "Schatten" meine ich so etwas: Wenn 0 ein erreichbares Quadrat ist, ist C das Zeichen und X ein Hindernis:

 012345678
0    0
1   00
2  000X
3 000C000
4  00000
5   000
6    0
 012345678

Da (5, 2) ein Hindernis ist, gehen Sie zunächst davon aus, dass Sie mit x> = 5 UND y <= 2 nichts erreichen können. Sie können dann von einem anderen Quadrat aus neu berechnen. Wenn Sie zu (5, 1) gehen möchten, können Sie die Manhattan-Entfernung von (4, 1) berechnen und prüfen, ob diese + die Entfernung vom Charakter zu (4, 1) geringer ist als die Bewegungsentfernung des Spielers.

Dies ist ein ziemlich triviales Beispiel, aber wenn Sie mehrere Hindernisse und / oder einen etwas größeren Bewegungsbereich haben, sollte es in der Lage sein, die Komplexität zu bewältigen.

Ob es tatsächlich besser wäre als nur das Füllen von Fluten, sei es in Bezug auf die Programmierkomplexität oder die Ausführungseffizienz, ich habe keine Ahnung. Es schien nur ein interessanter Weg zu sein, das Problem zu lösen.

Blechmann
quelle
Was meinst du mit Schatten werfen?
NRaf
1
Zur Verdeutlichung bearbeitet.
Tin Man