Dynamische Wegfindung in Echtzeit?

Ich mache derzeit einige Untersuchungen zur Wegfindung und meine Simulation sieht folgendermaßen aus: Ich habe eine 3D-Szene mit einem dargestellten Start- und Endpunkt. Ich kann Navigationsnetze, Wegpunkte und Polygone erstellen, um die Wegfindung zu erleichtern.

Ich habe einen A * -Algorithmus und einige seiner Varianten ausprobiert und sie funktionieren perfekt. Jetzt interessiere ich mich jedoch mehr für die "dynamische" Wegfindung. Wenn zum Beispiel ein Pfad von Punkt A nach Punkt B gefunden wird und plötzlich ein neues Hindernis auftaucht, möchte ich, dass mein Algorithmus in der Lage ist, einen Pfad sofort neu zu planen und nicht erneut von vorne zu suchen.

Ich habe etwas über den D * -Algorithmus gelesen und mich gefragt, ob dies für das, was ich brauche, angemessen wäre oder wie ein Overkill erscheinen würde.

Meine Fragen lauten also im Wesentlichen: Welcher Algorithmus ist am besten für die dynamische Pfadfindung in Echtzeit geeignet? ODER welche Kombination von Techniken könnte ich stattdessen verwenden?

algorithm path-finding Andrei
quelle

Ich bin nicht sicher, welchen Algorithmus sie verwenden, also ist dies keine Antwort, aber ich stelle mir vor, dass Sie versuchen, dies zu emulieren: YouTube-Video

MichaelHouse

Was ist mit der Verlängerung von A *? Erweitern Sie das, was in den Knoten der offenen / geschlossenen Mengen gespeichert ist, um das, was Sie möchten, und erweitern Sie A *, um es zu berücksichtigen.

user712092

Ich habe nach der gleichen Antwort gesucht wie Sie, und ich habe einen Artikel über HPA * gefunden, der sich auf Videospiele bezieht. Ich suche noch Artikel und werde sie wahrscheinlich umsetzen. Bisher ist es für mich sinnvoll, die Leistung zu verbessern, und es kann sowohl in statischen als auch in dynamischen Umgebungen verwendet werden. Hier ist Artikel

NelsonPunch

Antworten:

D * ist ziemlich involviert - ich empfehle nicht zu versuchen, es zu implementieren. Sogar bei Projekten, die gut finanziert sind und von klugen / erfahrenen Leuten entwickelt werden, wird D * lite verwendet, weil es so schwierig ist, mit D * richtig umzugehen.

Sie könnten an dieser Präsentation interessiert sein, die eine Diskussion über die Wegfindung von Left 4 Dead beinhaltet:

http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Ein Ansatz besteht darin, eine grobe Suche der Ebene A * zu verwenden, um einen allgemeinen Pfad für einen Agenten abzurufen, und dann eine Feineinzelheitssuche der Ebene A * für die lokale Umgebung eines Agenten durchzuführen. Auf diese Weise können Sie die Suche nach Kursdetails A * schnell neu berechnen, wenn sich das Gelände ändert. Anschließend können Sie die Suche nach feinen Details A * schnell nach einem kleinen Segment der Umgebung neu berechnen. Das ist nicht perfekt. Dies funktioniert so lange, wie Ihre Hindernisse nicht mehrere Kursdetail-Diagrammknoten blockieren können, was für die meisten Spiele in Ordnung ist. Dies ist die Methode, die ich empfehle, wenn Sie weniger als 100 Agenten haben.

Wenn Sie Hunderte oder Tausende von Agenten unterstützen möchten, können Sie so etwas wie Continuum Crowds implementieren. Sehen Sie sich diese Studie an: http://grail.cs.washington.edu/projects/crowd-flows/ Hier wird eine rein CPU-basierte Methode beschrieben, die Tausende von Akteuren in einer dynamischen Umgebung unterstützen kann.

Wenn Sie Zehntausende oder Hunderttausende von Agenten unterstützen möchten, können Sie mit GPU-Unterstützung so etwas wie Continuum Crowds implementieren. Hier finden Sie relevante Informationen: https://a248.e.akamai.net/f/674/9206/0/www2.ati.com/misc/siggraph_asia_08/GPUCrowdSimulation_SLIDES.pdf

Hier ist ein Video, in dem die Massen des Kontinuums in Aktion demonstriert werden: http://www.youtube.com/watch?v=lGOvYyJ6r1c (Fahren Sie mit 4:10 fort, um große dynamische Hindernisse wie Autos und Ampeln zu sehen, die Hunderte von Menschen betreffen, die in einer Stadt herumlaufen.)

Olhovsky
quelle

Danke für die Links. D * Lite scheint genau das zu sein, was ich gelesen habe

Andrei

Haben Sie sich einfaches Lenkverhalten angesehen?

http://www.red3d.com/cwr/steer/

Sie können sie verwenden, um von Ihrem A * -Pfad abzuweichen, um lokale Hindernisse zu vermeiden, und dann auf Ihren Pfad zurücklenken, wenn Sie fertig sind.

Es ist auch ziemlich einfach, mehrere Verhaltensweisen zu kombinieren.

BigSandwich
quelle

+1. Ich bin nicht sicher, warum das abgelehnt wurde. Obwohl dies einfach ist und möglicherweise nicht die Antwort, nach der der Fragesteller gesucht hat, denke ich, dass es

