A * -Algorithmus für taktische RPGs?

15

Ich spiele damit herum, ein wirklich schlechtes taktisches Rollenspiel in C ++ zu schreiben. Bisher besitze ich eine 2D-Kachelkarte und habe gerade den A * -Algorithmus basierend auf dem Pseudocode in der Wikipedia in Betrieb genommen .

Aber echte taktische RPGs finden nicht nur den besten Weg in einem flachen Flugzeug und bewegen sich dorthin. Sie haben normalerweise begrenzte Bewegungsbereiche und müssen nach oben oder unten klettern. Wenn Sie jemals Final Fantasy Tactics gespielt haben, sind diese von den Statistiken "Bewegen" und "Springen" betroffen. Hier verliere ich mich. Wie ändere ich den A * -Algorithmus so, dass er den besten Pfad zu einem Ziel findet, der Pfad jedoch nur so viele Kacheln lang ist? Wie soll ich Höhenunterschiede und Sprungwerte berücksichtigen? Wie implementiere ich das Springen über eine Lücke?

Wenn es hilft, wird meine Karte jetzt durch einen Vektor von Kachelobjekten dargestellt. Jede Kachel hat Zeiger auf die Kacheln Nord, Süd, Ost und West, die auf Null gesetzt werden, wenn dort keine Kachel vorhanden ist, z.

user137
quelle
5
Ich weiß nicht, warum die Reichweite ein Problem ist. Finde den kürzesten Weg und bewege danach die "Geschwindigkeits" -Quadrate entlang dieses Weges.
Mooing Duck

Antworten:

33

Klettern und Lücken sind nur verschiedene Kostenfunktionen. Für eine Einheit, die die Lücke überspringen kann, sind die Kosten normal (?), Während für eine nicht überspringende Einheit die Kosten beliebig hoch sind. Klettern kostet extra, ebenso wie schwieriges Terrain usw. Der A * -Algorithmus ist gut in der Lage, Kostenfunktionen zu verarbeiten. Wenn Ihre Implementierung dies nicht bereits tut, suchen Sie einfach bei Google nach einer Implementierung von A * mit einer Kostenfunktion.

Trotzdem halte ich A * nicht für einen besonders guten Ansatz für ein taktisches Rollenspiel. Oder genauer gesagt, es ist keine vollständige Geschichte. Sie möchten nicht, dass Ihre Einheiten blindlings auf ihr Ziel zusteuern. Sie möchten, dass sie sich so positionieren, dass sie Deckung und Hochstand ausnutzen, während sie auf das endgültige Ziel zusteuern und versuchen, Gegner zu flankieren und so weiter. Daher ist der taktische Wert des Endpunkts jeder Bewegung von enormer Bedeutung, nicht nur, wie nahe es dem Ziel ist. Dies erfordert eine gründlichere Problemlösung als die bloße Wegfindung.

Jack Aidley
quelle
10
Gute Punkte in Bezug auf die „taktische Positionierung“, aber diese Entscheidungen können auf einer höheren Ebene als der grundlegenden Pfadfindung angewendet werden. Auf der anderen Seite kann es eine gute Option sein, Kosten auf die Knoten im Pfadfindungsalgorithmus anzuwenden, die von einer Art taktischem Analysegerät generiert werden. Wenn der Feind beispielsweise eine Sichtlinie zum Gelände hat, verursachen Knoten in diesem Gelände hohe Kosten.
DrMcCleod
1
@ DrMcCleod: In der Tat, und das ist, was ich mit "oder genauer gesagt, es ist keine vollständige Geschichte" gemeint habe. Sie könnten sicherlich A * oder einen anderen Algorithmus verwenden, um einen Teil der Verarbeitung durchzuführen, aber ich denke, ich würde Ansätze wie den Versuch vermeiden, beobachtete Knoten durch Bewegungskosten zu vermeiden, da das Bewegen über Gelände, in dem eine Einheit unter Beschuss geraten könnte, besser als eine solche behandelt wird Risiko- / Ertragsberechnung, IMO.
Jack Aidley
13

Wenn Sie alle möglichen Bewegungsoptionen einer Einheit wünschen, verwenden Sie den Dijkstra-Algorithmus .

Der Unterschied zwischen A * und Dijkstra besteht darin, dass Sie mit Dijkstra alle möglichen kürzesten Routen erhalten, die mit bestimmten Kosten erreichbar sind. Wenn noch keine Route Ihr Ziel erreicht, werden die Kosten um eins erhöht und es wird fortgesetzt. A * hingegen berechnet lieber zuerst die Routen, die eine gute Chance haben, das Ziel zu erreichen.

