Wie man KI für Spiele erstellt: Ein Leitfaden für Anfänger

Ich bin auf ein interessantes Material über künstliche Intelligenz in Spielen gestoßen. Es erklärt die Grundlagen der KI mit einfachen Beispielen und enthält viele nützliche Werkzeuge und Methoden für eine komfortable Entwicklung und Gestaltung. Auch wie, wo und wann man sie einsetzen kann, wird behandelt.

Die meisten Beispiele sind in Pseudocode verfasst, daher sind keine tiefen Programmierkenntnisse erforderlich. Im Anhang finden sich 35 Seiten Text mit Bildern und GIFs, also bereiten Sie sich vor.

UPD. Ich entschuldige mich, aber ich habe diese Artikelübersetzung bereits auf Habrahabr gemacht PatientZero. Seinen Beitrag kann man lesen hier, aber irgendwie ist der Artikel an mir vorbeigegangen (ich habe die Suche genutzt, aber irgendetwas lief schief). Da ich in einem Blog schreibe, der sich dem Game Development widmet, wollte ich meine Übersetzung für die Abonnenten teilen (einige Punkte habe ich anders formuliert, andere absichtlich nach Rücksprache mit den Entwicklern weggelassen).

Was ist KI?

Die Gaming-KI konzentriert sich darauf, welche Aktionen ein Objekt in Abhängigkeit von den gegebenen Bedingungen ausführen sollte. Häufig wird dies als das Management von "intelligenten Agenten" bezeichnet, wobei ein Agent ein Spielcharakter, ein Fahrzeug, ein Bot oder manchmal etwas Abstrakteres sein kann: eine gesamte Gruppe von Entitäten oder sogar eine Zivilisation. In jedem Fall ist es etwas, das seine Umgebung wahrnehmen, darauf basierende Entscheidungen treffen und entsprechend handeln muss. Dies wird als der Zyklus Sense/Think/Act (Wahrnehmen/Denken/Handeln) bezeichnet:

• Wahrnehmen: Der Agent findet oder erhält Informationen über Dinge in seiner Umgebung, die sein Verhalten beeinflussen könnten (nahe Bedrohungen, Sammlungsobjekte, interessante Orte zur Erkundung).
• Denken: Der Agent entscheidet, wie er reagieren soll (er prüft, ob es sicher genug ist, um Objekte zu sammeln, oder ob er zunächst kämpfen oder sich verstecken sollte).
• Handeln: Der Agent führt Aktionen durch, um die vorherige Entscheidung umzusetzen (er beginnt, sich dem Gegner oder dem Objekt zuzubewegen).
• …nun hat sich die Situation geändert aufgrund der Aktionen der Charaktere, daher wird der Zyklus mit neuen Daten wiederholt.

KI konzentriert sich in der Regel auf den Sinn-Teil des Zyklus. Beispielsweise machen autonome Fahrzeuge Aufnahmen der Straße, kombinieren diese mit Radar- und LiDAR-Daten und interpretieren sie. Dies geschieht normalerweise durch maschinelles Lernen, das die eingehenden Daten verarbeitet und ihnen Bedeutung verleiht, indem es semantische Informationen extrahiert wie "Ein weiteres Fahrzeug befindet sich 20 Yards vor Ihnen". Dies sind sogenannte Klassifizierungsprobleme.

Spiele benötigen kein komplexes System zur Informationsgewinnung, da der Großteil der Daten bereits ein integraler Bestandteil davon ist. Es ist nicht nötig, Bilderkennungsalgorithmen zu verwenden, um festzustellen, ob ein Feind voraus ist – das Spiel weiß es bereits und überträgt 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 eingehalten werden müssen:

• Die KI muss nicht im Voraus trainiert werden, als wäre sie ein Algorithmus für maschinelles Lernen. Es ist sinnlos, ein neuronales Netzwerk während der Entwicklung zu schreiben, um Zehntausende von Spielern zu beobachten und die beste Spielweise gegen sie zu lernen. Warum? Weil das Spiel noch nicht veröffentlicht ist und es keine Spieler gibt.
• Das Spiel sollte unterhalten und herausfordern, weshalb die Agenten keinen optimalen Ansatz gegen Menschen finden sollten.
• Die Agenten müssen realistisch wirken, damit die Spieler das Gefühl haben, gegen echte Menschen zu spielen. Das AlphaGo-Programm übertraf den Menschen, aber die gewählten Züge waren weit entfernt von einem traditionellen Verständnis des Spiels. Wenn ein Spiel einen menschlichen Gegner imitiert, sollte dieses Gefühl nicht vorhanden sein. Der Algorithmus muss angepasst werden, um plausible Entscheidungen zu treffen, anstatt perfekte.
• KI muss in Echtzeit arbeiten. Das bedeutet, dass der Algorithmus die CPU nicht über einen längeren Zeitraum monopolistisch nutzen kann, um Entscheidungen zu treffen. Selbst 10 Millisekunden dafür sind zu lang, da den meisten Spielen nur 16 bis 33 Millisekunden ausreichen, um die gesamte Verarbeitung durchzuführen und zum nächsten Grafikframe überzugehen.
• Es wäre ideal, wenn zumindest ein Teil des Systems datenbasiert gesteuert wird, damit auch "Nicht-Coder" Änderungen vornehmen können und Anpassungen schneller erfolgen.

Betrachten wir Ansätze der KI, die den gesamten Zyklus Sense/Think/Act abdecken.

Treffen grundlegender Entscheidungen

Beginnen wir mit dem einfachsten Spiel – Pong. Ziel: Bewege die Plattform (Paddle) so, dass der Ball von ihr abprallt und nicht daran vorbeifliegt. Es ist wie Tennisspielen, bei dem du verlierst, wenn du den Ball nicht zurückspielst. Für die KI ist die Aufgabe relativ einfach – zu entscheiden, in welche Richtung die Plattform bewegt werden soll.

Bedingte Operatoren

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

Ein einfacher Algorithmus dafür, verfasst in Pseudocode:

jede Frame/Aktualisierung, während das Spiel läuft:
Wenn der Ball links von der Plattform ist:
Bewege die Plattform nach links
Sonst, wenn der Ball rechts von der Plattform ist:
Bewege die Plattform nach rechts

Wenn die Plattform 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 es nicht viele Daten oder mögliche Aktionen für den Agenten gibt.

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

• Der Teil Sense befindet sich in den beiden if-Operatoren. Das Spiel weiß, wo der Ball ist und wo sich die Plattform befindet, also greift die KI auf diese Informationen zu.
• Der Teil Think gehört ebenfalls zu zwei if-Operatoren. Sie repräsentieren zwei Lösungen, die in diesem Fall sich gegenseitig ausschließen. Infolgedessen wird eine der drei Aktionen gewählt – die Plattform nach links bewegen, nach rechts bewegen oder nichts tun, wenn sie bereits korrekt positioniert ist.
• Der Teil Act befindet sich in den Operatoren 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 eine einfache Regelmenge (in diesem Fall if-Operatoren im Code), die auf den aktuellen Zustand der Welt reagiert und handelt.

Entscheidungsbaum

Das Beispiel mit dem Spiel Pong entspricht tatsächlich dem formalen Konzept der KI, das als Entscheidungsbaum bezeichnet wird. Der Algorithmus durchläuft ihn, um zum 'Blatt' zu gelangen – einer Entscheidung darüber, welche Aktion zu ergreifen ist.

Lassen Sie uns ein Flussdiagramm des Entscheidungsbaums für den Algorithmus unserer Plattform erstellen:

Jeder Teil des Baums wird als Node (Knoten) bezeichnet – die KI verwendet die Grafentheorie, um solche Strukturen zu beschreiben. Es gibt zwei Arten von Knoten:

• Entscheidungsfindungsknoten: Auswahl zwischen zwei Alternativen basierend auf einer Bedingung, wobei jede Alternative als separater Knoten dargestellt wird.
• Endknoten: Eine auszuführende Aktion, die die endgültige Entscheidung darstellt.

