Welche Wegfindungsalgorithmen gibt es? [geschlossen]

Ich möchte mehr über die Algorithmen zur Pfadfindung erfahren. Gibt es eine Grundierung oder Materialien oder Tutorials im Internet, die ein guter Anfang für mich wäre?

Wenn Sie nachforschen und mehr über die Pfadfindung im Allgemeinen erfahren möchten, würde ich definitiv empfehlen, mehr als nur einen Algorithmus zu lernen. Sie möchten die Gesamtkonzepte verstehen, können sie jedoch auf alle Bereiche anwenden, an denen Sie arbeiten. Die meisten Spieleentwickler, die eine ernsthafte Pfadfindung benötigen, schreiben am Ende ihre eigenen benutzerdefinierten Algorithmen, obwohl sie stark auf bekannten Lösungen basieren. Jedes Spiel ist anders und hat unterschiedliche Anforderungen.

Ich beginne damit, einige der bekannteren Methoden wie A *, Dijkstras Algorithmus, Tiefen- und Breitensuche nachzulesen. Im Internet gibt es viele gute Informationen zu diesen Themen. ( http://en.wikipedia.org/wiki/Pathfinding )

Achten Sie beim Lesen auf die Vor- und Nachteile der einzelnen Ansätze sowie auf die Art der Daten, mit denen der Algorithmus arbeiten kann. Kann es auf dreidimensionale Pfade angewendet werden? Kann es geändert werden, um der menschlichen KI Rechnung zu tragen, die die Landminen auf der Karte meiden möchte?

Wenn es um die Wegfindung geht, ist A * so ziemlich das goldene Ticket, das jeder benutzt. Sie sollten auf jeden Fall wissen, wie es funktioniert. ( http://en.wikipedia.org/wiki/A*_search_algorithm )

Hier ist ein gutes Beispiel für A * für ein RTS-Spiel, bei dem Entitäten unterschiedlicher Größe berücksichtigt werden müssen: http://aigamedev.com/open/tutorials/clearance-based-pathfinding/

Viel Glück!

Pfadfindungsalgorithmen sind im Grunde genommen Algorithmen zur Lösung von Problemen bei der Graphensuche.

http://en.wikipedia.org/wiki/Pathfinding#Algorithms

Am bekanntesten ist der Djikstra-Algorithmus: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

und dessen Variante A * Suchalgorithmus: http://en.wikipedia.org/wiki/A*

Dies ist eine großartige Einstiegsressource, die alle Aspekte der Pfadfindung in einem sehr leicht verdaulichen Ansatz behandelt.

Amits Notizen zur Pfadfindung

... Pathfinding befasst sich mit dem Problem, einen guten Weg vom Startpunkt zum Ziel zu finden. ― Hindernissen ausweichen, Feinden ausweichen und Kosten (Kraftstoff, Zeit, Entfernung, Ausrüstung, Geld usw.) minimieren. Bewegung spricht das Problem an, einen Pfad einzuschlagen und sich auf diesem zu bewegen. Es ist möglich, Ihre Anstrengungen nur für eine davon zu verwenden. In einem Extremfall ein ausgeklügelter Pfadfinder in Verbindung mit einem einfachen Bewegungsalgorithmus ...

Die Wegfindung ist ein ziemlich gelöstes Problem ... Wie in fast jeder Antwort hier erwähnt, wird eine Variation von A * das sein, was Sie verwenden.

Die größere Herausforderung für mich ist, wie Sie Ihren Weg darstellen möchten . Verwenden eines Gitters, von Pfadknoten, Navigationsnetzen, hierarchischen Gittern oder anderen komplexen Strukturen usw.

Ich habe keine konkreten Referenzen im Sinn, aber wenn Sie AIGameDev erkunden , erhalten Sie alle möglichen Ideen, was es gibt.

Denken Sie daran, dass jede Darstellung ihre Vor- und Nachteile hat. Es geht nicht darum, den "Besten" zu finden, sondern darum, den zu finden, der am besten zu Ihrem Gameplay passt .

Auf Wikipedia gibt es eine gute Liste: Pathfinding

Soweit ich weiß, sind A * und D * beide sehr beliebt.

Es gibt verschiedene Algorithmen zur Wegfindung.

Eines der beliebtesten ist wahrscheinlich A * ( A-Star ). Dies ist ein sehr nützlicher Algorithmus, wenn Sie über eine heuristische Funktion verfügen, mit der Sie die geschätzten Kosten für das Erreichen eines Ziels ermitteln können (Beispiel: Entfernung der Sichtlinie zum Ziel). Ein * ist sehr nützlich, um den kürzesten Weg von einem Start- zu einem Endpunkt zu finden.

Abgesehen davon gibt es auch den Dijkstra-Algorithmus, der sehr nützlich ist, um den nächsten Gegenstand aus mehreren Gegenständen zu finden. Z.B. wenn Sie herausfinden möchten, welches Power-Up (oder ähnliches) Ihrem Spielcharakter am nächsten kommt.

Es gibt mehrere andere Algorithmen, aber ich denke, A * ist bei weitem der beliebteste. Mat Buckland hat ein exzellentes Kapitel über die Wegfindung in seinem Buchprogrammierspiel AI by Example . Ich empfehle Ihnen dringend, eine Kopie davon zu erhalten. Ansonsten findest du jede Menge Informationen online, indem du nach "A Star search" suchst.

Hier ist ein Tutorial zur Verwendung des Dijkstra-Algorithmus zur Pfadfindung.

Hier ist ein gutes Beispiel für die Verwendung von A * in einem Spiel mit Pseudocode: http://www.anotherearlymorning.com/2009/02/pathfinding-with-a-star/

Dies ist keine große Einführung, aber wir haben im letzten Herbst 2009 in unserer Algorithmusklasse ausführlich über Graph-Algorithmen gesprochen. Wir haben dieses Buch verwendet,

Einführung in Algorithmen, 3. Auflage von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein

http://mitpress.mit.edu/algorithms/

und es hat auch begleitende YouTube-Vorträge aus einer MIT-Klasse.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

Die Kapitel 17, 18 und 19 befassten sich mit kürzesten Wegen.

Siehe [Grafik- und Baumsuchalgorithmen] in Wikipedia 1 . Sie sind so ziemlich nur Variationen von State Space Search. Sie müssen nur all diese durchgehen und herausfinden, wo sie sich unterscheiden.

Es gibt auch Collaborative Diffusion , einen der zuvor erwähnten Algorithmen, die auf interessante Weise durchgeführt werden.

Dieser sieht interessant aus:

http://www.codeproject.com/Articles/455 Ich frage mich, ist es besser als A *?