Wenn Sie also nur den kürzesten Weg von Punkt A nach Punkt B wollen, ist A * eine gute Wahl. Aber wenn Sie alle möglichen Bewegungsoptionen und den kürzesten Weg zu jedem von ihnen wollen, dann ist Dijkstra genau das, was Sie wollen.

Alles, was Sie tun müssen, ist, Dijkstas Algorithmus ohne spezifischen Zielknoten auszuführen, jedoch mit einem Höchstbetrag, der nicht überschritten werden darf (Bewegungsbereich der Einheit). Wenn das Reisen zu einem Knoten die maximalen Kosten überschreiten würde, besuchen Sie ihn nicht. Wenn der Algorithmus aufgrund des Fehlens nicht besuchter Kanten beendet wird, ist jeder Knoten in der besuchten Menge ein mögliches Ziel, und die vorherigen Knotenmarkierungen der Knoten bilden eine verknüpfte Liste, die den Pfad zurück zum Anfangsknoten darstellt.

Hinsichtlich der Sprünge: Diese können sowohl in A * als auch in Dijkstra als weitere Kante dargestellt werden. Sie können die gleichen Kosten verursachen wie das Überqueren einer regulären oder einer anderen Kante. Sie können dem Algorithmus auch einen "jump_height" -Parameter übergeben, der den Algorithmus anweist, Sprungkanten zu ignorieren, die eine bestimmte Höhe überschreiten.

Philipp
quelle
9
Erwähnenswert ist hier, dass dies A*nur eine Verallgemeinerung von Dijkstra ist. Wenn Sie also eine verstehen, sollte es nicht allzu schwer sein, die andere zu verstehen.
Cubic
8
In der Tat, wenn Sie eine Heuristik haben, die in Ihrem A * -Algorithmus nur 0 zurückgibt, herzlichen Glückwunsch! Sie haben gerade den Dijkstra-Algorithmus geschrieben.
Yann
9
„Dijkstra gibt Ihnen alle möglichen kürzesten Wege mit einem gegebenen Kosten achieveable, und wenn keiner von ihnen Ihr Ziel erreicht noch erhöht sie die Kosten von ein und fährt fort : “ - Das ist weder , wie es funktioniert noch , was es gibt. Es ist eigentlich nur eine Verallgemeinerung der Breitensuche auf gewichtete Graphen. Es findet einen einzigen kürzesten Weg. Ein * ist nur eine Verallgemeinerung davon, wenn Sie eine Distanz-Heuristik zur Verfügung haben.
BlueRaja - Danny Pflughoeft
1
Ich bin mir nicht sicher, warum dies so positiv bewertet wird. Aus pragmatischer Sicht ist Dijkstra obsolet. Es wird in CS aus pädagogischen und historischen Gründen unterrichtet. Sogar A * ist für ernsthafte Arbeit überholt; Google Maps verwendet es auf keinen Fall. Heutzutage würden Sie nach ArcGraph-Varianten suchen.
MSalters
2
@MSalters Dijkstra und A * sind perfekte Algorithmen für einfache Probleme wie taktische RPGs. Es gibt einen sehr engen Bereich gültiger Bewegungen (Kacheln) und eine sehr begrenzte Anzahl von Möglichkeiten, sich über die Kacheln zu bewegen (orthogonal, manchmal diagonal) und normalerweise einen relativ kurzen maximalen Pfad: SQRT (ArenaWidth² * ArenaHeight²). In rechnerischer Hinsicht ist der Unterschied auf einer modernen Maschine für wahrscheinlich relativ kleine Werte vernachlässigbar. Warum sollte man sich also mit einer komplexeren Implementierung befassen, wenn eine einfache für die hier beschriebenen Zwecke ausreicht?
Valthek
2

Die anderen Antworten enthalten einige gute Informationen. Lesen Sie sie daher unbedingt durch.

Um jedoch Ihre Frage zu beantworten: Auf der Grundlage des Pseudocodes, mit dem Sie verknüpft haben, haben Sie eine Funktion, heuristic_cost_estimatemit der Sie die Kosten von KachelA zu KachelB berechnen (vorausgesetzt, sie sind benachbart). Anstatt eine Ebene (1) für diese Kosten zu verwenden, müssten Sie sie anpassen, um die Kachel- und Einheitenstatistiken sowie möglicherweise die Kantenstatistiken einzuschließen.

Beispielsweise:

if (edge == JUMP && !unit.canJump()) 
    return INF;
if (tile.Type == Forest && unit.moveType == HORSE) 
    return 2;
//Other cases here
//-----
else 
    return 1;