Der Algorithmus beginnt mit dem ersten Knoten („Wurzel“ des Baums). Er entscheidet entweder, zu welchem Kindknoten er wechseln soll, oder führt die im Knoten gespeicherte Aktion aus und endet.

Was ist der Vorteil, wenn Entscheidungsbäume dieselbe Funktion erfüllen wie die if-Anweisungen im vorherigen Abschnitt? Hier gibt es ein allgemeines System, in 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 darstellen, ohne sie hart zu kodieren. Lassen Sie es uns in Form einer Tabelle darstellen:

Auf der Code-Seite erhalten Sie ein System zur Verarbeitung von Zeilen. Erstellen Sie für jede dieser Zeilen einen Knoten, verbinden Sie die Entscheidungslogik mit der zweiten Spalte und die Kindknoten mit der dritten und vierten Spalte. Sie müssen weiterhin Bedingungen und Aktionen programmieren, aber die Struktur des Spiels wird jetzt komplexer. Sie fügen zusätzliche Entscheidungen und Aktionen hinzu und konfigurieren die gesamte KI, indem Sie einfach die Textdatei mit der Definition des Baumes bearbeiten. Anschließend übergeben Sie die Datei an den Game Designer, 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 Beispiel-Sets erstellt werden (zum Beispiel unter Verwendung des ID3-Algorithmus). Dies macht sie zu einem effizienten und leistungsstarken Werkzeug zur Klassifizierung von Situationen basierend auf den gesammelten Daten. Wir gehen jedoch über ein einfaches System zur Auswahl von Aktionen durch Agenten hinaus.

Szenarien

Wir haben ein Entscheidungsbaum-System untersucht, das vordefinierte Bedingungen und Aktionen verwendete. Der Entwickler von KI kann den Baum nach seinen Vorstellungen gestalten, muss jedoch immer noch auf den Programmierer zurückgreifen, der alles implementiert hat. Was wäre, wenn wir dem Designer die Werkzeuge geben könnten, um eigene 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 schaffen, in dem der Designer die Bedingungen zur Überprüfung dieser Werte festlegt. Dann würde die Datenstruktur des Entscheidungsbaums folgendermaßen aussehen:

Im Grunde genommen ist dies dasselbe wie in der ersten Tabelle, aber die Lösungen haben einen eigenen Code, der ein wenig an den bedingten Teil eines if-Operators erinnert. Im Code würde dies in der zweiten Spalte für Entscheidungsknoten ausgelesen, aber anstelle der Suche nach einer spezifischen Bedingung zum Ausführen (Ist der Ball links vom Paddle?) bewertet es den bedingten 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) annehmen und Variablen erstellen, die im Skript verfügbar sind (ball.position). Darüber hinaus ist die Skriptsprache einfacher als C++. Sie erfordert keinen vollständigen Kompilierungsprozess, was sie ideal für schnelle Anpassungen der Spiel-Logik macht und es „Nicht-Programmierern“ ermöglicht, eigene Funktionen zu erstellen.

Im gegebenen Beispiel wird die Skriptsprache nur zur Bewertung des bedingten Ausdrucks verwendet, aber sie kann auch für Aktionen genutzt werden. Zum Beispiel könnten Daten wie Bewege Paddle nach Rechts zu einem Skriptoperator werden (ball.position.x += 10). So kann die Aktion auch im Skript definiert werden, ohne dass eine Programmierung für 'Bewege Paddle nach Rechts' erforderlich ist.

Man kann noch einen Schritt weiter gehen und einen Entscheidungsbaum vollständig in einer Skriptsprache formulieren. Der Code wird in Form von festen (hardcoded) Bedingungsoperatoren vorliegen, die jedoch in externen Skriptdateien gespeichert sind, sodass sie ohne eine vollständige Neukompilierung des Programms geändert werden können. Oft kann die Skriptdatei während des Spiels geändert werden, um verschiedene KI-Reaktionen schnell zu testen.

Ereignisreaktion

Die obigen Beispiele eignen sich hervorragend für Pong. Sie führen kontinuierlich den Zyklus Sense/Think/Act aus und handeln basierend auf dem letzten Zustand der Welt. In komplexeren Spielen muss jedoch auf einzelne Ereignisse reagiert werden, anstatt alles auf einmal zu bewerten. Pong ist in diesem Fall also ein ungeeignetes Beispiel. Lassen Sie uns ein anderes wählen.

Stellen Sie sich einen Shooter vor, in dem die Feinde bewegungslos bleiben, bis sie den Spieler entdecken, woraufhin sie je nach ihrer „Spezialisierung“ handeln: Einige werden „rushen“, während andere aus der Ferne angreifen. Dies ist immer noch ein grundlegendes Reaktionssystem – „Wenn der Spieler gesehen wird, dann tue etwas“ – aber es kann logisch in das Ereignis „Spieler gesehen“ und die Reaktion (wählen Sie eine Antwort und führen Sie diese aus) unterteilt werden.

Das bringt uns zurück zum 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 sieht, wird das Ereignis Player Seen ausgelöst. Der Code wird einen separaten Abschnitt haben, der besagt: „wenn das Ereignis Player Seen eintritt, mache“, wobei die Antwort ist, die benötigt wird, um auf die Teile Think und Act zuzugreifen. So können Sie die Reaktionen auf das Ereignis Player Seen einstellen: für einen „rushenden“ Charakter – ChargeAndAttack, und für einen Sniper – HideAndSnipe. Diese Verbindungen können in der Datendatei erstellt werden, um schnelle Anpassungen vorzunehmen, ohne die Notwendigkeit, neu zu kompilieren. Hier kann auch eine Skriptsprache verwendet werden.

Komplexe Entscheidungen treffen

Obwohl einfache Reaktionssysteme sehr effektiv sein können, gibt es viele Situationen, in denen sie nicht ausreichen. Manchmal müssen Entscheidungen getroffen werden, die auf dem aktuellen Verhalten des Agenten basieren, was schwer als Bedingung darzustellen ist. Oft gibt es zu viele Bedingungen, um sie effektiv in einem Entscheidungsbaum oder Skript abzubilden. Manchmal ist es notwendig, im Voraus zu bewerten, wie sich die Situation entwickeln wird, bevor eine Entscheidung über den nächsten Schritt getroffen wird. Für diese Herausforderungen sind komplexere Ansätze erforderlich.

Endlicher Automat

Ein endlicher Automat oder FSM (Finite State Machine) ist ein Konzept, das besagt, dass sich unser Agent derzeit in einem von mehreren möglichen Zuständen befindet und dass er von einem Zustand in einen anderen wechseln kann. Es gibt eine bestimmte Anzahl solcher Zustände, daher der Name. Ein gutes Beispiel aus dem Alltag ist eine Ampel. An verschiedenen Orten gibt es unterschiedliche Lichtfolgen, aber das Prinzip bleibt gleich – jeder Zustand steht für etwas (stoppen, gehen usw.). Die Ampel befindet sich zu jedem Zeitpunkt nur in einem Zustand und wechselt basierend auf einfachen Regeln von einem Zustand in den anderen.

In Spielen mit NPCs gibt es eine ähnliche Geschichte. Nehmen wir als Beispiel einen Wächter mit diesen Zuständen:

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

Und mit diesen Bedingungen zur Änderung seines Zustands:

• Wenn der Wächter den 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 der Status-Variable des Wächters und verschiedenen Prüfungen schreiben: Gibt es einen Feind in der Nähe, wie hoch ist der Gesundheitszustand des NPC usw. Fügen wir noch einige weitere Zustände hinzu:

• Inaktiv (Idling) — zwischen den Patrouillen.
• Suchend (Searching) — wenn der gesichtete Feind verschwunden ist.
• Hilfe suchen (Finding Help) — wenn ein Feind bemerkt wird, der jedoch zu stark ist, um alleine gegen ihn zu kämpfen.

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

Letztendlich kann eine umfangreiche Liste von „Wenn-Dann“-Bedingungen zu unübersichtlich werden. Daher sollten wir einen formalisierten Ansatz entwickeln, der es uns ermöglicht, die Zustände und Übergänge zwischen diesen Zuständen im Blick zu behalten. <x и y, но не z>, dann <p>Um dies zu erreichen, werden wir alle möglichen Zustände berücksichtigen und unter jedem Zustand eine Liste aller Übergänge zu anderen Zuständen zusammenstellen, einschließlich der dafür erforderlichen Bedingungen.

