Ich habe diese Frage zuerst auf Stack Overflow gepostet, aber ich denke, niemand ist sehr an Videospielen interessiert ...

Welche Pfadsuchalgorithmen werden in Spielen aller Art verwendet? (Von allen Arten, in denen sich Charaktere bewegen) Wird Dijkstra viel benutzt? Ich würde nicht denken, da es nicht wirklich die Schritte aufzeigt, die nötig sind, um irgendwohin zu gelangen, oder? Wenn ich es richtig verstehe, bestimmt es nur, welches Objekt am nächsten ist. Ich versuche nicht wirklich, irgendetwas zu codieren. Ich mache nur ein paar Nachforschungen, aber wenn Sie Pseudocode oder etwas einfügen, wäre das in Ordnung (ich kann Java und C ++ verstehen). Grundsätzlich suche ich einen schnellen Überblick über die Wegfindung im Allgemeinen.

Ich weiß, dass A * wie DER Algorithmus für 2D-Spiele ist. Das ist großartig, aber was ist mit 2D-Spielen, die nicht gitterbasiert sind? Dinge wie Age of Empires oder Link's Awakening. Es gibt keine eindeutigen quadratischen Felder, zu denen navigiert werden kann. Was tun sie?

Was machen 3D-Spiele? Ich habe dieses Ding gelesen, http://www.ai-blog.net/archives/000152.html , von dem ich höre, dass es eine große Autorität in diesem Thema ist, aber es erklärt nicht wirklich, WIE, sobald die Maschen gesetzt sind. Die Wegfindung ist abgeschlossen. WENN A * das ist, was sie verwenden, wie wird so etwas in einer 3D-Umgebung gemacht? Und wie genau funktionieren die Splines zum Abrunden von Ecken?

Zu viele Fragen auf einmal, daher ist es schwierig, eine konkrete Antwort zu geben, aber einige dieser Themen zu diskutieren. Ich werde die Antwort in zwei Teile teilen und versuchen, sie so gut wie möglich anzusprechen. Ich behaupte nicht, dass eine dieser Listen vollständig ist , aber sie sind einige der verschiedenen Methoden, an die ich mich erinnern könnte.

Teil 1 - Pfadfindungsalgorithmen

Für den Anfang gibt es viele Möglichkeiten, die Pfadfindung zu implementieren, aber nicht alle geben den kürzesten Pfad zurück oder sind effizient oder sogar zuverlässig. Zum Beispiel:

• Primitive Methoden, die nicht "nach vorne schauen" und jeweils einen Schritt ausführen:

  • Zufälliges Zurücktreten - Gehen Sie Schritt für Schritt in Richtung des Ziels. Wenn Sie auf ein Hindernis stoßen, versuchen Sie, es zu umgehen, indem Sie ein wenig in eine zufällige Richtung zurücktreten und es dann erneut versuchen. Überhaupt nicht zuverlässig und wird in einer Vielzahl von Situationen stecken bleiben.

  • Hindernissuche - Ein anderer Ansatz, ähnlich dem zufälligen Zurücktreten, aber statt sich zufällig zurückzubewegen, beginnen Sie, um das Objekt herumzugehen, sobald eine Kollision gefunden wurde, als ob Sie die rechte Hand an der Wand festhalten und sie berühren müssten. Sobald es keine Kollision mehr gibt, bewegen Sie sich weiter in Richtung des Ziels. Wieder einmal kann in vielen Situationen stecken bleiben.

• Methoden, die vorausschauend den gesamten Pfad auf einmal finden:

  • Breitensuche - Einfaches Durchlaufen von Diagrammen durch gleichzeitiges Besuchen der einzelnen Kinderebenen. Halten Sie an, wenn der Pfad gefunden wurde. Wenn der Graph ungewichtet ist (dh der Abstand zwischen den benachbarten Knoten ist immer gleich), findet er den kürzesten Pfad, wenn auch nicht zu effizient. Bei gewichteten Diagrammen wird möglicherweise nicht der kürzeste Pfad zurückgegeben, es wird jedoch immer ein Pfad gefunden, falls vorhanden.

  • Tiefensuche - Eine andere Möglichkeit, einen Graphen zu durchlaufen, aber anstatt ihn Schicht für Schicht zu nehmen, versucht der Algorithmus, zuerst tief in den Graphen zu suchen. Diese Methode kann Probleme verursachen, wenn die Suchtiefe nicht eingeschränkt ist, insbesondere wenn eine rekursive Implementierung verwendet wird, die zu einem Stapelüberlauf führen kann. Daher ist es normalerweise sicherer, sie iterativ mithilfe eines Stapels zu implementieren.

  • Beste erste Suche - Ähnlich wie bei der Breitensuche, verwendet jedoch eine Heuristik, bei der der vielversprechendste Nachbar zuerst ausgewählt wird. Der zurückgegebene Pfad ist möglicherweise nicht der kürzeste, aber er ist schneller auszuführen als die erste Suche in der Breite. Ein * ist eine Art Best First Search.

  • Dijkstra's Methode - Verfolgt die Gesamtkosten von Anfang an zu jedem besuchten Knoten und verwendet sie, um die beste Reihenfolge für das Durchlaufen des Diagramms zu bestimmen. Funktioniert mit gewichteten Diagrammen und gibt den kürzesten Pfad zurück, erfordert jedoch möglicherweise viel Suche.

  • A * - Ähnlich wie bei Dijkstra, verwendet jedoch auch eine Heuristik, um zu schätzen, wie wahrscheinlich es ist, dass sich jeder Knoten nahe am Ziel befindet, um die beste Entscheidung zu treffen. Aufgrund dieser Heuristik findet A * den kürzesten Weg in einem gewichteten Graphen viel schneller.

