A * -Algorithmus für taktische RPGs?

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.

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.

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.

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.

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