Ich bin auf interessantes Material über künstliche Intelligenz in Spielen gestoßen. Mit einer Erklärung grundlegender Dinge über KI anhand einfacher Beispiele und im Inneren finden Sie viele nützliche Tools und Methoden für ihre praktische Entwicklung und Gestaltung. Dort erfahren Sie auch, wie, wo und wann Sie sie verwenden.
Die meisten Beispiele sind in Pseudocode geschrieben, sodass keine fortgeschrittenen Programmierkenntnisse erforderlich sind. Unter dem Schnitt befinden sich 35 Textblätter mit Bildern und GIFs, also machen Sie sich bereit.
UPD. Es tut mir leid, aber ich habe diesen Artikel über Habré bereits selbst übersetzt . Sie können seine Version lesen , aber aus irgendeinem Grund ist der Artikel an mir vorbeigegangen (ich habe die Suche verwendet, aber etwas ist schief gelaufen). Und da ich in einem Blog schreibe, der sich der Spieleentwicklung widmet, habe ich beschlossen, meine Version der Übersetzung den Abonnenten zu überlassen (einige Punkte sind anders formatiert, andere wurden auf Anraten der Entwickler bewusst weggelassen).
Was ist das?
Game AI konzentriert sich darauf, welche Aktionen ein Objekt basierend auf den Bedingungen, unter denen es sich befindet, ausführen sollte. Dies wird allgemein als „intelligentes Agenten“-Management bezeichnet, wobei ein Agent ein Spielercharakter, ein Fahrzeug, ein Bot oder manchmal etwas Abstrakteres ist: eine ganze Gruppe von Entitäten oder sogar eine Zivilisation. In jedem Fall ist es ein Ding, das seine Umgebung sehen, darauf basierend Entscheidungen treffen und entsprechend handeln muss. Dies wird als Sinnes-/Denk-/Handlungszyklus bezeichnet:
- Sinn: Der Agent findet oder empfängt Informationen über Dinge in seiner Umgebung, die sein Verhalten beeinflussen können (Bedrohungen in der Nähe, zu sammelnde Gegenstände, interessante Orte zum Erkunden).
- Denken Sie: Der Agent entscheidet, wie er reagiert (überlegt, ob es sicher genug ist, Gegenstände einzusammeln, oder ob er zuerst kämpfen/verstecken sollte).
- Handeln: Der Agent führt Aktionen aus, um die vorherige Entscheidung umzusetzen (beginnt, sich auf den Feind oder das Objekt zuzubewegen).
- ...jetzt hat sich die Situation aufgrund der Aktionen der Charaktere geändert, sodass sich der Zyklus mit neuen Daten wiederholt.
KI konzentriert sich tendenziell auf den Sense-Teil der Schleife. So machen beispielsweise autonome Autos Bilder von der Straße, kombinieren diese mit Radar- und Lidar-Daten und interpretieren sie. Dies geschieht in der Regel durch maschinelles Lernen, das eingehende Daten verarbeitet und ihnen eine Bedeutung verleiht, indem semantische Informationen wie „20 Meter vor Ihnen ist ein anderes Auto“ extrahiert werden. Dies sind die sogenannten Klassifikationsprobleme.
Spiele benötigen kein komplexes System zum Extrahieren von Informationen, da die meisten Daten bereits ein integraler Bestandteil davon sind. Es ist nicht erforderlich, Bilderkennungsalgorithmen auszuführen, um festzustellen, ob sich ein Feind vor Ihnen befindet – das Spiel weiß es bereits und lässt die Informationen direkt in den Entscheidungsprozess einfließen. Daher ist der Sense-Teil des Zyklus oft viel einfacher als der Think and Act-Teil.
Einschränkungen der Spiel-KI
KI weist eine Reihe von Einschränkungen auf, die beachtet werden müssen:
- KI muss nicht im Voraus trainiert werden, als wäre sie ein Algorithmus für maschinelles Lernen. Es macht keinen Sinn, während der Entwicklung ein neuronales Netzwerk zu schreiben, um Zehntausende Spieler zu überwachen und zu lernen, wie man am besten gegen sie spielt. Warum? Weil das Spiel nicht veröffentlicht wurde und es keine Spieler gibt.
- Das Spiel sollte Spaß machen und herausfordernd sein, daher sollten Agenten nicht den besten Ansatz gegen Menschen finden.
- Agenten müssen realistisch aussehen, damit die Spieler das Gefühl haben, gegen echte Menschen zu spielen. Das AlphaGo-Programm war den Menschen überlegen, aber die gewählten Schritte waren sehr weit vom traditionellen Verständnis des Spiels entfernt. Wenn das Spiel einen menschlichen Gegner simuliert, sollte dieses Gefühl nicht bestehen. Der Algorithmus muss so geändert werden, dass er plausible und nicht ideale Entscheidungen trifft.
- KI muss in Echtzeit funktionieren. Dies bedeutet, dass der Algorithmus die CPU-Nutzung nicht über längere Zeiträume für die Entscheidungsfindung monopolisieren kann. Selbst 10 Millisekunden sind zu lang, da die meisten Spiele nur 16 bis 33 Millisekunden benötigen, um die gesamte Verarbeitung durchzuführen und zum nächsten Grafikframe überzugehen.
- Idealerweise sollte zumindest ein Teil des Systems datengesteuert sein, damit Nicht-Programmierer schneller Änderungen vornehmen und Anpassungen vornehmen können.
Schauen wir uns KI-Ansätze an, die den gesamten Sense/Think/Act-Zyklus abdecken.
Grundlegende Entscheidungen treffen
Beginnen wir mit dem einfachsten Spiel – Pong. Ziel: Bewegen Sie das Paddel so, dass der Ball davon abprallt, anstatt daran vorbeizufliegen. Es ist wie beim Tennis, wo man verliert, wenn man den Ball nicht trifft. Hier hat die KI eine relativ einfache Aufgabe – zu entscheiden, in welche Richtung die Plattform bewegt werden soll.
Bedingte Anweisungen
Für die KI im Pong besteht die naheliegendste Lösung darin, immer zu versuchen, die Plattform unter dem Ball zu platzieren.
Ein einfacher Algorithmus dafür, geschrieben in Pseudocode:
jedes Frame/Update während das Spiel läuft:
wenn sich der Ball links vom Schläger befindet:
Paddel nach links bewegen
sonst, wenn sich der Ball rechts vom Schläger befindet:
Paddel nach rechts bewegen
Bewegt sich die Plattform mit der Geschwindigkeit des Balls, dann ist dies der ideale Algorithmus für die KI in Pong. Es besteht kein Grund zur Komplizierung, wenn dem Agenten nicht so viele Daten und Handlungsmöglichkeiten zur Verfügung stehen.
Dieser Ansatz ist so einfach, dass der gesamte Sinnes-/Denk-/Handlungszyklus kaum wahrnehmbar ist. Aber es ist da:
- Der Sense-Teil besteht aus zwei if-Anweisungen. Das Spiel weiß, wo sich der Ball befindet und wo sich die Plattform befindet, daher sucht die KI nach diesen Informationen.
- Der Think-Teil ist auch in den beiden if-Anweisungen enthalten. Sie verkörpern zwei Lösungen, die sich in diesem Fall gegenseitig ausschließen. Als Ergebnis wird eine von drei Aktionen ausgewählt: Bewegen Sie die Plattform nach links, bewegen Sie sie nach rechts oder tun Sie nichts, wenn sie bereits richtig positioniert ist.
- Der Act-Teil befindet sich in den Anweisungen „Move Paddle Left“ und „Move Paddle Right“. Je nach Spieldesign können sie die Plattform sofort oder mit einer bestimmten Geschwindigkeit bewegen.
Solche Ansätze werden als reaktiv bezeichnet – es gibt ein einfaches Regelwerk (in diesem Fall if-Anweisungen im Code), das auf den aktuellen Zustand der Welt reagiert und Maßnahmen ergreift.
Entscheidungsbaum
Das Pong-Beispiel entspricht tatsächlich einem formalen KI-Konzept namens Entscheidungsbaum. Der Algorithmus durchläuft es, um zu einem „Blatt“ zu gelangen – einer Entscheidung darüber, welche Maßnahmen ergriffen werden sollen.
Lassen Sie uns ein Blockdiagramm des Entscheidungsbaums für den Algorithmus unserer Plattform erstellen:
Jeder Teil des Baums wird als Knoten bezeichnet – KI nutzt die Graphentheorie, um solche Strukturen zu beschreiben. Es gibt zwei Arten von Knoten:
- Entscheidungsknoten: Auswahl zwischen zwei Alternativen basierend auf dem Testen einer bestimmten Bedingung, wobei jede Alternative als separater Knoten dargestellt wird.
- Endknoten: Die auszuführende Aktion, die die endgültige Entscheidung darstellt.
Der Algorithmus beginnt beim ersten Knoten (der „Wurzel“ des Baums). Entweder trifft es eine Entscheidung darüber, zu welchem untergeordneten Knoten es gehen soll, oder es führt die im Knoten gespeicherte Aktion aus und beendet den Vorgang.
Welchen Vorteil hat es, wenn ein Entscheidungsbaum die gleiche Aufgabe erfüllt wie die if-Anweisungen im vorherigen Abschnitt? Hier gibt es ein allgemeines System, bei dem jede Entscheidung nur eine Bedingung und zwei mögliche Ergebnisse hat. Dies ermöglicht es dem Entwickler, KI aus Daten zu erstellen, die Entscheidungen in einem Baum darstellen, ohne diese hart codieren zu müssen. Stellen wir es uns tabellarisch vor:
Auf der Codeseite erhalten Sie ein System zum Lesen von Strings. Erstellen Sie für jeden einen Knoten, verbinden Sie die Entscheidungslogik basierend auf der zweiten Spalte und untergeordnete Knoten basierend auf der dritten und vierten Spalte. Sie müssen noch die Bedingungen und Aktionen programmieren, aber jetzt wird die Struktur des Spiels komplexer. Hier fügen Sie zusätzliche Entscheidungen und Aktionen hinzu und passen dann die gesamte KI an, indem Sie einfach die Textdatei mit der Baumdefinition bearbeiten. Als nächstes übertragen Sie die Datei an den Spieleentwickler, der das Verhalten ändern kann, ohne das Spiel neu zu kompilieren oder den Code zu ändern.
Entscheidungsbäume sind sehr nützlich, wenn sie automatisch aus einer großen Menge von Beispielen erstellt werden (z. B. mithilfe des ID3-Algorithmus). Damit sind sie ein effektives und leistungsstarkes Werkzeug zur Klassifizierung von Situationen auf Basis der gewonnenen Daten. Wir gehen jedoch über ein einfaches System für Agenten zur Auswahl von Aktionen hinaus.
Szenarien
Wir haben ein Entscheidungsbaumsystem analysiert, das vorab erstellte Bedingungen und Aktionen verwendete. Die Person, die die KI entwirft, kann den Baum nach Belieben organisieren, muss sich aber immer noch auf den Programmierer verlassen, der alles programmiert hat. Was wäre, wenn wir dem Designer die Werkzeuge an die Hand geben könnten, um seine eigenen Bedingungen oder Aktionen zu erstellen?
Damit der Programmierer keinen Code für die Bedingungen Is Ball Left Of Paddle und Is Ball Right Of Paddle schreiben muss, kann er ein System erstellen, in dem der Designer Bedingungen schreibt, um diese Werte zu überprüfen. Dann sehen die Entscheidungsbaumdaten so aus:
Dies ist im Wesentlichen dasselbe wie in der ersten Tabelle, aber die Lösungen in sich haben ihren eigenen Code, ähnlich wie der bedingte Teil einer if-Anweisung. Auf der Codeseite würde dies die zweite Spalte für die Entscheidungsknoten einlesen, aber anstatt nach einer bestimmten auszuführenden Bedingung zu suchen (Ist der Ball links vom Paddel), wertet es den bedingten Ausdruck aus und gibt entsprechend „true“ oder „false“ zurück. Dies geschieht mithilfe der Skriptsprache Lua oder Angelscript. Mit ihnen kann ein Entwickler Objekte in seinem Spiel (Ball und Schläger) nehmen und Variablen erstellen, die im Skript verfügbar sind (ball.position). Außerdem ist die Skriptsprache einfacher als C++. Es erfordert keine vollständige Kompilierungsphase, ist also ideal für die schnelle Anpassung der Spiellogik und ermöglicht „Nicht-Programmierern“, die notwendigen Funktionen selbst zu erstellen.
Im obigen Beispiel wird die Skriptsprache nur zur Auswertung des bedingten Ausdrucks verwendet, sie kann aber auch für Aktionen verwendet werden. Beispielsweise könnten die Daten Move Paddle Right zu einer Skriptanweisung werden (ball.position.x += 10). Damit die Aktion auch im Skript definiert ist, ohne dass Move Paddle Right programmiert werden muss.
Sie können sogar noch weiter gehen und den gesamten Entscheidungsbaum in einer Skriptsprache schreiben. Dabei handelt es sich um Code in Form von fest codierten bedingten Anweisungen, die sich jedoch in externen Skriptdateien befinden, d. h. sie können geändert werden, ohne dass das gesamte Programm neu kompiliert werden muss. Sie können die Skriptdatei oft während des Spiels bearbeiten, um schnell verschiedene KI-Reaktionen zu testen.
Ereignisantwort
Die obigen Beispiele eignen sich perfekt für Pong. Sie durchlaufen kontinuierlich den Sinnes-/Denk-/Handlungszyklus und handeln basierend auf dem neuesten Stand der Welt. Aber in komplexeren Spielen muss man auf einzelne Ereignisse reagieren und nicht alles auf einmal bewerten. Pong ist in diesem Fall bereits ein schlechtes Beispiel. Wählen wir ein anderes.
Stellen Sie sich einen Shooter vor, bei dem die Feinde bewegungslos sind, bis sie den Spieler entdecken, und dann entsprechend ihrer „Spezialisierung“ handeln: Jemand rennt los, um zu „stürmen“, jemand greift aus der Ferne an. Es handelt sich immer noch um ein grundlegendes reaktives System – „Wenn ein Spieler entdeckt wird, tun Sie etwas“ –, aber es kann logisch in ein Ereignis „Spieler gesehen“ und eine Reaktion (wählen Sie eine Reaktion aus und führen Sie sie aus) unterteilt werden.
Dies bringt uns zurück zum Sinnes-/Denk-/Handlungszyklus. Wir können einen Sense-Teil programmieren, der bei jedem Frame prüft, ob die KI den Spieler sieht. Wenn nicht, passiert nichts, aber wenn es sieht, wird das Player Seen-Ereignis erstellt. Der Code verfügt über einen separaten Abschnitt mit der Aufschrift „Wenn das Player Seen-Ereignis eintritt, tun Sie dies.“ Dort finden Sie die Antwort, die Sie benötigen, um die Teile „Denken“ und „Handeln“ anzugehen. So richten Sie Reaktionen auf das Player Seen-Ereignis ein: für den „stürmenden“ Charakter – ChargeAndAttack, und für den Scharfschützen – HideAndSnipe. Diese Beziehungen können zur schnellen Bearbeitung in der Datendatei erstellt werden, ohne dass eine Neukompilierung erforderlich ist. Auch hier kann Skriptsprache verwendet werden.
Schwierige Entscheidungen treffen
Obwohl einfache Reaktionssysteme sehr leistungsfähig sind, gibt es viele Situationen, in denen sie nicht ausreichen. Manchmal müssen Sie basierend auf dem, was der Agent gerade tut, unterschiedliche Entscheidungen treffen, aber es ist schwer, sich das als Bedingung vorzustellen. Manchmal gibt es zu viele Bedingungen, um sie effektiv in einem Entscheidungsbaum oder Skript darzustellen. Manchmal muss man vorab abschätzen, wie sich die Situation verändern wird, bevor man sich für den nächsten Schritt entscheidet. Um diese Probleme zu lösen, sind ausgefeiltere Ansätze erforderlich.
Finite-State-Maschine
Finite-State-Machine oder FSM (Finite-State-Machine) gibt an, dass sich unser Agent derzeit in einem von mehreren möglichen Zuständen befindet und von einem Zustand in einen anderen übergehen kann. Es gibt eine gewisse Anzahl solcher Staaten – daher der Name. Das beste Beispiel aus dem Leben ist eine Ampel. An verschiedenen Orten gibt es unterschiedliche Lichtsequenzen, aber das Prinzip ist dasselbe – jeder Zustand repräsentiert etwas (Anhalten, Gehen usw.). Eine Ampel befindet sich immer nur in einem Zustand und wechselt nach einfachen Regeln von einem zum anderen.
Ähnlich verhält es sich mit NPCs in Spielen. Nehmen wir zum Beispiel eine Wache mit den folgenden Zuständen:
- Patrouillieren.
- Angreifen.
- Auf der Flucht.
Und diese Bedingungen für die Änderung seines Zustands:
- Wenn der Wächter den Feind sieht, greift er an.
- Wenn der Wachmann angreift, den Feind aber nicht mehr sieht, kehrt er zur Patrouille zurück.
- Wenn ein Wachmann angreift, aber schwer verwundet wird, rennt er weg.
Sie können auch if-Anweisungen mit einer Wächter-Zustandsvariablen und verschiedenen Prüfungen schreiben: Befindet sich ein Feind in der Nähe, wie hoch ist der Gesundheitszustand des NPCs usw. Fügen wir noch ein paar weitere Zustände hinzu:
- Müßiggang – zwischen den Patrouillen.
- Suchen – wenn der entdeckte Feind verschwunden ist.
- Hilfe finden – wenn ein Feind entdeckt wird, aber zu stark ist, um alleine zu kämpfen.
Die Auswahl für jeden von ihnen ist begrenzt – zum Beispiel wird der Wachmann nicht nach einem versteckten Feind suchen, wenn seine Gesundheit niedrig ist.
Schließlich gibt es eine riesige Liste mit „Wenns“ , Das „ kann zu umständlich werden, daher müssen wir eine Methode formalisieren, die es uns ermöglicht, Zustände und Übergänge zwischen Zuständen im Auge zu behalten. Dazu berücksichtigen wir alle Zustände und notieren unter jedem Zustand in einer Liste alle Übergänge in andere Zustände mit den dafür notwendigen Bedingungen.
Dies ist eine Zustandsübergangstabelle – eine umfassende Möglichkeit, FSM darzustellen. Lassen Sie uns ein Diagramm zeichnen und einen vollständigen Überblick darüber erhalten, wie sich das NPC-Verhalten ändert.
Das Diagramm spiegelt die Essenz der Entscheidungsfindung für diesen Agenten basierend auf der aktuellen Situation wider. Darüber hinaus zeigt jeder Pfeil einen Übergang zwischen Zuständen an, wenn die Bedingung daneben wahr ist.
Bei jedem Update überprüfen wir den aktuellen Status des Agenten, sehen uns die Liste der Übergänge an und wenn die Bedingungen für den Übergang erfüllt sind, akzeptiert er den neuen Status. Beispielsweise prüft jeder Frame, ob der 10-Sekunden-Timer abgelaufen ist. Ist dies der Fall, wechselt der Wächter vom Status „Leerlauf“ in den Status „Patrolling“. Auf die gleiche Weise prüft der Angriffszustand die Gesundheit des Agenten – wenn dieser niedrig ist, geht er in den Fluchtzustand über.
Hier geht es um die Handhabung von Übergängen zwischen Zuständen, aber was ist mit dem Verhalten, das mit den Zuständen selbst verbunden ist? Im Hinblick auf die Implementierung des tatsächlichen Verhaltens für einen bestimmten Zustand gibt es typischerweise zwei Arten von „Hooks“, bei denen wir dem FSM Aktionen zuweisen:
- Aktionen, die wir regelmäßig für den aktuellen Zustand durchführen.
- Die Maßnahmen, die wir beim Übergang von einem Zustand in einen anderen ergreifen.
Beispiele für den ersten Typ. Der Patrouillenstatus bewegt den Agenten in jedem Frame entlang der Patrouillenroute. Der angreifende Zustand versucht, in jedem Frame einen Angriff zu initiieren oder in einen Zustand überzugehen, in dem dies möglich ist.
Betrachten Sie für den zweiten Typ den Übergang „Wenn der Feind sichtbar und zu stark ist, wechseln Sie in den Zustand „Hilfe finden“. Der Agent muss auswählen, an wen er sich wenden kann, um Hilfe zu erhalten, und diese Informationen speichern, damit der Status „Hilfe finden“ weiß, wohin er gehen muss. Sobald Hilfe gefunden wird, kehrt der Agent in den Status „Angreifend“ zurück. Zu diesem Zeitpunkt möchte er den Verbündeten über die Bedrohung informieren, sodass die Aktion „NotifyFriendOfThreat“ ausgeführt werden kann.
Noch einmal können wir dieses System durch die Linse des Sinnes-/Denk-/Handlungszyklus betrachten. Der Sinn liegt in den von der Übergangslogik verwendeten Daten. Denken Sie – Übergänge sind in jedem Bundesstaat verfügbar. Und Act wird durch Aktionen ausgeführt, die periodisch innerhalb eines Staates oder bei Übergängen zwischen Staaten durchgeführt werden.
Manchmal kann die kontinuierliche Abfrage von Übergangsbedingungen kostspielig sein. Wenn beispielsweise jeder Agent in jedem Frame komplexe Berechnungen durchführt, um zu bestimmen, ob er Feinde sehen kann und um zu verstehen, ob er vom Status „Patrouillieren“ in den Status „Angreifend“ wechseln kann, wird dies viel CPU-Zeit in Anspruch nehmen.
Wichtige Veränderungen im Zustand der Welt können als Ereignisse betrachtet werden, die verarbeitet werden, sobald sie eintreten. Anstatt dass der FSM die Übergangsbedingung „Kann mein Agent den Player sehen?“ in jedem Frame überprüft, kann ein separates System so konfiguriert werden, dass die Überprüfung weniger häufig erfolgt (z. B. fünfmal pro Sekunde). Und das Ergebnis ist, dass „Spieler gesehen“ ausgegeben wird, wenn die Prüfung erfolgreich ist.
Dies wird an den FSM weitergeleitet, der nun zur Bedingung „Spieler gesehenes Ereignis empfangen“ gehen und entsprechend reagieren sollte. Das resultierende Verhalten ist das gleiche, abgesehen von einer kaum wahrnehmbaren Verzögerung vor der Reaktion. Durch die Trennung des Sense-Teils in einen separaten Teil des Programms hat sich jedoch die Leistung verbessert.
Hierarchischer endlicher Automat
Allerdings ist die Arbeit mit großen FSMs nicht immer bequem. Wenn wir den Angriffszustand erweitern wollen, um MeleeAttacking und RangedAttacking zu trennen, müssen wir die Übergänge von allen anderen Zuständen ändern, die zum Angriffszustand führen (aktuell und zukünftig).
Sie haben wahrscheinlich bemerkt, dass es in unserem Beispiel viele doppelte Übergänge gibt. Die meisten Übergänge im Leerlaufzustand sind identisch mit Übergängen im Überwachungszustand. Es wäre schön, uns nicht zu wiederholen, insbesondere wenn wir weitere ähnliche Staaten hinzufügen würden. Es ist sinnvoll, Leerlauf und Patrouille unter der allgemeinen Bezeichnung „Nicht-Kampf“ zu gruppieren, wo es nur einen gemeinsamen Satz von Übergängen zu Kampfzuständen gibt. Wenn wir uns diese Bezeichnung als einen Zustand vorstellen, werden Leerlauf und Patrouille zu Unterzuständen. Ein Beispiel für die Verwendung einer separaten Übergangstabelle für einen neuen Nichtkampf-Unterzustand:
Hauptstaaten:
Status außer Gefecht:
Und in Diagrammform:
Es ist das gleiche System, aber mit einem neuen Nicht-Kampf-Zustand, der Leerlauf und Patrouillieren umfasst. Wenn jeder Zustand einen FSM mit Unterzuständen enthält (und diese Unterzustände wiederum ihre eigenen FSMs enthalten – und so weiter, solange Sie benötigen), erhalten wir eine hierarchische Finite-State-Maschine oder HFSM (Hierarchical Finite State Machine). Indem wir den Nichtkampfzustand gruppieren, eliminieren wir eine Reihe überflüssiger Übergänge. Dasselbe können wir für alle neuen Zustände mit gemeinsamen Übergängen tun. Wenn wir beispielsweise in Zukunft den Angriffszustand auf die Zustände „Nahkampfangriff“ und „Raketenangriff“ erweitern, handelt es sich dabei um Unterzustände, die je nach Entfernung zum Feind und Munitionsverfügbarkeit zwischen den Zuständen wechseln. Dadurch können komplexe Verhaltensweisen und Unterverhaltensweisen mit einem Minimum an doppelten Übergängen dargestellt werden.
Verhaltensbaum
Mit HFSM werden komplexe Verhaltenskombinationen auf einfache Weise erstellt. Allerdings besteht eine leichte Schwierigkeit darin, dass die Entscheidungsfindung in Form von Übergangsregeln eng mit dem aktuellen Stand verknüpft ist. Und in vielen Spielen ist genau das nötig. Und eine sorgfältige Nutzung der Statushierarchie kann die Anzahl der Übergangswiederholungen reduzieren. Aber manchmal braucht man Regeln, die unabhängig vom Bundesstaat funktionieren oder die in fast jedem Bundesstaat gelten. Wenn beispielsweise die Gesundheit eines Agenten auf 25 % sinkt, möchten Sie, dass er wegläuft, unabhängig davon, ob er im Kampf war, untätig war oder redete – Sie müssen diese Bedingung zu jedem Zustand hinzufügen. Und wenn Ihr Designer später den unteren Gesundheitsschwellenwert von 25 % auf 10 % ändern möchte, muss dies erneut durchgeführt werden.
Idealerweise erfordert diese Situation ein System, in dem Entscheidungen darüber, „in welchem Zustand man sich befindet“, außerhalb der Staaten selbst liegen, um Änderungen nur an einer Stelle vorzunehmen und die Übergangsbedingungen nicht zu berühren. Hier erscheinen Verhaltensbäume.
Es gibt mehrere Möglichkeiten, sie zu implementieren, aber das Wesentliche ist für alle ungefähr das Gleiche und ähnelt einem Entscheidungsbaum: Der Algorithmus beginnt mit einem „Wurzel“-Knoten, und der Baum enthält Knoten, die entweder Entscheidungen oder Aktionen darstellen. Es gibt jedoch einige wesentliche Unterschiede:
- Knoten geben jetzt einen von drei Werten zurück: Erfolgreich (wenn der Job abgeschlossen ist), Fehlgeschlagen (wenn er nicht gestartet werden kann) oder Wird ausgeführt (wenn er noch ausgeführt wird und es kein Endergebnis gibt).
- Es gibt keine Entscheidungsknoten mehr, um zwischen zwei Alternativen zu wählen. Stattdessen handelt es sich um Decorator-Knoten, die über einen untergeordneten Knoten verfügen. Wenn sie erfolgreich sind, führen sie ihren einzigen untergeordneten Knoten aus.
- Knoten, die Aktionen ausführen, geben einen Running-Wert zurück, der die ausgeführten Aktionen darstellt.
Diese kleine Gruppe von Knoten kann kombiniert werden, um eine große Anzahl komplexer Verhaltensweisen zu erzeugen. Stellen wir uns den HFSM-Guard aus dem vorherigen Beispiel als Verhaltensbaum vor:
Bei dieser Struktur sollte es keinen offensichtlichen Übergang von den Zuständen „Leerlauf/Patrouille“ zu „Angriff“ oder einem anderen Zustand geben. Wenn ein Feind sichtbar ist und die Gesundheit des Charakters niedrig ist, stoppt die Ausführung am Fliehen-Knoten, unabhängig davon, welchen Knoten er zuvor ausgeführt hat – Patrouillieren, Leerlauf, Angreifen oder ein anderer.
Verhaltensbäume sind komplex – es gibt viele Möglichkeiten, sie zusammenzusetzen, und die richtige Kombination von Dekoratoren und zusammengesetzten Knoten zu finden, kann eine Herausforderung sein. Es stellt sich auch die Frage, wie oft der Baum überprüft werden soll – wollen wir jeden Teil davon durchgehen oder nur, wenn sich eine der Bedingungen geändert hat? Wie speichern wir den Zustand von Knoten – woher wissen wir, wann wir 10 Sekunden lang im Leerlauf waren, oder woher wissen wir, welche Knoten das letzte Mal ausgeführt wurden, damit wir die Sequenz korrekt verarbeiten können?
Aus diesem Grund gibt es viele Implementierungen. Beispielsweise haben einige Systeme Dekoratorknoten durch Inline-Dekoratoren ersetzt. Sie bewerten den Baum neu, wenn sich die Dekoratorbedingungen ändern, helfen beim Verbinden von Knoten und stellen regelmäßige Aktualisierungen bereit.
Utility-basiertes System
Einige Spiele haben viele verschiedene Mechaniken. Es ist wünschenswert, dass sie alle Vorteile einfacher und allgemeiner Übergangsregeln erhalten, jedoch nicht unbedingt in Form eines vollständigen Verhaltensbaums. Anstatt klare Auswahlmöglichkeiten oder einen Baum möglicher Aktionen zu haben, ist es einfacher, alle Aktionen zu prüfen und die im Moment am besten geeignete auszuwählen.
Das Utility-basierte System hilft dabei. Hierbei handelt es sich um ein System, bei dem der Agent über eine Vielzahl von Aktionen verfügt und auf der Grundlage des relativen Nutzens der einzelnen Aktionen auswählt, welche er ausführen möchte. Dabei ist der Nutzen ein willkürliches Maß dafür, wie wichtig oder wünschenswert es für den Agenten ist, diese Aktion auszuführen.
Der berechnete Nutzen einer Aktion basiert auf dem aktuellen Status und der aktuellen Umgebung. Der Agent kann jederzeit den am besten geeigneten anderen Status prüfen und auswählen. Dies ähnelt FSM, außer dass Übergänge durch eine Schätzung für jeden potenziellen Zustand, einschließlich des aktuellen, bestimmt werden. Bitte beachten Sie, dass wir die nützlichste Aktion auswählen, um fortzufahren (oder zu bleiben, wenn wir sie bereits abgeschlossen haben). Für mehr Abwechslung könnte dies eine ausgewogene, aber zufällige Auswahl aus einer kleinen Liste sein.
Das System weist einen beliebigen Bereich von Nutzenwerten zu, beispielsweise von 0 (völlig unerwünscht) bis 100 (völlig wünschenswert). Jede Aktion verfügt über eine Reihe von Parametern, die die Berechnung dieses Werts beeinflussen. Zurück zu unserem Wächter-Beispiel:
Übergänge zwischen Aktionen sind mehrdeutig – jeder Zustand kann jedem anderen folgen. Aktionsprioritäten finden sich in den zurückgegebenen Dienstprogrammwerten. Wenn ein Feind sichtbar und stark ist und die Gesundheit des Charakters niedrig ist, geben sowohl „Fleeing“ als auch „FindingHelp“ hohe Werte ungleich Null zurück. In diesem Fall wird FindingHelp immer höher sein. Ebenso ergeben Aktivitäten außerhalb des Kampfes nie mehr als 50, sodass sie immer niedriger ausfallen als Aktivitäten im Kampf. Dies müssen Sie bei der Erstellung von Aktionen und der Berechnung ihres Nutzens berücksichtigen.
In unserem Beispiel geben die Aktionen entweder einen festen konstanten Wert oder einen von zwei festen Werten zurück. Ein realistischeres System würde eine Schätzung aus einem kontinuierlichen Wertebereich zurückgeben. Beispielsweise liefert die Aktion „Flucht“ höhere Nutzenwerte, wenn die Gesundheit des Agenten niedrig ist, und die Aktion „Angreifen“ liefert niedrigere Nutzenwerte, wenn der Feind zu stark ist. Aus diesem Grund hat die Fluchtaktion Vorrang vor dem Angriff, wenn der Agent das Gefühl hat, dass er nicht über genügend Gesundheit verfügt, um den Feind zu besiegen. Dadurch können Aktionen anhand einer beliebigen Anzahl von Kriterien priorisiert werden, wodurch dieser Ansatz flexibler und variabler ist als ein Verhaltensbaum oder FSM.
Jede Aktion hat viele Bedingungen für die Programmberechnung. Sie können in Skriptsprache oder als eine Reihe mathematischer Formeln geschrieben sein. Die Sims, die den Tagesablauf eines Charakters simulieren, fügen eine zusätzliche Berechnungsebene hinzu: Der Agent erhält eine Reihe von „Motivationen“, die Einfluss auf die Nutzenbewertung haben. Wenn ein Charakter hungrig ist, wird er mit der Zeit noch hungriger und der Nutzwert der Aktion „EatFood“ erhöht sich, bis der Charakter sie ausführt, wodurch der Hungergrad sinkt und der Wert von „EatFood“ auf Null zurückgesetzt wird.
Die Idee, Aktionen auf der Grundlage eines Bewertungssystems auszuwählen, ist recht einfach, sodass ein dienstprogrammbasiertes System als Teil von KI-Entscheidungsprozessen verwendet werden kann und nicht als vollständiger Ersatz dafür. Der Entscheidungsbaum kann nach einer Nutzenbewertung von zwei untergeordneten Knoten fragen und den höheren auswählen. Ebenso kann ein Verhaltensbaum einen zusammengesetzten Dienstprogrammknoten haben, um den Nutzen von Aktionen zu bewerten und zu entscheiden, welches untergeordnete Element ausgeführt werden soll.
Bewegung und Navigation
In den vorherigen Beispielen hatten wir eine Plattform, die wir nach links oder rechts bewegten, und einen Wachmann, der patrouillierte oder angriff. Aber wie genau gehen wir mit der Agentenbewegung über einen bestimmten Zeitraum um? Wie stellen wir die Geschwindigkeit ein, wie weichen wir Hindernissen aus und wie planen wir eine Route, wenn es schwieriger ist, an ein Ziel zu gelangen, als nur geradeaus zu fahren? Schauen wir uns das an.
Management
In der Anfangsphase gehen wir davon aus, dass jeder Agent einen Geschwindigkeitswert hat, der beinhaltet, wie schnell er sich bewegt und in welche Richtung. Sie kann in Metern pro Sekunde, Kilometer pro Stunde, Pixel pro Sekunde usw. gemessen werden. Wenn wir uns an die Sense/Think/Act-Schleife erinnern, können wir uns vorstellen, dass der Think-Teil eine Geschwindigkeit auswählt und der Act-Teil diese Geschwindigkeit auf den Agenten anwendet. Normalerweise verfügen Spiele über ein Physiksystem, das diese Aufgabe für Sie erledigt, indem es den Geschwindigkeitswert jedes Objekts lernt und ihn anpasst. Daher können Sie der KI eine Aufgabe überlassen – zu entscheiden, welche Geschwindigkeit der Agent haben soll. Wenn Sie wissen, wo sich der Agent befinden soll, müssen Sie ihn mit einer festgelegten Geschwindigkeit in die richtige Richtung bewegen. Eine sehr triviale Gleichung:
gewünschte_Reise = Zielposition – Agentenposition
Stellen Sie sich eine 2D-Welt vor. Der Agent befindet sich am Punkt (-2,-2), das Ziel liegt irgendwo im Nordosten am Punkt (30, 20) und der für den Agenten erforderliche Weg dorthin ist (32, 22). Nehmen wir an, diese Positionen werden in Metern gemessen. Wenn wir die Geschwindigkeit des Agenten mit 5 Metern pro Sekunde annehmen, skalieren wir unseren Verschiebungsvektor und erhalten eine Geschwindigkeit von ungefähr (4.12, 2.83). Mit diesen Parametern würde der Agent in knapp 8 Sekunden am Ziel ankommen.
Sie können die Werte jederzeit neu berechnen. Wenn sich der Agent auf halbem Weg zum Ziel befände, wäre die Bewegung halb so lang, aber da die maximale Geschwindigkeit des Agenten 5 m/s beträgt (wir haben dies oben festgelegt), bleibt die Geschwindigkeit gleich. Dies funktioniert auch beim Verschieben von Zielen, sodass der Agent beim Bewegen kleine Änderungen vornehmen kann.
Aber wir wollen mehr Abwechslung – zum Beispiel eine langsame Erhöhung der Geschwindigkeit, um den Übergang einer Figur vom Stehen zum Laufen zu simulieren. Das Gleiche kann am Ende vor dem Anhalten erfolgen. Diese Merkmale werden als Lenkverhalten bezeichnet und haben jeweils spezifische Namen: Suchen, Fliehen, Ankommen usw. Die Idee dahinter ist, dass Beschleunigungskräfte auf die Geschwindigkeit des Agenten angewendet werden können, basierend auf dem Vergleich der Position des Agenten und seiner aktuellen Geschwindigkeit mit dem Ziel in um verschiedene Methoden zu nutzen, um zum Ziel zu gelangen.
Jedes Verhalten hat einen etwas anderen Zweck. Seek und Arrival sind Möglichkeiten, einen Agenten zu einem Ziel zu bewegen. Hindernisvermeidung und -trennung passen die Bewegung des Agenten an, um Hindernissen auf dem Weg zum Ziel auszuweichen. Ausrichtung und Zusammenhalt halten die Agenten zusammen. Beliebig viele unterschiedliche Lenkverhalten können summiert werden, um unter Berücksichtigung aller Faktoren einen einzigen Pfadvektor zu erzeugen. Ein Agent, der die Verhaltensweisen „Ankunft“, „Trennung“ und „Hindernisvermeidung“ nutzt, um sich von Wänden und anderen Agenten fernzuhalten. Dieser Ansatz funktioniert gut an offenen Standorten ohne unnötige Details.
Unter schwierigeren Bedingungen funktioniert das Hinzufügen verschiedener Verhaltensweisen schlechter – beispielsweise kann ein Agent aufgrund eines Konflikts zwischen Ankunft und Hindernisvermeidung in einer Wand stecken bleiben. Daher müssen Sie Optionen in Betracht ziehen, die komplexer sind als das einfache Addieren aller Werte. Der Weg ist dieser: Anstatt die Ergebnisse jedes Verhaltens zu addieren, können Sie Bewegungen in verschiedene Richtungen berücksichtigen und die beste Option auswählen.
In einem komplexen Umfeld mit Sackgassen und Entscheidungen darüber, welchen Weg wir einschlagen wollen, brauchen wir jedoch etwas noch Fortgeschritteneres.
Einen Weg finden
Das Lenkverhalten eignet sich hervorragend für einfache Bewegungen in einem offenen Bereich (Fußballfeld oder Arena), wo der Weg von A nach B ein gerader Weg mit nur kleinen Umwegen um Hindernisse herum ist. Für komplexe Routen brauchen wir die Wegfindung, also eine Möglichkeit, die Welt zu erkunden und uns für eine Route durch sie zu entscheiden.
Am einfachsten ist es, auf jedem Feld neben dem Agenten ein Raster anzubringen und zu bewerten, welche davon sich bewegen dürfen. Wenn eines davon ein Ziel ist, folgen Sie der Route von jedem Quadrat zum vorherigen, bis Sie den Anfang erreichen. Das ist die Route. Andernfalls wiederholen Sie den Vorgang mit anderen Feldern in der Nähe, bis Sie Ihr Ziel gefunden haben oder Ihnen die Felder ausgehen (was bedeutet, dass es keine mögliche Route mehr gibt). Dies wird offiziell als „Breadth-First Search“ oder BFS (Breadth-First-Suchalgorithmus) bezeichnet. Bei jedem Schritt blickt er in alle Richtungen (daher Breite, „Breite“). Der Suchraum ist wie eine Wellenfront, die sich bewegt, bis sie den gewünschten Ort erreicht – der Suchraum dehnt sich bei jedem Schritt aus, bis der Endpunkt enthalten ist, und kann dann bis zum Anfang zurückverfolgt werden.
Als Ergebnis erhalten Sie eine Platzliste, entlang derer die gewünschte Route zusammengestellt wird. Dies ist der Pfad (daher Pathfinding) – eine Liste von Orten, die der Agent besuchen wird, während er dem Ziel folgt.
Vorausgesetzt, wir kennen die Position jedes Quadrats auf der Welt, können wir Lenkverhalten nutzen, um uns entlang des Pfades zu bewegen – von Knoten 1 zu Knoten 2, dann von Knoten 2 zu Knoten 3 und so weiter. Die einfachste Möglichkeit besteht darin, in Richtung der Mitte des nächsten Quadrats zu gehen. Eine noch bessere Option besteht jedoch darin, in der Mitte der Kante zwischen dem aktuellen und dem nächsten Quadrat anzuhalten. Dadurch ist der Agent in der Lage, bei scharfen Kurven Kurven zu fahren.
Der BFS-Algorithmus hat auch Nachteile – er untersucht genauso viele Quadrate in der „falschen“ Richtung wie in der „richtigen“ Richtung. Hier kommt ein komplexerer Algorithmus namens A* (A star) ins Spiel. Es funktioniert auf die gleiche Weise, aber anstatt blind Nachbarquadrate zu untersuchen (dann Nachbarn von Nachbarn, dann Nachbarn von Nachbarn von Nachbarn usw.), sammelt es die Knoten in einer Liste und sortiert sie so, dass der nächste untersuchte Knoten immer der ist eine, die zum kürzesten Weg führt. Knoten werden auf der Grundlage einer Heuristik sortiert, die zwei Dinge berücksichtigt: die „Kosten“ einer hypothetischen Route zum gewünschten Quadrat (einschließlich etwaiger Reisekosten) und eine Schätzung, wie weit dieses Quadrat vom Ziel entfernt ist (wodurch die Suche im Feld verzerrt wird). richtige Richtung).
Dieses Beispiel zeigt, dass der Agent jeweils ein Feld erkundet und jedes Mal das angrenzende Feld auswählt, das am vielversprechendsten ist. Der resultierende Pfad ist derselbe wie bei BFS, allerdings wurden dabei weniger Felder berücksichtigt – was einen großen Einfluss auf die Spielleistung hat.
Bewegung ohne Raster
Die meisten Spiele sind jedoch nicht in einem Raster angeordnet, und es ist oft unmöglich, dies zu tun, ohne den Realismus zu opfern. Kompromisse sind nötig. Welche Größe sollen die Quadrate haben? Wenn sie zu groß sind, können kleine Korridore oder Abzweigungen nicht korrekt dargestellt werden. Zu klein, und es müssen zu viele Quadrate gesucht werden, was letztendlich viel Zeit in Anspruch nehmen wird.
Das erste, was wir verstehen müssen, ist, dass ein Netz uns einen Graphen verbundener Knoten liefert. Die A*- und BFS-Algorithmen funktionieren tatsächlich mit Diagrammen und kümmern sich überhaupt nicht um unser Netz. Wir könnten Knoten überall in der Spielwelt platzieren: Solange eine Verbindung zwischen zwei beliebigen verbundenen Knoten sowie zwischen den Start- und Endpunkten und mindestens einem der Knoten besteht, funktioniert der Algorithmus genauso gut wie zuvor. Dies wird oft als Wegpunktsystem bezeichnet, da jeder Knoten eine bedeutende Position in der Welt darstellt, die Teil einer beliebigen Anzahl hypothetischer Pfade sein kann.
Beispiel 1: ein Knoten in jedem Quadrat. Die Suche beginnt an dem Knoten, an dem sich der Agent befindet, und endet am Knoten des gewünschten Quadrats.
Beispiel 2: Eine kleinere Gruppe von Knoten (Wegpunkten). Die Suche beginnt am Platz des Agenten, durchläuft die erforderliche Anzahl von Knoten und wird dann bis zum Ziel fortgesetzt.
Dies ist ein völlig flexibles und leistungsstarkes System. Bei der Entscheidung, wo und wie ein Wegpunkt platziert werden soll, ist jedoch eine gewisse Vorsicht geboten, da Agenten andernfalls den nächstgelegenen Punkt möglicherweise einfach nicht sehen und den Weg nicht beginnen können. Es wäre einfacher, wenn wir Wegpunkte basierend auf der Geometrie der Welt automatisch platzieren könnten.
Hier erscheint das Navigationsnetz oder Navmesh (Navigationsnetz). Dabei handelt es sich in der Regel um ein zweidimensionales Netz aus Dreiecken, das über die Geometrie der Welt gelegt wird – überall dort, wo sich der Agent bewegen darf. Jedes der Dreiecke im Netz wird zu einem Knoten im Diagramm und hat bis zu drei benachbarte Dreiecke, die zu benachbarten Knoten im Diagramm werden.
Dieses Bild ist ein Beispiel der Unity-Engine – sie hat die Geometrie in der Welt analysiert und ein Navmesh erstellt (im Screenshot in Hellblau). Jedes Polygon in einem Navmesh ist ein Bereich, in dem ein Agent stehen oder sich von einem Polygon zu einem anderen bewegen kann. In diesem Beispiel sind die Polygone kleiner als die Etagen, auf denen sie sich befinden. Dies geschieht, um die Größe des Agenten zu berücksichtigen, der über seine nominale Position hinausragt.
Wir können nach einer Route durch dieses Netz suchen, wiederum mit dem A*-Algorithmus. Dadurch erhalten wir eine nahezu perfekte Route in der Welt, die die gesamte Geometrie berücksichtigt und keine unnötigen Knoten und die Erstellung von Wegpunkten erfordert.
Pathfinding ist ein zu weit gefasstes Thema, für das ein Abschnitt eines Artikels nicht ausreicht. Wenn Sie es genauer studieren möchten, wird dies hilfreich sein .
Planung
Bei der Wegfindung haben wir gelernt, dass es manchmal nicht ausreicht, nur eine Richtung auszuwählen und sich zu bewegen – wir müssen eine Route auswählen und ein paar Abbiegungen machen, um an unser gewünschtes Ziel zu gelangen. Wir können diese Idee verallgemeinern: Das Erreichen eines Ziels ist nicht nur der nächste Schritt, sondern eine ganze Abfolge, bei der man manchmal mehrere Schritte vorausschauen muss, um herauszufinden, was der erste sein sollte. Dies nennt man Planung. Pathfinding kann als eine von mehreren Erweiterungen der Planung betrachtet werden. In Bezug auf unseren Sinnes-/Denk-/Handlungszyklus ist dies der Punkt, an dem der Denkteil mehrere Handlungsteile für die Zukunft plant.
Schauen wir uns das Beispiel des Brettspiels Magic: The Gathering an. Wir gehen zunächst mit folgendem Kartensatz in der Hand vor:
- Sumpf – Gibt 1 schwarzes Mana (Landkarte).
- Wald – gibt 1 grünes Mana (Landkarte).
- Flüchtiger Zauberer – Zum Beschwören ist 1 blaues Mana erforderlich.
- Elbischer Mystiker – Zum Beschwören ist 1 grünes Mana erforderlich.
Wir ignorieren die verbleibenden drei Karten, um es einfacher zu machen. Gemäß den Regeln darf ein Spieler pro Spielzug 1 Landkarte spielen, er kann diese Karte „tippen“, um ihr Mana zu entziehen, und dann entsprechend der Manamenge Zauber wirken (einschließlich der Beschwörung einer Kreatur). In dieser Situation muss der menschliche Spieler „Wald“ spielen, 1 grünes Mana antippen und dann den Elfenmystiker beschwören. Aber wie kann die Spiel-KI das herausfinden?
Einfache Planung
Der triviale Ansatz besteht darin, jede Aktion der Reihe nach auszuprobieren, bis keine passende mehr übrig ist. Durch den Blick auf die Karten erkennt die KI, was Swamp spielen kann. Und er spielt es. Gibt es in dieser Runde noch weitere Aktionen? Es kann weder Elbish Mystic noch Fugitive Wizard beschwören, da diese jeweils grünes und blaues Mana benötigen, um sie zu beschwören, während Swamp nur schwarzes Mana liefert. Und er wird Forest nicht mehr spielen können, weil er bereits Swamp gespielt hat. Somit befolgte die Spiel-KI die Regeln, machte sie aber schlecht. Kann verbessert werden.
Die Planung kann eine Liste von Aktionen finden, die das Spiel in den gewünschten Zustand bringen. So wie jedes Feld auf einem Weg Nachbarn hatte (bei der Wegfindung), hat auch jede Aktion in einem Plan Nachbarn oder Nachfolger. Wir können nach diesen Aktionen und nachfolgenden Aktionen suchen, bis wir den gewünschten Zustand erreichen.
In unserem Beispiel lautet das gewünschte Ergebnis „Wenn möglich eine Kreatur beschwören“. Zu Beginn der Runde sehen wir nur zwei mögliche Aktionen, die die Spielregeln erlauben:
1. Swamp spielen (Ergebnis: Swamp im Spiel)
2. Wald spielen (Ergebnis: Wald im Spiel)
Jede durchgeführte Aktion kann zu weiteren Aktionen führen und andere schließen, wiederum abhängig von den Spielregeln. Stellen Sie sich vor, wir haben Sumpf gespielt – dadurch wird Sumpf als nächster Schritt entfernt (wir haben es bereits gespielt), und dadurch wird auch Wald entfernt (denn gemäß den Regeln können Sie pro Spielzug eine Landkarte spielen). Danach fügt die KI als nächsten Schritt den Erwerb von 1 schwarzen Mana hinzu, da es keine anderen Optionen gibt. Wenn er sich für „Tap the Swamp“ entscheidet, erhält er 1 Einheit schwarzes Mana und kann damit nichts anfangen.
1. Swamp spielen (Ergebnis: Swamp im Spiel)
1.1 „Tap“-Sumpf (Ergebnis: Sumpf „getappt“, +1 Einheit schwarzes Mana)
Keine Aktionen verfügbar – ENDE
2. Wald spielen (Ergebnis: Wald im Spiel)
Die Liste der Aktionen war kurz, wir landeten in einer Sackgasse. Wir wiederholen den Vorgang für den nächsten Schritt. Wir spielen Wald und öffnen die Aktion „1 grünes Mana erhalten“, die wiederum die dritte Aktion öffnet – Elbenmystiker beschwören.
1. Swamp spielen (Ergebnis: Swamp im Spiel)
1.1 „Tap“-Sumpf (Ergebnis: Sumpf „getappt“, +1 Einheit schwarzes Mana)
Keine Aktionen verfügbar – ENDE
2. Wald spielen (Ergebnis: Wald im Spiel)
2.1 Wald „tippen“ (Ergebnis: Wald wird „getappt“, +1 Einheit grünes Mana)
2.1.1 Elbischen Mystiker beschwören (Ergebnis: Elbischer Mystiker im Spiel, -1 grünes Mana)
Keine Aktionen verfügbar – ENDE
Schließlich haben wir alle möglichen Aktionen untersucht und einen Plan gefunden, der eine Kreatur beschwört.
Dies ist ein sehr vereinfachtes Beispiel. Es ist ratsam, den bestmöglichen Plan zu wählen und nicht nur irgendeinen Plan, der bestimmte Kriterien erfüllt. Im Allgemeinen ist es möglich, potenzielle Pläne anhand des Ergebnisses oder des Gesamtnutzens ihrer Umsetzung zu bewerten. Für das Ausspielen einer Länderkarte erhältst du 1 Punkt und für die Beschwörung einer Kreatur 3 Punkte. Swamp zu spielen wäre ein 1-Punkte-Plan. Und wenn man Wald → Tippe auf den Wald → Elbenmystiker beschwören spielt, erhältst du sofort 4 Punkte.
So funktioniert die Planung in Magic: The Gathering, aber die gleiche Logik gilt auch in anderen Situationen. Zum Beispiel beim Schach einen Bauern bewegen, um Platz für den Läufer zu schaffen. Oder gehen Sie hinter einer Wand in Deckung, um sicher in XCOM zu schießen. Im Allgemeinen verstehen Sie, worum es geht.
Verbesserte Planung
Manchmal gibt es zu viele potenzielle Maßnahmen, um alle möglichen Optionen in Betracht zu ziehen. Um auf das Beispiel von Magic: The Gathering zurückzukommen: Nehmen wir an, dass es im Spiel und auf Ihrer Hand mehrere Länder- und Kreaturenkarten gibt – die Anzahl der möglichen Zugkombinationen kann in die Dutzende gehen. Es gibt mehrere Lösungen für das Problem.
Die erste Methode ist die Rückwärtsverkettung. Anstatt alle Kombinationen auszuprobieren, ist es besser, mit dem Endergebnis zu beginnen und zu versuchen, einen direkten Weg zu finden. Anstatt von der Wurzel des Baumes zu einem bestimmten Blatt zu gehen, bewegen wir uns in die entgegengesetzte Richtung – vom Blatt zur Wurzel. Diese Methode ist einfacher und schneller.
Wenn der Feind 1 Gesundheit hat, können Sie den Plan „1 oder mehr Schaden verursachen“ finden. Um dies zu erreichen, müssen eine Reihe von Bedingungen erfüllt sein:
1. Schaden kann durch einen Zauber verursacht werden – er muss in der Hand sein.
2. Um einen Zauber zu wirken, brauchst du Mana.
3. Um Mana zu erhalten, musst du eine Länderkarte spielen.
4. Um eine Länderkarte auszuspielen, musst du sie auf der Hand haben.
Eine andere Möglichkeit ist die Best-First-Suche. Anstatt alle Wege auszuprobieren, wählen wir den am besten geeigneten aus. In den meisten Fällen liefert diese Methode den optimalen Plan ohne unnötige Suchkosten. A* ist eine Form der Best-First-Suche – durch die Prüfung der vielversprechendsten Routen von Anfang an kann bereits der beste Weg gefunden werden, ohne andere Optionen prüfen zu müssen.
Eine interessante und immer beliebter werdende Best-First-Suchoption ist die Monte-Carlo-Baumsuche. Anstatt bei der Auswahl jeder weiteren Aktion zu erraten, welche Pläne besser sind als andere, wählt der Algorithmus bei jedem Schritt zufällige Nachfolger aus, bis er das Ende erreicht (wenn der Plan zum Sieg oder zur Niederlage führte). Das Endergebnis wird dann verwendet, um die Gewichtung der vorherigen Optionen zu erhöhen oder zu verringern. Indem dieser Vorgang mehrmals hintereinander wiederholt wird, gibt der Algorithmus eine gute Schätzung darüber ab, was der beste nächste Zug ist, selbst wenn sich die Situation ändert (wenn der Feind Maßnahmen ergreift, um den Spieler zu stören).
Keine Geschichte über die Planung in Spielen wäre vollständig ohne die zielorientierte Aktionsplanung oder GOAP (zielorientierte Aktionsplanung). Dies ist eine weit verbreitete und diskutierte Methode, aber abgesehen von ein paar Unterscheidungsdetails handelt es sich im Wesentlichen um die Rückwärtsverkettungsmethode, über die wir zuvor gesprochen haben. Wenn das Ziel darin besteht, „den Spieler zu zerstören“ und der Spieler sich in Deckung befindet, könnte der Plan lauten: Mit einer Granate zerstören → holen → werfen.
Meist gibt es mehrere Ziele mit jeweils eigener Priorität. Wenn das Ziel mit der höchsten Priorität nicht erreicht werden kann (keine Aktionskombination ergibt einen „Töte den Spieler“-Plan, weil der Spieler nicht sichtbar ist), greift die KI auf Ziele mit niedrigerer Priorität zurück.
Training und Anpassung
Wir haben bereits gesagt, dass Spiel-KI normalerweise kein maschinelles Lernen nutzt, da es nicht für die Verwaltung von Agenten in Echtzeit geeignet ist. Das heißt aber nicht, dass man sich in diesem Bereich nichts ausleihen kann. Wir wollen in einem Shooter einen Gegner, von dem wir etwas lernen können. Informieren Sie sich beispielsweise über die besten Positionen auf der Karte. Oder ein Gegner in einem Kampfspiel, der die häufig verwendeten Combo-Moves des Spielers blockiert und ihn so motiviert, andere zu verwenden. Daher kann maschinelles Lernen in solchen Situationen sehr nützlich sein.
Statistiken und Wahrscheinlichkeiten
Bevor wir uns mit komplexen Beispielen befassen, wollen wir sehen, wie weit wir kommen können, wenn wir ein paar einfache Messungen vornehmen und diese zur Entscheidungsfindung nutzen. Zum Beispiel Echtzeitstrategie – wie stellen wir fest, ob ein Spieler in den ersten Minuten des Spiels einen Angriff starten kann und welche Verteidigung wir dagegen vorbereiten müssen? Wir können die vergangenen Erfahrungen eines Spielers untersuchen, um zu verstehen, wie zukünftige Reaktionen aussehen könnten. Zunächst einmal haben wir solche Rohdaten nicht, aber wir können sie sammeln – jedes Mal, wenn die KI gegen einen Menschen spielt, kann sie den Zeitpunkt des ersten Angriffs aufzeichnen. Nach einigen Sitzungen erhalten wir eine durchschnittliche Zeit, die der Spieler in Zukunft zum Angriff benötigen wird.
Es gibt auch ein Problem mit Durchschnittswerten: Wenn ein Spieler 20 Mal hetzt und 20 Mal langsam spielt, liegen die erforderlichen Werte irgendwo in der Mitte, und das bringt uns nichts Nützliches. Eine Lösung besteht darin, die Eingabedaten zu begrenzen – die letzten 20 Stück können berücksichtigt werden.
Ein ähnlicher Ansatz wird bei der Schätzung der Wahrscheinlichkeit bestimmter Aktionen verwendet, indem davon ausgegangen wird, dass die früheren Präferenzen des Spielers auch in Zukunft dieselben sein werden. Wenn ein Spieler uns fünfmal mit Feuerball, zweimal mit Blitz und einmal mit Nahkampf angreift, ist es offensichtlich, dass er Feuerball bevorzugt. Lassen Sie uns die Wahrscheinlichkeit des Einsatzes verschiedener Waffen extrapolieren und sehen: Feuerball = 62,5 %, Blitz = 25 % und Nahkampf = 12,5 %. Unsere Spiel-KI muss sich darauf vorbereiten, sich vor Feuer zu schützen.
Eine weitere interessante Methode besteht darin, mit dem Naive Bayes Classifier große Mengen an Eingabedaten zu untersuchen und die Situation so zu klassifizieren, dass die KI in der gewünschten Weise reagiert. Bayesianische Klassifikatoren sind vor allem für ihre Verwendung in E-Mail-Spamfiltern bekannt. Dort untersuchen sie die Wörter, vergleichen sie damit, wo diese Wörter zuvor aufgetaucht sind (im Spam oder nicht) und ziehen Schlussfolgerungen über eingehende E-Mails. Wir können das Gleiche auch mit weniger Eingaben erreichen. Basierend auf allen nützlichen Informationen, die die KI sieht (z. B. welche feindlichen Einheiten erstellt werden, welche Zauber sie verwenden oder welche Technologien sie erforscht haben) und dem Endergebnis (Krieg oder Frieden, Ansturm oder Verteidigung usw.) - Wir wählen das gewünschte KI-Verhalten.
Alle diese Trainingsmethoden sind ausreichend, es ist jedoch ratsam, sie auf der Grundlage von Testdaten anzuwenden. Die KI lernt, sich an die verschiedenen Strategien Ihrer Spieletester anzupassen. KI, die sich nach der Veröffentlichung an den Spieler anpasst, kann zu vorhersehbar oder zu schwer zu besiegen sein.
Wertbasierte Anpassung
Angesichts des Inhalts unserer Spielwelt und der Regeln können wir die Werte, die die Entscheidungsfindung beeinflussen, ändern, anstatt einfach die Eingabedaten zu verwenden. Wir machen das:
- Lassen Sie die KI Daten über den Zustand der Welt und wichtige Ereignisse während des Spiels sammeln (wie oben).
- Lassen Sie uns anhand dieser Daten einige wichtige Werte ändern.
- Auf Basis der Verarbeitung bzw. Auswertung dieser Werte setzen wir unsere Entscheidungen um.
Beispielsweise hat ein Agent auf einer Ego-Shooter-Karte mehrere Räume zur Auswahl. Jedes Zimmer hat seinen eigenen Wert, der bestimmt, wie wünschenswert es ist, es zu besuchen. Die KI wählt anhand des Wertes zufällig aus, in welchen Raum sie geht. Der Agent merkt sich dann, in welchem Raum er getötet wurde, und verringert dessen Wert (die Wahrscheinlichkeit, dass er dorthin zurückkehrt). Das Gleiche gilt für die umgekehrte Situation: Wenn der Agent viele Gegner zerstört, erhöht sich der Wert des Raums.
Markov-Modell
Was wäre, wenn wir die gesammelten Daten nutzen würden, um Vorhersagen zu treffen? Wenn wir uns an jeden Raum erinnern, in dem wir einen Spieler über einen bestimmten Zeitraum sehen, können wir vorhersagen, in welchen Raum der Spieler gehen wird. Indem wir die Bewegungen des Spielers durch Räume (Werte) verfolgen und aufzeichnen, können wir sie vorhersagen.
Nehmen wir drei Räume: Rot, Grün und Blau. Und auch die Beobachtungen, die wir beim Anschauen der Spielsitzung aufgezeichnet haben:
Die Anzahl der Beobachtungen in jedem Raum ist nahezu gleich – wir wissen immer noch nicht, wo wir einen guten Ort für einen Hinterhalt schaffen sollen. Das Sammeln von Statistiken wird auch durch das Respawnen von Spielern erschwert, die gleichmäßig auf der Karte erscheinen. Aber die Daten über den nächsten Raum, den sie betreten, nachdem sie auf der Karte angezeigt wurden, sind bereits nützlich.
Es ist zu erkennen, dass der grüne Raum den Spielern gefällt – die meisten Menschen ziehen vom roten Raum dorthin, 50 % von ihnen bleiben dort auch weiterhin. Das blaue Zimmer hingegen ist nicht beliebt; fast niemand geht dorthin, und wenn, dann bleiben sie nicht lange.
Aber die Daten sagen uns etwas Wichtigeres: Wenn sich ein Spieler in einem blauen Raum befindet, ist der nächste Raum, in dem wir ihn sehen, rot und nicht grün. Auch wenn der grüne Raum beliebter ist als der rote Raum, ändert sich die Situation, wenn sich der Spieler im blauen Raum befindet. Der nächste Status (d. h. der Raum, in den der Spieler geht) hängt vom vorherigen Status (d. h. dem Raum, in dem sich der Spieler gerade befindet) ab. Da wir Abhängigkeiten untersuchen, können wir genauere Vorhersagen treffen, als wenn wir Beobachtungen einfach unabhängig voneinander zählen würden.
Die Vorhersage eines zukünftigen Zustands auf der Grundlage von Daten aus einem vergangenen Zustand wird als Markov-Modell bezeichnet, und solche Beispiele (mit Räumen) werden Markov-Ketten genannt. Da die Muster die Wahrscheinlichkeit von Änderungen zwischen aufeinanderfolgenden Zuständen darstellen, werden sie visuell als FSMs mit einer Wahrscheinlichkeit um jeden Übergang herum angezeigt. Früher haben wir FSM verwendet, um den Verhaltenszustand eines Agenten darzustellen, aber dieses Konzept erstreckt sich auf jeden Zustand, unabhängig davon, ob er mit dem Agenten verbunden ist oder nicht. In diesem Fall stellen die Zustände den Raum dar, den der Agent einnimmt:
Dies ist eine einfache Möglichkeit, die relative Wahrscheinlichkeit von Zustandsänderungen darzustellen und der KI die Möglichkeit zu geben, den nächsten Zustand vorherzusagen. Sie können mit mehreren Schritten rechnen.
Befindet sich ein Spieler im grünen Raum, besteht eine 50-prozentige Chance, dass er dort bleibt, wenn er das nächste Mal beobachtet wird. Aber wie hoch sind die Chancen, dass er auch danach noch dort sein wird? Es besteht nicht nur die Möglichkeit, dass der Spieler nach zwei Beobachtungen im grünen Raum geblieben ist, sondern es besteht auch die Möglichkeit, dass er ihn verlassen hat und zurückgekehrt ist. Hier ist die neue Tabelle unter Berücksichtigung der neuen Daten:
Es zeigt, dass die Wahrscheinlichkeit, den Spieler nach zwei Beobachtungen im grünen Raum zu sehen, 51 % beträgt – 21 % davon, dass er aus dem roten Raum kommt, 5 % davon, dass der Spieler den blauen Raum zwischen ihnen besucht, und 25 %, dass der Spieler den grünen Raum nicht verlässt.
Die Tabelle ist lediglich ein visuelles Hilfsmittel – das Verfahren erfordert lediglich die Multiplikation der Wahrscheinlichkeiten bei jedem Schritt. Mit einer Einschränkung können Sie also weit in die Zukunft blicken: Wir gehen davon aus, dass die Chance, einen Raum zu betreten, ganz vom aktuellen Raum abhängt. Dies wird als Markov-Eigenschaft bezeichnet – der zukünftige Zustand hängt nur von der Gegenwart ab. Aber das ist nicht hundertprozentig korrekt. Spieler können ihre Entscheidungen abhängig von anderen Faktoren ändern: Gesundheitszustand oder Munitionsmenge. Da wir diese Werte nicht erfassen, sind unsere Prognosen weniger genau.
N-Gramm
Wie wäre es mit dem Beispiel eines Kampfspiels und der Vorhersage der Combo-Moves des Spielers? Das selbe! Aber statt eines einzelnen Zustands oder Ereignisses werden wir die gesamten Sequenzen untersuchen, die einen Combo-Schlag ausmachen.
Eine Möglichkeit hierfür besteht darin, jede Eingabe (z. B. Kick, Punch oder Block) in einem Puffer zu speichern und den gesamten Puffer als Ereignis zu schreiben. Wenn der Spieler also wiederholt Kick, Kick, Punch drückt, um den SuperDeathFist-Angriff auszuführen, speichert das KI-System alle Eingaben in einem Puffer und merkt sich die letzten drei, die in jedem Schritt verwendet wurden.
(Die fett gedruckten Linien zeigen, wann der Spieler den SuperDeathFist-Angriff startet.)
Die KI sieht alle Optionen, wenn der Spieler Kick auswählt, gefolgt von einem weiteren Kick, und stellt dann fest, dass die nächste Eingabe immer Punch ist. Dies ermöglicht es dem Agenten, den Combo-Move von SuperDeathFist vorherzusagen und ihn wenn möglich zu blockieren.
Diese Ereignissequenzen werden N-Gramme genannt, wobei N die Anzahl der gespeicherten Elemente ist. Im vorherigen Beispiel war es ein 3-Gramm (Trigramm), was bedeutet: Die ersten beiden Einträge werden verwendet, um den dritten vorherzusagen. Dementsprechend sagen in einem 5-Gramm die ersten vier Einträge den fünften voraus und so weiter.
Der Designer muss die Größe von N-Gramm sorgfältig auswählen. Ein kleineres N erfordert weniger Speicher, speichert aber auch weniger Verlauf. Ein 2-Gramm (Bigramm) zeichnet beispielsweise Kick, Kick oder Kick, Punch auf, kann jedoch Kick, Kick, Punch nicht speichern, sodass die KI nicht auf die SuperDeathFist-Kombination reagiert.
Andererseits erfordern größere Zahlen mehr Speicher und die KI wird schwieriger zu trainieren sein, da es viel mehr mögliche Optionen gibt. Wenn Sie drei mögliche Eingaben hätten: Tritt, Schlag oder Block, und wir ein 10-Gramm-Gerät verwenden würden, wären das etwa 60 verschiedene Optionen.
Das Bigramm-Modell ist eine einfache Markov-Kette – jedes Paar aus vergangenem Zustand und aktuellem Zustand ist ein Bigramm, und Sie können den zweiten Zustand basierend auf dem ersten vorhersagen. Die 3-Gramm- und größeren N-Gramme können auch als Markov-Ketten betrachtet werden, bei denen alle Elemente (außer dem letzten im N-Gramm) zusammen den ersten Zustand und das letzte Element den zweiten bilden. Das Kampfspielbeispiel zeigt die Chance des Übergangs vom Kick-and-Kick-Zustand in den Kick-and-Punch-Zustand. Indem wir mehrere Einträge im Eingabeverlauf als eine Einheit behandeln, transformieren wir im Wesentlichen die Eingabesequenz in einen Teil des gesamten Status. Dies gibt uns die Markov-Eigenschaft, die es uns ermöglicht, Markov-Ketten zu verwenden, um die nächste Eingabe vorherzusagen und zu erraten, welcher Combo-Zug als nächstes kommt.
Abschluss
Wir haben über die gängigsten Tools und Ansätze bei der Entwicklung künstlicher Intelligenz gesprochen. Außerdem haben wir uns angeschaut, in welchen Situationen sie eingesetzt werden müssen und wo sie besonders nützlich sind.
Dies sollte ausreichen, um die Grundlagen der Spiel-KI zu verstehen. Aber das sind natürlich nicht alle Methoden. Weniger beliebt, aber nicht weniger effektiv sind:
- Optimierungsalgorithmen einschließlich Bergsteiger-, Gefälleabstiegs- und genetischer Algorithmen
- kontradiktorische Such-/Planungsalgorithmen (Minimax- und Alpha-Beta-Pruning)
- Klassifizierungsmethoden (Perzeptrone, neuronale Netze und Support-Vektor-Maschinen)
- Systeme zur Verarbeitung der Wahrnehmung und des Gedächtnisses von Agenten
- Architekturansätze für KI (Hybridsysteme, Subset-Architekturen und andere Arten der Überlagerung von KI-Systemen)
- Animationstools (Planung und Bewegungskoordination)
- Leistungsfaktoren (Detaillierungsgrad, jederzeit und Timeslicing-Algorithmen)
Ähnliche Resourcen:
1. GameDev.net hat , und auch .
2. enthält viele Präsentationen und Artikel zu einem breiten Themenspektrum im Zusammenhang mit der Spiele-KI-Entwicklung.
3. Enthält Themen vom GDC AI Summit, von denen viele kostenlos verfügbar sind.
4. Nützliche Materialien finden Sie auch auf der Website .
5. Tommy Thompson, KI-Forscher und Spieleentwickler, macht Videos auf YouTube mit einer Erklärung und Untersuchung der KI in kommerziellen Spielen.
Bücher zum Thema:
1. Die Game AI Pro-Buchreihe ist eine Sammlung kurzer Artikel, die erklären, wie man bestimmte Funktionen implementiert oder wie man bestimmte Probleme löst.
2. Die AI Game Programming Wisdom-Serie ist der Vorgänger der Game AI Pro-Serie. Es enthält ältere Methoden, aber fast alle sind auch heute noch relevant.
3. ist einer der Grundlagentexte für alle, die das allgemeine Gebiet der künstlichen Intelligenz verstehen wollen. Dies ist kein Buch über Spieleentwicklung – es vermittelt die Grundlagen der KI.
Source: habr.com