Dies ist eine Zustandsübergangstabelle — eine komplexe Methode zur Darstellung von FSM. Lassen Sie uns ein Diagramm zeichnen und erhalten einen kompletten Überblick darüber, wie sich das Verhalten des NPC ändert.

Das Diagramm veranschaulicht den Entscheidungsprozess dieses Agenten basierend auf der aktuellen Situation. Jede Pfeil zeigt den Übergang zwischen Zuständen an, wenn die Bedingungen daneben erfüllt sind.

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

Das betrifft die Verarbeitung der Übergänge zwischen Zuständen, aber wie sieht es mit dem Verhalten aus, das mit den Zuständen selbst verbunden ist? Bei der Implementierung des tatsächlichen Verhaltens für einen bestimmten Zustand 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 beim Übergang von einem Zustand in einen anderen durchführen.

Beispiele für den ersten Typ. Im Zustand Patrolling bewegt sich der Agent in jedem Frame entlang des Patrouillenpfades. Im Zustand Attacking wird in jedem Frame versucht, einen Angriff zu starten oder in einen Zustand zu wechseln, wenn dies möglich ist.

Beim zweiten Typ betrachten wir den Übergang: „Wenn der Feind sichtbar ist und zu stark, dann wechsle in den Zustand Finding Help.“ Der Agent muss entscheiden, wohin er gehen soll, um Hilfe zu holen, und diese Information speichern, damit der Zustand Finding Help weiß, wo er sich hinwenden kann. Sobald Hilfe gefunden ist, wechselt der Agent zurück in den Zustand Attacking. In diesem Moment möchte er seinem Verbündeten von der Bedrohung berichten, weshalb die Aktion NotifyFriendOfThreat entstehen kann.

Und erneut können wir dieses System durch die Linse des Zyklus Sense / Think / Act betrachten. Sense zeigt sich in den Daten, die für die Logik des Übergangs verwendet werden. Think besteht aus den Übergängen, die in jedem Zustand verfügbar sind. Und Act wird durch Aktionen realisiert, die periodisch innerhalb des Zustands oder bei Übergängen zwischen Zuständen durchgeführt werden.

Ständige Abfragen der Übergangsbedingungen können teuer sein. Wenn jeder Agent zum Beispiel bei jedem Frame komplexe Berechnungen anstellt, um zu bestimmen, ob er Feinde sieht und ob er vom Zustand Patrouillieren zum Angreifen übergehen kann, benötigt das viel Rechenzeit.

Wesentliche Änderungen im Zustand der Welt können als Ereignisse betrachtet werden, die verarbeitet werden, sobald sie eintreten. Anstatt dass die FSM bei jedem Frame prüft, ob die Bedingung "Kann mein Agent den Spieler sehen?" vorliegt, kann ein separates System eingerichtet werden, das die Prüfungen seltener durchführt (z.B. 5 Mal pro Sekunde). Das Ergebnis wäre "Spieler gesehen", wenn die Prüfung erfolgreich ist.

Dies wird an die FSM übergeben, die nun in den Zustand "Spieler gesehen, Ereignis empfangen" wechseln und entsprechend reagieren muss. Das endgültige Verhalten bleibt gleich, abgesehen von einer nahezu unmerklichen Verzögerung vor der Antwort. Die Leistung hat sich jedoch durch die Trennung des Teils Sense in einen separaten Teil des Programms verbessert.

Hierarchische finite Zustandsmaschine

Mit großen FSM zu arbeiten, ist jedoch nicht immer bequem. 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 ändern, die zum Zustand Attacking (Angreifen) führen (sowohl die aktuellen als auch zukünftige).

Sie haben sicherlich bemerkt, dass unser Beispiel viele doppelte Übergänge enthält. Die meisten Übergänge im Zustand Idling sind identisch mit den Übergängen im Zustand Patrolling. Es wäre vorteilhaft, nicht redundant zu sein, insbesondere wenn wir weitere ähnliche Zustände hinzufügen. Es macht Sinn, Idling und Patrolling unter einem gemeinsamen Label 'nicht kämpfend' zu gruppieren, bei dem es nur einen gemeinsamen Satz von Übergängen zu kämpfenden Zuständen gibt. Wenn wir dieses Label 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ämpfenden Unterzustand:

Hauptzustände:


Zustand außerhalb des Kampfes:


Und in Form eines Diagramms:

Dies ist dasselbe System, jedoch mit einem neuen nicht-kämpferischen Zustand, der das Idling und Patrolling umfasst. Jeder Zustand enthält eine FSM mit Unterzuständen (und diese Unterzustände enthalten wiederum eigene FSMs – und so weiter, wie viele Sie benötigen), was uns zur Hierarchical Finite State Machine oder HFSM (hierarchische endliche Automate) führt. Durch die Gruppierung des nicht-kämpferischen Zustands haben wir viele redundante Übergänge entfernt. Das Gleiche können wir für alle neuen Zustände mit gemeinsamen Übergängen tun. Wenn wir beispielsweise in Zukunft den Zustand Attacking auf die Zustände MeleeAttacking und MissileAttacking erweitern, werden diese Unterzustände sein, die basierend auf der Entfernung zum Feind und dem Vorhandensein von Munition untereinander wechseln. So können komplexe Verhaltensmodelle und Untermodelle mit minimalen redundanten Übergängen dargestellt werden.

Verhaltensbaum

Mit HFSM lassen sich komplexe Verhaltensmuster einfach erstellen. Dennoch gibt es eine kleine Schwierigkeit: Die Entscheidungsfindung in Form von Übergangsregeln ist eng mit dem aktuellen Zustand verbunden. In vielen Spielen ist genau das erforderlich. Eine sorgfältige Nutzung der Zustandshierarchie kann die Anzahl der Wiederholungen bei Übergängen verringern. Manchmal sind jedoch Regeln erforderlich, die unabhängig vom aktuellen Zustand funktionieren oder die in nahezu allen Zuständen angewendet werden. Zum Beispiel, wenn die Gesundheit des Agents auf 25% fällt, möchten Sie, dass er unabhängig davon, ob er kämpft, herumsitzt oder spricht, wegläuft — dafür müssen Sie 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, muss wieder daran gearbeitet werden.

Idealerweise benötigen wir für diese Situation ein System, in dem die Entscheidungen darüber, „in welchem Zustand man sich befinden soll“, außerhalb der Zustände selbst liegen, um Änderungen nur an einem Ort vorzunehmen und die Übergangsbedingungen nicht zu beeinflussen. Hier kommen Verhaltenstrees ins Spiel.

Es gibt verschiedene Möglichkeiten, sie umzusetzen, aber das Grundprinzip ist für alle ähnlich und ähnelt einem Entscheidungsbaum: Der Algorithmus beginnt mit dem "Wurzel"-Knoten, und im Baum gibt es Knoten, die entweder Entscheidungen oder Aktionen darstellen. Allerdings gibt es einige wichtige Unterschiede:

• Jetzt liefern die Knoten eines von drei Werten zurück: Succeeded (wenn die Arbeit erfolgreich war), Failed (wenn sie nicht gestartet werden konnte) oder Running (wenn sie noch läuft und kein Endergebnis vorliegt).
• Es gibt keine Entscheidungsknoten mehr, um zwischen zwei Alternativen zu wählen. Stattdessen gibt es Decorator-Knoten, die einen einzigen Kindknoten haben. Wenn sie erfolgreich sind, führen sie ihren einzigen Kindknoten aus.
• Die Knoten, die Aktionen ausführen, geben den Wert Running zurück, um die durchgeführten Aktionen darzustellen.

Dieses kleine Set an Knoten kann kombiniert werden, um eine Vielzahl komplexer Verhaltensmodelle zu erstellen. Stellen wir uns das HFSM des Wächters aus dem vorherigen Beispiel in Form eines Verhaltensbaums vor:

Mit dieser Struktur sollte es keinen klaren Übergang von den Zuständen Idling/Patrolling in den Zustand Attacking oder in andere Zustände geben. Wenn der Feind sichtbar ist und die Gesundheit des Charakters niedrig ist, bleibt die Ausführung im Knoten Fleeing stehen, egal welchen Knoten er zuvor ausgeführt hat – Patrolling, Idling, Attacking oder einen anderen.

Verhaltenbäume sind komplex – es gibt viele Möglichkeiten, sie zusammenzustellen, und das Finden der richtigen Kombination von Dekoratoren und zusammengesetzten Knoten kann problematisch sein. Es gibt auch Fragen, wie oft der Baum überprüft werden sollte – wollen wir jeden Teil durchlaufen oder nur, wenn sich eine der Bedingungen geändert hat? Wie speichert man den Zustand, der sich auf die Knoten bezieht – wie erkennt man, wann wir 10 Sekunden im Zustand Idling waren oder wie weiß man, welche Knoten beim letzten Mal ausgeführt wurden, um die Sequenz richtig zu verarbeiten?

Deshalb gibt es viele Implementierungen. In einigen Systemen haben Dekorationsknoten eingebaute Dekoratoren ersetzt. Diese bewerten den Baum bei Änderungen der Bedingungen des Dekorators neu, helfen beim Verbinden von Knoten und bieten regelmäßige Aktualisierungen.

Nutzungsbasiertes System

Einige Spiele verfügen über eine Vielzahl unterschiedlicher Mechaniken. Es ist vorteilhaft, wenn sie alle Vorteile einfacher und allgemeiner Übergangsregeln nutzen, aber nicht zwingend in Form eines vollständigen Verhaltensbaums. Anstatt über einen klaren Satz von Entscheidungen oder einen Baum möglicher Aktionen zu verfügen, ist es einfacher, alle Aktionen zu studieren und den aktuell passendsten auszuwählen.

Ein utilitaristisches System unterstützt genau dabei. Es handelt sich um ein System, in dem der Agent eine Vielzahl von Aktionen hat und selbst auswählt, welche er ausführt, basierend auf der relativen Nützlichkeit jeder einzelnen. Dabei ist Nützlichkeit ein willkürliches Maß dafür, wie wichtig oder wünschenswert die Ausführung dieser Aktion für den Agenten ist.

Der Agent kann die berechnete Nützlichkeit einer Handlung basierend auf dem aktuellen Zustand und der Umgebung überprüfen und jederzeit den am besten geeigneten anderen Zustand auswählen. Dies ähnelt einem FSM, abgesehen davon, dass die Übergänge durch die Bewertung jedes potenziellen Zustands, 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). Für mehr Vielfalt könnte dies eine gewichtete, aber zufällige Auswahl aus einer kleinen Liste sein.

Das System weist einen zufälligen Bereich von Nützlichkeitswerten zu – zum Beispiel von 0 (völlig unerwünscht) bis 100 (vollständig wünschenswert). Jede Aktion hat eine Reihe von Parametern, die die Berechnung dieses Wertes beeinflussen. Zurück zu unserem Beispiel mit dem Wächter:

Übergänge zwischen Aktionen sind unklar – jeder Zustand kann auf jeden anderen folgen. Die Prioritäten der Aktionen basieren auf den zurückgegebenen Nutzwerten. Wenn der Feind sichtbar und stark ist und die Gesundheit des Charakters niedrig ist, geben sowohl Fliehen als auch Hilfe finden hohe, nicht null Werte zurück. Dabei wird Hilfe finden immer höher bewertet. Ähnlich erhalten nicht-kämpferische Aktionen niemals mehr als 50, weshalb sie immer unter den kämpferischen Aktionen liegen werden. Dies sollte bei der Erstellung von Aktionen und der Berechnung ihrer Nützlichkeit berücksichtigt werden.

In unserem Beispiel geben die Aktionen entweder einen festen Wert oder einen von zwei festen Werten zurück. Ein realistisches System würde jedoch eine Bewertung aus einem kontinuierlichen Wertebereich zurückgeben. Zum Beispiel liefert die Aktion Fliehen höhere Nutzenwerte, wenn die Gesundheit des Agenten niedrig ist, während die Aktion Angreifen niedrigere Werte zurückgibt, wenn der Gegner zu stark ist. Daher hat die Aktion Fliehen Vorrang vor Angreifen, wenn der Agent glaubt, dass er nicht genug Gesundheit hat, um den Gegner zu besiegen. Dies ermöglicht es, die Prioritäten der Aktionen basierend auf verschiedenen Kriterien zu ändern, was diesen Ansatz flexibler und variabler macht als ein Verhaltensbaum oder eine FSM.

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

Die Idee, Aktionen auf der Grundlage eines Bewertungssystems auszuwählen, ist ziemlich einfach, weshalb ein utilitaristisches System als Teil des Entscheidungsprozesses von KI verwendet werden kann, anstatt es vollständig zu ersetzen. Ein Entscheidungbaum kann die Nützlichkeitsbewertung von zwei Kindknoten anfordern und den höher bewerteten auswählen. In ähnlicher Weise kann ein Verhaltensbaum einen zusammengesetzten Nutzenknoten haben, der die Nützlichkeit der Aktionen bewertet, um zu entscheiden, welches Kindlement ausgeführt werden soll.

Bewegung und Navigation

In den vorherigen Beispielen hatten wir eine Plattform, die wir nach links oder rechts bewegten, und einen Wächter, der patrouillierte oder angreift. Aber wie genau kümmern wir uns um die Bewegung des Agenten über einen bestimmten Zeitraum? Wie legen wir die Geschwindigkeit fest, wie vermeiden wir Hindernisse und wie planen wir die Route, wenn es schwieriger ist, das Ziel zu erreichen, als einfach geradeaus zu gehen? Lassen Sie uns das genauer betrachten.

Verwaltung

Zu Beginn nehmen wir an, dass jeder Agent eine Geschwindigkeitsgröße hat, die umfasst, wie schnell er sich bewegt und in welche Richtung. Diese kann in Metern pro Sekunde, Kilometern pro Stunde, Pixeln pro Sekunde usw. gemessen werden. In Bezug auf den Zyklus Sense/Think/Act 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 die Geschwindigkeitswerte jedes Objekts analysiert und anpasst. Daher kann die KI mit einer einzigen Aufgabe betraut werden – zu entscheiden, welche Geschwindigkeit der Agent haben sollte. Wenn bekannt ist, wo sich der Agent befinden soll, muss er in die richtige Richtung mit der festgelegten Geschwindigkeit bewegt werden. Eine sehr triviale Gleichung:

desired_travel = destination_position – agent_position

Stellen Sie sich eine 2D-Welt vor. Der Agent befindet sich an Punkt (-2,-2), das Ziel irgendwo im Nordosten bei Punkt (30, 20). Der notwendige Weg für den Agenten, um dorthin zu gelangen, beträgt (32, 22). Angenommen, diese Positionen werden in Metern gemessen – wenn wir die Geschwindigkeit des Agenten mit 5 Metern pro Sekunde annehmen, würden wir unseren Bewegungsvektor skalieren und eine Geschwindigkeit von etwa (4,12, 2,83) erhalten. Mit diesen Parametern würde der Agent das Ziel in fast 8 Sekunden erreichen.

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

