Dynamischer Pfad-Algorithmus für Tower Defense-Spiel

Ich mache einen Tower Defense und brauche einen guten Pfad-Algorithmus dafür.

Ich habe über Dijkstra nachgedacht, aber ich brauche einen, der dynamisch sein kann. Es muss in der Lage sein, sich selbst zu aktualisieren, wenn eine Kante ohne eine vollständige Neuberechnung entfernt oder hinzugefügt wird.

Ich programmiere in C #, wenn es hilft.

Im Allgemeinen sollten Sie A * verwenden, es sei denn, Sie suchen nach etwas ganz anderem.

Ich musste ein ähnliches Problem lösen: Wegfindung auf einem großen labyrinthartigen Gitter mit ständig wechselnden "Kosten" und Barrieren.

Die Sache ist, dass im Tower Defense-Spiel die Anzahl der Entitäten, für die der Pfad gelöst werden muss, in der Regel viel größer ist als die Anzahl der Knoten in der Grafik. Ein * ist nicht der am besten geeignete Algorithmus, da Sie es jedes Mal neu lösen müssen, wenn sich etwas ändert. Gut ist es angebracht, wenn Sie nur einen Pfad finden müssen, aber in meinem Fall musste ich in der Lage sein, Entitäten zu handhaben, die an verschiedenen Orten erscheinen können und jeder seinen eigenen Pfad hat.

Der Floyd-Warshall- Algorithmus ist weitaus geeigneter, obwohl ich für meinen Fall einen benutzerdefinierten Algorithmus geschrieben habe, der bei jeder Änderung eines Knotens die Kosten für diesen Knoten von allen seinen Nachbarn neu berechnet und dann, wenn die Nachbarn geändert wurden, aufgerufen wird rekursiv auf sie.

Zu Beginn des Spiels starte ich diesen Algorithmus einfach auf allen "Ziel" -Knoten. Wann immer sich ein einzelner Knoten ändert (z. B. unpassierbar wird), starte ich ihn einfach auf diesem Knoten, und die Änderung wird an alle betroffenen Knoten weitergegeben und dann gestoppt. Daher ist keine globale Neuberechnung erforderlich, und der Algorithmus ist völlig unabhängig von der Anzahl der Entitäten, für die eine Pfadfindung erforderlich ist.

Mein Algorithmus war im Grunde so etwas wie (Pseudo-Code):

update_node method in Node class:
    $old <- $my_score
    find $neighbor node among all neighbors such that
        $neighbor.score + distance_to($neighbor) is minimal
    $my_score <- $neighbor.score + distance_to($neighbor)
    $next_node <- $neighbor
    if ($my_score != $old)
        for each $neighbor
            $neighbor.update_node()

Die anfängliche Punktzahl hängt davon ab, ob der Knoten ein Ziel oder eine Art Barriere ist.

Der Routenalgorithmus, den ich auf meinem TD verwendet habe, war aufgrund der Anzahl der Entitäten, die ich im Spiel hatte, vom normalen A * -Pfad rückwärts. Anstatt vom Tor zu den Bösewichten zu gelangen, habe ich vom Tor zu jedem freien Feld auf dem Brett geführt.

Dies dauert nicht sehr lange. Sie iterieren das Board nur, bis Sie Ihre "Kosten" gefunden haben, und es bietet ein gutes Feedback für blockierte Routen (wenn Sie diese tun). Der Floyd-Algorithmus ist im Vergleich zu A * schnell und cachefreundlich, da er keine datenabhängigen Suchvorgänge ausführt, sondern nur Daten in Streams lädt und verarbeitet.

