Unlimited Plugins, WordPress themes, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. Games

Serie Künstliche Intelligenz - Teil 1: Pfadfindung

by
Read Time:25 minsLanguages:

German (Deutsch) translation by Katharina Grigorovich-Nevolina (you can also view the original English article)

Dieses Tutorial ist das erste von drei Tutorials, in denen erläutert wird, wie Sie Spielen und Apps, die Sie erstellen, künstliche Intelligenz (KI) verleihen. In diesem ersten Tutorial lernen wir die Pfadfindung kennen.


Endergebnisvorschau

Werfen wir einen Blick auf das Endergebnis, auf das wir hinarbeiten werden:

Klicken Sie auf einen Punkt, dann auf einen anderen Punkt und die KI wird einen möglichst kurzen Weg zwischen ihnen finden. Sie können die Dropdown-Liste verwenden, um den zu verwendenden KI-Algorithmus auszuwählen.


Schritt 1: Überblick über die AI-Serie

Dieses Tutorial ist das erste von drei, in dem es darum geht, von Ihnen erstellten Spielen und Apps Künstliche Intelligenz (KI) zu verleihen. Sie denken vielleicht, dass das zu hart klingt, aber es ist eigentlich ziemlich einfach! Ich werde zwei wichtige Aspekte der KI in Spielen erklären und dann mit dem, was wir lernen, ein cooles Spiel erstellen. Ich wünsche Ihnen viel Spaß beim Verfolgen dieser kurzen Serie!


Schritt 2: Einführung

In Spielen ist einer der wichtigsten Aspekte, es sehr effizient zu machen, mit minimalen Ressourcen zu tun, was es tun muss. Dafür gibt es eine ganze Wissenschaft.

In diesem Tutorial werden wir einen Schlüsselaspekt der Spieleentwicklung behandeln: die Pfadfindung. Wir werden die 2 besten Methoden besprechen, wie sie funktionieren, wie wir sie in AS3 zum Laufen bringen und nicht zuletzt, wann man sie verwendet. Lassen Sie uns beginnen..


Schritt 3: Worum geht es bei Pfadfindung?

Angenommen, Sie befinden sich inmitten eines Waldes mit 50 verschiedenen möglichen Routen vor Ihnen, haben fast keine Energie und müssen den besten Ausweg finden, wie würden Sie das tun?

Eine Möglichkeit wäre, jeder der 50 Routen zu folgen; eine Trial-and-Error-Methode. Sie werden sicherlich aussteigen, aber das würde zu viel Zeit in Anspruch nehmen. Dies ist kein neues Problem und viele Leute haben Ideen, wie man es lösen kann. Einer von ihnen war Edsger W. Dijkstra, der einen Algorithmus entwickelte, um den kürzesten Weg für einen Graphen, eine Quelle und ein Ziel zu erhalten.

Bevor wir mit der Lösung des Problems beginnen können, müssen wir diese Elemente erstellen, den Graphen, der alle Informationen enthält, die Knoten, die den Wegpunkt des Graphen darstellen, und die Kanten, die die Knoten verbinden. Stellen Sie sich den Graphen als Karte vor: Die Knoten sind die Städte und die Kanten die Autobahnen, die sie verbinden.


Schritt 4: Einrichten des Projekts

Bevor wir mit dem Programmieren beginnen, richten wir zunächst unseren Arbeitsbereich ein. Erstellen Sie einen neuen Ordner und nennen Sie ihn "PathFinding". Erstellen Sie darin einen weiteren Ordner und nennen Sie ihn "Graph". Erstellen Sie dann im PathFinding-Ordner eine neue Flash (AS3) FLA-Datei und nennen Sie sie "PathFinding".


Schritt 5: Erstellen des Knotensymbols

In der "Pfadsuche.fla" Datei, gehen Sie zu Einfügen > Neues Symbol und erstellen Sie einen neuen MovieClip namens Node. Wählen Sie "Export for Actionscript" und schreiben Sie als Klasse "Graph.Node"


Schritt 6: Zeichnen des Knotens

Erstellen Sie im Node Movieclip einen neuen Kreis mit einem Radius von 25 und platzieren Sie ihn in der Mitte. Fügen Sie dann ein neues Textfeld hinzu, machen Sie es dynamisch und geben Sie ihm den Instanznamen "idx_txt" und positionieren Sie es in der Mitte der Bühne.


Schritt 7: Erstellen des Knotens