Wir möchten jedoch mehr Variabilität — zum Beispiel die Geschwindigkeit langsam erhöhen, um eine Figur zu simulieren, die aus dem Stand in den Lauf übergeht. Ebenso kann dies am Ende vor dem Anhalten erfolgen. Diese Funktionen sind als Steering-Verhalten bekannt, von denen jedes einen spezifischen Namen besitzt: Seek (Suchen), Flee (Fliehen), Arrival (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 der aktuellen Geschwindigkeit mit dem Zielort, um verschiedene Bewegungsarten zur Zielerreichung zu nutzen.

Jedes Verhalten hat ein leicht anderes Ziel. Seek und Arrival sind Methoden, um den Agenten zu einem Zielpunkt zu bewegen. Obstacle Avoidance (Überwindung von Hindernissen) und Separation (Trennung) passen die Bewegung des Agenten an, um Hindernisse auf dem Weg zum Ziel zu umgehen. Alignment (Ausrichtung) und Cohesion (Zusammenhalt) sorgen dafür, dass die Agenten zusammenbleiben, während sie sich bewegen. Eine beliebige Anzahl verschiedener Steuerungsverhalten kann summiert werden, um einen einzigen Pfadvektor unter Berücksichtigung aller Faktoren zu erhalten. Ein Agent, der die Verhaltensweisen Arrival, Separation und Obstacle Avoidance nutzt, um sich von Wänden und anderen Agenten fernzuhalten. Dieser Ansatz funktioniert gut in offenen Umgebungen ohne unnötige Details.

In schwierigeren Bedingungen funktioniert die Kombination verschiedener Verhaltensweisen schlechter – zum Beispiel kann ein Agent in einer Wand stecken bleiben aufgrund eines Konflikts zwischen Arrival und Obstacle Avoidance. Daher müssen wir Optionen in Betracht ziehen, die komplexer sind als einfach die Addition aller Werte. Eine Methode besteht darin, anstelle der Addition der Ergebnisse jedes Verhaltens die Bewegung in verschiedene Richtungen zu betrachten und die beste Option zu wählen.

In einer komplexen Umgebung mit Sackgassen und der Entscheidung, in welche Richtung man gehen soll, benötigen wir jedoch etwas noch Fortgeschrittenes.

Pfadfindung

Steuerverhalten eignet sich hervorragend für die einfache Fortbewegung im Freien (z. B. auf einem Fußballfeld oder in einer Arena), wo der Weg von A nach B direkt ist und nur minimale Abweichungen um Hindernisse erforderlich sind. Für komplexere Routen benötigen wir Pathfinding, das eine Methode zur Erkundung der Welt und zur Entscheidungsfindung über den besten Weg durch sie ist.

Der einfachste Weg besteht darin, ein Gitter auf jedes Quadrat neben dem Agenten zu legen und zu bewerten, in welchen davon Bewegungen erlaubt sind. Wenn eines von ihnen das Ziel ist, folgen Sie von dort aus dem Weg von jedem Quadrat zu dem zuvorigen, bis Sie den Anfang erreichen. Das ist der Weg. Andernfalls wiederholen Sie den Prozess mit den nächstgelegenen anderen Quadraten, bis Sie das Ziel finden oder keine Quadrate mehr vorhanden sind (was bedeutet, dass kein möglicher Weg existiert). Das ist formal bekannt als Breadth-First Search oder BFS (Breitensuche). In jedem Schritt wird in alle Richtungen geschaut (daher „Breite“). Der Suchraum ähnelt einer Wellenfront, die sich bewegt, bis das gesuchte Ziel erreicht ist – das Suchgebiet dehnt sich bei jedem Schritt aus, bis der Endpunkt erreicht ist, wonach der Weg zum Anfang zurückverfolgt werden kann.

Infolge dessen erhalten Sie eine Liste der Quadrate, anhand derer der benötigte Weg erstellt wird. Das ist der Pfad (pathfinding) – eine Liste der Orte, die der Agent besuchen wird, während er zum Ziel gelangt.

Da wir die Position jedes Quadrats auf der Welt kennen, können wir Steuerungsverhalten nutzen, um den Weg von Knoten 1 zu Knoten 2 und dann von Knoten 2 zu Knoten 3 und so weiter zu bewegen. Die einfachste Option besteht darin, sich auf das Zentrum des nächsten Quadrats zuzubewegen, aber noch besser ist es, in der Mitte der Kante zwischen dem aktuellen Quadrat und dem nächsten zu halten. Dadurch kann der Agent an scharfen Kurven die Ecken abschneiden.

Der BFS-Algorithmus hat auch Nachteile – er untersucht genauso viele Quadrate in die "falsche" Richtung wie in die "richtige". Hier kommt ein komplexerer Algorithmus ins Spiel, der A* (A-Stern) heißt. Er funktioniert ebenfalls, aber anstatt blind die Nachbarquadrate (dann die Nachbarn der Nachbarn, dann die Nachbarn der Nachbarn der Nachbarn und so weiter) zu erkunden, erstellt er eine Liste von Knoten und sortiert sie so, dass der nächste untersuchte Knoten immer der ist, der zur kürzesten Route führt. Die Knoten werden anhand einer Heuristik sortiert, die zwei Dinge berücksichtigt – die "Kosten" der hypothetischen Route zum gewünschten Quadrat (einschließlich aller Bewegungs- oder Umzugskosten) 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, wobei er immer das vielversprechendste benachbarte Quadrat auswählt. Der resultierende Pfad ist derselbe wie bei BFS, aber es wurden dabei weniger Quadrate berücksichtigt – was sich erheblich auf die Leistung des Spiels auswirkt.

Bewegung ohne Raster

Die meisten Spiele sind jedoch nicht in einem Raster angeordnet, und oft ist es nicht möglich, ein solches Raster ohne Verlust an Realismus einzuführen. Kompromisse sind erforderlich. Wie groß sollten die Quadrate sein? Zu groß – und sie können enge Korridore oder Kurven nicht korrekt darstellen, zu klein – und es gibt zu viele Quadrate zu durchsuchen, was letztendlich viel Zeit in Anspruch nimmt.

Das erste, was zu verstehen ist – das Gitter stellt ein Netzwerk aus verbundenen Knoten dar. Die Algorithmen A* und BFS arbeiten im Wesentlichen mit Graphen und sind unabhängig von unserem Gitter. Wir könnten Knoten überall im Spielraum platzieren: Solange eine Verbindung zwischen zwei verbundenen Knoten besteht, sowie zwischen dem Start- und dem Endpunkt und mindestens einem der Knoten, wird der Algorithmus genauso gut funktionieren wie zuvor. Oft wird dies als Wegpunkt-System (waypoint) bezeichnet, da jeder Knoten eine bedeutende Position in der Welt darstellt, die Teil einer beliebigen Anzahl von hypothetischen Wegen sein kann.

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

Beispiel 2: Ein kleinerer Knoten-Satz (Wegpunkte). Die Suche beginnt im Quadrat mit dem Agenten, durchläuft die erforderliche Anzahl an Knoten und setzt sich dann bis zum Ziel fort.

Dies ist ein sehr flexibles und leistungsstarkes System. Allerdings ist Vorsicht geboten, wenn es darum geht, wo und wie Wegpunkte gesetzt werden; andernfalls könnten die Agenten den nächstgelegenen Punkt einfach nicht sehen und ihren Weg nicht beginnen. Es wäre einfacher, wenn wir Wegpunkte automatisch basierend auf der Geometrie der Welt platzieren könnten.

Hier kommt das Navigationsnetz oder navmesh ins Spiel. Dabei handelt es sich in der Regel um ein 2D-Netz aus Dreiecken, das auf die Geometrie der Welt projiziert wird – überall dort, wo Agenten sich bewegen dürfen. Jedes der Dreiecke im Netz wird zu einem Knoten im Graphen und hat bis zu drei benachbarte Dreiecke, die als benachbarte Knoten im Graphen fungieren.

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

Wir können einen Pfad durch dieses Netzwerk suchen, indem wir erneut den A*-Algorithmus verwenden. Dies wird uns einen nahezu perfekten Pfad in einer Welt bieten, die die gesamte Geometrie berücksichtigt, ohne zusätzliche Knoten oder Wegpunkte zu erfordern.

Pathfinding ist ein zu umfangreiches Thema, das nicht in einem einzigen Abschnitt behandelt werden kann. Wenn Sie es ausführlicher studieren möchten, kann Ihnen dabei die Website von Amit Patel helfen..

Planung

Wir haben beim Pathfinding festgestellt, dass es manchmal nicht ausreicht, einfach eine Richtung zu wählen und loszulaufen – wir müssen den richtigen Weg wählen und mehrere Abbiegungen machen, um unser Ziel zu erreichen. Wir können diese Idee zusammenfassen: Das Erreichen eines Ziels ist nicht nur der nächste Schritt, sondern eine gesamte Abfolge von Handlungen, bei der es manchmal erforderlich ist, ein paar Schritte vorauszuschauen, um zu wissen, wie der erste Schritt aussehen sollte. Dies nennt man Planung. Pathfinding kann als eine der Ergänzungen zur Planung betrachtet werden. In Bezug auf unseren Sense/Think/Act-Zyklus ist dies der Teil, wo der Teil Think mehrere Teile Act für die Zukunft plant.

Lassen Sie uns ein Beispiel aus dem Kartenspiel Magic: The Gathering nehmen. Wir ziehen zuerst mit diesem Kartenset:

• Swamp – erzeugt 1 schwarze Mana (Landkarte).
• Forest — gibt 1 grünes Mana (Landkarte).
• Fugitive Wizard — benötigt 1 blaues Mana für den Beschwörungszauber.
• Elvish Mystic — benötigt 1 grünes Mana für den Beschwörungszauber.

Die verbleibenden drei Karten ignorieren wir, um es einfacher zu machen. Nach den Regeln darf der Spieler pro Zug 1 Landkarte spielen und kann diese Karte „tappen“, um Mana daraus zu gewinnen, und dann Zaubersprüche (einschließlich der Beschwörung von Kreaturen) entsprechend der Menge an Mana verwenden. In dieser Situation weiß der menschliche Spieler, dass er Forest spielen, 1 grünes Mana „tappen“ und dann Elvish Mystic beschwören muss. Aber wie kann der Spiel-Ideen-Algorithmus das herausfinden?

Einfache Planung

Ein trivialer Ansatz wäre, jede Aktion nacheinander auszuprobieren, bis keine geeigneten mehr vorhanden sind. Betrachtet man die Karten, sieht die KI, dass sie Swamp spielen kann. Und sie spielt es. Gibt es noch andere Aktionen in dieser Runde? Sie kann weder Elvish Mystic noch Fugitive Wizard beschwören, da für deren Beschwörung entsprechend grünes und blaues Mana erforderlich ist, während Swamp nur schwarzes Mana bietet. Außerdem kann sie Forest nicht mehr spielen, da sie bereits Swamp gespielt hat. So hat die Spiel-KI nach den Regeln gespielt, jedoch nicht optimal. Es gibt Verbesserungsmöglichkeiten.

Die Planung kann eine Liste von Aktionen finden, die das Spiel in den gewünschten Zustand versetzen. So wie jedes Quadrat auf dem Pfad Nachbarn hatte (im Pathfinding), hat auch jede Aktion im Plan Nachbarn oder Nachfolger. Wir können diese Aktionen und die folgenden Schritte suchen, bis wir den gewünschten Zustand erreichen.

In unserem Beispiel ist das gewünschte Ergebnis „ein Wesen zu beschwören, wenn möglich“. Zu Beginn des Zuges sehen wir nur zwei mögliche Aktionen, die durch die Spielregeln erlaubt sind:

1. Schlage einen Sümpf (Ergebnis: Sümpf im Spiel)
2. Schlage einen Wald (Ergebnis: Wald im Spiel)

Jede getätigte Aktion kann zu weiteren Aktionen führen und andere schließen, wiederum abhängig von den Spielregeln. Stellen Sie sich vor, wir haben den Sümpf gespielt — damit wird der Sümpf als nächster Schritt entfernt (wir haben ihn bereits gespielt), auch der Wald wird entfernt (da gemäß den Regeln nur eine Landkarte pro Zug ausgespielt werden kann). Daraufhin fügt die KI als nächsten Schritt das Erhalten von 1 schwarzer Mana hinzu, da es keine anderen Optionen gibt. Wenn sie weitergeht und den Sümpf aktiviert, erhält sie 1 Einheit schwarze Mana und kann damit nichts anstellen.

1. Schlage einen Sümpf (Ergebnis: Sümpf im Spiel)
1.1 «Tappen» Sumpf (Ergebnis: Sumpf «getappt», +1 Einheit schwarzes Mana)
Keine verfügbaren Aktionen – ENDE
2. Schlage einen Wald (Ergebnis: Wald im Spiel)

Die Liste der Aktionen ist kurz, wir sind in eine Sackgasse geraten. Wir wiederholen den Prozess für die nächste Aktion. Wir spielen Wald, aktivieren die Aktion „1 grünes Mana erhalten“, die wiederum die dritte Aktion öffnet – den Elbischen Mystiker herbeirufen.

1. Schlage einen Sümpf (Ergebnis: Sümpf im Spiel)
1.1 «Tappen» Sumpf (Ergebnis: Sumpf «getappt», +1 Einheit schwarzes Mana)
Keine verfügbaren Aktionen – ENDE
2. Schlage einen Wald (Ergebnis: Wald im Spiel)
2.1 «Tappen» Wald (Ergebnis: Wald «getappt», +1 Einheit grünes Mana)
2.1.1 Elbischen Mystiker herbeirufen (Ergebnis: Elbischer Mystiker im Spiel, -1 Einheit grünes Mana)
Keine verfügbaren Aktionen – ENDE

Schließlich haben wir alle möglichen Aktionen untersucht und einen Plan gefunden, um ein Wesen herbeizurufen.

Dies ist ein stark vereinfachtes Beispiel. Es ist ratsam, den bestmöglichen Plan auszuwählen, anstatt irgendeinen, der bestimmten Kriterien entspricht. In der Regel kann man potenzielle Pläne anhand des Endergebnisses oder des kumulierten Nutzens ihrer Ausführung bewerten. Man kann sich 1 Punkt für das Spielen von Länderkarten und 3 Punkte für das Herbeirufen eines Wesens gutschreiben. Das Spielen eines Sumpfs würde 1 Punkt bringen. Aber Wald spielen → Wald tappen → Elbischen Mystiker herbeirufen, würde sofort 4 Punkte bringen.

So funktioniert die Planung in Magic: The Gathering, und dieselbe Logik kann auch in anderen Situationen angewendet werden. Zum Beispiel, einen Bauern zu ziehen, um Platz für einen Läufer im Schach zu schaffen. Oder sich hinter einer Wand zu verstecken, um in XCOM sicher zu schießen. Kurz gesagt, das Prinzip ist klar.

Verbesserte Planung

Manchmal gibt es zu viele potenzielle Aktionen, als dass man jede mögliche Option in Betracht ziehen könnte. Zurück zum Beispiel mit Magic: The Gathering: Angenommen, man hat mehrere Landkarten und Kreaturen auf der Hand – die Anzahl der möglichen Zugkombinationen könnte in die Zehner gehen. Es gibt mehrere Ansätze zur Lösung des Problems.

Die erste Methode ist das Backwards Chaining. Anstatt alle Kombinationen zu durchlaufen, ist es besser, mit dem Endergebnis zu beginnen und einen direkten Pfad zu suchen. Anstatt vom Wurzelknoten des Baumes zu einem bestimmten Blatt zu gehen, bewegen wir uns in umgekehrter Richtung – vom Blatt zurück zur Wurzel. Diese Methode ist einfacher und schneller.

Wenn der Gegner 1 Lebenspunkt hat, kann man den Plan "1 oder mehr Schadenspunkte verursachen" finden. Um dies zu erreichen, müssen eine Reihe von Bedingungen erfüllt werden:

1. Ein Zauber kann Schaden anrichten — er muss in der Hand sein.
2. Um einen Zauber zu wirken — wird Mana benötigt.
3. Um Mana zu erhalten — muss eine Landkarte ausgespielt werden.
4. Um eine Landkarte auszuspielen — muss sie in der Hand sein.

Ein anderer Ansatz ist die Best-First-Suche. Anstatt alle Wege zu überprüfen, wählen wir den passendsten aus. Oft führt diese Methode zu einem optimalen Plan ohne überflüssige Suchkosten. A* ist eine Form der Best-First-Suche — indem sie von Anfang an die vielversprechendsten Routen erkundet, kann sie bereits den besten Weg finden, ohne die anderen Optionen prüfen zu müssen.

Eine interessante und immer beliebter werdende Variante der Best-First-Suche ist die Monte Carlo Tree Search. Anstatt zu erraten, welche Pläne besser sind als andere bei der Auswahl jeder nachfolgenden Aktion, wählt der Algorithmus in jedem Schritt zufällige Nachfolger, bis er ein Ende erreicht (wenn der Plan zu einem Sieg oder einer Niederlage führt). Anschließend wird das Endergebnis verwendet, um das «Gewicht» der vorherigen Optionen zu erhöhen oder zu senken. Durch mehrmaliges Wiederholen dieses Prozesses bietet der Algorithmus eine gute Einschätzung, welcher nächste Schritt besser ist, selbst wenn sich die Situation ändert (wenn der Gegner Maßnahmen ergreift, um den Spieler zu behindern).

Im Kontext des Game Planning ist es unmöglich, Goal-Oriented Action Planning oder GOAP (zielorientierte Aktionsplanung) zu ignorieren. Dies ist eine weit verbreitete und diskutierte Methode, aber abgesehen von einigen besonderen Details ist es im Grunde genommen eine Form des Backwards Chaining, über die wir zuvor gesprochen haben. Wenn die Aufgabe darin besteht, den Spieler zu 'eliminieren' und der Spieler sich hinter einem Deckung befindet, könnte der Plan folgendermaßen aussehen: Mit einer Granate vernichten → sie holen → werfen.

Es gibt in der Regel mehrere Ziele, jedes mit seiner eigenen Priorität. Wenn das Ziel mit der höchsten Priorität nicht erreicht werden kann (keine Handlungskombination führt zu einem Plan, um den Spieler zu eliminieren, weil der Spieler nicht sichtbar ist), wird die KI zu Zielen mit niedrigerer Priorität zurückkehren.

Training und Anpassung

Wir haben bereits erwähnt, dass Spiel-KIs in der Regel kein maschinelles Lernen verwenden, da dies nicht geeignet ist, um Agenten in Echtzeit zu steuern. Das bedeutet jedoch nicht, dass wir nichts aus diesem Bereich übernehmen können. Wir wünschen uns einen Gegner in einem Shooter, von dem man lernen kann. Zum Beispiel, um die besten Positionen auf der Karte zu erkennen. Oder einen Gegner im Kampfspiel, der oft verwendete Kombinationen des Spielers blockiert und so motiviert, andere Techniken zu verwenden. In solchen Situationen kann maschinelles Lernen sehr nützlich sein.

Statistiken und Wahrscheinlichkeiten

Bevor wir zu komplexeren Beispielen übergehen, wollen wir zunächst abschätzen, wie weit wir mit einigen einfachen Messungen und deren Verwendung für Entscheidungen kommen können. Zum Beispiel, wie können wir in Echtzeit herausfinden, ob ein Spieler in den ersten Minuten des Spiels einen Angriff starten kann und welche Verteidigungsstrategie wir dagegen vorbereiten sollten? Wir können die bisherigen Erfahrungen des Spielers analysieren, um zu verstehen, wie seine zukünftige Reaktion aussehen könnte. Zunächst haben wir keine Ausgangsdaten, aber wir können sie sammeln – jedes Mal, wenn die KI gegen einen Menschen spielt, könnte sie die Zeit bis zum ersten Angriff aufzeichnen. Nach mehreren Sitzungen würden wir den Durchschnittswert der Zeit erhalten, nach der ein Spieler in Zukunft angreifen wird.

Mittelwerte bringen jedoch auch ein Problem mit sich: Wenn ein Spieler 20 Mal ‚rushte‘ und 20 Mal langsam spielte, würden die benötigten Werte irgendwo in der Mitte liegen, was uns wenig nützlich wäre. Eine Lösung besteht darin, die Eingabedaten zu begrenzen – wir könnten die letzten 20 Zeitwerte heranziehen.

Ein ähnlicher Ansatz wird verwendet, um die Wahrscheinlichkeit bestimmter Aktionen zu bewerten, wobei angenommen wird, dass die früheren Vorlieben eines Spielers in der Zukunft gleich bleiben. Wenn ein Spieler uns fünfmal mit einem Feuerball, zweimal mit Blitz und einmal im Nahkampf angreift, ist es offensichtlich, dass er Feuerball bevorzugt. Lassen Sie uns extrapolieren und die Wahrscheinlichkeit der Verwendung verschiedener Waffen sehen: Feuerball = 62,5 %, Blitz = 25 % und Nahkampf = 12,5 %. Unsere Spiel-KI muss sich auf den Schutz vor Feuer vorbereiten.

Eine weitere interessante Methode ist die Verwendung des Naive Bayes Classifier (naiver Bayes-Klassifikator), um große Mengen an Eingabedaten zu analysieren und die Situation zu klassifizieren, damit die KI entsprechend reagiert. Bayes-Klassifikatoren sind besonders bekannt für ihren Einsatz in Spamfiltern. Dort analysieren sie Wörter, vergleichen sie mit vorherigen Vorkommen dieser Wörter (in Spam-Nachrichten oder nicht) und ziehen Rückschlüsse auf eingehende E-Mails. Wir können dasselbe auch mit weniger Eingabedaten tun. Basierend auf all den nützlichen Informationen, die die KI sieht (z. B. welche feindlichen Einheiten erstellt wurden, welche Zauber sie verwenden oder welche Technologien sie erforscht haben), und dem endgültigen Ergebnis (Krieg oder Frieden, „Rush“ oder verteidigen usw.) werden wir das richtige Verhalten der KI auswählen.

Diese Ausbildungsansätze sind zwar ausreichend, jedoch ist es vorteilhaft, sie auf der Grundlage der Testergebnisse zu verwenden. Die KI wird lernen, sich an die verschiedenen Strategien anzupassen, die Ihre Playtester genutzt haben. Eine KI, die sich nach der Veröffentlichung an den Spieler anpasst, kann zu vorhersehbar oder im Gegenteil zu schwierig zu besiegen werden.

Anpassung basierend auf Werten

Angesichts des Inhalts unserer Spielwelt und der Regeln können wir die Menge an Werten verändern, die die Entscheidungen beeinflussen, anstatt einfach nur die Eingabewerte zu verwenden. So gehen wir vor:

• Lassen Sie die KI Daten zum Zustand der Welt und zu Schlüsselmomenten während des Spiels sammeln (wie oben angegeben).
• Ändern wir einige wichtige Werte basierend auf diesen Daten.
• Setzen wir 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 es ist, ihn zu besuchen. Die KI wählt zufällig aus, in welchen Raum sie gehen möchte, basierend auf diesem Wert. Dann merkt sich der Agent, in welchem Raum er getötet wurde, und reduziert dessen Wert (d.h. die Wahrscheinlichkeit, dass er dorthin zurückkehrt). Ähnlich verhält es sich in der umgekehrten Situation: Wenn der Agent viele Gegner vernichtet, steigt der Wert des Raums.

Markow-Modell

Was wäre, wenn wir die gesammelten Daten zur Vorhersage nutzen? Wenn wir uns jeden Raum merken, in dem wir während eines bestimmten Zeitraums einen Spieler gesehen haben, können wir vorhersagen, in welchen Raum der Spieler gehen könnte. Indem wir die Bewegungen des Spielers durch die Räume (Werte) verfolgen und aufzeichnen, können wir deren Verhalten prognostizieren.

Nehmen wir an, es gibt drei Räume: einen roten, einen grünen und einen blauen. Und außerdem die Beobachtungen, die wir während einer Spielsitzung aufgezeichnet haben:

Die Anzahl der Beobachtungen für jeden Raum ist nahezu gleich – wo wir den besten Platz für einen Hinterhalt einrichten können, wissen wir noch nicht. Die Datensammlung wird zudem durch das Respawning der Spieler erschwert, die gleichmäßig auf der Karte erscheinen. Doch die Informationen über den nächsten Raum, in den sie nach dem Auftauchen auf der Karte gehen, sind bereits nützlich.

Es ist offensichtlich, dass der grüne Raum bei den Spielern beliebt ist – die Mehrheit der Personen aus dem roten Raum wechselt dorthin, wobei 50 % weiterhin dort bleiben. Der blaue Raum hingegen erfreut sich keiner Beliebtheit; kaum jemand betritt ihn, und wenn doch, verweilen sie nicht lange.

Die Daten zeigen uns etwas Wichtigeres: Wenn ein Spieler sich im blauen Raum befindet, ist der nächste Raum, in dem wir ihn wahrscheinlich sehen werden, rot und nicht grün. Obwohl 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 wechseln wird) hängt vom vorherigen Zustand (also dem Raum, in dem sich der Spieler derzeit befindet) ab. Durch die Untersuchung dieser Abhängigkeiten können wir genauere Vorhersagen treffen, als wenn wir 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, während solche Beispiele (mit Räumen) Markov-Ketten genannt werden. Da diese Modelle die Wahrscheinlichkeit von Änderungen zwischen aufeinanderfolgenden Zuständen darstellen, werden sie visuell als FSM mit Wahrscheinlichkeiten für jeden Übergang angezeigt. Zuvor verwendeten wir FSM, um den Verhaltenszustand des Agenten darzustellen, aber dieses Konzept gilt für 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, die es der KI ermöglicht, den nächsten Zustand vorherzusagen. Man kann mehrere Schritte im Voraus vorhersagen.