Das gibt dir deinen Weg. Dann würden Sie die Einheit einfach entlang ihres Pfades bewegen, während Sie Bewegungspunkte verbrauchen, und sie anhalten, wenn verbleibende Punkte <edgeCost sind. Beachten Sie, dass dies möglicherweise nicht ganz optimal ist, wenn Sie die verbleibenden Punkte = 1 haben. Es sollte jedoch für ein Übungs-RPG ausreichen. In Wirklichkeit würde man taktischer sein wollen, wie Jack Aidley betonte!

Herausforderung:
Wenn Sie sich weiterentwickeln möchten, möchten Sie wahrscheinlich Djikstras wie vorgeschlagen verwenden, um alle Räume in X-Entfernung zu finden. Dann möchten Sie jedes Feld in dieser Liste auf der Grundlage der Nähe zum Ziel und der Verteidigung nach einem "besten" Ort auswerten Macht, ob du von dieser Position aus angegriffen werden kannst oder nicht usw. Auf der Grundlage dieser Informationen wählst du ein Plättchen und bewegst dich dann auf dem Pfad, den du gerade mit Djikstras berechnet hast.

Mars
quelle
1

Klettern und Lücken sind ziemlich trivial, da sie nur die Kosten verändern. Bei der Pfadfindung (und dem größten Teil der taktischen KI) geht es darum, die Kosten aller zu besuchenden Knoten zu summieren und diese zu minimieren. Eine unpassierbare Klippe hat unendlich (sehr, sehr hohe) Kosten, Pisten haben höhere Kosten als normal usw.

Dies findet jedoch den global optimalen Pfad, der nicht die beste Lösung ist, da echte Gegner normalerweise nicht den optimalen Pfad finden. Es ist höchst unrealistisch, manchmal bis zu einem Punkt, der für den Spieler offensichtlich und ärgerlich ist (insbesondere, wenn die KI als solche im Grunde unbesiegbar ist, weil auch sie das Optimum wählt).

Gute Simulationen finden bewusst nicht den besten Weg. Ein viel besserer Algorithmus könnte darin bestehen, eine hierarchische Pfadfindung durchzuführen - wenn nicht anders angegeben, indem Sie eine gerade Linie auf der Karte zeichnen und 4-5 Wegpunkte nehmen, dann die Pfadfindung von einem Wegpunkt zum nächsten, wobei nur die bisher vorhandenen Knotengewichte berücksichtigt werden bekannt und setzt alle anderen Knotengewichte auf "gleichgültig". Alternativ können Sie A * zuerst in einem gröberen Raster ausführen und dann von einem großen Knoten zum nächsten suchen (aber ich denke, dass das Zeichnen einer Linie auf der Karte auch in Ordnung ist).

Dies ist viel realistischer (und verbraucht auch einen Bruchteil der Verarbeitungsleistung, da das Diagramm viel kleiner ist). Ja, es kann bedeuten, dass sich eine Einheit auf eine Klippe zubewegt, nur um herauszufinden, dass sie nicht darüber hinwegkommt. Das ist in Ordnung, es passiert auch echten Gegnern. Das nächste Mal wird es nicht wieder vorkommen (da jetzt die unendlichen Kosten bekannt sind).

Damon
quelle
1
Wohlgemerkt, diese "einfache hierarchische Pfadfindung" kann ziemlich dumm aussehen. Man bekommt Einheiten, die direkt zu einem Bergrücken laufen, nur um dort festzustellen, dass der Weg blockiert ist. Sie wandern dann durch den Gebirgspass zum nächsten Wegpunkt und von dort zu ihrem Ziel - auch wenn dieser letztere Wegpunkt für sie weit vom Kurs entfernt war. Die Vorverarbeitung hätte den Bergpass im Vordergrund identifiziert und dort hindurchgeführt. Aber selbst wenn Sie das nicht tun, sollten Sie den Rest neu planen, sobald Sie zu weit vom geplanten Kurs entfernt sind.
MSalters
@MSalters: Das kann mit der "draw a line" -Methode schon nach dem ersten Versuch passieren, ja. Es ist unwahrscheinlich, dass es bei der hierarchischen Methode des groben Rasters mehr als einmal vorkommt (die z. B. den Durchschnitt oder den Median oder sogar den maximalen Kostenwert der darin enthaltenen Knoten verwendet). Es ist so ziemlich genau, wie ein menschlicher Gegner spielen würde - vermeiden Sie große Hindernisse , die Sie kennen oder von weitem wie eine Bergkette sehen können, und planen Sie ansonsten eine grobe, meist gerade Route und beißen Sie sich durch. Wenn Sie nicht wissen, dass es einen Berg gibt, gehen Sie direkt dorthin.
Damon