Jeder Knoten besteht aus 2 Hauptelementen; einen Index, um ihn zu identifizieren, und seine Position im Diagramm. Erstellen Sie in diesem Sinne eine neue Klasse innerhalb des Graph-Ordners/-Pakets und nennen Sie sie "Node". Lassen Sie es die Sprite-Klasse erweitern und fügen Sie dann einfach zwei Variablen hinzu: eine int für den Index und eine Vector3D für die Position. Fügen Sie außerdem die entsprechenden Set- und Get-Methoden hinzu:


Schritt 8: Erstellen der Kante

Die Kante enthält drei Elemente: die Indizes der beiden Knoten, die sie verbindet, und ihre "Kosten" (oder in diesem Fall die Entfernung zwischen den Knoten). Erstellen Sie erneut im Graph-Paket/Ordner eine neue Klasse und nennen Sie sie "Edge"; lassen Sie es die Sprite-Klasse wieder erweitern.

Fügen Sie nun zwei Ints für die Knoten und eine Zahl für die Kosten hinzu, fügen Sie dann die entsprechenden Set- und Get-Methoden hinzu:


Schritt 9: Erstellen des Diagramms

Der Graph ist ein komplexeres Element, da er alle Informationen speichern muss. Erstellen Sie im Ordner Graph eine neue Klasse und nennen Sie sie "Graph". Da sie nur Daten enthält, muss die Sprite-Klasse nicht erweitert werden.

Der Graph enthält einen Vektor mit allen Knoten im Graphen, einen weiteren Vektor mit den Kanten, die jeder Knoten hat und einen statischen int, um den nächsten verfügbaren Index für einen Knoten zu erhalten. Auf diese Weise ist es einfacher, auf alle Elemente im Graphen zuzugreifen, da der Knotenindex der Schlüssel des Kantenvektors ist, d. h., wenn Sie die Kanten eines Knotens mit dem Index 3 erhalten möchten, greifen Sie auf den Kantenvektor an der Position 3 zu und erhalten die Kanten für diesen Knoten.

Lassen Sie uns nun diese Variablen erstellen:

Der Graph benötigt auch Methoden zum Hinzufügen und Abrufen von Knoten und Kanten:


Schritt 10: Erstellen eines Diagramms 

Da wir nun alle benötigten Elemente haben, können wir einen Graphen erstellen.

Erstellen Sie im PathFinding-Ordner eine neue Klasse und nennen Sie sie "Main", dies wird unsere Hauptklasse sein:

Jetzt müssen wir die soeben erstellten Klassen importieren, da sie sich im Graph-Ordner befinden. Erstellen Sie dann zwei Variablen: eine für den Graphen und eine andere, die ein Array der Position der Knoten ist, die wir hinzufügen möchten. Danach fügen Sie einfach diese Knoten und ihre Kanten hinzu:


Schritt 11: Wie wählt man den richtigen Pfad?

Wie ich Ihnen bereits sagte, gibt es viele Methoden, um einen Pfad zwischen zwei Knoten zu erhalten, wie DFS (Deep First Search) oder BFS (Broad First Search). , möchten Sie auch den "besten" Pfad wählen, was meistens denjenigen bedeutet, der weniger Zeit in Anspruch nimmt oder der am nächsten liegt, je nachdem, was Sie wollen.

Während dieses Tutorials werde ich es nur als das bezeichnen, das weniger kostet. (In unserem Fall denken Sie daran, dass "Kosten" Entfernung bedeutet. In einem Spiel möchten Sie vielleicht den am wenigsten gefährlichen Weg finden, den am wenigsten Kraftstoff verbrauchen oder den am wenigsten sichtbaren ...)

Es gibt Algorithmen, die je nach Kosten funktionieren, die wichtigsten sind der Dijkstra-Algorithmus und der A* (A-Star)-Algorithmus. Sprechen wir zuerst über den Dijkstra-Algorithmus Al


Schritt 12: Einführung in den Dijkstra-Algorithmus

Dieser Algorithmus wurde 1959 von Edsger Dijkstra entwickelt. Es wird in Abhängigkeit von den Kosten, die jede Kante darstellt, vorangetrieben. Die Kanten mit den niedrigeren Kosten werden immer zuerst ausgewählt. Wenn Sie also das Ziel erreichen, können Sie sicher sein, dass der Pfad mit den niedrigsten Kosten ist, der verfügbar ist.


Schritt 13: Wie funktioniert der Dijkstra-Algorithmus?

