Gibt es Pfadfindungsalgorithmen, die mit unterschiedlichen Bewegungstypen umgehen können?

12

Ich entwickle einen Bot für einen BattleTech-Brettspielsimulator http://en.wikipedia.org/wiki/BattleTech , der rundenbasiert ist.

Das Brett ist in Sechsecke unterteilt, von denen jedes einen anderen Geländetyp und eine andere Höhe hat. Sie fahren einen Roboter, der über sie fährt, um andere Roboter zu zerstören.

Ich kenne nur die Dijkstra- und A * -Pfadfindungsalgorithmen, aber das Problem ist, dass es drei Arten von Bewegungen gibt: Gehen, Laufen und Springen mehrerer Sechsecke (jede von ihnen hat ihre eigenen Regeln). Laufen und Gehen sind fast dasselbe.

Der beste Weg könnte eine Kombination oder jede Bewegungsart sein. Hier ist ein Beispiel für eine Karte: http://megamek.info/sites/default/files/isometric_view.png

Kennen Sie einen guten Algorithmus für diese komplexe Wegfindung oder eine Möglichkeit, A * -Ergebnisse für jede Bewegungsart zu kombinieren?

ai movement path-finding alexvisio
quelle
Ich denke, dies wird oft durch eine geschickte Manipulation eines gewichteten Pfades mit A * (wobei das Gewicht die Kosten dieses Pfades / Quadrats sind) gehandhabt. Wenn beispielsweise das Springen vorzuziehen ist, wird es weniger schwer (z. B. 5) als das Gehen (z. B. 10).
Asche999
Wie genau unterscheiden sich die drei Bewegungsarten? Können sie kombiniert werden (gehe zu Kachel A, renne zu B und springe dann in derselben Runde zu C)? Wenn ja, welche Regeln verhindern, dass der Spieler immer die billigste Methode verwendet, um von Feld A zu Feld B zu gelangen?
Philipp
@Philipp Ja, das können sie sein, wenn sie A * verwenden. Sie können jedes Plättchen, auf das Sie sich bewegen können, mit jeder Bewegungsart zur offenen Liste hinzufügen. Anhand des Preises für jedes Plättchen + einer guten Heuristik können Sie bestimmen, welches Plättchen Sie weiterentwickeln möchten.
Altar
@Philipp Nein, Sie können pro Spielzug nur eine Bewegungsart verwenden.
Alexvisio
Gehen: Bewegen Sie sich mit geringem Höhenunterschied durch die Sechsecke. Laufen: das Gleiche, aber Sie können weit gehen, obwohl Sie Hitze erzeugen und an Genauigkeit verlieren (es ist also nicht immer das Beste). Springen: Sie können Hindernisse (eine Mauer oder einen Fluss) überspringen, anstatt um sie herum zu gehen.
Alexvisio

Antworten:

10

Sowohl Dijkstra als auch A * können den Kanten (= Verbindungen) von einer Kachel zur anderen unterschiedliche Kosten hinzufügen. Sie ermöglichen es auch, zwei Knoten (= Kacheln) mit mehr als einer Kante zu verbinden, die jeweils unterschiedliche Kosten verursachen.

Der alternative Sprungmodus würde bedeuten, dass es eine alternative direkte Kante von jedem Plättchen zu jedem Plättchen in Sprungdistanz gibt. Da ein Mech in einer Runde entweder laufen oder springen kann, sind die Kosten für die Verwendung dieser Kante die Bewegungspunkte einer ganzen Runde zuzüglich der verbleibenden Punkte der aktuellen Runde, als es in dieser Runde bereits eine Bewegung gab.

Nach Ihrer Beschreibung macht die Entscheidung für Gehen oder Laufen keinen großen Unterschied in Bezug auf die Wahl des Pfades, sondern es scheint eher eine strategische Entscheidung zu sein. Der Schauspieler kann definitiv gehen, wenn das Ziel in der aktuellen Runde erreicht werden kann, ohne auf Laufen zurückzugreifen. Ansonsten gibt es viele Faktoren zu berücksichtigen, wie zum Beispiel:

  • Aktuelle Hitze und Wahrscheinlichkeit, in den Kampf verwickelt zu sein, bevor er sich abkühlen kann
  • Schwierigkeit von irgendwelchen Schüssen, die diese Runde abgefeuert werden müssen
  • wie strategisch wichtig es ist, schnell ans ziel zu kommen

Es gibt keine strengen Regeln, um diese Entscheidung zu treffen. Das Beste, was Sie tun können, ist ein heuristischer Ansatz. Weisen Sie allen Umständen positive oder negative Punktwerte zu, addieren Sie sie und prüfen Sie, ob das Ergebnis positiv oder negativ ist.

Es gibt noch einen weiteren Faktor bei der Pfadfindung, den Sie berücksichtigen sollten: Unter bestimmten Umständen kann es für einen Mech sinnvoll sein, zu vermeiden, dass er an bestimmten Orten seinen Zug beendet. Wenn Sie sich in einem Gefahrenbereich befinden, ist es möglicherweise besser, drei Runden von A nach B zu drehen, aber jede Runde in Deckung zu beenden, als nur zwei Runden zu verwenden, die jedoch am Ende jeweils freigelegt sind. Oder vielleicht nicht. Das hängt von den Umständen und der genauen Spielmechanik ab. Dies ist wiederum eine strategische Entscheidung, die Sie auf der Grundlage von Heuristiken treffen müssen. Sie können dies darstellen, indem Sie den Kanten, die den Zug auf einem gefährlichen Plättchen beenden, zusätzliche Kosten hinzufügen, um die KI von diesem Zug abzuhalten.

Philipp
quelle