Wenn sich der Spieler im grünen Raum befindet, beträgt die Wahrscheinlichkeit 50 %, dass er bei der nächsten Beobachtung dort bleibt. Aber wie hoch ist die Wahrscheinlichkeit, dass er auch danach noch dort ist? Es gibt nicht nur die Wahrscheinlichkeit, dass der Spieler nach zwei Beobachtungen im grünen Raum bleibt, sondern auch die Möglichkeit, dass er gegangen ist und zurückgekehrt ist. Hier ist eine neue Tabelle, die diese neuen Informationen berücksichtigt:

Aus der Tabelle geht hervor, dass die Wahrscheinlichkeit, den Spieler nach zwei Beobachtungen im grünen Raum zu sehen, 51 % beträgt. Davon 21 %, dass er aus dem roten Raum kommt, 5 %, dass der Spieler zwischenzeitlich den blauen Raum besucht hat, und 25 %, dass der Spieler überhaupt nicht aus dem grünen Raum gegangen ist.

Die Tabelle ist ein einfaches visuelles Werkzeug – das Verfahren erfordert nur, dass man die Wahrscheinlichkeiten in jedem Schritt multipliziert. Das bedeutet, dass Sie weit in die Zukunft blicken können, mit einer Ausnahme: Wir gehen davon aus, dass die Chance, einen Raum zu betreten, ausschließlich von dem aktuellen Raum abhängt. Dies wird als Markow-Eigenschaft bezeichnet – der zukünftige Zustand hängt nur von der Gegenwart ab. Doch das ist nicht hundertprozentig genau. Spieler können Entscheidungen basierend auf anderen Faktoren ändern: Gesundheitslevel oder Anzahl der Munition. Da wir diese Werte nicht festhalten, werden unsere Vorhersagen weniger präzise sein.

