Wie funktioniert die Pfadfindung in RTS-Spielen?

42

[Crossposting von Stackoverflow]

In einem Spiel wie Warcraft 3 oder Age of Empires scheinen die Möglichkeiten, mit denen sich ein KI-Gegner auf der Karte bewegen kann, nahezu unbegrenzt zu sein. Die Karten sind riesig und die Position anderer Spieler ändert sich ständig.

Wie funktioniert die KI-Wegfindung in solchen Spielen? Standardmethoden für die Graphensuche (wie DFS, BFS oder A *) scheinen in einem solchen Setup nicht möglich zu sein.

Decken
quelle
2
Warum würde A * in dieser Grafik nicht funktionieren?
User712092
Related blog: ai-blog.net/archives/000152.html
tenfour
1
@tenfour, die Verbindung ist jetzt unterbrochen.
Montreal

Antworten:

29

In den meisten Fällen ist die Verwendung von A * über einem Navigationsnetz (allgemein als "Navmesh" bezeichnet) die Wegfindungslösung, die kommerzielle RTS verwenden. Es gibt eine detaillierte Erklärung, wie navmeshes arbeitet, warum sie eine bessere Lösung als Wegpunkt - Systeme sind, und Links zu Implementierungsressourcen, hier .

Wenn Sie spezielle Spielmodi (Punkt- / Knotenerfassung) oder Einheiten entwickeln möchten, die patrouillieren, Deckung suchen usw., möchten Sie wahrscheinlich eine Wegpunktebene auf Ihrem Navmesh implementieren, um das KI-Verhalten zu steuern ( keine Pfadfindung ).

Ari Patrick
quelle
17

Schauen Sie sich den Flowfield- Algorithmus an, der in Supreme Commander 2 verwendet wird. Er ist viel besser als die meisten RTS-Pathfinding-Systeme (fahren Sie mit ein paar Beispielen auf 0:50 fort).

