Dynamischer Pfad-Algorithmus für Tower Defense-Spiel

16

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.

Dani
quelle

Antworten:

8

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

John Haugeland
quelle
Wenn ich mit A * nicht so vertraut bin, wie würde ich mich mit sich dynamisch ändernden Umgebungen befassen? Bei jedem Frame neu berechnen? Bei Kollisionen?
Justin L.
1
Im Allgemeinen würden Sie in einem einfachen Spiel wie diesem jeden Frame neu verschieben. Das Kartenraster ist wahrscheinlich sehr klein und die Anzahl der Agenten beträgt höchstens Hunderte. Wenn es sich um ein großes Leistungsproblem handelte, konnten Sie es später optimieren, indem Sie den Baum nur bei Bedarf neu erstellten.
Coderanger
6
Wenn es träge ist, meine Empfehlungen: Berechnen Sie nicht den Pfad für jeden Mob. Wahrscheinlich gehen sie alle den gleichen Weg. Ich berechne nur bei neuer Turmplatzierung neu, und der Turm befindet sich im aktuellen Pfad . Sogar dann, mache eine Neuberechnung für Monster nur an Punkten auf dem Weg vor dem Blockquadrat, nicht für Mobs, die daran vorbeigehen und es daher egal ist. Um die Wegfindung zu verkürzen, können Sie den Weg zum Quadrat nach dem blockierten Quadrat einschränken, da Sie den Pfad bereits von dort kennen.
Seanmonstar
4
Tatsächlich ist "Mob" Fachsprache (und MMO / MUD-Player) für "Mobiles Objekt".
3
Ungeachtet dessen ist es seit langem in MUD1 und Standard genug, um in vielen Publikationen aufgetaucht zu sein. en.wikipedia.org/wiki/Mob_%28computer_gaming%29
19

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.

Eiche
quelle
1
Es wäre auch einfach, dies dynamisch über Frames zu verteilen, wenn sich die CPU-Last ändert.
Am
+1 für A * ist nicht der richtige Algorithmus.
Ricket
5

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

Richard Fabian
quelle
4

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.

ZorbaTHut
quelle
1
Es ist erwähnenswert, dass Tower Defense bei Mobiltelefonen beliebt ist, bei denen die Pfadfindung nicht schnell ist. Besonders auf etwas älteren Geräten wie dem Sidekick oder Android 1.6 Geräten.
Seanmonstar
1
Entwickler verwenden seit Jahrzehnten Pfadfindungsalgorithmen wie A * und Dijkstra auf weitaus weniger leistungsfähiger Hardware (denken Sie an Game Boy). Jedes Telefon, das neu genug ist, um einen für Spiele geeigneten Bildschirm zu haben, sollte kein Problem haben, vorausgesetzt natürlich, die Implementierung ist einigermaßen effizient. Hier werden einige raffinierte Optimierungen besprochen: harablog.files.wordpress.com/2009/06/beyondastar.pdf
Mike Strobel
+1. Zu dem gleichen Schluss kam ich, als ich meinen eigenen DTD-Klon entwickelte. Ich habe versucht, die Pfade schrittweise zu aktualisieren, aber der Algorithmus wurde zu komplex. Nachdem ich einen Tag damit verbracht hatte, wechselte ich bei jeder Änderung zu einer vollständigen Neuberechnung. Das hat funktioniert, und mit ein paar Änderungen konnte ich es schnell genug machen.
8.
2

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.

Tenpn
quelle
1

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.

Loktar
quelle
Dies funktioniert nur bei TD-Spielen, bei denen Sie nur Türme am Rand des Pfades platzieren können - keine Spiele, bei denen Türme an einer beliebigen Stelle auf dem Brett platziert werden können.
Iain
Ja, anfangs hat der Autor nicht angegeben, welchen Typ er haben möchte, also habe ich angenommen, dass er nicht dynamisch ist.
Loktar
1

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

Ian Schreiber
quelle
1

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

MrValdez
quelle
1
Vermutlich handelt es sich um etwas wie Desktop TD, bei dem der Benutzer die Karte im laufenden Betrieb erstellt. Trotzdem ist dies für die "dummen" Feinde eine nette Lösung, damit Sie Feinde mit besserer KI ein bisschen schwieriger machen können.
Coderanger