N-Gramme

Wie sieht es mit dem Beispiel eines Kampfspiels und der Vorhersage von Komboangriffen des Spielers aus? Dasselbe! Aber anstelle eines einzelnen Zustands oder Ereignisses werden wir ganze Sequenzen untersuchen, aus denen der Komboangriff besteht.

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

(Fett markierte Zeilen, wenn der Spieler die SuperDeathFist-Attacke ausführt.)

Die KI wird alle Möglichkeiten sehen, wenn der Spieler Kick gefolgt von einem weiteren Kick auswählt, und danach bemerken, dass die nächste Eingabe immer Punch ist. Das ermöglicht dem Agenten, die SuperDeathFist-Kombo vorherzusagen und sie gegebenenfalls zu blockieren.

Diese Abfolgen werden N-Gramme (N-grams) genannt, wobei N die Anzahl der gespeicherten Elemente ist. Im vorherigen Beispiel handelte es sich um ein 3-Gramm (Trigramm), was bedeutet: Die ersten beiden Aufzeichnungen werden verwendet, um die dritte vorherzusagen. In einer 5-Gramm sagen die ersten vier Aufzeichnungen die fünfte vorher und so weiter.

Der Entwickler muss die Größe der N-Gramme sorgfältig wählen. Eine kleinere Zahl von N benötigt weniger Speicher, speichert aber auch weniger Historie. Zum Beispiel wird ein 2-Gramm (Bigramm) Kick, Kick oder Kick, Punch aufzeichnen, kann jedoch Kick, Kick, Punch nicht speichern, weshalb die KI nicht auf die SuperDeathFist-Kombo reagiert.