themenbezogen ist

Ich habe dieses Lenkverhalten in unserem neuesten Spiel gelesen und umgesetzt. Jetzt werden wir es wieder durch andere Methoden ersetzen. Ich denke, es funktioniert nicht gut zusammen mit vorkomplizierten optimalen Pfaden. Die "Kombination" mehrerer Verhaltensweisen führt normalerweise zu schlechten Ergebnissen. Wenn Sie es dennoch verwenden möchten, versuchen Sie nicht, Ihren Weg gleichzeitig zu steuern und zu verfolgen. Schalten Sie stattdessen auf 100% Lenkung und 100% zurück, sobald Sie das Hindernis passiert haben.

Imi

Da sich Ihr Beitrag im Bereich "Spieleentwicklung" des Stapelaustauschs befindet, antworten Ihnen die meisten Spieleprogrammierer auf folgende Fragen: Es geht nicht um die dynamische Pfadfindung in Echtzeit, es geht um die dynamische Pfadfindung in Echtzeit * nach *!

Einige Kantenfälle, in denen eine Kante in Ihrem Navigationsdiagramm vollständig verdeckt ist, erfordern, dass der Pathfinder einen anderen Pfad berechnet. Meistens können Sie Ihre Objekte jedoch einfach um die Hindernisse herum lenken, die Position vorhersagen und in die richtige Richtung ausweichen. Für die meisten Spiele wäre es zu schwer, die Position dynamischer Agenten im Laufe der Zeit vorhersagen zu müssen, zumal man Spieleraktionen oder Agentenentscheidungen nicht genau vorhersagen kann.

Daher würde ich raten, zunächst das Lenkverhalten (http://red3d.com/cwr/steer/) zu implementieren, Fälle zu behandeln, in denen der Pfad unmöglich wird, und dann eine Ebene darüber hinzuzufügen, um Randfälle zu behandeln, die nicht vorhanden sind. t von den beiden vorherigen Lösungen behandelt.

Hoffe das hilft

emartel
quelle

Oh nein. "Pfadverfolgung" ist das Gleiche wie die Pfadfindung. Es gibt viele Ansätze, die es ermöglichen, Tausenden von Agenten auf einem Desktop-PC in Echtzeit zu folgen , wenn sich Hindernisse ändern. Es ist sicherlich nicht zu teuer, einen Weg für einen einzelnen Agenten zu finden, wenn sich Hindernisse bewegen. Hier ist ein solcher Ansatz von vielen: grail.cs.washington.edu/projects/crowd-flows GPU-beschleunigte Versionen von Continuum-Crowd existieren.

Olhovsky

Da müsste ich nicht zustimmen. Jede Engine behandelt die Pfadfindung und -verfolgung als zwei unterschiedliche Probleme, wobei das erste eine grafische Suche des navigierbaren Bereichs ist und das andere den optimalen Bewegungsvektor innerhalb des lokalen Raums sucht. Ich habe an einer solchen Crowd-Simulation gearbeitet und Middleware hergestellt, die von AAA-Spielen verwendet wird, ohne auf die GPU angewiesen zu sein. Die meisten Implementierungen verwenden ein Flussfeld (den Pfadfinder) und eine Steuerung, um dem Fluss zu folgen und andere Agenten (den Pfadfolger) zu vermeiden. Wie meine Antwort sagte, ist dies eine "Spielprogrammierer" -Antwort, keine akademische Antwort.

Emartel

Ich weiß, dass Sie die GPU nicht für Contiuum Crowds benötigen, weshalb ich eine CPU-basierte Version verknüpft habe. Ihre Beschreibung des folgenden Pfads ist immer noch eine Pfadfindungssuche. Es handelt sich lediglich um eine Pfadfindungssuche auf einer anderen Detailebene in einem anderen Datensatz. Also, was Sie wirklich haben, ist ein Kursdetail-Wegfindungspass und ein Feindetail-Wegfindungspass. Letztendlich versuchen Sie, den Weg zu finden, dem ein Schauspieler folgen sollte. Neue Begriffe dafür zu erfinden, verwirrt die Dinge.

Olhovsky

Es tut mir leid, aber "path following" ist kein erfundener Begriff. Wenn Sie in der Industrie erstellte Dokumente lesen, werden Sie feststellen, dass sie immer wieder verwendet werden: Verknüpfen oder Verknüpfen, um nur einige zu verknüpfen. Leider kann ich Sie nicht mit NDA-geschützten Dokumentationen von Engines / Middlewares verknüpfen, die in der Branche weit verbreitet sind.

emartel

Ihr erster Link ist der Link, den ich übrigens in meiner Antwort angegeben habe. Okay, fair genug, es könnte fair sein, diese Art der Pfadfindung als Pfadverfolgung zu bezeichnen. Letztendlich versuchen beide, den Weg zu finden, dem sie folgen müssen, aber ich denke, dass ich in diesem Fall falsch liege und wir sollten das, was wir in Ihrem zweiten Link sehen, als Pfadverfolgung bezeichnen. ZB das Verknüpfen von groben Pfadpunkten mit kubischen Splies / Biezer-Kurven / Fügen Sie Ihre Methode hier ein. Trotzdem bin ich nach wie vor nicht der Meinung, dass es nicht machbar ist, eine Wegfindung um dynamische Hindernisse herum durchzuführen, wie Ihre Antwort nahezulegen scheint.

Olhovsky