• Dann gibt es Variationen von A * (oder Pfadfindungsoptimierungen im Allgemeinen), die es schneller oder an bestimmte Umstände angepasster machen, wie zum Beispiel (siehe verwandte Antwort und eine umfassende Liste zu cstheory.SE ):

  • LPA * - Ähnlich wie A *, kann jedoch den besten Pfad schneller neu berechnen, wenn eine kleine Änderung am Diagramm vorgenommen wird
  • D * Lite - Basierend auf LPA * wird dasselbe getan, jedoch wird davon ausgegangen, dass der "Startpunkt" eine Einheit ist, die sich in Richtung Ziel bewegt, während Änderungen an der Grafik vorgenommen werden
  • HPA * (Hierarchisch) - Verwendet mehrere Ebenen auf verschiedenen Abstraktionsebenen, um die Suche zu beschleunigen. Zum Beispiel kann eine Schicht auf höherer Ebene einfach Räume verbinden, während eine Schicht auf niedrigerer Ebene dafür sorgt, dass Hindernisse vermieden werden.
  • IDA * (Iterative Deepening) - Reduziert die Speichernutzung im Vergleich zu regulärem A * durch die Verwendung von iterativer Vertiefung.
  • SMA * (Simplified Memory Bounded) - Verwendet nur den verfügbaren Speicher, um die Suche durchzuführen.
  • Jump Point Search - Dank an Eric in den Kommentaren für die Erwähnung! Beschleunigt die Wegfindung auf kostengünstigen Rasterkarten ( Link ).

Teil 2 - Darstellung des Suchraums

Und zum Schluss, um diese Frage zu beantworten:

Ich weiß, dass A * wie DER Algorithmus für 2D-Spiele ist. Das ist großartig, aber was ist mit 2D-Spielen, die nicht gitterbasiert sind?

Zwei große Missverständnisse hier! Eigentlich:

1. Ein * ist egal, ob es sich um ein 2D- oder ein 3D-Spiel handelt, und ist für beide Fälle gleichermaßen geeignet.
2. A * funktioniert unter jeder Graphendarstellung, daher ist es egal, ob die Welt ein Gitter ist oder nicht.

Wenn die Welt also kein Gitter sein muss, wie können Sie sie auf andere Weise darstellen? Im Folgenden finden Sie eine kurze Übersicht über die Möglichkeiten, den Weltraum für die Pfadfindung zu unterteilen. Die meisten dieser Möglichkeiten funktionieren sowohl in 2D als auch in 3D:

• Rechteckgitter - Unterteilen Sie die Welt in ein regelmäßiges Quadratgitter, wobei jede Zelle im Gitter ein Knoten im Diagramm ist und die Verbindung zwischen zwei ungehinderten Knoten eine Kante ist.

  

• Quadtree - Ein anderer Weg, um den Raum zu unterteilen, aber anstatt in ein Gitter von Zellen mit normaler Größe zu unterteilen, unterteilen Sie diese in vier und teilen Sie sie dann rekursiv in vier. Durch Hinzufügen einer dritten Dimension wird es zu einem Octree .

  

• Konvexe Polygone - Unterteilen der begehbaren Fläche in ein Netz miteinander verbundener konvexer Polygone. Jedes Polygon wird zu einem Knoten, und gemeinsame Kanten sind die Kanten des Diagramms. Dies können zum Beispiel Dreiecke sein und manchmal sogar ein Netz, das von einem Künstler beim Erstellen der Ebenen-Assets erstellt wurde. Wird oft als Navigationsnetz bezeichnet . Siehe diesen Link . Hier ist ein sehr beliebtes Toolset zum Erstellen von Navigationsnetzen: Recast .

  

• Sichtbarkeitspunkte - Die gebräuchlichste Methode besteht darin, einen Knoten direkt außerhalb der konvexen Scheitelpunkte des Hindernisses zu platzieren und dann jedes Knotenpaar zu verbinden, das sich gegenseitig sehen kann . Überprüfen Sie diesen Link . Die Knoten müssen jedoch nicht die Eckpunkte sein und können vom Designer manuell in der Karte platziert werden. In diesem Fall wird das System häufig als Wegpunktdiagramm bezeichnet .