Da dieser Algorithmus mit Kosten arbeitet, müssen wir einen Ort haben, an dem wir die Kosten für die Verschiebung zu jedem Knoten von der Quelle (dem Startknoten) speichern; nennen Sie dies einen Kostenvektor.

Wenn die Quelle beispielsweise der Knoten 0 ist, werden beim Zugriff auf den Kostenvektor an Position 3 die bisher niedrigsten Kosten für den Übergang von 0 nach 3 zurückgegeben. Wir benötigen auch eine Möglichkeit, den kürzesten Pfad zu speichern: Erklären Sie im nächsten Schritt den Shortest Path Tree.

Die grundlegenden Schritte des Algorithmus sind die folgenden:

  1. Nehmen Sie den nächsten noch nicht analysierten Knoten.
  2. Fügen Sie dem Shortest Path Tree seine beste Kante hinzu.
  3. Wenn es sich um den Zielknoten handelt, beenden Sie die Suche.
  4. Rufen Sie alle Kanten dieses Knotens ab.
  5. Berechnen Sie für jede Kante die Kosten für die Bewegung vom Quellknoten zum Ankunftsknoten.
  6. Wenn die Gesamtkosten dieser Kante bis jetzt geringer sind als die Kosten des Ankunftsknotens, dann aktualisieren Sie die Knotenkosten mit den neuen.
  7. Nehmen Sie den nächstgelegenen Knoten, der noch nicht analysiert wurde.
  8. Wiederholen Sie dies, bis das Ziel erreicht ist oder keine Knoten mehr verfügbar sind.

Eine Animation macht mehr Sinn. Hier versuchen wir von 1 bis 6 zu kommen:


Schritt 14: Die Hauptelemente des Algorithmus

Dieser Algorithmus besteht aus verschiedenen Vektoren, die alle benötigten Informationen speichern, beispielsweise die Kosten der Knoten oder den bisher besten Weg. Ich erkläre das besser:

  • Der Kostenvektor : Hier speichern wir die bisher besten Kosten für das Erreichen eines bestimmten Knotens von der Quelle. Wenn beispielsweise der Quellknoten 3 ist und wir auf Element 6 des Kostenvektors zugreifen, erhalten wir die besten bisher gefundenen Kosten für den Übergang von 3, dem Quellknoten, zum Knoten 6.
  • Der Shortest Path Tree (SPT): Dieser Vektor enthält die Kante mit den niedrigsten Kosten, um zu einem bestimmten Knoten zu gelangen. Dies bedeutet, dass, wenn wir auf das Element 7 des SPT zugreifen, es die beste Kante zurückgibt, um auf diesen Knoten zuzugreifen.
  • Die Search Frontier (SF): Dieser Vektor speichert die beste Kante, um zu einem bestimmten Knoten zu gelangen, fast der gleiche wie der SPT, aber dieser Vektor enthält alle Knoten, die noch nicht in der SPT sind. Dies bedeutet, dass die SF als Testbereich fungiert, in dem wir alle Kanten für einen Knoten testen. Wenn alle Kanten analysiert sind, stellen wir sicher, dass die SF die beste enthält, und können sie dann zum SPT hinzufügen.
  • Die indizierte Prioritätswarteschlange ((Indexed Priority Queue) pq): Eine Prioritätswarteschlange ist eine Datenstruktur, die ihre Elemente immer in geordneter Weise vorhält. Da der Algorithmus zuerst den Knoten mit den niedrigsten Kosten ermitteln muss, hält diese Struktur die Knoten abhängig von ihren Kosten in absteigender Reihenfolge. Da wir jedoch den Index des Knotens und nicht die Kosten selbst abrufen möchten, verwenden wir eine indizierte Prioritätswarteschlange. Wenn beispielsweise das erste Element von pq Knoten 4 ist, bedeutet dies, dass es das Element mit den niedrigsten Kosten ist.

Hinweis: AS3 enthält nicht viele Datenstrukturen, einschließlich der indizierten Prioritätswarteschlange, daher habe ich eine codiert, die in diesem Tutorial verwendet wird. Um es zu erhalten, laden Sie einfach die Quelldateien herunter und importieren Sie den Ordner utils in den Ordner PathFinding. Die Klasse ist utils.IndexPriorityQ.


Schritt 15: Erstellen Sie einen Algorithmusordner

Bevor wir mit dem Codieren beginnen, erstellen Sie im PathFinding-Ordner einen neuen Ordner und nennen ihn "Algorithmen".

Erstellen Sie in diesem neuen Ordner eine neue AS3-Klasse namens "Dijkstra":


