Wie man eine Spiel-KI erstellt: ein Leitfaden für Einsteiger

Ich bin auf ein interessantes Material über künstliche Intelligenz in Spielen gestoßen. Es erklärt grundlegende Dinge über KI anhand einfacher Beispiele und enthält viele nützliche Werkzeuge und Methoden für die bequeme Entwicklung und Gestaltung. Wo, wie und wann man sie einsetzen kann, wird ebenfalls behandelt.

Die meisten Beispiele sind in Pseudocode verfasst, daher sind keine tiefen Programmierkenntnisse erforderlich. Unter dem Beitrag sind 35 Seiten Text mit Bildern und GIFs, also bereitet euch vor.

UPD. Entschuldigung, aber ich habe bereits meine eigene Übersetzung dieses Artikels auf Habr gemacht. PatientZero. Man kann seine Version lesen hier, aber aus irgendeinem Grund ist der Artikel an mir vorbeigegangen (ich habe die Suche benutzt, aber etwas lief schief). Da ich in einem Blog schreibe, der sich mit Game Development beschäftigt, habe ich beschlossen, meine Übersetzung für die Abonnenten zu hinterlassen (einige Punkte habe ich anders formuliert, andere wurden absichtlich auf Anraten der Entwickler weggelassen).

Was ist KI?

Spiel-KI konzentriert sich darauf, welche Aktionen ein Objekt basierend auf den Bedingungen, in denen es sich befindet, ausführen sollte. Dies wird normalerweise als Steuerung „intelligenter Agenten“ bezeichnet, wobei der Agent eine Spielfigur, ein Fahrzeug, ein Bot oder manchmal etwas Abstrakteres ist: eine ganze Gruppe von Entitäten oder sogar eine Zivilisation. In jedem Fall handelt es sich um etwas, das seine Umgebung wahrnehmen, Entscheidungen darauf basierend treffen und entsprechend handeln muss. Dies wird als Zyklus von Sense/Think/Act (Wahrnehmen/Denken/Handeln) bezeichnet:

• Sense: Der Agent findet oder erhält Informationen über Dinge in seiner Umgebung, die sein Verhalten beeinflussen könnten (drohende Gefahren in der Nähe, Sammelobjekte, interessante Orte zur Erkundung).
• Think: Der Agent entscheidet, wie er reagieren soll (prüft, ob es sicher genug ist, Objekte zu sammeln, oder ob er zuerst kämpfen/sich verstecken sollte).
• Act: Der Agent führt Aktionen aus, um die vorherige Entscheidung umzusetzen (beginnt, sich auf den Gegner oder das Objekt zuzubewegen).
• …die Situation hat sich jetzt aufgrund der Aktionen der Charaktere verändert, daher wird der Zyklus mit neuen Daten wiederholt.

KI konzentriert sich in der Regel auf den Sinn-Teil des Zyklus. Autonome Fahrzeuge machen zum Beispiel Bilder der Straße, kombinieren sie mit Radar- und LiDAR-Daten und interpretieren diese. Normalerweise übernimmt das maschinelles Lernen, das Eingabedaten verarbeitet und ihnen Bedeutung verleiht, indem es semantische Informationen wie „Da ist ein weiteres Auto 20 Yards vor Ihnen“ extrahiert. Dies sind sogenannte Klassifikationsprobleme.

Spiele benötigen kein komplexes System zur Informationsgewinnung, da der Großteil der Daten bereits ein integraler Bestandteil ist. Es ist nicht notwendig, Algorithmen zur Bildverarbeitung einzusetzen, um festzustellen, ob ein Gegner vor einem steht — das Spiel weiß bereits Bescheid und übermittelt die Informationen direkt im Entscheidungsprozess. Daher ist der Sinn-Teil des Zyklus oft viel einfacher als Denken und Handeln.

Einschränkungen der Spiel-KI

Die KI hat eine Reihe von Einschränkungen, die beachtet werden müssen:

• Die KI muss nicht im Voraus trainiert werden, wie es bei einem Machine-Learning-Algorithmus der Fall ist. Es ist sinnlos, während der Entwicklung ein neuronales Netzwerk zu schreiben, um Dutzende von Tausenden von Spielern zu beobachten und den besten Spielansatz gegen sie zu erlernen. Warum? Weil das Spiel nicht veröffentlicht ist und es keine Spieler gibt.
• Das Spiel soll unterhalten und herausfordern, deshalb sollten die Agenten nicht den besten Ansatz gegen Menschen finden.
• Die Agenten müssen realistisch wirken, damit die Spieler das Gefühl haben, gegen echte Menschen zu spielen. Das Programm AlphaGo hat den Menschen übertroffen, aber die gewählten Züge waren fernab des traditionellen Verständnisses des Spiels. Wenn ein Spiel einen menschlichen Gegner imitiert, sollte es dieses Gefühl nicht haben. Der Algorithmus muss angepasst werden, damit er plausible Entscheidungen trifft und nicht perfekte.
• Die KI muss in Echtzeit arbeiten. Das bedeutet, dass der Algorithmus die CPU nicht über längere Zeiträume monopolartig für Entscheidungsfindungen nutzen kann. Selbst 10 Millisekunden dafür sind zu lang, da den meisten Spielen ausreichend 16 bis 33 Millisekunden zur Verfügung stehen, um die gesamte Verarbeitung durchzuführen und zum nächsten Grafikframe überzugehen.
• Ideal wäre es, wenn zumindest ein Teil des Systems datengetrieben gesteuert wird, damit auch „Nicht-Coder“ Änderungen vornehmen können und Anpassungen schneller erfolgen.

Lassen Sie uns die KI-Ansätze betrachten, die den gesamten Zyklus Sinn/Denk/Handeln abdecken.

Grundlegende Entscheidungen treffen

Lass uns mit einem einfachen Spiel beginnen – Pong. Ziel: Bewege das Paddle so, dass der Ball davon abprallt und nicht daran vorbeifliegt. Es ist wie Tennis, bei dem du verlierst, wenn du den Ball nicht zurückspielst. Hier hat die KI eine relativ einfache Aufgabe – zu entscheiden, in welche Richtung sie das Paddle bewegen soll.

Bedingte Operatoren

Für die KI in Pong gibt es eine naheliegende Lösung – immer versuchen, das Paddle unter dem Ball zu positionieren.

Ein einfacher Algorithmus dafür, in Pseudocode geschrieben:

für jedes Frame/Update, während das Spiel läuft:
wenn der Ball links vom Paddle ist:
bewege das Paddle nach links
sonst, wenn der Ball rechts vom Paddle ist:
bewege das Paddle nach rechts

Wenn das Paddle sich mit der Geschwindigkeit des Balls bewegt, ist das der ideale Algorithmus für die KI in Pong. Es gibt keinen Grund, es komplizierter zu machen, wenn die Daten und möglichen Aktionen für den Agenten nicht viele sind.

Dieser Ansatz ist so einfach, dass der gesamte Zyklus Sense/Think/Act kaum wahrnehmbar ist. Aber er ist vorhanden:

• Der Teil Sense befindet sich in den beiden if-Operatoren. Das Spiel weiß, wo der Ball ist und wo das Paddle ist, also fragt die KI danach.
• Der Teil Think wird ebenfalls durch zwei if-Operatoren dargestellt. Sie verkörpern zwei Entscheidungen, die in diesem Fall sich gegenseitig ausschließen. Infolge dessen wird eine von drei Aktionen gewählt – das Paddle nach links bewegen, nach rechts bewegen oder nichts tun, wenn es bereits richtig positioniert ist.
• Der Teil Act befindet sich in den Operatoren Move Paddle Left und Move Paddle Right. Je nach Spieldesign können sie das Paddle sofort oder mit einer bestimmten Geschwindigkeit bewegen.

Solche Ansätze werden reaktiv genannt – es gibt eine einfache Regelset (in diesem Fall if-Operatoren im Code), die auf den aktuellen Zustand der Welt reagieren und handeln.

Entscheidungsbaum

Das Beispiel mit dem Spiel Pong entspricht tatsächlich dem formalen Konzept der KI, das Entscheidungsbaum genannt wird. Der Algorithmus durchläuft ihn, um zu einem „Blatt“ zu gelangen – eine Entscheidung darüber, welche Aktion zu ergreifen ist.

Lass uns ein Flussdiagramm des Entscheidungsbaums für unseren Paddle-Algorithmus erstellen:

Jeder Teil des Baumes wird als Node (Knoten) bezeichnet – die KI verwendet die Graphentheorie zur Beschreibung solcher Strukturen. Es gibt zwei Arten von Knoten:

• Entscheidungsknoten: eine Wahl zwischen zwei Alternativen basierend auf der Überprüfung einer Bedingung, wobei jede Alternative als eigener Knoten dargestellt wird.
• Endknoten: eine auszuführende Aktion, die die endgültige Entscheidung darstellt.

Der Algorithmus beginnt mit dem ersten Knoten (dem „Wurzel“-Knoten des Baums). Er trifft entweder eine Entscheidung, zu welchem Kindknoten er wechseln soll, oder führt eine im Knoten gespeicherte Aktion aus und beendet sich.