ZorbaTHut
quelle
4
Das ist eine wirklich coole Demo, aber sie sagt mir nichts über die Implementierung selbst
MetaGuru
4
Sie haben es in einem Satz erwähnt - es basiert auf der Crowd Flow-Forschung von UW, die Sie unter grail.cs.washington.edu/projects/crowd-flows finden .
Der Flowfield-Algorithmus scheint ziemlich interessant zu sein und scheint definitiv eine viel bessere Arbeit als die meisten Algorithmen zu leisten, aber ich wünschte, es gäbe eine öffentliche Dokumentation darüber, wie das System selbst funktioniert, und nicht nur darüber, auf welchem ​​System es basiert. Natürlich gibt es viele Fragen, die Entwickler stellen sollten, bevor sie ein Kernsystem wie dieses implementieren. In diesem Fall scheint es jedoch die einzige Möglichkeit zu geben, diese Fragen zu beantworten, indem sie das System zuerst implementieren. :(
Ari Patrick
2
@Kragen: Du brauchst wirklich nur zwei Einheiten, bevor ein einfaches A * (besonders Wegpunkt) dazu führt, dass sie immer wieder aufeinander stoßen, und du brauchst eine Art System, um das Problem zu umgehen.
5
Basierend auf dem Video sieht die Wegfindung von Starcraft 2 so aus. Verwendet SC2 Flowfield?
Chris Bui
7

Viele ältere Spiele verwenden A *. Das ursprüngliche Starcraft verwendete A *; was zu einigen Problemen im Umgang mit Kollisionen führte. Starcraft 2 beherrscht Kollisionen sehr gut und nutzt ein Schwärm- / Flockverhalten, um die Flüssigkeitskontrolle großer Gruppen aufrechtzuerhalten. Dieser Spielev-Artikel beschreibt, wie dies erreicht werden könnte.

phillipwei
quelle
2

Ich stimme den anderen Antworten bereits zu, versuche aber auch, WoW / Warcraft3 als tatsächliche 2D-Welten zu betrachten. Sie sind nicht so verschieden von Fliesen, es sind nur die Fliesen.

Sie könnten sich auch überlegen, wie ein GPS den besten Weg findet. es gibt jede Menge Hinweise für die Wegfindung durch verknüpfte Karten.

Ich denke, einige der ersten "Quake Bots" -Skripte könnten Ihnen auch helfen, da sie für die Arbeit in "unbekannten Gebieten" entwickelt wurden, weil wir unsere eigenen Levels von Grund auf neu entwerfen konnten.

Alles in allem würde meine persönliche Art, mit einer solchen Karte umzugehen, darin bestehen, sie als A * -Pfadfinder zu betrachten. Aber zuerst würde ich jeden "Kachelpunkt" vorberechnen und all diese mit "nächster Nachbar" usw. indizieren. Wenn ein Objekt von A nach B gehen muss, dann schaue einfach in B nach, was damit verbunden ist, und wiederhole dies bis zu dir erreiche das Ziel.

Abhängig von der Art des Spiels und der Landschaft / des Szenarios können auch andere Taktiken vor dem Scannen hilfreich sein. Einige Spiele haben sehr kleine Hindernisse und dies können "Straßenlinien" -Bewegungen sein, andere "Wie kann ich mich fortbewegen" für Objekte.

Hoffe, das ergibt ein wenig Sinn und hat dir vielleicht ein paar Gedanken zum Arbeiten gegeben.

BerggreenDK
quelle
1

Die meisten Spiele verwenden einen Suchalgorithmus oder A *, um Pfade auf einer Karte zu finden. Die KI ist in einigen Aspekten offensichtlich aus Leistungsgründen optimiert.

Sie werden dies in Starcraft 2 bemerken, wo Zerglings offensichtlich überhaupt nicht gut zurechtkommen. Es wäre ein CPU-Albtraum, dies für Zerglings zu tun. Sie tun einfach das Beste, um von A nach B zu gelangen, und versuchen nicht einmal, den besten Weg zu finden. Sie werden so nah wie möglich kommen und dann an den Drosseln oder Rampen den Flaschenhals schließen.

Bryan Harrington
quelle
1

Karte ist ein Raster. Das Gitter ist eine Grafik. Ein * arbeitet mit einem Graphen, es ist ein Suchalgorithmus für Graphen. Ein * sollte einige Knoten des Graphen durchsuchen.

Wie bereits erwähnt, können sie Navigationsnetze verwenden. Aber das A * (oder etwas Ähnliches) befindet sich sowieso auf diesem Netz, weil Polygone dieses Netzes nur Knoten eines Graphen sind; Ein * sucht dann nach einem Pfad von einem Polygon zu einem anderen Polygon.

Wir sind uns nicht sicher, ob es sich um Warcraft- oder kommerzielle Spiele handelt, aber es gibt auch eine Technik namens Collaborative Diffusion , die sehr einfach ist. es wird normalerweise auf Gitter getan. Es gibt auch Techniken namens Potential Fields , die denen der vorherigen sehr ähnlich sind, wenn sie nicht gleich sind.

Sie könnten auch versuchen:

  • ob für einige dieser Spiele Quellcode verfügbar ist
  • ob für einige Klone dieser Spiele Quellen verfügbar sind
  • ob SDK oder Editoren etwas nicht andeuten
  • Fragen Sie die Arbeitgeber von Unternehmen, die diese Spiele herstellen. Einige von ihnen sind möglicherweise bereit, sie zu teilen
user712092
quelle
0

Ich bin völlig unerfahren, aber ich denke, dass eine gute Lösung auf Heuristiken basiert, nicht auf einer vollständigen Überprüfung der bekannten Karte. Ich kann mir vorstellen, dass Heuristiken lokal und erfahrungsbasiert sind. Lokale Kontrollen können auf lokalen Geländekontrollen und Hindernissen basieren und sich in die gewünschte Richtung bewegen. Ich denke, dass die meisten Karten keine komplexen labyrinthartigen Bewegungen erfordern, sondern ziemlich miteinander verbunden sind. Eine andere Heuristik besteht darin, zuvor bekannte Pfade (die von anderen Einheiten oder explizit vom Benutzer erkundet wurden) zu verwenden, um Einheiten an bekannte oder nahezu bekannte Positionen zu bewegen. Aber ich spreche über das Bewegen auf großen Karten, nicht wirklich in geschlossenen Räumen, wie ZorbaTHut sagte. In überfüllten Fällen kann der Algorithmus komplexer sein und eine Art "Vorhersage", Koordination zwischen Einheiten desselben Teams oder einfach semaphorische Wartestrategien erfordern. Ebenfalls,

Ich denke, heuristische Algorithmen sind gut, weil sie normalerweise eine gute Lösung für große Räume mit einer angemessenen Rechenzeit bieten (was wichtig ist, wenn Sie viele Einheiten bewegen).

Es tut mir leid, wenn dies eine generische Antwort ist: Ich habe mit Menschenmengen gearbeitet, aber der Raum war ziemlich eigenartig und ich kann nicht genau erklären, wie der Algorithmus funktioniert hat (er basierte auf Agenten, jedenfalls nicht global definiert). Ich hoffe, Sie können einige nützliche Ideen aus meiner Antwort erhalten.

AkiRoss
quelle
Mmmh, ich frage mich, was an dem, was ich gesagt habe, falsch war. War es zu schwer, einen Kommentar zu schreiben?
AkiRoss
Übrigens möchte ich hervorheben, dass A * einen heuristischen Ansatz verwendet. Danke für den -2.
AkiRoss
Ihre Antwort lautet: "Graben A * und seine Art, und rollen Sie Ihre eigenen". Das kann der Anfang einer vernünftigen Antwort sein, aber Sie geben außer dem Vorschlag nur sehr wenige Informationen an. Der Grund für das Abstimmen ist, dass Sie nicht klar machen, wie schwierig die Implementierung Ihrer Lösung ist. Ich bezweifle nicht, dass ein Supergenie mit einer unbegrenzten Zeit einen Suchalgorithmus für ein gegebenes RTS programmieren / optimieren kann, der A * auf einem Navmesh überlegen wäre. Aber "Genie" und "Unbegrenzt" sind sehr schwer zu bekommen.
deft_code
Oh, richtig. Ich dachte, der Typ wollte eine generische Antwort, da er nicht fragte, wie man eine macht, sondern wie sie im Allgemeinen funktionieren. Wie auch immer, ich bin kein Experte, wie gesagt: Ich habe nur einige Informationen zu den Lösungen gegeben, die ich über das Erkunden großer Räume in einer allgemeinen IA-Anwendung kenne. Vielen Dank für Ihren Kommentar.
AkiRoss