Beginnen Sie damit, dass Ihr Board auf unendliche Kosten eingestellt ist, setzen Sie das Zielquadrat auf Null und iterieren Sie dann über das Board, um festzustellen, ob eine benachbarte Zelle weniger kostet als die aktuellen Kosten plus die Reisekosten. Die Reisekosten sind dort, wo Sie Ihre Heuristik angeben (in meinem Fall waren die Kosten für das diagonale Reisen unendlich, aber die Kosten für das Reisen durch einen Turm waren hoch, so dass sie durch Türme essen durften, es sei denn, sie hatten keine Wahl)

Sobald Sie Ihr Kostenraster haben, können Sie schnell ein "Fluss" -Raster daraus erstellen, indem Sie den steilsten Kostengradienten für die Zellen testen. Dies funktioniert sehr gut für große Mengen von bösen Jungs, da keiner von ihnen jemals einen Weg finden muss, sie folgen einfach den virtuellen Wegweisern.

Ein weiterer Vorteil ist, dass Sie diese Aufgabe auf diese Weise nur jedes Mal ausführen müssen, wenn Sie die Hindernisse anpassen (oder in meinem Spiel, wenn sich ein Schleicher durch einen Ihrer Türme frisst). Nicht jedes Mal, wenn ein Creep / Mob das Feld betritt (was bei Tausenden von Mobs und Dutzenden pro Sekunde ein ziemlicher Kopfschmerz gewesen wäre).

Die Wegfindung ist schnell und bei etwas, das der Größe eines normalen Tower Defense-Spiels entspricht, können Sie problemlos einen vollständigen A * - oder Dijkstra-Pass ausführen, wenn sich etwas ändert. Wir reden gut unter einer Millisekunde für eine vollständige Aktualisierung. Jede Art von adaptiver Wegfindung ist schrecklich kompliziert. Machen Sie es einfach, es sei denn, Sie bauen das größte Tower Defense-Gitter der Welt.

Wie funktioniert die A * -Pfadfindung? könnte ein guter Anfang sein :-)

Dies mag für Ihre Lösung zu viel sein, aber denken Sie daran, das Routing rückwärts statt vorwärts durchzuführen.

In einem TD-Spiel versuchen die Gegner im Allgemeinen, ein bestimmtes Ziel zu erreichen. Leite von diesem Ziel zurück zum ersten Feind und speichere diesen Pfad. Verwenden Sie bei der Pfadgenerierung für nachfolgende Feinde den ersten Pfad als Ausgangspunkt usw. Wenn Sie mehrere feindliche Eintrittspunkte oder mehrere Ziele haben, können Sie mit einer Reihe von vorab zwischengespeicherten Pfaden beginnen.

Wegpunkt-Pfadfindung wäre wahrscheinlich das Beste für ein td-Spiel, da das ai im Allgemeinen auf der Grundlage des Levels einem direkten Pfad folgt. Grundsätzlich setzen Sie Ihre Knoten oder Wegpunkte, dann zeigen Sie mit dem "ai" -Punkt auf den Wegpunkt und gehen zu ihm, sobald er sich dem nächsten Wegpunkt nähert.

Da jemand gefragt hat, adressieren Sie sich dynamisch ändernden Umgebungen, indem Sie den Pfad jedes Mal neu berechnen, wenn der Spieler einen Turm platziert oder entfernt. In der Zwischenzeit speichern Sie diesen Pfad im Speicher. Die Umgebung ändert sich nicht bei jedem Frame.

Beachten Sie, dass einige TD-Spiele einen festgelegten Pfad haben und es Ihnen nicht erlauben, Türme darauf zu platzieren. Daher lösen sie die Pfadfindung auf einfache Weise: indem Sie einen Pfad fest codieren und ihn nicht blockieren lassen :)

Eine einfache Lösung ist zu betrügen.

Entwerfen Sie die Karte im Voraus, um sicherzustellen, dass es keine Sackgassen gibt. Fügen Sie dann an jeder Kreuzung einen Auslöser hinzu, mit dem der Charakter eine Route auswählen kann (Beispiel: Immer nach links, Immer nach rechts oder nach dem Zufallsprinzip).