Schritt 16: Der Dijkstra-Algorithmus in AS3

Lassen Sie uns nun den Algorithmus codieren. Es benötigt drei grundlegende Dinge: den Graphen selbst, den Quellknoten und den Zielknoten; aber wir müssen auch die Vektoren erstellen, über die wir gerade gesprochen haben (Kosten, SPT, SF). Denken Sie daran, die Graph-Klassen zu importieren:


Schritt 17: Die Suchfunktion

Sobald wir die Klasse eingerichtet haben, können wir mit der Codierung des Algorithmus beginnen, der sich in der Funktion "Suchen" befindet. Ich werde den Code mit Kommentaren erklären. Wenn Sie also noch Fragen haben, kehren Sie zu den Schritten 12 und 13 zurück, um sich daran zu erinnern, wie dieser Algorithmus funktioniert:


Schritt 18: Den Pfad bekommen

Wenn die Funktion die Suche beendet hat, wird der Pfad auf dem SPT durcheinander gebracht, sodass es an uns liegt, ihn abzurufen. Da die SPT die beste Kante hat, um zu einem Knoten zu gelangen, können wir rückwärts arbeiten, um den besten Pfad zu erhalten. Nehmen Sie als Referenz das folgende Bild, das aus der vorherigen Animation stammt:

Wenn wir auf den SPT am Zielknoten zugreifen, der in diesem Fall 6 ist, wird die beste Kante zurückgegeben, um dorthin zu gelangen. Das wäre die 6 - 5 Kante. Wenn wir diesen Vorgang nun mit dem neuen Knoten wiederholen, der mit der Kante, der 5, kommt, würden wir die beste Kante erhalten, um zu diesem Knoten zu gelangen, der die 5 - 2-Kante ist. Wenn wir diesen Vorgang noch einmal mit dem Knoten 2 wiederholen, erhalten wir die Kante 2 - 1, also kommen wir endlich zum Anfang, jetzt verbinden wir all diese Kanten und erhalten den besten Weg:6  > 5  > 2  > 1.

Wie Sie sehen, müssen wir vom Ziel ausgehend rückwärts arbeiten und uns zur Quelle bewegen, um den besten Pfad zu erhalten.


Schritt 19: Die getPath-Funktion

Erstellen Sie eine neue Funktion, die ein Array mit den Knoten des Pfads zurückgibt, nennen Sie es "getPath":


Schritt 20: Die komplette Dijkstra-Klasse

Wir haben fast alles fertig, wir müssen nur noch den Konstruktor füllen und die Suchfunktion aufrufen, damit die Klasse so aussieht:


Schritt 21: Erstellen eines neuen Diagramms

Um ein besseres Ergebnis des Algorithmus zu sehen, habe ich eine Klasse geschrieben, die beim Erstellen von Graphen hilft. Es heißt Grapher und befindet sich im Ordner utils, der mit den Quelldateien geliefert wird. Diese Klasse erstellt ein Gitter von Knoten, von dem aus wir beobachten können, wie sich der Algorithmus durch den Graphen bewegt.

Öffnen Sie mit dieser Klasse wieder die "Main.as" Datei und ändern Sie sie. Wir haben jetzt folgenden Code:

Speichern Sie die Datei und führen Sie sie aus und Sie erhalten dieses Ergebnis:


Schritt 22: Verwenden des Dijkstra-Algorithmus

Lassen Sie uns nun eine Suche mit dem neuen Algorithmus durchführen, den wir gerade erstellt haben. Importieren Sie die Dijkstra-Klasse, erstellen Sie eine Instanz davon und rufen Sie die Funktion getPath auf:

Speichern Sie die Datei und führen Sie sie aus. Sie sehen die vom Algorithmus analysierten Kanten als rote Linien, der beste gefundene Pfad (von Knoten 24 zu Knoten 35) erscheint als schwarze Linie:


Schritt 23: Gibt es nicht etwas Besseres?

Wie wir sehen, findet der Dijkstra-Algorithmus zwar den kürzesten Weg zwischen zwei Knoten, aber wie das letzte Bild zeigt, gibt es viele rote Linien. Dies bedeutet, dass alle diese Kanten analysiert wurden, was keine große Sache ist, da wir einen kleinen Graphen haben, aber stellen Sie sich einen größeren Graphen vor; das wären einfach zu viele Kanten, um sie zu analysieren. Wenn wir nur einen Weg finden könnten, dies zu reduzieren und den Algorithmus noch effizienter zu machen ... nun, ich präsentiere Ihnen den A* (A-Star) Algorithmus.