Was ist also der Vorteil, wenn der Entscheidungsbaum die gleiche Funktion wie die if-Anweisungen im vorherigen Abschnitt erfüllt? 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 im Baum repräsentieren, ohne hart kodiert zu werden. Stellen wir es in Tabellenform dar:

Auf der Code-Seite erhalten Sie ein System zum Lesen von Zeilen. Erstellen Sie einen Knoten für jede von ihnen, verbinden Sie die Entscheidungslogik basierend auf der zweiten Spalte und die Kindknoten basierend auf der dritten und vierten Spalte. Sie müssen weiterhin die Bedingungen und Aktionen programmieren, aber jetzt wird die Struktur des Spiels komplexer. Sie fügen zusätzliche Entscheidungen und Aktionen hinzu und konfigurieren dann die gesamte KI, indem Sie einfach die Textdatei mit der Baumdefinition bearbeiten. Übergeben Sie die Datei dann an den Spieldesigner, der das Verhalten ändern kann, ohne das Spiel neu zu kompilieren oder den Code zu ändern.

Entscheidungsbäume sind äußerst nützlich, wenn sie automatisch auf der Grundlage eines großen Beispielsets erstellt werden (z. B. unter Verwendung des ID3-Algorithmus). Dadurch werden sie zu einem effizienten und leistungsstarken Werkzeug zur Klassifizierung von Situationen basierend auf erhaltenen Daten. Dennoch gehen wir über ein einfaches System hinaus, das von Agenten zur Auswahl von Aktionen verwendet wird.

Szenarien

Wir haben das System des Entscheidungsbaums behandelt, das zuvor definierte Bedingungen und Aktionen verwendete. Der Mensch, der die KI entwirft, kann den Baum so organisieren, wie er möchte, muss jedoch weiterhin auf den Programmierer angewiesen sein, der alles programmiert hat. Was wäre, wenn wir dem Designer 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 die Bedingungen zur Überprüfung dieser Werte aufzeichnet. Dann könnte die Datenstruktur des Entscheidungsbaums folgendermaßen aussehen:

Im Grunde genommen ist es dasselbe wie in der ersten Tabelle, aber die Lösungen haben ihren eigenen Code, der dem bedingten Teil eines if-Operators ähnelt. Im Code würde dies in der zweiten Spalte für Entscheidungsneigungen abgerufen werden, aber anstelle nach einer bestimmten Bedingung für die Ausführung (Ist der Ball links vom Paddle?) zu suchen, bewertet es den Ausdruck und gibt entsprechend true oder false zurück. Dies geschieht mit der Skriptsprache Lua oder Angelscript. Mit diesen kann der Entwickler Objekte in seinem Spiel (Ball und Paddle) übernehmen und Variablen erstellen, die im Skript verfügbar sind (ball.position). Darüber hinaus ist die Skriptsprache einfacher als C++. Sie benötigt keinen vollständigen Kompilierungsprozess, was sie ideal für schnelle Anpassungen der Spiel-Logik macht und es «Nicht-Entwicklern» ermöglicht, selbst die gewünschten Funktionen zu erstellen.

Im obigen Beispiel wird die Skriptsprache nur zur Bewertung des bedingten Ausdrucks verwendet, kann jedoch auch für Aktionen genutzt werden. Zum Beispiel könnten die Daten Move Paddle Right zu einer Skriptanweisung werden (ball.position.x += 10). So kann auch die Aktion im Skript definiert werden, ohne dass das Programmieren von Move Paddle Right notwendig ist.

Man könnte noch weiter gehen und den Entscheidungsbaum vollständig in der Skriptsprache schreiben. Das wäre Code in Form von fest programmierten (hardcoded) Bedingungsanweisungen, die jedoch in externen Skriptdateien gespeichert sind, d.h. sie können geändert werden, ohne das gesamte Programm neu zu kompilieren. Oftmals kann die Skriptdatei während des Spiels verändert werden, um verschiedene KI-Reaktionen schnell zu testen.

Reaktion auf Ereignisse

Die obigen Beispiele passen perfekt zu Pong. Sie durchlaufen kontinuierlich den Zyklus Sense/Think/Act und handeln basierend auf dem letzten Zustand der Welt. In komplexeren Spielen muss jedoch auf einzelne Ereignisse reagiert werden, nicht alles auf einmal bewertet werden. In diesem Fall ist Pong kein passendes Beispiel mehr. Wählen wir ein anderes.

Stellen Sie sich einen Shooter vor, bei dem die Feinde unbeweglich sind, bis sie den Spieler entdecken, woraufhin sie je nach ihrer «Spezialisierung» handeln: Manche werden versuchen, direkt anzugreifen, andere werden aus der Distanz angreifen. Das ist immer noch ein grundlegendes Reaktionssystem — «Wenn der Spieler gesehen wird, dann tu etwas» — aber es kann logisch in das Ereignis Player Seen (Spieler gesehen) und die Reaktion (Wählen Sie eine Antwort und führen Sie sie aus) unterteilt werden.

Das bringt uns zu dem Zyklus Sense/Think/Act. Wir können den Sense-Teil programmieren, der in jedem Frame überprüft, ob die KI den Spieler sieht. Wenn nicht, passiert nichts, aber wenn sie es sieht, wird das Ereignis 'Spieler gesehen' ausgelöst. Der Code hat einen separaten Abschnitt, in dem steht: "Wenn das Ereignis 'Spieler gesehen' eintritt, mache ", wobei die Aktion ist, die Sie benötigen, um auf die Teile Think und Act zuzugreifen. So stellen Sie die Reaktionen auf das Ereignis 'Spieler gesehen' ein: für einen 'rushing' Charakter - ChargeAndAttack, und für einen Sniper - HideAndSnipe. Diese Verbindungen können in einer Datendatei erstellt werden, um eine schnelle Bearbeitung zu ermöglichen, ohne das Programm neu zu kompilieren. Hier kann auch eine Skriptsprache verwendet werden.

Komplexe Entscheidungen treffen

Obwohl einfache Reaktionssysteme sehr effektiv sind, gibt es viele Situationen, in denen sie nicht ausreichen. Manchmal müssen unterschiedliche Entscheidungen getroffen werden, basierend darauf, was der Agent gerade tut, aber es ist schwierig, dies als Bedingung darzustellen. Manchmal gibt es zu viele Bedingungen, um sie effektiv in einem Entscheidungsbaum oder Skript darzustellen. Manchmal muss bewertet werden, wie sich die Situation ändern könnte, bevor eine Entscheidung über den nächsten Schritt getroffen wird. Für diese Probleme sind komplexere Ansätze erforderlich.

Endlicher Automat

Ein Finite State Machine (FSM) ist eine Möglichkeit zu sagen, dass unser Agent sich derzeit in einem von mehreren möglichen Zuständen befindet und dass er von einem Zustand in einen anderen übergehen kann. Es gibt eine bestimmte Anzahl solcher Zustände - daher der Name. Ein gutes Beispiel aus dem Leben ist eine Ampel. An verschiedenen Orten gibt es unterschiedliche Lichtfolgen, aber das Prinzip ist dasselbe - jeder Zustand stellt etwas dar (Halt, Gehe usw.). Die Ampel befindet sich immer zu einem bestimmten Zeitpunkt in genau einem Zustand und wechselt basierend auf einfachen Regeln von einem zum anderen.

Mit NPCs in Spielen sieht es ähnlich aus. Nehmen wir zum Beispiel einen Wächter mit diesen Zuständen:

• Patrouillierend (Patrolling).
• Angreifend (Attacking).
• Flüchtend (Fleeing).

Und mit diesen Bedingungen für den Wechsel seines Zustands:

• Wenn der Wächter einen Gegner sieht, greift er an.
• Wenn der Wächter angreift, aber den Gegner nicht mehr sieht, kehrt er zur Patrouille zurück.
• Wenn der Wächter angreift, aber schwer verwundet ist, flieht er.

Man kann auch if-Anweisungen mit dem Status des Wächters und verschiedene Überprüfungen schreiben: Ist ein Feind in der Nähe? Welches Gesundheitsniveau hat das NPC usw.? Fügen wir ein paar weitere Zustände hinzu:

• Inaktivität (Idling) – zwischen den Patrouillen.
• Suche (Searching) – wenn ein gesichteter Feind sich versteckt hat.
• Hilfe anfordern (Finding Help) – wenn ein Feind gesehen wird, aber zu stark ist, um alleine gegen ihn zu kämpfen.

Die Wahl für jeden von ihnen ist eingeschränkt – zum Beispiel wird der Wächter nicht nach einem versteckten Feind suchen, wenn er wenig Gesundheit hat.

Letztlich kann eine riesige Liste von „wenn“ <x и y, но не z>, dann <p>zu umfangreich werden, daher sollten wir eine Methode formal definieren, die es uns ermöglicht, die Zustände und die Übergänge zwischen den Zuständen im Kopf zu behalten. Dazu berücksichtigen wir alle Zustände und notieren unter jedem Zustand eine Liste aller Übergänge zu anderen Zuständen, einschließlich der erforderlichen Bedingungen.

