Suchen Sie den kürzesten Weg durch Hindernisse, wenn alle normalen Wege blockiert sind

10

Ich mache eine Turmverteidigung und habe grundlegende Pfadfindungsfunktionen, aber ich habe ein Problem.

Ich möchte den Pfad blockierbar machen, und wenn ein Block auftritt, greifen die Läufer die blockierenden Türme an.

Ich brauche also einen Weg, um den kürzesten Weg zu finden, der vor allem die geringste Anzahl von Türmen im Weg hat.

Wie mache ich das?

algorithm path-finding tower-defense Dani
quelle
1
Wäre das nicht eine Kollisionserkennung auf Ihrem begehbaren Weg?
Prix
Da die Sperrtürme zerstörbar sind, gibt es tatsächlich einen Weg. Allein die Kosten für das Durchqueren sind viel höher als für das Befahren eines freien Weges. (Siehe Antwort von Coderanger unten)
Bummzack

Antworten:

21

Wenn Sie auf Ihrem Weg punkten, machen Sie es einfach so, dass das Durchqueren eines Turms genauso viel kostet wie das Durchlaufen einer großen Anzahl von Kacheln. Im Allgemeinen wird versucht, sie zu umgehen, aber wenn es keinen solchen Pfad gibt, wird die Ausgabe immer noch die geringste Anzahl von Hindernissen durchlaufen. Sie können die Strafe so einstellen, dass sie manchmal nur durchlaufen wird, anstatt sich um die Karte zu drehen, wenn Sie möchten.

Codierer
quelle
Ich
3
Der A * -Algorithmus ( en.wikipedia.org/wiki/A * _search_algorithm) arbeitet mit Pfadkosten. Erhöhen Sie einfach die Kosten für Segmente, die durch einen Turm verlaufen. Ihre Agenten werden dann versuchen, die Türme zu meiden, oder wenn es "billiger" ist, einen Turm anzugreifen, werden sie ihn angreifen. Die Idee des A * -Algorithmus ist es, die Kosten zu minimieren, damit Sie in der Lage sein sollten, das zu erreichen, was Sie wollen, indem Sie einfach die Pfadkosten
anpassen
Dies ist eine großartige Lösung, an die ich nicht gedacht hätte, danke!
Jhocking
Nur eine Anmerkung: Wenn Sie den Turmknoten enorme Bewegungskosten verursachen, ohne auch die Schätzung zu erhöhen, die für den A * -Algorithmus verwendet wird, wenn der Pfad offensichtlich blockiert ist, bedeutet dies, dass Ihre Agenten jeden Knoten auf ihrem Teil des Hindernisses überprüfen, bevor sie sich für eine Unterbrechung entscheiden. durch Punkt. Abhängig von der Anzahl der Knoten und Agenten kann dies den Algorithmus unerschwinglich langsam machen.
Martin Sojka