Schritt 24: Der A * Algorithmus

Der A*-Algorithmus ist eine modifizierte Version von Dijkstra. Es berücksichtigt eine modifizierte Methode zum Ermitteln der Kosten jedes Knotens mit einem heuristischen Ansatz. Das bedeutet, dass wir dem Algorithmus eine kleine "Hilfe" geben und ihm sagen, wohin er gehen soll, indem wir als Kompass arbeiten und den Algorithmus direkt zum Ziel bewegen.

Anstatt die Kosten eines Knotens durch Summieren der Kantenkosten mit den gespeicherten Knotenkosten zu berechnen, werden sie jetzt berechnet, indem die gespeicherten Knotenkosten und heuristische Kosten summiert werden . Diese neuen Kosten werden F-Kosten genannt


Schritt 25: Die F-Kosten

Die F-Kosten werden mit der folgenden Formel berechnet: F = G + H, wobei G die Kosten des Knotens und H die heuristischen Kosten dieses Knotens zum Ziel sind. In diesem Tutorial werden die H-Kosten anhand des Euklidischen Abstands zwischen dem Knoten und dem Ziel berechnet, der der geraden Entfernung zwischen den beiden Knoten ist.

Dies bewirkt, dass am Ende die Knoten mit niedrigeren F-Kosten die ersten sind, die getestet werden, und da die F-Kosten hauptsächlich von den H-Kosten abhängen, priorisiert der Algorithmus am Ende immer die Knoten, die dem Ziel am nächsten sind.


Schritt 26: Der A*-Algorithmus in AS3

Erstellen Sie im Ordner Algorithmen eine neue Klasse namens "Astar". Die Variablen innerhalb der Klasse sind fast die gleichen wie in der Dijkstra-Klasse, aber hier haben wir einen anderen Vektor zum Speichern der F-Kosten jedes Knotens:

Schritt 27: Die neue Suchklasse

Der einzige Unterschied zwischen der Suchfunktion des Dijkstra-Algorithmus und dieser besteht darin, dass die Knoten (in der Warteschlange mit indizierter Priorität) nach dem F-Kostenvektor sortiert werden und dass der F-Kostenvektor durch die berechneten H-Kosten und die gespeicherten G-Kosten:


Schritt 28: Die komplette A * Klasse

Dies sind die einzigen erforderlichen Änderungen, da die Funktion getPath für beide Klassen gleich ist. Am Ende wird die Klasse diese sein:


Schritt 29: Verwenden des A * Algorithmus

Öffnen Sie erneut die "Main.as" Datei und importieren Sie die Astar-Klasse, löschen Sie dann die von uns erstellte Dijkstra-Suche und ersetzen Sie sie durch eine A*-Suche:

Speichern Sie die Datei und führen Sie sie aus. Wie Sie sehen, ist das Ergebnis sehr beeindruckend, es gibt keine roten Linien, was bedeutet, dass die Suche direkt von der Quelle zum Ziel ging, ohne zusätzliche Kanten zu analysieren:


Schritt 30: Welcher ist besser?

Nun, obwohl der A*-Algorithmus schneller und besser darin ist, einen direkten Pfad von der Quelle zum Ziel zu finden, wird es einige Fälle geben, in denen Dijkstra die beste Option ist.

Stellen Sie sich zum Beispiel ein RTS-Spiel vor, bei dem Sie Ihren Dorfbewohner angewiesen haben, nach Ressourcen zu suchen. Mit dem A*-Algorithmus müssten Sie nach jeder Ressource auf der Karte suchen und dann analysieren, welche näher liegt. Da bei einer Dijkstra-Suche derselbe Umfang in alle Richtungen ausgeweitet wird, ist die erste gefundene Ressource die beste, die Sie sammeln können, und Sie haben nur eine Suche im Vergleich zu den vielen Suchen der A* durchgeführt.

Grundsätzlich sollten Sie den Dijkstra-Algorithmus verwenden, wenn Sie eine allgemeine Suche durchführen, und den A*-Algorithmus, wenn Sie nach einem bestimmten Artikel suchen.


Schlussfolgerung

Das war's für dieses Tutorial, ich hoffe es hat euch gefallen und werdet es für eure Projekte verwenden. Behalten Sie das nächste Tutorial dieser KI-Serie im Auge und lassen Sie mich wissen, was Sie davon halten.

Danke fürs Lesen! -Eduardo

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.