Dies ist eine Zustandsübergangstabelle – eine umfassende Methode zur Darstellung von FSM. Wir zeichnen ein Diagramm und erhalten einen vollständigen Überblick darüber, wie sich das Verhalten von NPCs verändert.

Das Diagramm spiegelt das Wesen der Entscheidungsfindung für diesen Agenten basierend auf der aktuellen Situation wider. Jede Pfeil zeigt einen Übergang zwischen den Zuständen, wenn die Bedingung daneben wahr ist.

Bei jedem Update überprüfen wir den aktuellen Zustand des Agenten, durchsehen die Liste der Übergänge, und wenn die Bedingungen für den Übergang erfüllt sind, nimmt er einen neuen Zustand an. Zum Beispiel wird bei jedem Frame überprüft, ob der 10-Sekunden-Timer abgelaufen ist, und wenn ja, wechselt der Wächter vom Zustand Idling in Patrolling. Ebenso überprüft der Zustand Attacking die Gesundheit des Agenten – wenn sie niedrig ist, wechselt er in den Zustand Fleeing.

Das betrifft die Verarbeitung von Übergängen zwischen Zuständen, aber was ist mit dem Verhalten, das mit den Zuständen selbst verbunden ist? Wenn es um die Implementierung des tatsächlichen Verhaltens für einen bestimmten Zustand geht, gibt es normalerweise zwei Arten von „Hooks“, bei denen wir Aktionen der FSM zuweisen:

• Aktionen, die wir regelmäßig für den aktuellen Zustand ausführen.
• Aktionen, die wir bei einem Übergang von einem Zustand in einen anderen unternehmen.

Beispiele für den ersten Typ. Der Zustand Patrolling wird jeden Frame den Agenten entlang des Patrouillenwegs bewegen. Der Zustand Attacking wird jeden Frame versuchen, einen Angriff zu beginnen oder in einen Zustand überzugehen, wenn dies möglich ist.

Für den zweiten Typ betrachten wir den Übergang: „Wenn der Feind sichtbar ist und der Feind zu stark ist, dann wechsle in den Zustand Finding Help. Der Agent muss wählen, wo er Hilfe suchen möchte, und diese Information speichern, damit der Zustand Finding Help weiß, wohin er sich wenden kann. Sobald Hilfe gefunden ist, wechselt der Agent zurück in den Zustand Attacking. In diesem Moment möchte er seinen Verbündeten über die Bedrohung informieren, weshalb die Aktion NotifyFriendOfThreat auftreten kann.

Und erneut können wir dieses System durch die Linse des Zyklus Sense / Think / Act betrachten. Sense wird in den Daten verkörpert, die von der Übergangslogik verwendet werden. Think sind die Übergänge, die in jedem Zustand verfügbar sind. Und Act erfolgt durch die Aktionen, die periodisch innerhalb eines Zustands oder bei Übergängen zwischen Zuständen ausgeführt werden.

Manchmal kann die kontinuierliche Abfrage von Übergangsbedingungen kostspielig sein. Wenn jeder Agent zum Beispiel in jedem Frame komplexe Berechnungen durchführen muss, um zu bestimmen, ob er Feinde sieht und zu erkennen, ob er von Patrolling zu Attacking wechseln kann – das kostet viel Rechenzeit.

Wichtige Veränderungen des Weltzustands können als Ereignisse betrachtet werden, die verarbeitet werden, sobald sie auftreten. Anstatt dass die FSM in jedem Frame die Übergangsbedingung „Kann mein Agent den Spieler sehen?“ prüft, könnte man ein separates System einrichten, das die Prüfungen seltener durchführt (zum Beispiel 5 Mal pro Sekunde). Das Ergebnis könnte Player Seen sein, wenn die Prüfung bestanden wird.

Dies wird an die FSM übergeben, die jetzt in den Zustand Player Seen event received übergehen und entsprechend reagieren muss. Das endgültige Verhalten bleibt gleich, abgesehen von einer nahezu unmerklichen Verzögerung bei der Antwort. Die Leistung hat sich jedoch verbessert, da ein Teil des Sense in einen separaten Teil des Programms ausgelagert wurde.

Hierarchische endliche Zustandsmaschine

Es ist jedoch nicht immer bequem, mit großen FSM zu arbeiten. Wenn wir den Angriffsstatus erweitern möchten, indem wir ihn durch separate MeleeAttacking (Nahkampf) und RangedAttacking (Fernkampf) ersetzen, müssen wir die Übergänge aus allen anderen Zuständen, die in den Zustand Attacking führen (aktuelle und zukünftige), ändern.

Sie haben sicherlich bemerkt, dass in unserem Beispiel viele redundante Übergänge vorkommen. Die meisten Übergänge im Zustand Idling sind identisch mit den Übergängen im Zustand Patrolling. Es wäre besser, nicht zu wiederholen, insbesondere wenn wir mehr ähnliche Zustände hinzufügen. Es macht Sinn, Idling und Patrolling unter einem gemeinsamen Etikett „nicht kämpferisch“ zu gruppieren, wobei es nur einen gemeinsamen Satz von Übergängen zu kämpferischen Zuständen gibt. Wenn wir dieses Etikett als Zustand betrachten, werden Idling und Patrolling zu Unterzuständen. Ein Beispiel für die Verwendung einer separaten Übergangstabelle für den neuen nicht kämpferischen Unterzustand:

Hauptzustände:


Zustand außer Gefecht:


Und in Form eines Diagramms:

Es ist dasselbe System, aber mit einem neuen nicht kämpferischen Zustand, der Idling und Patrolling umfasst. Mit jedem Zustand, der eine FSM mit Unterzuständen enthält (und diese Unterzustände ihrerseits eigene FSMs haben – so viele, wie Sie benötigen), erhalten wir eine Hierarchical Finite State Machine oder HFSM (hierarchische endliche Zustandsmaschine). Durch die Gruppierung des nicht kämpferischen Zustands haben wir eine Menge überflüssiger Übergänge eliminiert. Dasselbe können wir für zukünftige Zustände mit gemeinsamen Übergängen tun. Wenn wir beispielsweise den Zustand Attacking in die Zustände MeleeAttacking und MissileAttacking erweitern, werden sie zu Unterzuständen, die auf der Grundlage der Entfernung zum Feind und der Verfügbarkeit von Munition zwischen einander wechseln. Dadurch können komplexe Verhaltensmodelle und Unterverhaltensmodelle mit minimalen redundanten Übergängen dargestellt werden.

Verhaltenbaum

Mit HFSM werden komplexe Verhaltenskombinationen auf einfache Weise erstellt. Es gibt jedoch eine kleine Schwierigkeit, da die Entscheidungsfindung in Form von Übergangsregeln eng mit dem aktuellen Zustand verbunden ist. In vielen Spielen ist das genau das, was benötigt wird. Eine sorgfältige Nutzung der Zustandshierarchie kann jedoch die Anzahl der Wiederholungen bei Übergängen verringern. Manchmal sind jedoch Regeln erforderlich, die unabhängig vom aktuellen Zustand funktionieren oder die in fast allen Zuständen angewendet werden. Wenn beispielsweise die Gesundheit des Agenten auf 25 % gefallen ist, möchten Sie, dass er unabhängig davon, ob er im Kampf war, untätig war oder sprach, wegläuft – Sie müssen diese Bedingung in jeden Zustand einfügen. Wenn Ihr Designer später den Schwellenwert für niedrige Gesundheit von 25 % auf 10 % ändern möchte, müssen Sie sich wieder damit beschäftigen.

Idealerweise benötigt man für diese Situation ein System, in dem Entscheidungen darüber, "in welchem Zustand man sich befinden soll", außerhalb der eigentlichen Zustände liegen, sodass Änderungen nur an einem Ort vorgenommen werden und die Übergangsbedingungen nicht berührt werden. Hier kommen Verhaltensbäume ins Spiel.

Es gibt mehrere Möglichkeiten zu implementieren, aber der Kern ist für alle ungefähr gleich und ähnelt einem Entscheidungsbaum: Der Algorithmus beginnt mit einem "Wurzel"-Knoten, und im Baum befinden sich Knoten, die entweder Entscheidungen oder Aktionen repräsentieren. Es gibt jedoch einige wichtige Unterschiede:

• Jetzt geben die Knoten eines von drei Werten zurück: Succeeded (wenn die Aufgabe erfüllt wurde), Failed (wenn sie nicht gestartet werden kann) oder Running (wenn sie noch läuft und kein endgültiges Ergebnis vorliegt).
• Es gibt keine Entscheidungsknoten mehr, um zwischen zwei Alternativen zu wählen. Stattdessen gibt es Decorator-Knoten mit einem einzigen Kindknoten. Wenn sie Succeed, führen sie ihren einzigen Kindknoten aus.
• Knoten, die Aktionen ausführen, geben den Wert Running zurück, um die laufenden Aktionen darzustellen.