Auf der anderen Seite erfordern große Zahlen mehr Speicher, und es wird schwieriger für die KI, zu lernen, da es viel mehr mögliche Optionen gibt. Wenn Sie drei mögliche Eingaben wie Kick, Punch oder Block hatten und wir ein 10-Gramm-Modell verwendet haben, ergibt sich etwa 60.000 verschiedene Optionen.

Das Bigramm-Modell ist eine einfache Markov-Kette — jedes Paar "vergangener Zustand / aktueller Zustand" stellt ein Bigramm dar, und Sie können den zweiten Zustand basierend auf dem ersten vorhersagen. 3-Gramm- und größere N-Gramm-Modelle können ebenfalls als Markov-Ketten betrachtet werden, bei denen alle Elemente (außer dem letzten im N-Gramm) zusammen den ersten Zustand bilden, während das letzte Element den zweiten Zustand darstellt. Das Beispiel mit dem Kampfspiel zeigt die Übergangswahrscheinlichkeit vom Zustand Kick und Kick zu Kick und Punch. Wenn wir mehrere Aufzeichnungen der Eingabevergangenheit als eine Einheit betrachten, transformieren wir im Wesentlichen die Eingabesequenz in einen Teil eines Gesamtzustands. Dies gibt uns die Markov-Eigenschaft, die es ermöglicht, Markov-Ketten zu verwenden, um die nächste Eingabe vorherzusagen und zu raten, welcher Kombinationszug als nächstes kommt.

Fazit

Wir haben über die gängigsten Werkzeuge und Ansätze in der Entwicklung von Künstlicher Intelligenz gesprochen. Außerdem haben wir Situationen erörtert, in denen sie angewendet werden müssen und wo sie besonders nützlich sind.

Das sollte ausreichen, um die grundlegenden Dinge im Bereich des Game AI zu verstehen. Natürlich ist das jedoch bei weitem nicht alles. Zu den weniger populären, aber nicht weniger effektiven Methoden gehören:

• Optimierungsalgorithmen, einschließlich Hill Climbing, Gradient Descent und genetischen Algorithmen.
• Wettbewerbsfähige Such-/Planungsalgorithmen (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 zur KI (hybride Systeme, Teilmengen von Architekturen und andere Methoden zur Überlagerung von KI-Systemen).
• Animationswerkzeuge (Planung und Koordinierung von Bewegungen).
• Leistungsfaktoren (Detailierungsgrad, Anytime-Algorithmen und Timeslicing).

Internetressourcen zu diesem 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 von Themen im Bereich der Entwicklung von Game AI.
3. Der 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, erstellt Videos auf dem YouTube-Kanal AI and Games mit Erklärungen und Untersuchungen zur KI in kommerziellen Spielen.

Bücher zu dem Thema:

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

Game AI Pro: Gesammeltes Wissen von Game AI-Profis
Game AI Pro 2: Gesammeltes Wissen von Game AI-Profis
Game AI Pro 3: Gesammeltes Wissen von Game AI-Profis

2. Die Reihe AI Game Programming Wisdom ist der Vorläufer der Serie Game AI Pro. Sie enthält ältere Methoden, die jedoch bis heute fast alle relevant sind.

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 eines der grundlegenden Werke für alle, die sich mit dem allgemeinen Bereich der künstlichen Intelligenz auseinandersetzen möchten. Dieses Buch behandelt nicht die Spielentwicklung — es lehrt die grundlegenden Prinzipien der KI.

Quelle: habr.com