Dieser kleine Satz von Knoten kann kombiniert werden, um eine große Anzahl komplexer Verhaltensmodelle zu erstellen. Stellen wir uns das HFSM eines Wächters aus dem vorherigen Beispiel in Form eines Verhaltensbaums vor:

Mit dieser Struktur sollte es keinen expliziten Übergang von den Zuständen Idling/Patrolling zum Zustand Attacking oder zu anderen geben. Wenn der Feind sichtbar ist und die Gesundheit des Charakters niedrig, wird die Ausführung am Knoten Fleeing angehalten, unabhängig davon, welchen Knoten er zuvor ausgeführt hat – Patrolling, Idling, Attacking oder einen anderen.

Verhaltensbäume sind komplex – es gibt viele Möglichkeiten, sie zu erstellen, und das richtige Zusammenspiel von Dekoratoren und zusammengesetzten Knoten zu finden, kann problematisch sein. Es gibt auch Fragen dazu, wie oft der Baum überprüft werden sollte – wollen wir ihn bei jedem Teil durchlaufen oder nur, wenn sich eine der Bedingungen ändert? Wie speichert man den Zustand, der sich auf die Knoten bezieht – wie wissen wir, wann wir 10 Sekunden im Zustand Idling waren oder wie wissen wir, welche Knoten zuletzt ausgeführt wurden, um die Sequenz korrekt zu verarbeiten?

Deshalb gibt es zahlreiche Implementierungen. In einigen Systemen wurden die Decorator-Knoten durch eingebaute Dekoratoren ersetzt. Diese evaluieren den Baum erneut, wenn sich die Bedingungen des Dekorators ändern, helfen beim Anhängen an Knoten und bieten zeitliche Aktualisierungen.

Utility-basiertes System

Einige Spiele verfügen über zahlreiche verschiedene Mechaniken. Es ist wünschenswert, dass sie alle Vorteile einfacher und allgemeiner Übergangsregeln erhalten, es ist jedoch nicht unbedingt notwendig, diese in Form eines vollständigen Verhaltensbaums darzustellen. Anstatt eine klare Auswahl oder einen Baum möglicher Aktionen zu haben, ist es einfacher, alle Aktionen zu studieren und die am besten geeignete für den aktuellen Moment auszuwählen.

Ein utilitaristisches System hilft dabei genau. Es handelt sich um ein System, in dem der Agent viele Handlungen hat und selbst auswählt, welche er basierend auf der relativen Nützlichkeit jedes einzelnen ausführen möchte. Wo Nützlichkeit eine willkürliche Maßzahl dafür ist, wie wichtig oder wünschenswert es für den Agenten ist, diese Aktion auszuführen.

Basierend auf dem aktuellen Zustand und der Umgebung kann der Agent die geschätzte Nützlichkeit einer Aktion überprüfen und jederzeit den am besten passenden anderen Zustand wählen. Dies ähnelt einem FSM, mit dem Unterschied, dass die Übergänge durch Bewertungen für jeden potenziellen Zustand, einschließlich des aktuellen, bestimmt werden. Beachten Sie, dass wir die nützlichste Aktion für den Übergang wählen (oder bleiben, wenn wir sie bereits ausgeführt haben). Um mehr Vielfalt zu bieten, kann dies eine gewichtete, aber zufällige Auswahl aus einer kleinen Liste sein.

Das System ordnet willkürlich einen Wertebereich für die Nützlichkeit zu – zum Beispiel von 0 (völlig unerwünscht) bis 100 (vollständig erwünscht). Jedes Handeln hat eine Reihe von Parametern, die sich auf die Berechnung dieses Wertes auswirken. Wenn wir zu unserem Beispiel mit dem Wachmann zurückkehren:

Übergänge zwischen Aktionen sind mehrdeutig – jeder Zustand kann auf einen beliebigen anderen folgen. Die Prioritäten der Handlungen basieren auf den zurückgegebenen Nützlichkeitswerten. Wenn der Feind sichtbar ist und dieser Feind stark ist, während die Gesundheit des Charakters niedrig ist, werden sowohl Fleeing als auch FindingHelp hohe, von Null verschiedene Werte zurückgeben. Dabei wird FindingHelp immer höher bewertet. Ähnlich werden nicht-kämpferische Aktionen niemals mehr als 50 zurückgeben, weshalb sie immer unter den kämpferischen liegen. Dies muss bei der Erstellung von Handlungen und der Berechnung ihrer Nützlichkeit berücksichtigt werden.

In unserem Beispiel geben die Aktionen entweder einen festen konstanten Wert oder einen von zwei festen Werten zurück. Ein realistischeres System würde die Rückgabe einer Bewertung aus einem kontinuierlichen Wertebereich vorsehen. Zum Beispiel liefert die Aktion Fliehen höhere Nutzwerte, wenn die Gesundheit des Agenten niedrig ist, während die Aktion Angreifen niedrigere Werte zurückgibt, wenn der Feind zu stark ist. Aus diesem Grund hat die Aktion Fliehen Vorrang vor Angreifen in jeder Situation, in der der Agent das Gefühl hat, nicht genügend Gesundheit zu haben, um den Gegner zu besiegen. Dies erlaubt es, die Prioritäten der Aktionen basierend auf einer beliebigen Anzahl von Kriterien zu ändern, was diesen Ansatz flexibler und variabler macht als ein Verhaltensbaum oder FSM.

Jede Aktion hat viele Bedingungen zur Berechnung des Programms. Diese können in einer Skriptsprache oder in Form einer Reihe von mathematischen Formeln geschrieben werden. In Die Sims, das den Tagesablauf eines Charakters modelliert, wird eine zusätzliche Ebene der Berechnungen hinzugefügt – der Agent erhält eine Reihe von „Motivationen“, die die Nutzwertbewertungen beeinflussen. Wenn der Charakter hungrig ist, wird er im Laufe der Zeit noch hungriger, und das Ergebnis der Nutzwertbewertung der Aktion Essen wird steigen, bis der Charakter diese ausführt, wodurch der Hunger gesenkt wird und der Wert für Essen auf null zurückkehrt.

Die Idee, Handlungen auf der Grundlage eines Bewertungssystems auszuwählen, ist ziemlich einfach, daher kann das nutzwertbasierte System als Teil der Entscheidungsprozesse der KI verwendet werden, anstatt sie vollständig zu ersetzen. Ein Entscheidungsbaum kann den Nutzwert von zwei Kindknoten abfragen und den höheren auswählen. In ähnlicher Weise kann ein Verhaltensbaum einen zusammengesetzten Knoten für die Bewertung der Nutzwerte von Handlungen haben, um 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 bewegt haben, und einen Wächter, der patrouillierte oder angriff. Aber wie genau behandeln wir die Bewegung des Agenten über einen bestimmten Zeitraum? Wie legen wir die Geschwindigkeit fest, wie vermeiden wir Hindernisse und wie planen wir eine Route, wenn es schwieriger ist, das Ziel zu erreichen, als einfach geradeaus zu gehen? Lassen Sie uns das betrachten.

Verwaltung

In der Anfangsphase gehen wir davon aus, dass jeder Agent einen Geschwindigkeitswert hat, der beinhaltet, wie schnell er sich bewegt und in welche Richtung. Dies kann in Metern pro Sekunde, Kilometern pro Stunde, Pixel pro Sekunde usw. gemessen werden. Wenn wir uns an den Zyklus Sense/Think/Act erinnern, können wir uns vorstellen, dass der Teil Think die Geschwindigkeit auswählt und der Teil Act diese Geschwindigkeit auf den Agenten anwendet. In Spielen gibt es normalerweise ein physikalisches System, das diese Aufgabe für Sie übernimmt, indem es den Geschwindigkeitswert jedes Objekts berücksichtigt und anpasst. Daher kann die KI mit der Aufgabe betraut werden, zu entscheiden, welche Geschwindigkeit der Agent haben sollte. Wenn bekannt ist, wo sich der Agent befinden soll, kann er in die richtige Richtung mit einer festgelegten Geschwindigkeit bewegt werden. Eine sehr triviale Gleichung:

desired_travel = ziel_position – agent_position

Stellen Sie sich eine 2D-Welt vor. Der Agent befindet sich an Punkt (-2,-2), das Ziel irgendwo nordöstlich an Punkt (30, 20), und der notwendige Weg für den Agenten, um dort zu sein, ist (32, 22). Angenommen, diese Positionen werden in Metern gemessen – wenn wir die Geschwindigkeit des Agenten auf 5 Meter pro Sekunde ansetzen, dann skalieren wir unseren Bewegungsvektor und erhalten eine Geschwindigkeit von etwa (4,12, 2,83). Mit diesen Parametern würde der Agent sein Ziel in fast 8 Sekunden erreichen.

Die Werte können jederzeit neu berechnet werden. Wenn der Agent auf halbem Weg zum Ziel war, wäre die Bewegung die Hälfte der Länge, aber da die maximale Geschwindigkeit des Agenten 5 m/s beträgt (das haben wir oben festgelegt), bleibt die Geschwindigkeit gleich. Das funktioniert auch für sich bewegende Ziele, sodass der Agent kleine Anpassungen vornehmen kann, während diese sich bewegen.

Aber wir möchten mehr Variabilität – zum Beispiel die Geschwindigkeit langsam erhöhen, um einen Charakter zu simulieren, der sich aus einer stehenden Position in einen Lauf bewegt. Das Gleiche kann auch am Ende vor dem Anhalten gemacht werden. Diese Funktionen sind bekannt als Steering Behaviours, von denen jede spezifische Namen hat: Seek (Suchen), Flee (Fliehen), Arrival (Ankunft) usw. Die Idee ist, dass Beschleunigungskräfte auf die Geschwindigkeit des Agenten angewendet werden können, basierend auf dem Vergleich der Position des Agenten und der aktuellen Geschwindigkeit mit dem Ziel, um verschiedene Methoden zur Bewegung in Richtung des Ziels zu nutzen.

Jedes Verhalten hat ein etwas anderes Ziel. Seek und Arrival sind Methoden, um den Agenten zu einem Zielpunkt zu bewegen. Obstacle Avoidance (Hindernisvermeidung) und Separation (Trennung) korrigieren die Bewegung des Agenten, um Hindernisse auf dem Weg zum Ziel zu umgehen. Alignment (Ausrichtung) und Cohesion (Zusammenhalt) halten die Agenten während der Bewegung zusammen. Eine beliebige Anzahl verschiedener Steering Behaviours kann summiert werden, um einen einzigen Bewegungsvektor unter Berücksichtigung aller Faktoren zu erhalten. Ein Agent verwendet die Verhaltensweisen Arrival, Separation und Obstacle Avoidance, um Abstand zu Wänden und anderen Agenten zu halten. Dieser Ansatz funktioniert gut in offenen Locations ohne überflüssige Details.

In schwierigeren Bedingungen funktioniert das Addieren verschiedener Verhaltensweisen schlechter – zum Beispiel kann ein Agent an einer Wand stecken bleiben aufgrund eines Konflikts zwischen Arrival und Obstacle Avoidance. Daher müssen komplexere Optionen als nur das Addieren aller Werte in Betracht gezogen werden. Eine Möglichkeit ist, anstatt die Ergebnisse jedes Verhaltens zu addieren, die Bewegung in verschiedene Richtungen zu betrachten und die beste Option auszuwählen.

In einer komplexen Umgebung mit Sackgassen und Entscheidungen über die Richtung, in die man gehen soll, benötigen wir jedoch etwas noch Fortgeschrittenes.

Wegsuche

Steering Behaviours eignen sich hervorragend für einfache Bewegungen in offenem Gelände (Fußballfeld oder Arena), wo es von A nach B in gerader Linie mit geringfügigen Abweichungen um Hindernisse geht. Für komplexe Routen benötigen wir Pathfinding, das eine Methode ist, die Welt zu erkunden und eine Route durch sie zu bestimmen.

Die einfachste Methode besteht darin, ein Raster über jedes Quadrat neben dem Agenten zu legen und zu bewerten, in welchen er sich bewegen darf. Wenn eines davon das Ziel ist, folgen Sie ihm, indem Sie von jedem Quadrat zu dem vorhergehenden zurückverfolgen, bis Sie den Anfang erreichen. Das ist der Weg. Andernfalls wiederholen Sie den Vorgang mit den nächstgelegenen anderen Quadraten, bis Sie das Ziel finden oder alle Quadrate aufgebraucht sind (was bedeutet, dass kein möglicher Weg besteht). Dies wird formal als Breadth-First Search oder BFS (Breitensuche) bezeichnet. Bei jedem Schritt schaut es in alle Richtungen (deshalb

In der Folge erhalten Sie eine Liste von Quadraten, aus denen die benötigte Route besteht. Das ist der Pfad (von hier, pathfinding) - eine Liste der Orte, die der Agent besuchen wird, um zum Ziel zu gelangen.

Angesichts dessen, dass wir die Position jedes Quadrats in der Welt kennen, können wir Steering-Bewegungen verwenden, um dem Pfad zu folgen - von Knoten 1 zu Knoten 2, dann von Knoten 2 zu Knoten 3 und so weiter. Die einfachste Variante besteht darin, zum Zentrum des nächsten Quadrats zu steuern, aber noch besser wäre es, an der Mitte der Kante zwischen dem aktuellen Quadrat und dem nächsten zu halten. Dadurch kann der Agent an scharfen Kurven die Ecken schneiden.

Der BFS-Algorithmus hat auch Nachteile - er untersucht genauso viele Quadrate in die "falsche" Richtung wie in die "richtige". Hier kommt ein komplexerer Algorithmus namens A* (A Stern) ins Spiel. Er funktioniert ähnlich, aber anstatt blind die benachbarten Quadrate zu durchsuchen (dann die Nachbarn der Nachbarn, dann die Nachbarn der Nachbarn der Nachbarn und so weiter), sammelt er die Knoten in einer Liste und sortiert sie so, dass der nächste untersuchte Knoten immer der ist, der den kürzesten Weg führt. Die Knoten werden basierend auf einer Heuristik sortiert, die zwei Dinge berücksichtigt: die „Kosten“ des hypothetischen Pfades zum gewünschten Quadrat (einschließlich aller Bewegungs- und Reisekosten) und eine Schätzung, wie weit dieses Quadrat vom Ziel entfernt ist (was die Suche in die richtige Richtung lenkt).

In diesem Beispiel wird gezeigt, dass der Agent jeweils ein Quadrat erkundet und dabei immer das am vielversprechendsten erscheinende Nachbarquadrat auswählt. Der resultierende Pfad ist derselbe wie bei BFS, aber es wurden weniger Quadrate betrachtet – was für die Leistung des Spiels von großer Bedeutung ist.

Bewegung ohne Raster

Aber die meisten Spiele sind nicht im Raster angeordnet, und oft ist es nicht möglich, dies ohne Einbußen an der Realitätsnähe zu tun. Es sind Kompromisse erforderlich. Wie groß sollten die Quadrate sein? Zu groß – und sie können enge Korridore oder Kurven nicht richtig darstellen, zu klein – es gibt zu viele Quadrate, die durchsucht werden müssen, was viel Zeit in Anspruch nehmen kann.

Das erste, was man verstehen sollte, ist, dass ein Raster uns einen Graphen verbundener Knoten liefert. Die Algorithmen A* und BFS arbeiten tatsächlich mit Graphen und kümmern sich überhaupt nicht um unser Raster. Wir könnten Knoten an beliebigen Stellen der Spielwelt setzen: Solange eine Verbindung zwischen zwei verbundenen Knoten und auch zwischen dem Start- und dem Endpunkt sowie mindestens einem der Knoten besteht, funktioniert der Algorithmus genauso gut wie zuvor. Oft wird dies als Wegpunkt-System bezeichnet, da jeder Knoten eine signifikante Position in der Welt darstellt, die Teil beliebig vieler hypothetischer Wege sein kann.

Beispiel 1: Ein Knoten in jedem Quadrat. Die Suche beginnt aus dem Knoten, in dem sich der Agent befindet, und endet im Knoten des gewünschten Quadrats.

Beispiel 2: Ein kleinerer Satz von Knoten (Wegpunkten). Die Suche beginnt im Quadrat mit dem Agenten, verläuft über die erforderliche Anzahl von Knoten und setzt sich dann bis zum Ziel fort.

Dies ist ein recht flexibles und leistungsfähiges System. Aber es ist Vorsicht geboten, wo und wie Wegpunkte platziert werden, sonst sehen die Agenten möglicherweise einfach den nächstgelegenen Punkt nicht und können ihren Weg nicht beginnen. Es wäre einfacher, wenn wir Wegpunkte automatisch basierend auf der Geometrie der Welt platzieren könnten.

Hier kommt das Navigation Mesh oder Navmesh ins Spiel. Dies ist normalerweise ein 2D-Netzwerk von Dreiecken, das auf die Geometrie der Welt gelegt wird – überall dort, wo es dem Agenten erlaubt ist zu gehen. Jedes der Dreiecke im Netz wird zu einem Knoten im Graphen und hat bis zu drei benachbarte Dreiecke, die zu benachbarten Knoten im Graphen werden.

Dieses Bild ist ein Beispiel aus der Unity-Engine – es hat die Geometrie der Welt analysiert und ein Navmesh erstellt (auf dem Screenshot in hellblau dargestellt). Jedes Polygon im Navmesh ist ein Bereich, auf dem ein Agent stehen oder von einem Polygon zum anderen bewegen kann. In diesem Beispiel sind die Polygone kleiner als die Etagen, auf denen sie sich befinden – dies wurde gemacht, um die Größe des Agents zu berücksichtigen, der über seine nominelle Position hinausgehen kann.

Wir können den Weg durch dieses Netz suchen, indem wir erneut den A*-Algorithmus verwenden. Dies wird uns einen nahezu perfekten Weg in der Welt bieten, der die gesamte Geometrie berücksichtigt und dabei keine überflüssigen Knoten und Wegpunkte benötigt.

Pathfinding ist ein zu umfangreiches Thema, um nur einen Abschnitt eines Artikels darüber zu haben. Wenn Sie es detaillierter studieren möchten, finden Sie Hilfe auf der Webseite von Amit Patel.

Planung

Wir haben bei Pathfinding festgestellt, dass es manchmal nicht ausreicht, einfach eine Richtung zu wählen und zu gehen – wir müssen einen Weg wählen und mehrere Abzweigungen machen, um das gewünschte Ziel zu erreichen. Wir können diese Idee zusammenfassen: Das Erreichen eines Ziels ist nicht nur der nächste Schritt, sondern eine ganze Abfolge, bei der es manchmal erforderlich ist, einige Schritte vorausschauen, um herauszufinden, wie der erste Schritt aussehen sollte. Dies wird als Planung bezeichnet. Pathfinding kann als eine von mehreren Ergänzungen zur Planung angesehen werden. Aus der Sicht unseres Sense/Think/Act-Zyklus ist es der Teil, in dem das Denken mehrere Teile des Handelns für die Zukunft plant.

Nehmen wir als Beispiel das Kartenspiel Magic: The Gathering. Wir ziehen zuerst mit diesem Kartensatz auf der Hand:

• Sumpf – gibt 1 schwarze Mana (Landkarte).
• Wald – gibt 1 grüne Mana (Landkarte).
• Flüchtiger Zauberer – benötigt 1 blaue Mana zum Beschwören.
• Elfen-Mystiker – benötigt 1 grüne Mana zum Beschwören.

Die verbleibenden drei Karten ignorieren wir, um es einfacher zu machen. Nach den Regeln darf der Spieler 1 Landkarte pro Zug spielen, er kann diese Karte „tap“ (um Mana daraus zu ziehen), und anschließend die Zauber (einschließlich der Beschwörung von Kreaturen) entsprechend der verfügbaren Mana verwenden. In dieser Situation weiß der menschliche Spieler, dass er den Wald spielen, 1 grüne Mana „tap“ und dann den Elfen-Mystiker beschwören muss. Aber wie kann der Spiel-IA das herausfinden?

Einfache Planung

Der triviale Ansatz besteht darin, jede Handlung der Reihe nach auszuprobieren, bis keine passenden mehr übrig sind. Der KI sieht anhand der Karten, dass sie Swamp spielen kann. Und sie spielt es. Gibt es noch andere Handlungen in diesem Zug? Sie kann weder Elvish Mystic noch Fugitive Wizard beschwören, da für deren Beschwörung jeweils grüne und blaue Mana erforderlich sind, während Swamp nur schwarze Mana erzeugt. Und sie kann bereits keinen Forest mehr spielen, weil sie Swamp bereits gespielt hat. So hat die spielende KI gemäß den Regeln gehandelt, aber schlecht. Dieses Vorgehen kann verbessert werden.

Die Planung kann eine Liste von Handlungen finden, die das Spiel in den gewünschten Zustand versetzen. So wie jede Quadrate auf dem Weg Nachbarn hatte (im Pathfinding), hat jede Handlung im Plan ebenfalls Nachbarn oder Nachfolger. Wir können diese Handlungen und die nächsten Handlungen suchen, bis wir den gewünschten Zustand erreichen.

In unserem Beispiel ist das gewünschte Ergebnis „ein Wesen beschwören, wenn dies möglich ist“. Zu Beginn des Zugs sehen wir nur zwei mögliche Handlungen, die den Regeln des Spiels entsprechen:

1. Swamp spielen (Ergebnis: Swamp im Spiel)
2. Forest spielen (Ergebnis: Forest im Spiel)

Jede ausgeführte Handlung kann zu weiteren Handlungen führen und andere schließen, wiederum abhängig von den Regeln des Spiels. Stellen Sie sich vor, wir haben Swamp gespielt – dies entfernt Swamp als nächsten Schritt (wir haben es bereits gespielt), außerdem entfernt es Forest (da gemäß den Regeln in einem Zug nur eine Länderkarte gespielt werden kann). Danach fügt die KI als nächsten Schritt das Erhalten von 1 schwarzer Mana hinzu, da es keine anderen Optionen gibt. Wenn sie weitermachen und Swamp tappen wählt, erhält sie 1 Einheit schwarze Mana und kann damit nichts tun.

1. Swamp spielen (Ergebnis: Swamp im Spiel)
1.1 Swamp „tappt“ (Ergebnis: Swamp „getappt“, +1 Einheit schwarze Mana)
Keine verfügbaren Handlungen – ENDE
2. Forest spielen (Ergebnis: Forest im Spiel)

Die Liste der Handlungen ist kurz geworden, wir sind an einem toten Punkt angekommen. Wir wiederholen den Prozess für die nächste Handlung. Wir spielen Forest, öffnen die Handlung „1 grüne Mana erhalten“, die ihrerseits die dritte Handlung – das Beschwören von Elvish Mystic – eröffnet.

1. Swamp spielen (Ergebnis: Swamp im Spiel)
1.1 Swamp „tappt“ (Ergebnis: Swamp „getappt“, +1 Einheit schwarze Mana)
Keine verfügbaren Handlungen – ENDE
2. Forest spielen (Ergebnis: Forest im Spiel)
2.1 Forest „tappt“ (Ergebnis: Forest „getappt“, +1 Einheit grüne Mana)
2.1.1 Elvish Mystic beschwören (Ergebnis: Elvish Mystic im Spiel, -1 Einheit grüne Mana)
Keine verfügbaren Handlungen – ENDE

Schließlich haben wir alle möglichen Handlungen untersucht und einen Plan gefunden, der ein Wesen beschwört.

Dies ist ein sehr vereinfachtes Beispiel. Es ist ratsam, den bestmöglichen Plan zu wählen und nicht einfach irgendetwas, das bestimmten Kriterien entspricht. Oft kann man potenzielle Pläne anhand des Endergebnisses oder des Gesamtnutzens ihrer Ausführung bewerten. Man kann sich 1 Punkt für das Spielen einer Landkarte und 3 Punkte für das Beschwören eines Wesens gutschreiben. Das Spielen von Swamp wäre ein Plan, der 1 Punkt einbringt. Und das Spielen von Forest → Tap the Forest → beschwören von Elvish Mystic – bringt sofort 4 Punkte.

So funktioniert das Planen in Magic: The Gathering, aber dasselbe Prinzip lässt sich auch auf andere Situationen anwenden. Zum Beispiel, einen Bauern zu bewegen, um Platz für den Zug eines Läufers im Schach zu schaffen. Oder sich hinter einer Wand zu verstecken, um in XCOM sicher zu schießen. Im Grunde versteht ihr das Wesentliche.

Verbessertes Planen

Manchmal gibt es zu viele potenzielle Aktionen, um jede mögliche Option zu betrachten. Zurück zum Beispiel mit Magic: The Gathering: Angenommen, im Spiel hast du mehrere Landkarten und Kreaturen auf der Hand – die Anzahl möglicher Spielkombinationen kann in die Dutzende gehen. Es gibt mehrere Lösungsansätze für dieses Problem.

Der erste Ansatz ist das Backwards Chaining (Rückwärtsverknüpfung). Anstatt alle Kombinationen durchzugehen, ist es besser, mit dem Endergebnis zu beginnen und zu versuchen, einen direkten Pfad zu finden. Anstatt den Weg von der Wurzel eines Baumes zu einem bestimmten Blatt zu verfolgen, bewegen wir uns in umgekehrter Richtung – vom Blatt zur Wurzel. Diese Methode ist einfacher und schneller.

Wenn der Gegner 1 Lebenspunkt hat, kann man einen Plan finden, um „1 oder mehr Schadenspunkte zuzufügen“. Um dies zu erreichen, müssen einige Bedingungen erfüllt sein:

1. Der Schaden kann durch einen Zauberspruch verursacht werden – dieser muss auf der Hand sein.
2. Um einen Zauberspruch zu wirken – braucht man Mana.
3. Um Mana zu erhalten – muss man eine Landkarte ausspielen.
4. Um eine Landkarte auszuspielen – muss man sie auf der Hand haben.

Eine andere Methode ist der Best-First Search (Besten-Erstsuche). Anstatt alle Wege zu durchforsten, wählen wir den vielversprechendsten aus. Diese Methode liefert in der Regel den optimalen Plan ohne unnötige Suchkosten. A* ist eine Form des Besten-Erstsuchens – indem er vielversprechende Routen von Anfang an erforscht, kann er den besten Weg finden, ohne andere Optionen überprüfen zu müssen.

Eine interessante und zunehmend beliebte Variante der besten ersten Suche ist die Monte Carlo Tree Search. Anstatt zu erraten, welche Pläne besser sind als andere, wählt der Algorithmus bei jedem Schritt zufällige Nachfolger, bis er das Ende erreicht (wenn der Plan zu einem Sieg oder einer Niederlage führt). Das endgültige Ergebnis wird dann verwendet, um die Bewertung des „Gewichts“ der vorherigen Optionen zu erhöhen oder zu senken. Durch mehrmaliges Wiederholen dieses Prozesses gibt der Algorithmus eine gute Einschätzung ab, welcher nächste Schritt besser ist, selbst wenn sich die Situation ändert (wenn der Gegner Maßnahmen ergreift, um den Spieler zu behindern).

In der Erzählung über Planung in Spielen kommt man nicht ohne Goal-Oriented Action Planning oder GOAP (zielorientierte Aktionsplanung) aus. Dies ist eine weit verbreitete und diskutierte Methode, aber abgesehen von einigen unterscheidenden Details handelt es sich im Wesentlichen um eine Methode des rückwärts gerichteten Denkens, die wir zuvor erwähnt haben. Wenn die Aufgabe lautet „den Spieler eliminieren“ und der Spieler sich hinter einer Deckung befindet, könnte der Plan so aussehen: zerstöre mit einer Granate → hole sie → wirf sie.

Normalerweise gibt es mehrere Ziele, jedes mit seiner eigenen Priorität. Wenn das Ziel mit der höchsten Priorität nicht erreicht werden kann (da keine Kombination von Aktionen einen Plan „den Spieler eliminieren“ erstellt, weil der Spieler nicht sichtbar ist), kehrt die KI zu den Zielen mit niedrigerer Priorität zurück.

Training und Anpassung

Wir haben bereits erwähnt, dass KI in Spielen normalerweise kein maschinelles Lernen verwendet, da es nicht geeignet ist, um Agenten in Echtzeit zu steuern. Aber das bedeutet nicht, dass man aus diesem Bereich nichts lernen kann. Wir wünschen uns einen Gegner in einem Shooter, von dem man etwas lernen kann. Zum Beispiel über die besten Positionen auf der Karte. Oder einen Gegner in einem Kampfspiel, der häufig verwendete Kombinationen des Spielers blockieren würde, was dazu anregt, andere zu verwenden. Maschinelles Lernen kann in solchen Situationen also sehr nützlich sein.

Statistik und Wahrscheinlichkeiten

Bevor wir zu komplexen Beispielen übergehen, lassen Sie uns überlegen, wie weit wir gehen können, indem wir einige einfache Messungen vornehmen und diese zur Entscheidungsfindung nutzen. Zum Beispiel, die Echtzeit-Strategie – wie können wir feststellen, ob ein Spieler in den ersten Minuten des Spiels einen Angriff starten kann und welche Verteidigung wir dagegen aufbauen sollten? Wir können die bisherigen Erfahrungen des Spielers analysieren, um zu verstehen, wie seine zukünftige Reaktion aussehen könnte. Zunächst einmal haben wir keine solchen Ausgangsdaten, aber wir können sie sammeln – jedes Mal, wenn die KI gegen einen Menschen spielt, kann sie die Zeit des ersten Angriffs aufzeichnen. Nach mehreren Sitzungen erhalten wir den Durchschnittswert der Zeit, nach der der Spieler in der Zukunft angreifen wird.

Es gibt jedoch auch ein Problem mit Durchschnittswerten: Wenn ein Spieler 20 Mal „rushte“ und 20 Mal langsam spielte, dann werden die benötigten Werte irgendwo in der Mitte liegen, was uns nichts Nützliches bringt. Eine mögliche Lösung besteht darin, die Eingangsdaten zu begrenzen – wir können die letzten 20 Angriffe berücksichtigen.

Ein ähnlicher Ansatz wird verwendet, um die Wahrscheinlichkeit bestimmter Aktionen abzuschätzen, wobei davon ausgegangen wird, dass die früheren Vorlieben des Spielers auch in Zukunft bestehen bleiben. Wenn ein Spieler uns fünf Mal mit Feuerbällen angreift, zwei Mal mit Blitz und ein Mal im Nahkampf, ist offensichtlich, dass er Feuerbälle bevorzugt. Wir extrapolieren und sehen die Wahrscheinlichkeit, verschiedene Waffen zu verwenden: Feuerball = 62,5 %, Blitz = 25 % und Nahkampf = 12,5 %. Unsere Spiel-KI muss sich auf den Schutz gegen Feuer vorbereiten.

Eine weitere interessante Methode ist die Verwendung des Naive Bayes Classifier, um große Mengen an Eingabedaten zu analysieren und die Situation zu klassifizieren, damit die KI entsprechend reagiert. Bayes-Klassifikatoren sind am bekanntesten für ihren Einsatz in Spamfiltern für E-Mails. Dort untersuchen sie Wörter, vergleichen sie mit ihren vorherigen Vorkommen (ob in Spam oder nicht) und ziehen Schlüsse über eingehende Nachrichten. Wir können dasselbe tun, sogar mit weniger Eingabedaten. Basierend auf allen nützlichen Informationen, die die KI sieht (z. B. welche feindlichen Einheiten erstellt wurden, welche Zauber sie einsetzen oder welche Technologien sie erforschen), und dem endgültigen Ergebnis (Krieg oder Frieden, „rushen“ oder verteidigen usw.) – wählen wir das angemessene Verhalten der KI aus.

Alle diese Lernmethoden sind ausreichend, aber es ist ratsam, sie auf Basis von Testergebnissen zu verwenden. KI wird lernen, sich an die verschiedenen Strategien anzupassen, die Ihre Playtester verwendet haben. Eine KI, die sich nach dem Release an den Spieler anpasst, kann zu vorhersehbar oder umgekehrt zu schwierig zu besiegen werden.

Anpassung basierend auf Werten

Angesichts des Inhalts unserer Spielwelt und der Regeln können wir die Menge der Werte ändern, die die Entscheidungsfindung beeinflussen, anstatt nur die Eingabedaten zu verwenden. So machen wir das:

• Lassen Sie die KI Daten über den Zustand der Welt und wichtige Ereignisse während des Spiels sammeln (wie oben angegeben).
• Wir werden einige wichtige Werte (value) basierend auf diesen Daten ändern.
• Wir setzen unsere Entscheidungen um, die auf der Verarbeitung oder Bewertung dieser Werte basieren.

Zum Beispiel hat der Agent mehrere Räume zur Auswahl auf der Karte eines Ego-Shooters. Jeder Raum hat seinen eigenen Wert, der bestimmt, wie wünschenswert er für einen Besuch ist. Die KI wählt zufällig, in welchen Raum sie gehen soll, basierend auf dem Wert. Der Agent merkt sich dann, in welchem Raum er getötet wurde, und reduziert dessen Wert (die Wahrscheinlichkeit, dass er zurückkommt). Analog für die umgekehrte Situation – wenn der Agent viele Gegner vernichtet, steigt der Wert des Raums.

Markov-Modell

Was, wenn wir die gesammelten Daten zur Vorhersage verwenden? Wenn wir uns an jeden Raum erinnern, in dem wir den Spieler über einen bestimmten Zeitraum gesehen haben, können wir vorhersagen, in welchen Raum der Spieler wechseln könnte. Indem wir die Bewegungen des Spielers durch die Räume (values) verfolgen und aufzeichnen, können wir diese vorhersagen.

Nehmen wir drei Räume: rot, grün und blau. Und die Beobachtungen, die wir während der Betrachtung der Spielsitzung aufgezeichnet haben:

Die Anzahl der Beobachtungen für jeden Raum ist nahezu gleich – wo wir einen guten Platz für einen Hinterhalt schaffen können, wissen wir immer noch nicht. Die Sammlung von Statistiken wird auch durch das Respawning der Spieler erschwert, die gleichmäßig auf der gesamten Karte erscheinen. Aber die Daten über den nächsten Raum, in den sie nach ihrem Erscheinen auf der Karte eintreten – sind bereits hilfreich.

Es ist offensichtlich, dass der grüne Raum die Spieler ansprechend findet – die Mehrheit der Leute wandert von rot dorthin, wobei 50 % von ihnen dort verweilen. Der blaue Raum hingegen erfreut sich keiner Beliebtheit, dort gehen fast keine Leute hin, und wenn sie es tun, verweilen sie nicht.

Doch die Daten zeigen uns etwas Wichtigeres – wenn sich ein Spieler im blauen Raum aufhält, wird der nächste Raum, in dem wir ihn wahrscheinlich sehen, der rote und nicht der grüne sein. Trotz der Tatsache, dass der grüne Raum beliebter ist als der rote, ändert sich die Situation, wenn der Spieler im blauen Raum ist. Der nächste Zustand (also der Raum, in den der Spieler wechselt) hängt vom vorherigen Zustand (also dem Raum, in dem sich der Spieler derzeit befindet) ab. Aufgrund der Abhängigkeitsanalysen werden wir genauere Prognosen machen, als wenn wir einfach die Beobachtungen unabhängig voneinander zählen würden.

Die Vorhersage des zukünftigen Zustands basierend auf Daten des vergangenen Zustands wird als Markov-Modell bezeichnet, und solche Beispiele (mit Räumen) werden Markov-Ketten genannt. Da diese Modelle die Wahrscheinlichkeit von Änderungen zwischen aufeinanderfolgenden Zuständen darstellen, werden sie visuell in Form eines FSM mit Wahrscheinlichkeiten um jeden Übergang dargestellt. Früher haben wir FSM verwendet, um den Verhaltenszustand darzustellen, in dem sich der Agent befand, aber dieses Konzept erstreckt sich auf jeden Zustand, unabhängig davon, ob er mit dem Agenten in Verbindung steht oder nicht. In diesem Fall stellen die Zustände den Raum dar, den der Agent besetzt:

Dies ist eine einfache Möglichkeit, die relative Wahrscheinlichkeit von Zustandsänderungen darzustellen, die es der KI ermöglicht, das nächste Zustand zu prognostizieren. Man kann mehrere Schritte im Voraus vorhersagen.

Wenn sich der Spieler im grünen Raum befindet, besteht eine 50 %ige Chance, dass er beim nächsten Beobachtung dort bleibt. Aber wie hoch ist die Wahrscheinlichkeit, dass er auch danach noch dort ist? Es gibt nicht nur die Chance, dass der Spieler nach zwei Beobachtungen im grünen Raum geblieben ist, sondern auch die Möglichkeit, dass er weggegangen und zurückgekehrt ist. Hier ist eine neue Tabelle unter Berücksichtigung der neuen Daten:

Hieraus ergibt sich, dass die Chance, den Spieler nach zwei Beobachtungen im grünen Raum zu sehen, bei 51 % liegt – 21 %, dass er aus dem roten Raum kommt, 5 %, dass der Spieler dazwischen den blauen Raum besucht hat, und 25 %, dass der Spieler den grünen Raum überhaupt nicht verlassen hat.

Eine Tabelle ist ein einfaches visuelles Werkzeug – das Verfahren erfordert nur die Multiplikation von Wahrscheinlichkeiten in jedem Schritt. Das bedeutet, dass Sie weit in die Zukunft schauen können, mit einer Ausnahme: Wir nehmen an, dass die Chance, den Raum zu betreten, vollständig von dem aktuellen Raum abhängt. Dies wird als Markowsches Eigentum (Markov Property) bezeichnet – der zukünftige Zustand hängt nur vom aktuellen ab. Aber das ist nicht hundertprozentig genau. Spieler können Entscheidungen je nach anderen Faktoren ändern: Gesundheitszustand oder Anzahl der Munition. Da wir diese Werte nicht festhalten, werden unsere Prognosen weniger genau sein.

N-Gramme

Was ist mit dem Beispiel eines Kampfspiels und der Vorhersage von Kombinationszügen des Spielers? Dasselbe! Statt eines einzelnen Zustands oder Ereignisses untersuchen wir ganze Sequenzen, aus denen der Kombinationsangriff besteht.

Eine Möglichkeit, dies zu tun, besteht darin, jede Eingabe (wie Kick, Punch oder Block) im Puffer zu speichern und den gesamten Puffer als ein Ereignis aufzuzeichnen. Der Spieler drückt also wiederholt Kick, Kick, Punch, um den SuperDeathFist-Angriff auszuführen. Das KI-System speichert alle Eingaben im Puffer und merkt sich die letzten drei, die in jedem Schritt verwendet werden.

(Die Zeilen sind fett hervorgehoben, wenn der Spieler den SuperDeathFist-Angriff ausführt.)

Die KI wird alle Varianten sehen, bei denen der Spieler Kick gewählt hat, gefolgt von einem weiteren Kick, und dann bemerken, dass die nächste Eingabe immer Punch ist. Dies ermöglicht es dem Agenten, den SuperDeathFist-Kombinationsangriff vorherzusagen und ihn zu blockieren, wenn möglich.

Diese Ereignisse werden als N-Gramme (N-grams) bezeichnet, wobei N die Anzahl der gespeicherten Elemente ist. Im vorherigen Beispiel handelte es sich um ein 3-Gramm (Trigramm), was bedeutet: Die ersten beiden Einträge werden verwendet, um den dritten vorherzusagen. Entsprechend sagen in einem 5-Gramm die ersten vier Einträge den fünften vor und so weiter.

Der Entwickler muss die Größe der N-Gramme sorgfältig auswählen. Eine kleinere Zahl von N benötigt weniger Speicher, speichert jedoch auch eine kürzere Geschichte. Zum Beispiel wird ein 2-Gramm (Bigramm) Kick, Kick oder Kick, Punch aufzeichnen, kann jedoch Kick, Kick, Punch nicht speichern, sodass die KI nicht auf den SuperDeathFist-Kombinationsangriff reagieren wird.

Andererseits benötigen große Zahlen mehr Speicher und es wird für die KI schwieriger, zu lernen, da es viel mehr mögliche Varianten gibt. Wenn Sie drei mögliche Eingaben wie Kick, Punch oder Block hatten und wir ein 10-Gramm verwendet haben, ergeben sich etwa 60.000 verschiedene Varianten.

Das Bigram-Modell ist eine einfache Markow-Kette – jedes Paar „vorheriger Zustand / aktueller Zustand“ ist ein Bigramm, und Sie können den zweiten Zustand anhand des ersten vorhersagen. Trigramme und größere N-Gramme können ebenfalls als Markow-Ketten betrachtet werden, wobei alle Elemente (außer dem letzten im N-Gramm) zusammen den ersten Zustand bilden und das letzte Element den zweiten. Ein Beispiel aus dem Kampfspiel zeigt die Wahrscheinlichkeit des Übergangs vom Zustand Kick und Kick zu den Zuständen Kick und Punch. Wenn wir mehrere Aufzeichnungen der Eingangsvergangenheit als eine Einheit betrachten, verwandeln wir im Wesentlichen die Eingabesequenz in einen Teil des gesamten Zustands. Dies gibt uns die Markow-Eigenschaft, die es ermöglicht, Markow-Ketten zur Vorhersage der nächsten Eingabe zu verwenden und zu erraten, welcher Kombinationszug als nächstes kommt.

Fazit

Wir haben über die gängigsten Werkzeuge und Ansätze in der Entwicklung künstlicher Intelligenz gesprochen. Außerdem haben wir die Situationen untersucht, in denen sie angewendet werden sollten und wo sie besonders nützlich sind.

Das sollte ausreichen, um die Grundlagen im Gaming-AI zu verstehen. Aber natürlich ist das bei weitem nicht alles. Zu den weniger verbreiteten, aber nicht weniger effektiven Methoden gehören:

• Optimierungsalgorithmen, einschließlich Hill Climbing, Gradientenabstieg und genetische Algorithmen
• Wettbewerbsalgorithmen für Suche / Planung (Minimax und Alpha-Beta-Pruning)
• Klassifikationsmethoden (Perzeptronen, neuronale Netze und Support Vector Machines)
• Systeme zur Verarbeitung von Wahrnehmung und Gedächtnis von Agenten
• Architektonische Ansätze für KI (hybride Systeme, Untergruppen von Architekturen und andere Möglichkeiten zur Überlappung von KI-Systemen)
• Animationswerkzeuge (Planung und Koordination von Bewegungen)
• Leistungsfaktoren (Detailgrad, Anytime-Algorithmen und Timeslicing)

Internetressourcen zum Thema:

1. Auf GameDev.net gibt es einen Bereich mit Artikeln und Tutorials zu KI, sowie Forum.
2. AiGameDev.com enthält eine Vielzahl von Präsentationen und Artikeln zu einem breiten Spektrum im Bereich der Entwicklung von Gaming-AI.
3. Das GDC Vault beinhaltet Themen vom GDC AI Summit, von denen viele kostenlos verfügbar sind.
4. Nützliche Materialien finden Sie auch auf der Website AI Game Programmers Guild.
5. Tommy Thompson, KI-Forscher und Spieleentwickler, veröffentlicht Videos auf dem YouTube-Kanal AI and Games mit Erklärungen und Analysen von KI in kommerziellen Spielen.

Bücher zu diesem Thema:

1. Die Buchreihe Game AI Pro besteht aus Sammlungen kurzer Artikel, die erklären, wie bestimmte Funktionen implementiert oder spezifische Probleme gelöst werden können.

Game AI Pro: Gesammelte Weisheit von Game AI-Experten
Game AI Pro 2: Gesammelte Weisheit von Game AI-Experten
Game AI Pro 3: Gesammelte Weisheit von Game AI-Experten

2. Die Reihe AI Game Programming Wisdom ist der Vorgänger der Reihe Game AI Pro. Sie enthält ältere Methoden, aber fast alle sind auch heute noch relevant.

AI Game Programming Wisdom 1
AI Game Programming Wisdom 2
AI Game Programming Wisdom 3
AI Game Programming Wisdom 4

3. Artificial Intelligence: A Modern Approach — ist einer der Grundlagenliteraturen für alle, die sich mit dem allgemeinen Bereich der künstlichen Intelligenz vertraut machen möchten. Dieses Buch handelt nicht von der Spieleentwicklung – es lehrt die grundlegenden Grundlagen der KI.

Quelle: habr.com