Einführung

Dieser Artikel führt Sie in eine Vielzahl von Konzepten der künstlichen Intelligenz in Spielen ein („Gaming-KI“), damit Sie verstehen, mit welchen Tools KI-Probleme gelöst werden können, wie sie zusammenarbeiten und wie Sie sie in der ausgewählten Engine implementieren können.

Ich gehe davon aus, dass Sie mit Videospielen vertraut sind, die sich mit mathematischen Konzepten wie Geometrie, Trigonometrie usw. auskennen. Die meisten Codebeispiele werden in Pseudocode geschrieben, sodass Sie keine bestimmte Sprache kennen müssen.

Was ist eine "Gaming-KI"?

Die Spiel-KI befasst sich hauptsächlich mit der Auswahl von Aktionen einer Entität in Abhängigkeit von den aktuellen Bedingungen. In der traditionellen KI-Literatur wird es als Management von " intelligenten Agenten " bezeichnet. Der Agent ist normalerweise ein Charakter im Spiel, aber es kann eine Maschine, ein Roboter oder sogar etwas Abstrakteres sein - eine ganze Gruppe von Wesenheiten, ein Land oder eine Zivilisation. In jedem Fall ist es ein Objekt, das seine Umgebung überwacht, darauf basierende Entscheidungen trifft und in Übereinstimmung mit diesen Entscheidungen handelt. Dies wird manchmal als Wahrnehmungs-Denk-Handlungszyklus (Sinn / Denken / Handeln) bezeichnet:

• Wahrnehmung: Der Agent erkennt Informationen über die Umgebung, die sein Verhalten beeinflussen können, oder wird darüber informiert (z. B. Gefahren in der Nähe, gesammelte Gegenstände, wichtige Punkte usw.).
• Denken: Der Agent entscheidet, wie er reagiert (z. B. entscheidet er, ob es sicher ist, Gegenstände zu sammeln, ob er kämpfen oder sich zuerst verstecken soll).
• Aktion: Der Agent führt Aktionen aus, um seine Entscheidungen umzusetzen (z. B. beginnt er sich auf dem Weg zum Feind oder zum Subjekt zu bewegen usw.).
• ... dann ändert sich aufgrund der Aktionen der Charaktere die Situation, sodass der Zyklus mit neuen Daten wiederholt werden sollte.

Reale KI-Aufgaben, insbesondere solche, die heute relevant sind, konzentrieren sich normalerweise auf die „Wahrnehmung“. Zum Beispiel sollten unbemannte Fahrzeuge Bilder der Straße vor sich erhalten, diese mit anderen Daten (Radar und Lidar) kombinieren und versuchen, das zu interpretieren, was sie sehen. Normalerweise wird diese Aufgabe durch maschinelles Lernen gelöst, das besonders gut mit großen Arrays von verrauschten Daten aus der realen Welt (z. B. mit Fotos der Straße vor dem Auto oder einigen Videobildern) funktioniert und ihnen eine Bedeutung gibt, indem sie semantische Informationen extrahieren, z. B. „20 Meter vor mir ein anderes Auto. " Solche Aufgaben werden Klassifizierungsprobleme genannt .

Spiele sind insofern ungewöhnlich, als sie kein komplexes System benötigen, um diese Informationen zu extrahieren, da sie ein wesentlicher Bestandteil der Simulation sind. Es ist nicht erforderlich, Bilderkennungsalgorithmen auszuführen, um den Feind vor Ihnen zu erkennen. Das Spiel weiß, dass es einen Feind gibt und kann diese Informationen direkt an den Entscheidungsprozess übertragen. Daher wird die „Wahrnehmung“ in diesem Zyklus normalerweise stark vereinfacht, und die gesamte Komplexität entsteht bei der Implementierung von „Denken“ und „Handeln“.

Einschränkungen bei der Entwicklung der Spiel-KI

Die Spiel-KI berücksichtigt normalerweise die folgenden Einschränkungen:

• Im Gegensatz zum Algorithmus für maschinelles Lernen trainiert er normalerweise nicht im Voraus. Bei der Entwicklung eines Spiels ist es unpraktisch, ein neuronales Netzwerk zu schreiben, um Zehntausende von Spielern zu überwachen, um den besten Weg zu finden, gegen sie zu spielen, da das Spiel noch nicht veröffentlicht wurde und keine Spieler hat!
• Es wird normalerweise davon ausgegangen, dass das Spiel den Spieler unterhalten und herausfordern sollte und nicht „optimal“ ist. Selbst wenn Sie Agenten trainieren können, um den Spielern bestmöglich zu widerstehen, benötigen Designer meistens etwas anderes als sie.
• Oft müssen Agenten ein „realistisches“ Verhalten haben, damit die Spieler das Gefühl haben, mit menschenähnlichen Gegnern zu konkurrieren. Das AlphaGo-Programm erwies sich als viel besser als Menschen, aber die Bewegungen, die es wählt, sind so weit vom traditionellen Verständnis des Spiels entfernt, dass erfahrene Gegner von einem Spiel gegen einen Außerirdischen sprachen. Wenn das Spiel vorgibt, ein menschlicher Gegner zu sein, ist dies normalerweise unerwünscht. Daher muss der Algorithmus so eingerichtet werden, dass er plausible und keine idealen Entscheidungen trifft.
• AI muss in Echtzeit ausgeführt werden. In diesem Zusammenhang bedeutet dies, dass der Algorithmus für eine Entscheidung Prozessorressourcen für eine lange Zeit nicht monopolisieren kann. Selbst 10 Millisekunden, um eine Entscheidung zu treffen, sind zu viel, da die meisten Spiele nur 16 bis 33 Millisekunden haben, um alle Vorgänge für den nächsten Frame der Grafik abzuschließen.
• Im Idealfall sollte zumindest ein Teil des Systems von den Daten abhängen und nicht fest codiert sein, damit Nicht-Programmierer Änderungen schneller vornehmen können.

Nachdem wir all dies gelernt haben, können wir beginnen, äußerst einfache Ansätze zur Schaffung von KI zu betrachten, die den gesamten Zyklus von "Wahrnehmung-Denken-Handeln" auf eine Weise implementieren, die Effizienz gewährleistet und es Spieledesignern ermöglicht, komplexe Verhaltensweisen zu wählen, die menschlichen Handlungen ähnlich sind.

Einfache Entscheidungsfindung

Beginnen wir mit einem sehr einfachen Spiel wie Pong. Die Aufgabe des Spielers ist es, den "Schläger" so zu bewegen, dass der Ball von ihm abprallt, anstatt vorbei zu fliegen. Die Regeln sind ähnlich wie beim Tennis - Sie verlieren, wenn Sie den Ball verpassen. AI hat eine relativ einfache Aufgabe, Entscheidungen über die Wahl der Bewegungsrichtung des Schlägers zu treffen.

Hartcodierte bedingte Konstruktionen

Wenn wir KI schreiben wollten, um den Schläger zu steuern, gibt es eine intuitive und einfache Lösung - bewegen Sie den Schläger einfach ständig so, dass er unter dem Ball liegt. Wenn der Ball den Schläger erreicht, ist er bereits in perfekter Position und kann ihn treffen.

Ein einfacher Algorithmus hierfür, ausgedrückt in Pseudocode, könnte sein:

  in jedem Frame / Update, während das Spiel läuft:

 Wenn sich der Ball links vom Schläger befindet:

	 Bewegen Sie den Schläger nach links

 Andernfalls, wenn sich der Ball rechts vom Schläger befindet:

	 Bewegen Sie den Schläger nach rechts 

Wenn wir davon ausgehen, dass sich der Schläger mit nicht weniger Geschwindigkeit als der Ball bewegen kann, ist dies der perfekte Algorithmus für den KI-Spieler in Pong. In Fällen, in denen nicht so viele Wahrnehmungsdaten für die Verarbeitung vorhanden sind und nur wenige Aktionen vom Agenten ausgeführt werden können, benötigen wir nichts Komplizierteres.

Dieser Ansatz ist so einfach, dass er kaum den gesamten Zyklus von "Wahrnehmung-Denken-Handeln" zeigt. Aber er ist es .

• Wahrnehmungen sind zwei if-Aussagen. Das Spiel weiß, wo sich Ball und Schläger befinden. Daher fragt die KI das Spiel nach ihrer Position und „fühlt“, ob sich der Ball links oder rechts befindet.
• Das Denken besteht auch aus zwei if-Anweisungen. Sie enthalten zwei Lösungen, die sich in diesem Fall gegenseitig ausschließen und zur Auswahl einer von drei Aktionen führen: Bewegen Sie den Schläger nach links, bewegen Sie ihn nach rechts oder tun Sie nichts, wenn der Schläger bereits richtig positioniert ist.
• Eine "Aktion" besteht darin, "den Schläger nach links zu bewegen" oder "den Schläger nach rechts zu bewegen". Abhängig davon, wie das Spiel implementiert ist, kann dies die Form haben, die Position des Schlägers sofort zu verschieben oder die Geschwindigkeit und Richtung des Schlägers so einzustellen, dass er in einem anderen Spielcode richtig verschoben werden kann.

Solche Ansätze werden oft als "reaktiv" bezeichnet, da es ein einfaches Regelwerk gibt (in unserem Fall sind dies "if" -Anweisungen im Code), die auf den Zustand der Welt reagieren und sofort entscheiden, wie vorzugehen ist.

Entscheidungsbäume

Dieses Pong-Beispiel ähnelt dem formalen KI-Konzept, das als Entscheidungsbaum bezeichnet wird . Dies ist ein System, in dem Entscheidungen in Form eines Baums angeordnet sind und der Algorithmus ihn umgehen muss, um ein „Blatt“ zu erhalten, das die endgültige Entscheidung über die ausgewählte Aktion enthält. Zeichnen wir anhand eines Flussdiagramms eine grafische Darstellung des Entscheidungsbaums für den Pong-Schlägeralgorithmus:


Es ist zu sehen, dass es einem Baum ähnelt, nur verkehrt herum!

Jeder Teil des Entscheidungsbaums wird normalerweise als "Knoten" bezeichnet, da in der KI die Graphentheorie verwendet wird, um solche Strukturen zu beschreiben. Jeder Knoten kann einer von zwei Typen sein:

1. Lösungsknoten: Auswahl von zwei Alternativen basierend auf der Überprüfung einer Bedingung. Jede Alternative wird als eigener Knoten dargestellt.
2. Endknoten: Eine ausgeführte Aktion, die die endgültige Entscheidung des Baums darstellt.

Der Algorithmus beginnt mit dem ersten Knoten, der von der „Wurzel“ des Baums zugewiesen wurde. Danach entscheidet er entweder anhand der Bedingung, zu welchem ​​untergeordneten Knoten er wechseln soll, oder führt die im Knoten gespeicherte Aktion aus und funktioniert dann nicht mehr.

Auf den ersten Blick ist der Vorteil des Entscheidungsbaums nicht offensichtlich, da er genau die gleiche Aufgabe erfüllt wie die if-Anweisungen aus dem vorherigen Abschnitt. Es gibt jedoch ein sehr allgemeines System, in dem jede Lösung genau 1 Bedingung und 2 mögliche Ergebnisse aufweist, wodurch der Entwickler AI aus den Daten erstellen kann, die die Lösungen im Baum darstellen, und es vermeiden muss, sie hart in den Code zu schreiben. Es ist leicht, sich ein einfaches Datenformat zur Beschreibung eines solchen Baums vorzustellen:

Knotennummer	Entscheidung (oder "Ende")	Aktion	Aktion
1	Der Ball links vom Schläger?	Huh? Überprüfen Sie Knoten 2	Nein? Überprüfen Sie Knoten 3
2	Das Ende	Bewegen Sie den Schläger nach links
3	Der Ball rechts vom Schläger?	Huh? Gehen Sie zu Knoten 4	Nein? Gehen Sie zu Knoten 5
4	Das Ende	Bewegen Sie den Schläger nach rechts
5	Das Ende	Nichts tun

Aus Sicht des Codes müssen wir das System zwingen, jede dieser Zeilen zu lesen, für jeden Knoten zu erstellen, die Entscheidungslogik basierend auf der zweiten Spalte anzuhängen und untergeordnete Knoten basierend auf der dritten und vierten Spalte anzuhängen. Wir müssen die Bedingungen und Aktionen noch manuell definieren, aber jetzt können wir uns ein komplexeres Spiel vorstellen, in dem Sie neue Lösungen und Aktionen hinzufügen und die gesamte KI konfigurieren können, indem Sie die einzige Textdatei ändern, die die Baumdefinition enthält. Wir können die Datei an den Spieledesigner übertragen, der das Verhalten anpassen kann, ohne das Spiel neu kompilieren und den Code ändern zu müssen - vorausgesetzt, der Code verfügt bereits über nützliche Bedingungen und Aktionen.

Entscheidungsbäume können sehr leistungsfähig sein, wenn sie automatisch anhand einer Vielzahl von Beispielen erstellt werden (z. B. mithilfe des ID3-Algorithmus ). Es macht sie zu einem effektiven und leistungsstarken Tool zur Klassifizierung der Situation auf der Grundlage eingehender Daten. Dieses Thema liegt jedoch außerhalb des Bereichs der Designer, einfache Systeme zur Auswahl von Aktionen für Agenten zu erstellen.

Skripting

Oben haben wir ein Entscheidungsbaumsystem untersucht, das vorab erstellte Bedingungen und Aktionen verwendet. Der KI-Entwickler kann den Baum nach Belieben neu erstellen, sollte sich jedoch darauf verlassen, dass der Programmierer bereits alle erforderlichen Bedingungen und Aktionen für ihn erstellt hat. Aber was ist, wenn wir dem Designer leistungsfähigere Werkzeuge geben, mit denen er seine eigenen Bedingungen und möglicherweise seine Handlungen erstellen kann?

Zum Beispiel, anstatt den Encoder zu zwingen, die Bedingungen "Ball links vom Schläger?" Zu schreiben. und „Der Ball rechts vom Schläger?“ ​​kann er einfach ein System erstellen, in das der Designer die Bedingungen für die Überprüfung dieser Werte unabhängig schreibt. Infolgedessen können die Entscheidungsbaumdaten folgendermaßen aussehen:

Knotennummer	Entscheidung (oder "Ende")	Lösung	Aktion
1	ball.position.x <paddle.position.x	Huh? Überprüfen Sie Knoten 2	Nein? Überprüfen Sie Knoten 3
2	Das Ende	Bewegen Sie den Schläger nach links
3	ball.position.x> paddle.position.x	Huh? Überprüfen Sie Knoten 4	Nein? Überprüfen Sie Knoten 5
4	Das Ende	Bewegen Sie den Schläger nach rechts
5	Das Ende	Nichts tun

Das gleiche wie zuvor, aber jetzt haben die Lösungen ihren eigenen Code, ähnlich dem bedingten Teil der if-Anweisung. Der Code liest die Entscheidungsknoten aus der zweiten Spalte und berechnet den bedingten Ausdruck und gibt true oder false zurück, anstatt nach einer bestimmten Bedingung zu suchen (z. B. „der Ball links vom Schläger?“). Dies kann implementiert werden, indem eine Skriptsprache wie Lua oder Angelscript eingebettet wird, mit der der Entwickler Objekte aus dem Spiel (z. B. einen Ball und einen Schläger) entnehmen und Variablen erstellen kann, auf die über das Skript zugegriffen werden kann (z. B. ball.position). Es ist normalerweise einfacher, in einer Skriptsprache zu schreiben als in C ++, und es erfordert keine vollständige Kompilierungsphase. Daher eignet es sich gut für schnelle Änderungen an der Spiellogik und ermöglicht es weniger technisch versierten Teammitgliedern, Spielfunktionen ohne Eingreifen eines Encoders zu erstellen.

Im obigen Beispiel wird die Skriptsprache nur zum Auswerten des bedingten Ausdrucks verwendet. Die endgültigen Aktionen können jedoch auch im Skript beschrieben werden. Beispielsweise können diese Aktionen vom Typ "Verschieben des Schlägers nach rechts" zu einem ball.position.x += 10 wie " ball.position.x += 10 werden. Das heißt, die Aktion wird auch im Skript festgelegt, ohne den MovePaddleRight-Funktionscode zu schreiben.

Wenn Sie einen weiteren Schritt nach vorne machen, können Sie (und dies geschieht häufig) zu seiner logischen Schlussfolgerung gehen und den gesamten Entscheidungsbaum in einer Skriptsprache und nicht als Liste von Datenzeilen schreiben. Dies ist ein Code, der den oben gezeigten bedingten Konstruktionen ähnelt, nur dass sie nicht „fest codiert“ sind - sie befinden sich in externen Skriptdateien, dh sie können geändert werden, ohne das gesamte Programm neu zu kompilieren. Es ist oft sogar möglich, die Skriptdatei während der Spielausführung zu ändern, wodurch Entwickler schnell verschiedene Ansätze zur Implementierung von KI testen können.

Reaktion auf Ereignisse

Die oben gezeigten Beispiele sind für die Einzelbildausführung in einfachen Spielen wie Pong vorgesehen. Die Idee ist, dass sie kontinuierlich einen Zyklus von "Wahrnehmung-Denken-Handeln" durchführen und weiterhin auf der Grundlage des letzten Zustands der Welt handeln. In komplexeren Spielen ist es jedoch oft sinnvoller, auf „Ereignisse“ zu reagieren, dh auf wichtige Änderungen in der Spielumgebung, anstatt zu rechnen.

Dies gilt nicht besonders für Pong. Wählen wir also ein anderes Beispiel. Stellen Sie sich ein Shooter-Spiel vor, in dem Feinde bewegungslos sind, bis sie einen Spieler finden. Danach beginnen sie, abhängig von ihrer Klasse Aktionen auszuführen. Nahkämpfer können auf den Spieler zueilen, und Scharfschützen bleiben auf Distanz und versuchen zu zielen. Im Wesentlichen ist dies ein einfaches reaktives System - „Wenn wir einen Spieler sehen, dann tun wir etwas“ -, das jedoch logisch in ein Ereignis („einen Spieler sehen“) und eine Reaktion (eine Antwort auswählen und ausführen) unterteilt werden kann.

Dies bringt uns zurück zum Zyklus von Wahrnehmung, Denken und Handeln. Möglicherweise haben wir ein Codefragment, bei dem es sich um einen Wahrnehmungscode handelt, der in jedem Frame prüft, ob der Feind den Spieler sieht. Wenn nicht, passiert nichts. Aber wenn er sieht, erzeugt dies ein Ereignis "den Spieler sehen". Der Code wird einen separaten Teil haben, der besagt: „Wenn das Ereignis„ Den Spieler sehen “eintritt, dann machen wir„ xyz “und„ xyz “ist jede Antwort, die wir zum Denken und Handeln verarbeiten möchten. Für einen Charakterkämpfer können Sie die Lauf- und Angriffsreaktion mit dem Ereignis "Den Spieler sehen" verbinden. Für den Scharfschützen verbinden wir die Antwortfunktion "Verstecken und Zielen" mit diesem Ereignis. Wie in den vorherigen Beispielen können wir solche Zuordnungen in der Datendatei erstellen, damit sie schnell geändert werden können, ohne die Engine neu zu erstellen. Darüber hinaus ist es möglich (und dies wird häufig verwendet), solche Antwortfunktionen in einer Skriptsprache zu schreiben, damit sie bei Auftreten komplexer Ereignisse komplexe Lösungen erstellen können.

Verbesserte Entscheidungsfindung

Obwohl einfache reaktive Systeme sehr leistungsfähig sind, gibt es viele Situationen, in denen sie nicht ausreichen. Manchmal müssen wir unterschiedliche Entscheidungen treffen, je nachdem, was der Agent gerade tut, und es ist unpraktisch, sie als Bedingung darzustellen. Manchmal gibt es einfach zu viele Bedingungen, um sie effektiv in Form eines Entscheidungsbaums oder Skripts darzustellen. Manchmal müssen wir im Voraus überlegen und bewerten, wie sich die Situation ändern wird, bevor wir uns für den nächsten Schritt entscheiden. Für solche Aufgaben werden komplexere Lösungen benötigt.

Zustandsautomaten

Eine Finite-State-Maschine (FSM) ist eine Möglichkeit, mit anderen Worten zu sagen, dass sich ein Objekt - beispielsweise einer unserer KI-Agenten - derzeit in einem von mehreren möglichen Zuständen befindet und von dem es ausgehen kann ein Staat zum anderen. Es gibt eine endliche Anzahl solcher Zustände, daher der Name. Ein Beispiel aus der realen Welt ist die Ampel, die von rot nach gelb, dann nach grün und wieder zurück wechselt. An verschiedenen Orten gibt es verschiedene Lichtfolgen, aber das Prinzip ist das gleiche - jeder Zustand bedeutet etwas ("stehen", "essen", "stehen, wenn möglich" usw.), zu einem bestimmten Zeitpunkt gibt es nur einen Zustand, und Übergänge zwischen ihnen basieren auf einfachen Regeln.

Dies gilt gut für NPCs in Spielen. Die Wache kann die folgenden klar getrennten Zustände haben:

• Patrouille
• Angriff
• Flug

Und wir können die folgenden Regeln für den Übergang zwischen Staaten aufstellen:

• Wenn der Wachmann den Feind sieht, greift er an
• Wenn der Wachmann angreift, den Feind aber nicht mehr sieht, patrouilliert er wieder
• Wenn ein Wachmann angreift, aber schwer verletzt ist, entkommt er

Dieses Schema ist recht einfach und wir können es mit genau definierten "Wenn" -Operatoren und einer Variablen aufschreiben, in der der Zustand der Wache und verschiedene Kontrollen gespeichert werden - die Anwesenheit von Feinden in der Nähe, das Gesundheitsniveau der Wache usw. Aber stellen Sie sich vor, wir müssen noch ein paar Zustände hinzufügen:

• Warten (zwischen Patrouillen)
• Suche (wenn sich der zuvor gesehene Feind versteckt hat)
• Flucht um Hilfe (wenn der Feind entdeckt wird, aber er zu stark ist, um mit ihm allein zu kämpfen)

Und die Auswahlmöglichkeiten in jedem Bundesstaat sind normalerweise begrenzt - zum Beispiel wird ein Wachmann wahrscheinlich nicht nach einem Feind suchen wollen, der aus den Augen verloren wurde, wenn seine Gesundheit zu niedrig ist.

Früher oder später wird die lange Liste von "wenn <x und y, aber nicht z> dann <p>" zu umständlich, und ein formalisierter Ansatz zur Implementierung von Zuständen und Übergängen zwischen ihnen kann hier helfen. Dazu betrachten wir alle Zustände und listen unter jedem Zustand alle Übergänge zu anderen Zuständen zusammen mit den dafür erforderlichen Bedingungen auf. Wir müssen auch den Anfangszustand angeben, damit wir wissen, wo wir anfangen sollen, bevor wir andere Bedingungen anwenden.

Zustand	Übergangsbedingung	Neuer Zustand
Warten	erwartet für 10 Sekunden	Patrouille
	Der Feind ist sichtbar und der Feind ist zu stark	Hilfesuche
	Der Feind ist sichtbar und viel Gesundheit	Angriff
	Der Feind ist sichtbar und wenig Gesundheit	Flug
Patrouille	Patrouillenroute abgeschlossen	Warten
	Der Feind ist sichtbar und der Feind ist zu stark	Hilfesuche
	Der Feind ist sichtbar und viel Gesundheit	Angriff
	Der Feind ist sichtbar und wenig Gesundheit	Flug
Angriff	Der Feind ist nicht sichtbar	Warten
	wenig Gesundheit	Flug
Flug	Der Feind ist nicht sichtbar	Warten
Suche	10 Sekunden lang gesucht	Warten
	Der Feind ist sichtbar und der Feind ist zu stark	Hilfesuche
	Der Feind ist sichtbar und viel Gesundheit	Angriff
	Der Feind ist sichtbar und wenig Gesundheit	Flug
Hilfesuche	Freund sehen	Angriff
Ausgangszustand: Warten

Ein solches Schema wird als Zustandsübergangstabelle bezeichnet. Es ist eine komplexe (und unattraktive) Art, ein Raumschiff darzustellen. Aus diesen Daten können Sie auch ein Diagramm zeichnen und eine komplexe grafische Darstellung des Verhaltens von NPCs erhalten.


Es erfasst das Wesentliche, Entscheidungen für den Agenten basierend auf der Situation zu treffen, in der er sich befindet. Jeder Pfeil zeigt einen Übergang zwischen Zuständen an, wenn die Bedingung neben dem Pfeil erfüllt ist.

Bei jeder Aktualisierung (oder jedem „Zyklus“) überprüfen wir den aktuellen Status des Agenten, sehen uns die Liste der Übergänge an und wechseln in einen neuen Status, wenn die Übergangsbedingung erfüllt ist. Der Status "Ausstehend" prüft in jedem Frame oder Zyklus, ob der 10-Sekunden-Timer abgelaufen ist. Wenn es abgelaufen ist, wird der Übergang in den Status "Patrouille" gestartet. In ähnlicher Weise prüft der Status "Angriff", ob der Agent viel Gesundheit hat, und wenn ja, wechselt er in den Status "Flug".

So werden Zustandsübergänge behandelt - aber was ist mit den Verhaltensweisen, die mit den Zuständen selbst verbunden sind? Unter dem Gesichtspunkt, die Aktionen selbst für einen Staat auszuführen, gibt es normalerweise zwei Arten, Aktionen an ein Raumschiff anzuhängen:

1. Aktionen für den aktuellen Status werden periodisch ausgeführt, beispielsweise in jedem Rahmen oder "Zyklus".
2. Aktionen werden während des Übergangs von einem Zustand in einen anderen ausgeführt.

Ein Beispiel für den ersten Typ: Der Status "Patrouille" in jedem Frame oder Zyklus bewegt den Agenten weiterhin entlang der Patrouillenroute. Der Status „Angriff“ in jedem Frame oder Zyklus versucht, einen Angriff zu starten oder an eine Position zu verschieben, von der aus dies möglich ist. Usw.

Ein Beispiel für den zweiten Typ: Betrachten Sie den Übergang "Wenn der Feind sichtbar und der Feind zu stark ist → Suche nach Hilfe". Der Agent muss auswählen, wohin er umziehen möchte, um Hilfe zu suchen, und diese Informationen speichern, damit der Status "Hilfesuche" weiß, wohin er gehen soll. In ähnlicher Weise kehrt der Agent im Status "Hilfesuche", wenn Hilfe gefunden wird, wieder in den Status "Angriff" zurück. In diesem Moment möchte er jedoch den freundlichen Charakter über die Bedrohung informieren, sodass während dieses Übergangs möglicherweise die Aktion "Einen Freund über die Gefahr informieren" ausgeführt wird.

Und hier können wir dieses System noch einmal unter dem Gesichtspunkt „Wahrnehmung-Denken-Handeln“ betrachten. Die Wahrnehmung ist in die von der Übergangslogik verwendeten Daten eingebettet. Das Denken ist in die Übergänge eingebaut, die für jeden Zustand verfügbar sind. Und die Aktion wird durch Aktionen ausgeführt, die periodisch in einem Zustand oder während des Übergangs zwischen Zuständen ausgeführt werden.

Dieses einfache System funktioniert gut, obwohl das ständige Abrufen von Übergangsbedingungen manchmal ein kostspieliger Prozess sein kann. Wenn beispielsweise jeder Agent in jedem Frame komplexe Berechnungen durchführen muss, um die Sichtbarkeit von Feinden zu bestimmen und über den Übergang von Patrouille zu Angriff zu entscheiden, kann dies viel Prozessorzeit in Anspruch nehmen. Wie wir bereits gesehen haben, ist es möglich, wichtige Veränderungen im Zustand der Welt als „Ereignisse“ wahrzunehmen, die verarbeitet werden, nachdem sie eingetreten sind. Anstatt die Übergangsbedingung "Kann mein Agent den Spieler sehen?" Explizit zu überprüfen, können wir daher in jedem Frame ein separates Sichtbarkeitssystem erstellen, das diese Überprüfungen etwas seltener durchführt (z. B. 5 Mal pro Sekunde) und den "Spieler" erstellt siehe ”, wenn der Test ausgelöst wird. Es wird an die Zustandsmaschine übertragen, die nun die Bedingung für den Übergang "Empfangen des Ereignisses" Spieler sehen "" hat und entsprechend darauf reagiert. Das resultierende Verhalten wird ähnlich sein, mit Ausnahme einer kaum wahrnehmbaren (und sogar zunehmenden realistischen) Reaktionsverzögerung, aber die Produktivität wird aufgrund der Übertragung der „Wahrnehmung“ auf einen separaten Teil des Programms steigen.

Hierarchische Zustandsmaschinen

All dies ist gut, aber mit großen Zustandsautomaten wird es sehr unpraktisch zu arbeiten. Wenn wir den Status "Angriff" erweitern möchten, indem wir ihn durch separate Zustände "Nahkampfangriff" und "Angriff aus der Ferne" ersetzen, müssen wir die eingehenden Übergänge von jedem gegenwärtigen und zukünftigen Status ändern, der die Fähigkeit benötigt, in den Status "Angriff" zu wechseln.

Sie haben wahrscheinlich auch bemerkt, dass es in unserem Beispiel viele doppelte Übergänge gibt. Die meisten Übergänge im Status "Ausstehend" sind identisch mit Übergängen im Status "Patrouille", und es wäre schön, Doppelarbeit zu vermeiden, insbesondere wenn wir noch ähnlichere Zustände hinzufügen möchten. Es ist logisch, "Warten" und "Patrouillieren" in einer Gruppe "Nichtkampfstaaten" zu kombinieren, die nur einen gemeinsamen Satz von Übergängen zu Kampfstaaten aufweist. Wenn wir diese Gruppe als Zustand darstellen, können wir das „Warten“ und das „Patrouillieren“ als „Unterzustände“ dieses Zustands betrachten, wodurch wir das gesamte System effektiver beschreiben können. Ein Beispiel für die Verwendung einer separaten Umrechnungstabelle für einen neuen Nichtkampf-Unterzustand:

Die Hauptbedingungen:

Zustand	Übergangsbedingung	Neuer Zustand
Nicht im Kampf	Der Feind ist sichtbar und der Feind ist zu stark	Hilfesuche
	Der Feind ist sichtbar und viel Gesundheit	Angriff
	Der Feind ist sichtbar und wenig Gesundheit	Flug
Angriff	Der Feind ist nicht sichtbar	Nicht im Kampf
	wenig Gesundheit	Flug
Flug	Der Feind ist nicht sichtbar	Nicht im Kampf
Suche	10 Sekunden lang gesucht	Nicht im Kampf
	Der Feind ist sichtbar und der Feind ist zu stark	Hilfesuche
	Der Feind ist sichtbar und viel Gesundheit	Angriff
	Der Feind ist sichtbar und wenig Gesundheit	Flug
Hilfesuche	Freund sehen	Angriff
Ausgangszustand: Nichtkampf

Nichtkampfstatus:

Zustand	Übergangsbedingung	Neuer Zustand
Warten	erwartet für 10 Sekunden	Patrouille
Patrouille	beendete die Patrouillenroute	Warten
Ausgangszustand: Warten

Und in Diagrammform:


Tatsächlich ist dies das gleiche System, nur dass es jetzt einen Nichtkampfzustand gibt, der "Patrouille" und "Warten" ersetzt, die an sich eine Zustandsmaschine mit zwei Unterzuständen von Patrouillieren und Warten sind. Wenn jeder Zustand möglicherweise eine Zustandsmaschine von Unterzuständen enthalten kann (und diese Unterzustände können auch eine eigene Zustandsmaschine usw. enthalten), haben wir eine hierarchische Zustandsmaschine (HFSM). Durch die Gruppierung von Verhaltensweisen außerhalb des Kampfes werden eine Reihe unnötiger Übergänge abgeschnitten, und wir können dasselbe für alle neuen Zustände tun, die möglicherweise gemeinsame Übergänge aufweisen. Wenn wir beispielsweise in Zukunft den Status "Angriff" auf den Status "Nahkampfangriff" und "Projektilangriff" erweitern, können dies Unterzustände sein, deren Übergang auf der Entfernung zum Feind und dem Vorhandensein von Munition basiert und die gemeinsame Ausgangsübergänge auf der Grundlage des Gesundheitsniveaus und der Munition aufweisen andere Dinge. Somit können mit einem Minimum an doppelten Übergängen komplexe Verhaltensweisen und Unterverhalten dargestellt werden.

Verhaltensbäume

Mit HFSM haben wir die Möglichkeit, ziemlich komplexe Verhaltensweisen auf ziemlich intuitive Weise zu erstellen. Es fällt jedoch sofort auf, dass die Entscheidungsfindung in Form von Übergangsregeln eng mit dem aktuellen Stand zusammenhängt. Viele Spiele erfordern genau das. Durch sorgfältige Verwendung der Statushierarchie wird die Anzahl der doppelten Übergänge verringert. Aber manchmal brauchen wir Regeln, die unabhängig vom aktuellen Status oder in fast allen Bundesstaaten gelten. Wenn beispielsweise die Gesundheit des Agenten auf 25% gesunken ist, möchte er möglicherweise weglaufen, unabhängig davon, ob er sich im Kampf befindet, wartet oder spricht oder sich in einem anderen Zustand befindet. Wir möchten uns nicht daran erinnern, dass wir diese Bedingung zu jedem Zustand hinzufügen müssen, den wir dem Charakter in Zukunft hinzufügen können. Wenn der Designer später sagt, dass er den Schwellenwert von 25% auf 10% ändern möchte, müssen wir nicht jeden entsprechenden Übergang sortieren und ändern.

Ideal in einer solchen Situation war ein System, in dem Entscheidungen darüber, in welchem ​​Zustand man sich befindet, getrennt von den Zuständen selbst existieren, so dass wir nur ein Element ändern können und die Übergänge immer noch korrekt verarbeitet werden. Hier bieten sich Verhaltensbäume an.

Es gibt verschiedene Möglichkeiten, Verhaltensbäume zu implementieren, aber das Wesentliche ist für die meisten gleich und dem oben genannten Entscheidungsbaum sehr ähnlich: Der Algorithmus beginnt mit der Arbeit am „Wurzelknoten“, und es gibt Knoten im Baum, die Entscheidungen oder Aktionen anzeigen. Es gibt jedoch wesentliche Unterschiede:

• Knoten geben jetzt einen von drei Werten zurück: "erfolgreich" (wenn der Job abgeschlossen ist), "nicht erfolgreich" (wenn der Job nicht abgeschlossen wurde) oder "ausgeführt" (wenn der Job noch abgeschlossen ist und nicht vollständig erfolgreich war oder fehlgeschlagen ist).
• Jetzt haben wir keine Entscheidungsknoten, in denen wir aus zwei Alternativen auswählen können, aber es gibt Dekorationsknoten mit einem einzelnen untergeordneten Knoten. Wenn sie "erfolgreich" sind, führen sie ihren einzigen untergeordneten Knoten aus. Dekorationsknoten enthalten häufig Bedingungen, die bestimmen, ob die Ausführung mit Erfolg (was bedeutet, dass Sie ihren Teilbaum ausführen müssen) oder fehlgeschlagen ist (dann muss nichts getan werden). Sie können auch "in Bearbeitung" zurückkehren.
• Durchführen von Aktionsknoten geben den Wert "running" zurück, um anzuzeigen, was passiert.

Eine kleine Gruppe von Knoten kann kombiniert werden, wodurch eine große Anzahl komplexer Verhaltensweisen entsteht. Oft ist dieses Schema sehr kurz. Beispielsweise können wir die hierarchische Zertifizierungsstelle des Schutzes aus dem vorherigen Beispiel in Form eines Verhaltensbaums umschreiben:


Bei Verwendung dieser Struktur ist kein expliziter Übergang von den Zuständen "Warten" oder "Patrouillieren" zu den Zuständen "Angreifen" oder anderen Zuständen erforderlich. Wenn der Baum von oben nach unten und von links nach rechts durchlaufen wird, wird die richtige Entscheidung auf der Grundlage der aktuellen Situation getroffen. Wenn der Feind sichtbar ist und der Charakter wenig Gesundheit hat, schließt der Baum die Ausführung auf dem Knoten "Flug" ab, unabhängig vom zuvor ausgeführten Knoten ("Patrouille", "Warten", "Angriff" usw.).

Möglicherweise stellen Sie fest, dass wir noch keinen Übergang haben, um von "Patrol" in den Status "Warten" zurückzukehren - und hier werden bedingungslose Dekorateure nützlich sein. Der Standard-Dekorationsknoten ist "Wiederholen" - er hat keine Bedingungen, er fängt nur den untergeordneten Knoten ab, der "erfolgreich" zurückgibt, führt den untergeordneten Knoten erneut aus und gibt "ausgeführt" zurück. Der neue Baum sieht folgendermaßen aus:


Verhaltensbäume sind recht komplex, da es oft viele verschiedene Möglichkeiten gibt, einen Baum zu erstellen, und die richtige Kombination von Dekorations- und Komponentenknoten zu finden, kann eine entmutigende Aufgabe sein. Es gibt auch Probleme damit, wie oft wir den Baum überprüfen müssen (wollen wir ihn in jedem Frame durchlaufen oder wenn etwas passiert, das die Bedingungen beeinflussen kann?) Und wie der Status relativ zu den Knoten gespeichert wird (woher wissen wir, dass wir 10 Sekunden gewartet haben? Wie Werden wir herausfinden, wie viele Knoten zuletzt ausgeführt wurden, um die Sequenz korrekt zu vervollständigen?) Daher gibt es viele verschiedene Implementierungen. Beispielsweise werden auf einigen Systemen, wie dem Unreal Engine 4-Verhaltensbaumsystem, Dekorationsknoten durch Zeichenfolgendekoratoren ersetzt, die den Baum nur dann überprüfen, wenn sich die Dekorationsbedingungen ändern und „Dienste“ bereitstellen.Diese können mit Knoten verbunden werden und regelmäßige Aktualisierungen bereitstellen, auch wenn der Baum nicht erneut überprüft wird. Verhaltensbäume sind leistungsstarke Werkzeuge, aber das Erlernen ihrer korrekten Verwendung, insbesondere bei so vielen verschiedenen Implementierungen, kann eine entmutigende Aufgabe sein.

Dienstprogrammbasierte Systeme

Einige Spiele erfordern das Vorhandensein vieler verschiedener Aktionen, daher erfordern sie einfachere, zentralisierte Übergangsregeln, aber sie benötigen nicht die Fähigkeit, den Verhaltensbaum vollständig zu implementieren. Anstatt eine explizite Auswahl oder einen Baum potenzieller Aktionen mit impliziten Fallback-Positionen zu erstellen, die durch die Struktur des Baums definiert sind, ist es vielleicht besser, einfach alle Aktionen zu untersuchen und die derzeit am besten geeignete auszuwählen.

Dies ist, was Utility-basierte Systeme tun - dies sind Systeme, in denen der Agent über viele Aktionen verfügt, und er wählt eine aus, die auf dem relativen Utility basiertjede Handlung. Die Nützlichkeit ist hier ein willkürliches Maß für die Wichtigkeit oder den Wunsch eines Agenten, diese Aktion auszuführen. Durch das Schreiben von Dienstprogrammfunktionen zur Berechnung des Nutzens einer Aktion basierend auf dem aktuellen Status des Agenten und seiner Umgebung kann der Agent die Dienstprogrammwerte überprüfen und den derzeit am besten geeigneten Status auswählen.

Dies ist auch einer endlichen Zustandsmaschine sehr ähnlich, außer dass Übergänge durch eine Bewertung jedes möglichen Zustands, einschließlich des aktuellen, bestimmt werden. Es ist erwähnenswert, dass wir im allgemeinen Fall den Übergang zur wertvollsten Aktion wählen (oder dabei sind, wenn wir diese Aktion bereits ausführen), aber für eine größere Variabilität kann es sich um eine gewichtete zufällige Auswahl handeln (wobei der wertvollsten Aktion Vorrang eingeräumt wird, aber die Auswahl anderer zugelassen wird). , eine Auswahl von zufälligen Aktionen aus den Top 5 (oder einer anderen Menge) usw.

Das Standard-Utility-basierte System weist einen bestimmten willkürlichen Bereich von Utility-Werten zu - beispielsweise von 0 (völlig unerwünscht) bis 100 (absolut wünschenswert), und jede Aktion kann eine Reihe von Faktoren haben, die die Art und Weise beeinflussen, wie der Wert berechnet wird. Wenn wir zu unserem Beispiel mit der Wache zurückkehren, kann man sich so etwas vorstellen:

Aktion	Dienstprogrammberechnung
Hilfesuche	Wenn der Feind sichtbar und der Feind stark ist und die Gesundheit niedrig ist, geben Sie 100 zurück, andernfalls 0
Flug	Wenn der Feind sichtbar ist und wenig Gesundheit vorhanden ist, geben Sie 90 zurück, andernfalls 0
Angriff	Wenn der Feind sichtbar ist, geben Sie 80 zurück
Warten	Wenn wir warten und bereits 10 Sekunden warten, geben Sie 0 zurück, andernfalls 50
Patrouille	Wenn wir am Ende der Patrouillenroute sind, geben Sie 0 zurück, andernfalls 50

Einer der wichtigsten Aspekte dieses Schemas ist, dass die Übergänge zwischen Aktionen implizit ausgedrückt werden - von jedem Staat aus können Sie völlig legitim zu jedem anderen gehen. Darüber hinaus sind Aktionsprioritäten in den zurückgegebenen Dienstprogrammwerten enthalten. Wenn der Feind sichtbar ist und wenn er stark ist und der Charakter wenig Gesundheit hat, geben Werte ungleich Null die Flug- und Hilfesuche zurück , aber die Hilfesuche hat immer eine höhere Bewertung. In ähnlicher Weise geben Aktionen außerhalb des Kampfes niemals mehr als 50 zurück, sodass sie immer von den Kämpfen besiegt werden. In diesem Sinne werden Aktionen und ihre Nutzenberechnungen erstellt.

In unserem Beispiel geben Aktionen entweder einen konstanten Nutzwert oder einen von zwei konstanten Nutzwerten zurück. Ein realistischeres System verwendet einen Rückgabewert aus einem kontinuierlichen Wertebereich. Beispielsweise kann die Aktion " Flucht" höhere Nutzwerte zurückgeben, wenn der Zustand des Agenten geringer ist, und die Aktion " Angriff" kann niedrigere Nutzwerte zurückgeben, wenn der Feind zu stark ist. Dadurch kann Getaway Vorrang vor Assault haben.in jeder Situation, in der der Agent das Gefühl hat, nicht gesund genug zu sein, um den Feind zu bekämpfen. Auf diese Weise können Sie die relativen Prioritäten von Aktionen auf der Grundlage einer beliebigen Anzahl von Kriterien ändern, wodurch dieser Ansatz flexibler als ein Verhaltensbaum oder ein Raumschiff wird.

Jede Aktion hat normalerweise mehrere Bedingungen, die die Berechnung des Nutzens beeinflussen. Um nicht alles im Code fest zu machen, können Sie sie in einer Skriptsprache oder als eine Reihe mathematischer Formeln schreiben, die auf verständliche Weise zusammengestellt werden. Weitere Informationen hierzu finden Sie in Vorträgen und Präsentationen von Dave Mark ( @IADaveMark ).

In einigen Spielen, die versuchen, das tägliche Leben des Charakters zu simulieren, beispielsweise in Die Sims, wird eine weitere Berechnungsebene hinzugefügt, in der der Agent „Bestrebungen“ oder „Motivationen“ hat, die sich auf die Nutzwerte auswirken. Wenn ein Charakter beispielsweise die Hungermotivation hat, kann sie mit der Zeit zunehmen, und die Berechnung des Nutzens für die Aktion "Essen" gibt immer höhere Werte zurück, bis der Charakter diese Aktion ausführen kann, wodurch der Hunger und die Aktion " Essen “wird auf Null oder einen Wert nahe Null reduziert.

Die Idee, Aktionen basierend auf dem Punktesystem auszuwählen, ist ziemlich einfach. Es ist daher offensichtlich, dass Sie die Entscheidungsfindung basierend auf dem Nutzen in anderen KI-Entscheidungsprozessen verwenden und nicht vollständig durch diese ersetzen können. Der Entscheidungsbaum kann den Nutzwert seiner beiden untergeordneten Knoten abfragen und den Knoten mit dem höchsten Wert auswählen. In ähnlicher Weise kann ein Verhaltensbaum einen zusammengesetzten Dienstprogrammknoten haben, der das Dienstprogramm zählt, um den untergeordneten Knoten auszuwählen, der ausgeführt werden soll.

Bewegung und Navigation

In unseren vorherigen Beispielen gab es entweder einen einfachen Schläger, den wir von links nach rechts bewegen mussten, oder einen Wachcharakter, dem immer befohlen wurde, zu patrouillieren oder anzugreifen. Aber wie genau steuern wir die Bewegung eines Agenten über einen bestimmten Zeitraum? Wie können wir die Geschwindigkeit einstellen, Hindernissen ausweichen und eine Route planen, wenn es unmöglich ist, den Endpunkt direkt zu erreichen? Nun werden wir diese Aufgabe betrachten.

Lenkung

Auf der einfachsten Ebene ist es oft ratsam, mit jedem Agenten so zu arbeiten, als hätte er einen Geschwindigkeitswert, der die Geschwindigkeit und Richtung seiner Bewegung bestimmt. Diese Geschwindigkeit kann in Metern pro Sekunde, in Meilen pro Stunde, in Pixeln pro Sekunde usw. gemessen werden. Wenn wir uns an unseren Zyklus „Wahrnehmung-Denken-Handeln“ erinnern, können wir uns vorstellen, dass „Denken“ Geschwindigkeit wählen kann. Danach wendet „Handeln“ diese Geschwindigkeit auf den Agenten an und bewegt ihn um die Welt. Normalerweise gibt es in Spielen ein physikalisches System, das diese Aufgabe unabhängig ausführt, den Wert der Geschwindigkeit jeder Entität untersucht und ihre Position entsprechend ändert. Daher ist es häufig möglich, diesem System solche Arbeiten zuzuweisen, so dass die KI nur die Aufgabe hat, die Agentengeschwindigkeit zu wählen.

Wenn wir wissen, wo der Agent sein möchte, müssen wir unsere Geschwindigkeit nutzen, um den Agenten in diese Richtung zu bewegen. In einer trivialen Form erhalten wir die folgende Gleichung:

 Gewünschte Reise = Zielposition - Agentenposition 

Stellen Sie sich eine 2D-Welt vor, in der sich der Agent an den Koordinaten (-2, -2) befindet und der Zielpunkt ungefähr im Nordosten liegt, an den Koordinaten (30, 20), dh um dorthin zu gelangen, müssen Sie sich bewegen (32, 22). Nehmen wir an, dass diese Positionen in Metern angegeben sind. Wenn wir entscheiden, dass sich der Agent mit einer Geschwindigkeit von 5 m / s bewegen kann, reduzieren Sie die Skalierung des Verschiebungsvektors auf diesen Wert und sehen Sie, dass wir die Geschwindigkeit ungefähr (4.12, 2.83) einstellen müssen. Wenn sich der Agent basierend auf diesem Wert bewegt, erreicht er erwartungsgemäß in knapp 8 Sekunden den Endpunkt.

Berechnungen können jederzeit erneut durchgeführt werden. Befindet sich der Agent beispielsweise auf halber Strecke zum Ziel, ist die gewünschte Bewegung halb so groß, aber nach Skalierung auf die maximale Agentengeschwindigkeit von 5 m / s bleibt die Geschwindigkeit gleich. Dies funktioniert auch für sich bewegende Ziele (innerhalb eines angemessenen Rahmens), wodurch der Agent auf dem Weg kleine Anpassungen vornehmen kann.

Oft brauchen wir jedoch mehr Kontrolle. Zum Beispiel müssen wir möglicherweise die Geschwindigkeit langsam erhöhen, als ob der Charakter zuerst stehen geblieben wäre, dann zu einem Schritt übergegangen wäre und später gelaufen wäre. Auf der anderen Seite müssen wir es möglicherweise verlangsamen, wenn es sich dem Ziel nähert. Oft werden solche Aufgaben mit dem sogenannten " Lenkverhalten" gelöst."Sie haben ihre eigenen Namen wie" Suchen "," Fliehen "," Ankunft "usw. (Auf Habré gibt es eine Reihe von Artikeln über sie: https://habr.com/post/358366/ .) Ihre Idee ist, dass Sie die Agentengeschwindigkeit anwenden können Beschleunigungskräfte basierend auf einem Vergleich der Position des Agenten und der aktuellen Bewegungsgeschwindigkeit zum Ziel, wodurch verschiedene Arten der Bewegung zum Ziel geschaffen werden.

Jedes Verhalten hat seinen eigenen, etwas anderen Zweck. Suchen und Ankommen werden verwendet, um den Agenten an sein Ziel zu verschieben. Hindernisvermeidung und -trennung helfen dem Agenten, kleine Korrekturbewegungen auszuführen, um kleine Hindernisse zwischen dem Agenten und seinem Ziel zu umgehen. Ausrichtung und Zusammenhalt zwingen die Agenten, sich zusammen zu bewegen und Herdentiere nachzuahmen. Alle Variationen verschiedener Lenkverhalten können miteinander kombiniert werden, häufig in Form einer gewichteten Summe, um einen Gesamtwert zu erstellen, der all diese verschiedenen Faktoren berücksichtigt und einen einzelnen resultierenden Vektor erzeugt. Beispielsweise kann ein Agent das Ankunftsverhalten zusammen mit dem Verhalten von Trennung und Hindernisvermeidung verwenden, um sich von Wänden und anderen Agenten fernzuhalten. Dieser Ansatz funktioniert gut in offenen Umgebungen, die nicht zu komplex und überfüllt sind.

In komplexeren Umgebungen funktioniert das einfache Hinzufügen der Ausgabewerte des Verhaltens jedoch nicht sehr gut. Manchmal ist die Bewegung in der Nähe des Objekts zu langsam, oder der Agent bleibt hängen, wenn das Ankunftsverhalten das Hindernis passieren möchte, und das Verhalten zur Vermeidung von Hindernissen drückt den Agenten auf die Seite, von der es stammt . Daher ist es manchmal sinnvoll, Lenkverhaltensvariationen zu berücksichtigen, die komplizierter sind als das einfache Addieren aller Werte. Eine der Familien solcher Ansätze besteht in einer anderen Implementierung - wir berücksichtigen nicht jedes der Verhaltensweisen, die uns die Richtung geben, gefolgt von ihrer Kombination, um einen Konsens zu erzielen (was an sich möglicherweise unzureichend ist). Stattdessen betrachten wir Bewegungen in verschiedene Richtungen - zum Beispiel in acht Himmelsrichtungen oder an 5-6 Punkten vor dem Agenten.Danach wählen wir die besten.

In komplexen Umgebungen mit Sackgassen und Kurvenoptionen benötigen wir jedoch etwas Fortgeschritteneres, und wir werden bald darauf zurückkommen.

Wegfindung

Das Lenkverhalten eignet sich hervorragend für einfache Bewegungen in einem ziemlich offenen Bereich wie einem Fußballfeld oder einer Arena, in der Sie mit leichten Anpassungen in einer geraden Linie von A nach B gelangen können, um Hindernissen auszuweichen. Was aber, wenn der Weg zum Endpunkt komplizierter ist? Dann brauchen wir eine „Wegfindung“ - die Welt erkunden und einen Weg entlang zeichnen, damit der Agent den Endpunkt erreicht.

Der einfachste Weg ist, ein Gitter auf die Welt zu legen und für jede Zelle neben dem Agenten benachbarte Zellen zu betrachten, in die wir uns bewegen können. Wenn einer von ihnen unser Endpunkt ist, gehen Sie die Route von jeder Zelle zur vorherigen zurück, bis wir zum Anfang gelangen, und erhalten Sie so eine Route. Andernfalls wiederholen Sie den Vorgang mit den erreichbaren Nachbarn der vorherigen Nachbarn, bis wir den Endpunkt gefunden haben oder uns die Zellen ausgehen (dies bedeutet, dass es keine Route gibt). Formal wird dieser Ansatz als BFS- Algorithmus (Breadth-First Search) bezeichnet, da er bei jedem Schritt in alle Richtungen (dh „weit“) schaut, bevor die Suche verschoben wird. Der Suchraum ist wie eine Wellenfront, die sich bewegt, bis sie auf den Ort stößt, den wir gesucht haben.

Dies ist ein einfaches Beispiel für eine Suche in Aktion. Der Suchbereich wird in jeder Phase erweitert, bis ein Endpunkt darin enthalten ist. Anschließend können Sie den Pfad zum Anfang verfolgen.


Als Ergebnis erhalten wir eine Liste von Gitterzellen, die die Route bilden, die Sie gehen müssen. Normalerweise wird es als "Pfad" bezeichnet, Pfad (daher "Suche nach Pfaden", Pfadfindung), aber Sie können es sich auch als Plan vorstellen, da es sich um eine Liste von Orten handelt, die Sie besuchen müssen, um Ihr Ziel, dh den Endpunkt, zu erreichen.

Nachdem wir die Position jeder Zelle in der Welt kennen, können Sie das oben beschriebene Lenkverhalten verwenden, um sich entlang der Route zu bewegen - zuerst vom Startknoten zu Knoten 2, dann von Knoten 2 zu Knoten 3 und so weiter. Der einfachste Ansatz besteht darin, sich in Richtung der Mitte der nächsten Zelle zu bewegen, aber es gibt auch eine beliebte Alternative - sich in Richtung der Mitte der Rippe zwischen der aktuellen Zelle und der nächsten zu bewegen. Dies ermöglicht es dem Agenten, Ecken scharfer Kurven zu schneiden, um eine realistischere Bewegung zu erzeugen.

Wie Sie sehen, kann dieser Algorithmus Ressourcen verschwenden, da er so viele Zellen in der „falschen“ Richtung untersucht wie in der „richtigen“. Es erlaubt auch nicht, die Bewegungskosten zu berücksichtigen, bei denen einige Zellen "teurer" sein können als andere. Hier helfen wir einem komplexeren Algorithmus namens A *. Es funktioniert ähnlich wie die Breitensuche, aber anstatt Nachbarn, Nachbarn, Nachbarn, Nachbarn, Nachbarn usw. blind zu erkunden, werden alle diese Knoten in eine Liste aufgenommen und so sortiert, dass immer der nächste untersuchte Knoten derjenige ist führt höchstwahrscheinlich zum kürzesten Weg. Knoten werden nach Heuristiken sortiert (das ist in der Tat eine vernünftige Annahme).Dabei werden zwei Aspekte berücksichtigt - die Kosten eines hypothetischen Wegs zur Zelle (wobei alle erforderlichen Kosten für den Umzug berücksichtigt werden) und eine Bewertung, wie weit diese Zelle vom Endpunkt entfernt ist (wodurch die Suche in die richtige Richtung verschoben wird).


In diesem Beispiel haben wir gezeigt, dass er jeweils eine Zelle untersucht und jedes Mal eine benachbarte Zelle auswählt, die die besten (oder eine der besten) Aussichten hat. Der resultierende Pfad ähnelt dem Breitensuchpfad, es werden jedoch weniger Zellen untersucht, und dies ist sehr wichtig für die Leistung des Spiels auf komplexen Ebenen.

Bewegung ohne Netz

In den vorherigen Beispielen wurde ein der Welt überlagertes Gitter verwendet, und wir haben eine Route um die Welt durch die Zellen dieses Gitters gelegt. Die meisten Spiele überlappen das Raster jedoch nicht, und daher kann das Überlagern des Rasters zu unrealistischen Bewegungsmustern führen. Dieser Ansatz erfordert möglicherweise auch Kompromisse hinsichtlich der Größe jeder Zelle. Wenn sie zu groß ist, kann sie kleine Korridore und Kurven nicht angemessen beschreiben. Wenn sie zu klein ist, kann das Durchsuchen von Tausenden von Zellen zu lang sein. Was sind die Alternativen?

Das erste, was wir verstehen müssen, ist, dass das Gitter aus mathematischer Sicht einen " Graphen " liefert"von verbundenen Knoten. Die A * (und BFS) -Algorithmen arbeiten mit Graphen, und das Gitter ist für sie nicht wichtig. Daher können wir Knoten an beliebigen Positionen der Welt platzieren, und wenn es eine gerade Linie zwischen zwei verbundenen Knoten gibt, aber es gibt eine Linie zwischen dem Anfang und dem Ende Wenn es nur einen Knoten gibt, funktioniert unser Algorithmus wie zuvor und ist sogar noch besser, da weniger Knoten vorhanden sind. Dies wird häufig als Wegpunktsystem bezeichnet, da jeder Knoten eine wichtige Position in der Welt angibt, die erstellt werden kann Teil einer beliebigen Anzahl von hypothetischen pu s.


Beispiel 1: Ein Knoten in jeder Zelle des Gitters. Die Suche beginnt mit dem Knoten, in dem sich der Agent befindet, und endet mit der letzten Zelle.


Beispiel 2: Eine viel kleinere Anzahl von Knoten oder Wegpunkten . Die Suche beginnt mit dem Agenten, durchläuft die erforderliche Anzahl von Wegpunkten und bewegt sich zum Endpunkt. Beachten Sie, dass das Bewegen zum ersten Punkt des Pfades südwestlich des Spielers eine ineffiziente Route ist. Daher ist normalerweise eine Nachbearbeitung des generierten Pfads erforderlich (z. B. um festzustellen, dass der Pfad direkt zum Wegpunkt im Nordosten führen kann).

Dies ist ein ziemlich flexibles und leistungsstarkes System, das jedoch eine sorgfältige Lokalisierung der Wegpunkte erfordert, da die Agenten sonst möglicherweise nicht den nächstgelegenen Wegpunkt sehen, um die Route zu starten. Es wäre großartig, wenn wir auf der Grundlage der Geometrie der Welt automatisch Wegpunkte generieren könnten.

Und dann kommt Navmesh zur Rettung. Dies ist die Abkürzung für Navigation Mesh. Im Wesentlichen ist dies (normalerweise) ein zweidimensionales Netz von Dreiecken, das sich ungefähr mit der Geometrie der Welt an den Stellen überlappt, an denen das Spiel dem Agenten erlaubt, sich zu bewegen. Jedes der Dreiecke im Netz wird zu einem Knoten des Diagramms und hat bis zu drei benachbarte Dreiecke, die zu benachbarten Knoten des Diagramms werden.

Unten finden Sie ein Beispiel aus der Unity-Engine. Die Engine analysierte die Geometrie der Welt und erstellte ein Navmesh (blau), eine Annäherung an die Geometrie. Jedes Nammesh-Polygon ist ein Bereich, in dem ein Agent stehen kann, und ein Agent kann von einem Polygon zu einem benachbarten wechseln. (In diesem Beispiel sind die Polygone schmaler als der Boden, auf dem sie liegen, um den Radius des Agenten zu berücksichtigen, der über die Nennposition des Agenten hinausgeht.)



Wir können erneut mit A * nach einer Route durch ein Netz suchen. Dies gibt uns eine ideale Route um die Welt, die die gesamte Geometrie berücksichtigt und keine übermäßige Anzahl zusätzlicher Knoten (wie beim Raster) und die Beteiligung des Menschen an der Erzeugung von Punkten erfordert der Weg.

Das Finden von Pfaden ist ein umfangreiches Thema, für das es viele Ansätze gibt, insbesondere wenn Sie Details auf niedriger Ebene selbst programmieren müssen. Eine der besten Quellen für zusätzliche Informationen ist die Website von Amit Patel (Übersetzung des Artikels über Habré: https://habr.com/post/331192/ ).

Planung

Am Beispiel der Suche nach Pfaden haben wir festgestellt, dass es manchmal nicht ausreicht, nur eine Richtung zu wählen und sich darin zu bewegen. Wir müssen eine Route auswählen und mehrere Bewegungen ausführen, bevor wir den gewünschten Endpunkt erreichen. Wir können diese Idee auf eine Vielzahl von Konzepten verallgemeinern, bei denen das Ziel nicht nur der nächste Schritt ist. Um dies zu erreichen, müssen Sie eine Reihe von Schritten ausführen. Um zu wissen, was der erste Schritt sein sollte, müssen Sie möglicherweise einige Schritte nach vorne schauen. Dieser Ansatz wird als Planung bezeichnet . Das Finden von Pfaden kann als eine der spezifischen Anwendungen der Planung angesehen werden, aber dieses Konzept hat viel mehr Anwendungen. Zurück zum Zyklus „Wahrnehmung-Denken-Handeln“: Diese Planung ist eine Denkphase, in der versucht wird, mehrere Handlungsphasen für die Zukunft zu planen.

Schauen wir uns das Spiel Magic: The Gathering an. Wenn Sie Ihren ersten Zug haben, haben Sie mehrere Karten in der Hand, darunter "Sumpf", der 1 Punkt schwarzes Mana ergibt, und "Wald", der 1 Punkt grünes Mana ergibt, "Exorzist", für den 1 Punkt blaues Mana benötigt wird, und " Elven Mystic “, um zu nennen, dass du 1 Punkt grünes Mana brauchst. (Der Einfachheit halber lassen wir die verbleibenden drei Karten weg.) Die Regeln besagen, dass ein Spieler eine Landkarte pro Spielzug spielen, seine Landkarten „berühren“ kann, um Mana von ihnen zu erhalten, und so viele Zauber (einschließlich Beschwörungskreaturen) wirken kann. wie viel Mana er hat. In dieser Situation spielt der Spieler wahrscheinlich "Wald", berührt ihn, um 1 grünen Manapunkt zu erhalten, und ruft dann "Elfenmystiker". Aber woher weiß eine Gaming-KI, dass eine solche Entscheidung getroffen werden muss?

Einfacher "Scheduler"

Ein naiver Ansatz kann darin bestehen, einfach jede Aktion der Reihe nach zu durchlaufen, bis es geeignete gibt. Wenn AI auf die Hand schaut, sieht er, dass sie „Swamp“ spielen kann, und tut dies daher. Gibt es nach diesem Zug noch weitere Aktionen? Er kann weder Elven Mystic noch Exile Wizard beschwören, da dies grünes oder blaues Mana erfordert und der gespielte Sumpf nur schwarzes Mana gibt. Und wir können "Forest" nicht spielen, weil wir bereits "Swamp" gespielt haben. Das heißt, der KI-Spieler wird den Zug gemäß den Regeln ausführen, aber er wird nicht sehr optimal sein. Zum Glück gibt es eine bessere Lösung.

Fast so wie bei der Suche nach Pfaden eine Liste von Positionen gefunden wird, um sich um die Welt zu bewegen, um zum richtigen Punkt zu gelangen, kann unser Planer eine Liste von Aktionen finden, die das Spiel in den richtigen Zustand versetzen. So wie jede Position auf dem Pfad eine Reihe von Nachbarn hat, die potenzielle Optionen für die Auswahl des nächsten Schritts auf dem Pfad darstellen, hat jede Aktion im Plan Nachbarn oder „Erben“, die Kandidaten für den nächsten Schritt des Plans sind. Wir können nach diesen Aktionen und den folgenden Aktionen suchen, bis wir den gewünschten Zustand erreicht haben.

Nehmen wir für unser Beispiel an, das gewünschte Ergebnis wäre "eine Kreatur beschwören, wenn möglich". Zu Beginn des Zuges haben wir nur zwei mögliche Aktionen, die nach den Spielregeln zulässig sind:

 1. Spielen Sie "Swamp" (Ergebnis: "Swamp" verlässt die Hand und betritt das Spiel)
2. Spielen Sie "Wald" (Ergebnis: "Wald" verlässt die Hand und betritt das Spiel) 

Jede durchgeführte Aktion kann weitere Aktionen öffnen oder schließen, auch gemäß den Spielregeln. Stellen Sie sich vor, wir haben uns für "Swamp" entschieden - dies schließt die Möglichkeit, diese Karte als potenzielle Vererbungsaktion zu spielen (da "Swamp" bereits gespielt wurde), und schließt die Möglichkeit, "Forest" zu spielen (da Sie nach den Spielregeln nur eine Landkarte pro Spielzug spielen dürfen). und fügt die Fähigkeit hinzu, den „Sumpf“ zu berühren, um 1 Punkt schwarzes Mana zu erhalten - und dies ist in der Tat die einzige vererbte Aktion. Wenn wir noch einen Schritt machen und "Touch" Swamp "auswählen, erhalten wir 1 Punkt schwarzes Mana, mit dem wir nichts tun können. Das ist also sinnlos.

 1. Spielen Sie "Swamp" (Ergebnis: "Swamp" verlässt die Hand und betritt das Spiel)
            1.1 Berühre „Sumpf“ (Ergebnis: Wir haben „Sumpf“ berührt, +1 schwarzes Mana ist verfügbar)
                        Keine Aktion mehr - ENDE
2. Spielen Sie "Wald" (Ergebnis: "Wald" verlässt die Hand und betritt das Spiel) 

Diese kurze Liste von Aktionen hat uns nicht viel gebracht und zu einer „Sackgasse“ geführt, wenn wir die Analogie mit der Suche nach Pfaden verwenden. Daher wiederholen wir den Vorgang für den nächsten Schritt. Wir spielen Forest. Dies beseitigt auch die Fähigkeit, „Wald“ und „Sumpf“ zu spielen, und öffnet sich als potenzieller (und einziger) nächster Schritt „Berühre den Wald“. Dies gibt uns 1 Punkt grünes Mana, was wiederum den dritten Schritt eröffnet - "Nenne" Elfenmystiker "."

 1. Spielen Sie "Swamp" (Ergebnis: "Swamp" verlässt die Hand und betritt das Spiel)
            1.1 Berühre „Sumpf“ (Ergebnis: Wir haben „Sumpf“ berührt, +1 schwarzes Mana ist verfügbar)
                        Keine Aktion mehr - ENDE
2. Spielen Sie "Wald" (Ergebnis: "Wald" verlässt die Hand und betritt das Spiel)
            2.1 Berühre „Wald“ (Ergebnis: Wir haben „Sumpf“ berührt, +1 grünes Mana ist verfügbar)
                        2.1.1 Rufe "Elven Mystic" (Ergebnis: "Elven Mystic" im Spiel, -1 grünes Mana ist verfügbar)
                                    Keine Aktion mehr - ENDE 

Jetzt haben wir alle möglichen Aktionen und Aktionen untersucht, die sich aus diesen Aktionen ergeben, und einen Plan gefunden, mit dem wir die Kreatur beschwören können: „Wald spielen“, „Wald berühren“, „Elfenmystiker“ nennen.

Offensichtlich ist dies ein sehr vereinfachtes Beispiel, und normalerweise müssen Sie das beste auswählenEin Plan und nicht nur ein Plan, der einige Kriterien erfüllt (z. B. "eine Kreatur anrufen"). In der Regel können Sie potenzielle Pläne anhand des Endergebnisses oder des kumulierten Nutzens der Verwendung des Plans bewerten. Zum Beispiel können Sie sich 1 Punkt für eine angelegte Landkarte und 3 Punkte für das Aufrufen einer Kreatur geben. "Spiel" Sumpf "ist ein kurzer Plan mit 1 Punkt, und der Plan" Wald spielen "→" Wald "berühren →" Elfenmystiker "nennen gibt 4 Punkte, 1 für den Boden und 3 für die Kreatur. Dies ist der rentabelste verfügbare Plan. Sie sollten ihn daher auswählen, wenn wir solche Punkte festgelegt haben.

Oben haben wir gezeigt, wie das Planen innerhalb derselben Magic: The Gathering-Bewegung funktioniert, aber es kann auch auf Aktionen in einer Reihe von Zügen angewendet werden (z. B. „einen Bauern bewegen, um Raum für die Entwicklung des Bischofs zu schaffen“ im Schach oder „in Deckung für eine Einheit laufen“ könnte in der nächsten Runde schießen, sicher "in XCOM" oder nach der allgemeinen Strategie des gesamten Spiels (z. B. "Pylone für alle anderen Protoss-Gebäude bauen" in Starcraft oder "einen Trank zur Stärkung der Gesundheit trinken, bevor der Feind angegriffen wird" in Skyrim).

Verbesserte Planung

Manchmal gibt es bei jedem Schritt zu viele mögliche Aktionen, und die Bewertung jeder Option ist unangemessen. Kehren wir zum Beispiel von Magic: The Gathering zurück - stellen Sie sich vor, wir haben mehrere Kreaturen zur Hand, viele Länder wurden bereits gespielt, sodass wir jede Kreatur, mehrere Kreaturen mit ihren gespielten Fähigkeiten und ein paar weitere Landkarten auf der Hand nennen können - die Anzahl der Permutationen Land, Landnutzung, Beschwörung von Kreaturen und Nutzung der Fähigkeiten von Kreaturen können Tausenden oder sogar Zehntausenden entsprechen. Glücklicherweise gibt es verschiedene Möglichkeiten, um dieses Problem zu lösen.

Die erste heißt Rückwärtsverkettung"(" Round Trip "). Anstatt alle Aktionen und ihre Ergebnisse zu überprüfen, können wir mit jedem der gewünschten Endergebnisse beginnen und prüfen, ob wir einen direkten Weg zu ihnen finden können. Sie können dies mit dem Versuch vergleichen, ein bestimmtes Blatt in einem Baum zu erreichen - es ist viel logischer Beginnen Sie von diesem Blatt und gehen Sie zurück, indem Sie eine Route entlang des Stammes legen (und diese Route können wir dann in umgekehrter Reihenfolge gehen), als vom Stamm aus zu beginnen und zu erraten, welcher Zweig bei jedem Schritt zu wählen ist. Wenn Sie am Ende beginnen und in die entgegengesetzte Richtung gehen, dann erstellt e-Plan wird viel schneller und einfacher.

Wenn der Feind beispielsweise noch 1 Gesundheitspunkt hat, kann es nützlich sein, einen Plan zu finden, um "dem Feind 1 oder mehr Punkte direkten Schaden zuzufügen". Unser System weiß, dass es, um dieses Ziel zu erreichen, einen direkten Schadenszauber wirken muss, was wiederum bedeutet, dass es in unseren Händen sein muss und wir genug Mana brauchen, um es auszusprechen. Dies bedeutet wiederum, dass wir genug Land berühren müssen, um dieses Mana zu erhalten, was möglicherweise erfordert, dass Sie eine zusätzliche Landkarte spielen.

Eine andere Möglichkeit besteht darin, nach der ersten besten Übereinstimmung zu suchen. Anstatt alle Permutationen für eine lange Zeit zu umgehen, messen wir, wie „gut“ jeder Teilplan ist (ähnlich wie wir ihn aus den obigen Planoptionen ausgewählt haben) und berechnen jedes Mal den am besten aussehenden. Oft können Sie so einen optimalen oder zumindest ziemlich guten Plan erstellen, ohne jede mögliche Neuanordnung von Plänen berücksichtigen zu müssen. A * ist eine Variation der Suche nach dem ersten besten Spiel - es untersucht zuerst die vielversprechendsten Routen, sodass es normalerweise den Weg zum Ziel finden kann, ohne zu weit in andere Richtungen klettern zu müssen.

Eine interessante und immer beliebter werdende Suchoption für das erste beste Match ist die Monte-Carlo -Baumsuche.. Anstatt zu erraten, welche Pläne bei der Auswahl jeder nachfolgenden Aktion besser sind als andere, wählt diese Methode bei jedem Schritt zufällige nachfolgende Aktionen aus, bis das Ende erreicht ist, an dem keine Aktionen mehr möglich sind - wahrscheinlich, weil der hypothetische Plan zu einem Zustand des Sieges oder des Verlusts geführt hat - und verwendet dieses Ergebnis, um den zuvor ausgewählten Optionen mehr oder weniger Gewicht zu verleihen. Wenn der Vorgang viele Male wiederholt wird, kann die Methode eine gute Einschätzung des besten nächsten Schritts erstellen, selbst wenn sich die Situation ändert (z. B. wenn der Feind versucht, unsere Pläne zu vereiteln).

Schließlich wäre keine Diskussion über die Planung in Spielen vollständig, ohne die zielbasierte Aktionsplanung zu erwähnen(Zielorientierte Aktionsplanung, GOAP). Dies ist eine weit verbreitete und viel diskutierte Technik. Wenn Sie jedoch einige spezifische Implementierungsdetails ignorieren, handelt es sich im Wesentlichen um einen Roundtrip-Planer, der mit einem Ziel beginnt und versucht, eine Aktion aufzunehmen, die zu diesem Ziel führt, oder wahrscheinlicher eine Liste von Aktionen, die zu diesem Ziel führen zum Ziel. Wenn das Ziel beispielsweise darin bestand, „den Spieler zu töten“ und der Spieler in Deckung war, könnte der Plan lauten: „Den Spieler mit einer Granate rauchen“ → „Waffe herausziehen“ → „Angriff“.

Normalerweise gibt es mehrere Ziele, und jedes hat seine eigene Priorität. Wenn beispielsweise die Ziele mit der höchsten Priorität nicht erreicht werden können, kann keine Reihe von Aktionen den Plan "Spieler töten" bilden, da der Spieler nicht sichtbar ist. Das System kehrt dann zu den Zielen mit niedrigeren Prioritäten zurück, z. B. "Patrouille" oder "Wache vor Ort".

Training und Anpassung

Am Anfang des Artikels haben wir erwähnt, dass die Gaming-KI im Allgemeinen kein „maschinelles Lernen“ verwendet, da sie normalerweise nicht für die Echtzeitsteuerung intelligenter Agenten in der Gaming-Welt geeignet ist. Dies bedeutet jedoch nicht, dass wir in diesem Bereich, in dem es sinnvoll ist, nichts ausleihen können. Möglicherweise benötigen wir einen Computergegner im Shooter, um die besten Bewegungsorte für die meisten Kills zu finden. Oder wir wollen den Gegner in einem Kampfspiel. In Tekken oder Street Fighter lernte er beispielsweise, einen Spieler zu erkennen, der dieselben Combos verwendet, um sie zu blockieren, und zwang den Spieler, andere Taktiken anzuwenden. Das heißt, es gibt Zeiten, in denen ein bestimmter Prozentsatz des maschinellen Lernens nützlich ist.

Statistiken und Wahrscheinlichkeiten

Bevor wir zu komplexeren Beispielen übergehen, sollten wir herausfinden, wie weit wir gehen können, indem wir einfach Messungen vornehmen und diese Daten verwenden, um Entscheidungen zu treffen. Nehmen wir zum Beispiel an, wir haben ein Spiel im Genre der Echtzeitstrategie, und wir müssen verstehen, ob der Spieler in den ersten Minuten in Eile geht, um zu entscheiden, ob er mehr Verteidigung aufbauen will. Wir können das vorherige Verhalten des Spielers extrapolieren, um zu verstehen, wie das zukünftige Verhalten aussehen könnte. Zuerst haben wir keine Daten, die extrapoliert werden können, aber jedes Mal, wenn die KI gegen einen lebenden Feind spielt, kann sie den Zeitpunkt des ersten Angriffs aufzeichnen. Nach einigen Spielen kann diese Zeit gemittelt werden, und wir werden in Zukunft eine ausreichende Annäherung an die Angriffszeit des Spielers erhalten.

Das Problem bei der einfachen Mittelwertbildung besteht darin, dass sie normalerweise im Laufe der Zeit in der Mitte konvergiert. Wenn ein Spieler die Rush-Strategie die ersten 20 Male verwendet und die nächsten 20 Male zu einer viel langsameren Strategie gewechselt hat, liegt der Durchschnittswert irgendwo in der Mitte, was uns keine nützlichen Informationen liefert. Eine Möglichkeit zur Verbesserung der Daten besteht darin, ein einfaches Mittelungsfenster zu verwenden, das nur die letzten 20 Datenpunkte berücksichtigt.

Ein ähnlicher Ansatz kann verwendet werden, um die Wahrscheinlichkeit bestimmter Aktionen zu bewerten, vorausgesetzt, die vorherigen Präferenzen des Spielers werden auch in Zukunft beibehalten. Wenn ein Spieler beispielsweise fünf Mal mit einem Feuerball angreift, zwei Mal mit einem Blitz und nur einmal Hand in Hand, dann würde er höchstwahrscheinlich einen Feuerball 5 von 8 Mal bevorzugen. Aus diesen Daten extrapoliert, können wir sehen, dass die Wahrscheinlichkeit der Verwendung einer Waffe wie folgt ist: Feuerball = 62,5%, Blitz = 25% Nahkampf = 12,5%. Unsere KI-Charaktere werden erkennen, dass sie besser dran sind, feuerfeste Rüstungen zu finden!

Eine weitere interessante Methode ist die Verwendung des Naive Bayes-Klassifikators zur Untersuchung großer Mengen von Eingabedaten, um die aktuelle Situation zu klassifizieren, damit der KI-Agent entsprechend reagieren kann. Bayesianische Klassifikatoren sind wahrscheinlich am bekanntesten für ihre Verwendung in Spam-E-Mail-Filtern, in denen sie die Wörter in der E-Mail auswerten und mit den Wörtern vergleichen, die in der Vergangenheit am häufigsten in Spam und normalen Nachrichten gefunden wurden. Basierend auf diesen Berechnungen entscheiden sie über die Wahrscheinlichkeit, dass die zuletzt empfangene Nachricht Spam ist. Wir können etwas Ähnliches tun, nur mit weniger Input. Durch Aufzeichnen aller beobachtbaren nützlichen Informationen (z. B. erzeugte feindliche Einheiten,verwendete Zaubersprüche oder Forschungstechnologien) und die Verfolgung der daraus resultierenden Situation (Krieg / Frieden, Eilstrategie / Verteidigungsstrategie usw.) können wir basierend darauf das geeignete Verhalten auswählen.

Die Verwendung all dieser Unterrichtstechniken kann ausreichend sein und wird häufig und vorzugsweise auf die Daten angewendet, die während des Testens vor der Veröffentlichung des Spiels gesammelt wurden. Dies ermöglicht es der KI, sich an die verschiedenen Strategien der Spieletester anzupassen und sich nach der Veröffentlichung des Spiels nicht zu ändern. Eine KI, die sich nach der Veröffentlichung eines Spiels an einen Spieler anpasst, kann zu vorhersehbar oder sogar zu komplex werden, um besiegt zu werden.

Einfache gewichtsbasierte Anpassung

Gehen wir noch einen Schritt weiter. Anstatt nur die Eingabedaten zu verwenden, um zwischen diskreten vordefinierten Strategien zu wählen, können Sie die Werte ändern, die die Entscheidungsfindung beeinflussen. Wenn wir die Spielwelt und die Spielregeln gut verstehen, können wir Folgendes tun:

• ( );
• «» ;
• .

Stellen Sie sich einen Computeragenten vor, der in einem Ego-Shooter Räume auf einer Karte auswählen kann. Jedes Zimmer hat ein Gewicht, das bestimmt, wie wünschenswert es ist, dieses Zimmer zu besuchen. Anfangs haben alle Räume die gleiche Bedeutung. Bei der Auswahl eines Raums wählt die KI ihn zufällig aus, jedoch unter dem Einfluss dieser Gewichte. Stellen Sie sich nun vor, ein Computeragent, der getötet wird, merkt sich, in welchem ​​Raum dies geschieht, und reduziert sein Gewicht, sodass es weniger wahrscheinlich ist, dass er in Zukunft dorthin zurückkehrt. Stellen Sie sich vor, ein Computeragent hat einen Mord begangen. Dann kann er das Gewicht des Raumes erhöhen, in dem er sich befindet, um es in die Liste der Präferenzen aufzunehmen. Wenn also ein Raum für den KI-Spieler besonders gefährlich wird, beginnt er dies in Zukunft zu vermeiden, und wenn ein anderer Raum der KI erlaubt, viele Morde zu erleiden,dann wird er dorthin zurückkehren.

Markov-Modelle

Was wäre, wenn wir die gesammelten Daten für Prognosen verwenden wollten? Wenn wir beispielsweise jeden Raum aufzeichnen, in dem wir einen Spieler für einen bestimmten Zeitraum sehen, können wir vernünftigerweise vorhersagen, in welchen Raum er wechseln kann. Indem wir sowohl den aktuellen Raum, in dem sich der Spieler befindet, als auch den vorherigen verfolgen und diese Wertepaare aufzeichnen, können wir berechnen, wie oft jede der vorherigen Situationen zur nächsten Situation führt, und dieses Wissen für Prognosen verwenden.

Stellen Sie sich vor, es gibt drei Räume - rot, grün und blau - und wir haben während der Spielsitzung solche Beobachtungen erhalten:

Der erste Raum, in dem der Spieler gesehen wird	Gesamtbeobachtungen	Nebenzimmer	Wie oft gesehen	Prozentsatz
Rot	10	Rot	2	20%
		Grün	7	70%
		Blau	1	10%
Grün	10	Rot	3	30%
		Grün	5	50%
		Blau	2	20%
Blau	8	Rot	6	75%
		Grün	2	25%
		Blau	0	0%

Die Anzahl der Erkennungen in jedem der Räume ist ziemlich gleichmäßig, so dass wir nicht verstehen, welcher der Räume ein guter Ort für einen Hinterhalt sein kann. Daten können durch die Tatsache verzerrt werden, dass Spieler gleichmäßig auf der Karte erscheinen und mit gleicher Wahrscheinlichkeit in einem dieser drei Räume erscheinen. Daten zum Besuch des nächsten Raums können jedoch hilfreich sein und uns helfen, die Bewegung des Spielers auf der Karte vorherzusagen.

Wir können sofort feststellen, dass der grüne Raum für Spieler sehr attraktiv ist - die meisten Spieler aus dem roten Raum wurden grün, und 50% der Spieler, die im grünen Raum zu sehen sind, bleiben beim nächsten Check dort. Wir können auch feststellen, dass das blaue Zimmer ein ziemlich unattraktiver Ort ist. Menschen wechseln selten von roten oder grünen Räumen zu blauen und es scheint, dass niemand lange Zeit darin verweilen möchte.

Aber die Daten sagen uns etwas Spezifischeres - sie sagen, dass ein Spieler, der sich im blauen Raum befindet und ihr folgt, eher Rot als Grün wählt. Trotz der Tatsache, dass der grüne Raum ein viel beliebterer Ort ist als der rote, ist die Tendenz etwas entgegengesetzt, wenn sich der Spieler im blauen Raum befindet. Es scheint, dass der nächste Zustand (d. H. Der Raum, in dem er sich weiter bewegt) vom vorherigen Zustand abhängt (d. H. Der Raum, in dem er sich jetzt befindet), sodass diese Daten es uns ermöglichen, bessere Vorhersagen über das Verhalten von Spielern zu erstellen als mit unabhängiger Beobachtungszählung.

Diese Idee, dass wir das Wissen über den vorherigen Zustand nutzen können, um den zukünftigen Zustand vorherzusagen, wird als Markov-Modell bezeichnetund ähnliche Beispiele, in denen wir Ereignisse genau gemessen haben (zum Beispiel „in welchem ​​Raum sich der Spieler befindet“), werden Markov-Ketten genannt. Da sie die Wahrscheinlichkeit eines Übergangs zwischen aufeinanderfolgenden Zuständen darstellen, werden sie häufig grafisch in Form einer endlichen Zustandsmaschine dargestellt, in deren Nähe jeder Übergang angegeben ist, dessen Wahrscheinlichkeit angegeben ist. Früher haben wir eine Zustandsmaschine verwendet, um den Verhaltenszustand darzustellen, in dem sich der Agent befindet. Dieses Konzept kann jedoch auf alle Arten von Zuständen erweitert werden, unabhängig davon, ob sie dem Agenten zugeordnet sind oder nicht. In unserem Fall geben Staaten die vom Agenten belegten Räume an. Es wird so aussehen:


Dies ist ein einfacher Ansatz, um die relative Wahrscheinlichkeit des Übergangs in verschiedene Zustände anzuzeigen, wodurch AI die Möglichkeit erhält, den nächsten Zustand vorherzusagen. Wir können jedoch noch weiter gehen, indem wir ein System schaffen, das in zwei oder mehr Schritten in die Zukunft blickt.

Wenn ein Spieler im grünen Raum entdeckt wurde, verwenden wir Daten, die uns sagen, dass eine 50-prozentige Wahrscheinlichkeit besteht, dass er sich bei der nächsten Beobachtung noch im grünen Raum befindet. Aber wie hoch ist die Wahrscheinlichkeit, dass er zum dritten Mal dabei bleibt? Dies ist nicht nur die Wahrscheinlichkeit, dass er für zwei Beobachtungen im grünen Raum bleibt (50% * 50% = 25%), sondern auch die Wahrscheinlichkeit, dass er ihn verlässt und zurückkehrt. Hier ist eine neue Tabelle mit vorherigen Werten, die auf drei Beobachtungen angewendet wurden: eine aktuelle und zwei hypothetische in der Zukunft.

Beobachtung 1	Hypothetische Beobachtung 2		3
		30%		20%	6%
				70%	21%
				10%	3%
		50%		30%	15%
				50%	25%
				20%	10%
		20%		75%	15%
				25%	5%
				0%	0%
				:	100%

Hier sehen wir, dass die Wahrscheinlichkeit, einen Spieler nach 2 Beobachtungen im grünen Raum zu sehen, 51% beträgt - 21% dessen, was er aus dem roten Raum kommt, 5% dessen, was wir sehen, wenn der Spieler den blauen Raum besucht, und 25% dessen, was er die ganze Zeit ist wird im grünen Raum bleiben.

Eine Tabelle ist nur ein visueller Hinweis, eine Prozedur erfordert nur eine Multiplikation der Wahrscheinlichkeiten in jeder Phase. Dies bedeutet, dass wir weit in die Zukunft schauen können, aber mit einer wesentlichen Einschränkung: Wir gehen davon aus, dass die Wahrscheinlichkeit, einen Raum zu betreten, vollständig davon abhängt, in welchem ​​Raum wir uns gerade befinden. Diese Vorstellung, dass der zukünftige Zustand nur vom aktuellen abhängt, wird als Markov-Eigenschaft bezeichnet. Obwohl es uns erlaubt, leistungsstarke Werkzeuge wie Markov-Ketten zu verwenden, ist es normalerweise nur eine Annäherung. Spieler können sich aufgrund anderer Faktoren wie Gesundheitszustand und Munitionsmenge dazu entschließen, Räume zu besuchen. Da wir diese Informationen nicht als Teil der Bedingung aufzeichnen, sind unsere Vorhersagen weniger genau.

N Gramm

Kehren wir zu unserem Beispiel mit Combo-Erkennung in einem Kampfspiel zurück. Dies ist eine ähnliche Situation, in der wir den zukünftigen Zustand basierend auf der Vergangenheit vorhersagen möchten (um zu entscheiden, wie ein Angriff blockiert oder ihm ausgewichen werden soll), aber anstatt einen einzelnen Zustand oder ein einzelnes Ereignis zu untersuchen, werden wir Sequenzen von Ereignissen betrachten, die eine Kombinationsbewegung erzeugen.

Eine Möglichkeit, dies zu tun, besteht darin, jede Spielereingabe (z. B. Kick , Hand oder Block ) im Puffer zu speichern und den gesamten Puffer als Ereignis zu schreiben. Stellen Sie sich vor, ein Spieler drückt ständig einen Tritt , einen Tritt , einen Tritt , um den Angriff „ Todeskrebs “ zu verwenden. ", und das KI-System speichert alle Eingaben des Spielers im Puffer und merkt sich die letzten 3 Einträge, die bei jedem Schritt verwendet wurden.

Geben Sie ein	Eine vorhandene Eingabesequenz	Neuer Eingangsspeicher
Kick	Kick	Nein
Handschlag	Kick, Kick	Nein
Kick	Kick, Kick, Kick	Kick, Kick, Kick
Kick	Treten, treten, treten, treten	Kick, Kick, Kick
Handschlag	Treten, treten, treten, treten, treten	Kick, Kick, Kick
Blockieren	Treten, Treten, Treten, Treten, Treten, Blockieren	Treten, treten, blockieren
Kick	Treten, Treten, Treten, Treten, Treten, Blockieren, Treten	Treten, blocken, treten
Kick	Treten, Treten, Treten, Treten, Treten, Blockieren, Treten, Treten	Blockieren, treten, treten
Handschlag	, , , , , , , ,	, ,

(In fetten Linien führt der Spieler den Angriff „Superbuck of Death“ aus.)

Sie können alle Zeiten anzeigen , in denen der Spieler in der Vergangenheit einen Tritt gewählt hat , gefolgt von einem weiteren Tritt , und feststellen, dass die nächste Eingabe immer ein Schlag ist . Auf diese Weise kann der KI-Agent vorhersagen, dass ein Spieler, der gerade einen Tritt gefolgt von einem Tritt gewählt hat, höchstwahrscheinlich als nächstes einen Tritt auswählt und so den Todes-Superkulak startet . Auf diese Weise kann die KI entscheiden, eine Aktion zu wählen, die diesem Schlag entgegenwirkt, z. B. Blockieren oder Ausweichen.

Solche Ereignissequenzen werden N-Gramm genannt.Dabei ist N die Anzahl der gespeicherten Elemente. Im vorherigen Beispiel waren es 3 Gramm, auch Trigramm genannt, dh die ersten beiden Elemente werden verwendet, um das dritte vorherzusagen. Im 5-Gramm wird das fünfte für die ersten 4 Elemente vorhergesagt und so weiter.

Entwickler sollten die Größe von N-Gramm sorgfältig auswählen (manchmal auch als Reihenfolge bezeichnet). Je kleiner die Anzahl, desto weniger Speicher wird benötigt, denn je kleiner die Anzahl der zulässigen Permutationen ist, desto weniger Verlauf wird gespeichert, was bedeutet, dass der Kontext verloren geht. Zum Beispiel enthält ein 2-Gramm (auch als "Bigram" bezeichnet) Aufzeichnungen zum Treten , Treten und Aufzeichnungen zum Treten , Treten , kann aber keinen Tritt speichern .kick , hand kick kann daher diese combo nicht verfolgen.

Auf der anderen Seite, je größer die Reihenfolge, desto mehr Speicher wird benötigt, und das System wird höchstwahrscheinlich schwieriger zu trainieren sein, da wir viel mehr mögliche Permutationen haben werden, was bedeutet, dass wir niemals dasselbe zweimal treffen können. Wenn es zum Beispiel drei mögliche Eingaben gibt ( Kick , Hand und Block ) und wir ein 10-Gramm verwenden, gibt es fast 60.000 verschiedene Permutationen.

Das Bigram-Modell ist im Wesentlichen eine Markov-Trivialkette - jedes Paar „zukünftiger Zustand / aktueller Zustand“ ist ein Bigram und wir können den zweiten Zustand basierend auf dem ersten vorhersagen. Trigramme und große N-Gramme können auch als Markov-Ketten betrachtet werden, bei denen alle Elemente des N-Gramms mit Ausnahme des letzten den ersten Zustand bilden und das letzte Element der zweite Zustand ist. In unserem Beispiel wird ein Kampfspiel mit der Wahrscheinlichkeit des Übergangs vom Zustand der dargestellten treten und tritt in dem Zustand Kick, dann Punch. Indem wir mehrere Elemente des Eingabeverlaufs als ein einzelnes Element wahrnehmen, transformieren wir die Eingabesequenz im Wesentlichen in ein Fragment des Zustands, wodurch wir eine Markov-Eigenschaft erhalten, mit der wir Markov-Ketten verwenden können, um die nächste Eingabe vorherzusagen, dh zu erraten, welche Kombinationsbewegung folgen wird.

Wissensrepräsentation

Wir haben verschiedene Möglichkeiten besprochen, Entscheidungen zu treffen, Pläne zu erstellen und Prognosen zu erstellen. Alle Möglichkeiten basieren auf den Beobachtungen des Agenten über den Zustand der Welt. Aber wie können wir die gesamte Spielwelt effektiv beobachten? Oben haben wir gesehen, dass die Art und Weise, wie die Geometrie der Welt dargestellt wird, die Bewegung entlang der Welt stark beeinflusst. Daher ist es leicht vorstellbar, dass dies auch für andere Aspekte der Spiel-KI gilt. Wie können wir alle erforderlichen Informationen auf optimale Weise (so dass sie häufig aktualisiert werden und für viele Agenten zugänglich sind) und praktisch (damit die Informationen leicht im Entscheidungsprozess verwendet werden können) sammeln und organisieren? Wie kann man einfache Daten in Informationen oder Wissen umwandeln ? Für verschiedene Spiele können die Lösungen unterschiedlich sein, es gibt jedoch mehrere gängigste Ansätze.

Tags / Tags

Manchmal haben wir bereits eine große Menge nützlicher Daten, und das einzige, was wir brauchen, ist eine gute Möglichkeit, sie zu kategorisieren und danach zu suchen. Zum Beispiel kann es in der Spielwelt viele Objekte geben, von denen einige einen guten Schutz vor feindlichen Kugeln bieten. Oder wir haben zum Beispiel eine Reihe von aufgezeichneten Audiodialogen, die in bestimmten Situationen anwendbar sind, und wir brauchen eine Möglichkeit, sie schnell herauszufinden. Der naheliegende Schritt besteht darin, eine kleine zusätzliche Information hinzuzufügen, mit der Sie suchen können. Solche Fragmente werden Tags oder Tags genannt.

Kehren wir zum Beispiel des Tierheims zurück. In der Spielwelt kann es eine Reihe von Objekten geben - Kisten, Fässer, Grashalme, Drahtzäune. Einige von ihnen eignen sich zum Schutz, zum Beispiel Kisten und Fässer, andere nicht. Wenn unser Agent die Aktion „In den Schutz verschieben“ ausführt, muss er daher nach Objekten in der Nähe suchen und geeignete Kandidaten identifizieren. Er kann nicht nur nach Namen suchen - vielleicht hat das Spiel Crate_01, Crate_02 bis Crate_27 und wir möchten nicht nach all diesen Namen im Code suchen. Wir möchten dem Code nicht jedes Mal einen anderen Namen hinzufügen, wenn der Künstler eine neue Variante der Box oder des Fasses erstellt. Stattdessen können Sie nach jedem Namen suchen, der das Wort "Crate" enthält, aber eines Tages kann ein Künstler "Broken_Crate" mit einem riesigen Loch hinzufügen, das als Unterschlupf ungeeignet ist.

Daher erstellen wir stattdessen ein "COVER" -Tag und bitten Künstler und Designer, dieses Tag an alle Objekte anzuhängen, die als Unterschlupf verwendet werden können. Wenn sie allen Fässern und (ganzen) Feldern ein Tag hinzufügen, muss die KI-Prozedur nur Objekte mit diesem Tag finden, und sie weiß, dass die Objekte für diesen Zweck geeignet sind. Das Tag funktioniert auch dann, wenn die Objekte später umbenannt werden, und kann in Zukunft zu Objekten hinzugefügt werden, ohne dass unnötige Änderungen am Code vorgenommen werden müssen.

Im Code werden Tags normalerweise als Zeichenfolgen dargestellt. Wenn jedoch alle verwendeten Tags bekannt sind, können Sie Zeichenfolgen in eindeutige Zahlen konvertieren, um Platz zu sparen und die Suche zu beschleunigen. In einigen Engines sind Tags integrierte Funktionen, z. B. in Unity und in Unreal Engine 4 Daher reicht es aus, die Auswahl der darin enthaltenen Tags zu bestimmen und sie für den beabsichtigten Zweck zu verwenden.

Intelligente Objekte

Mithilfe von Tags können Sie der Umgebung des Agenten zusätzliche Informationen hinzufügen, um die verfügbaren Optionen zu ermitteln. So werden Anforderungen wie "Finde alle Orte, an denen ich mich am nächsten verstecken kann" oder "Finde alle Feinde in der Nähe, die Zauber wirken können" effizient und ausgeführt mit minimalem Aufwand für neue Spielressourcen gearbeitet. Manchmal enthalten die Tags jedoch nicht genügend Informationen für ihre vollständige Verwendung.

Stellen Sie sich einen Simulator einer mittelalterlichen Stadt vor, in der Abenteurer dort herumlaufen, wo sie bei Bedarf trainieren, kämpfen und sich entspannen möchten. Wir können Trainingsorte in verschiedenen Teilen der Stadt einrichten und ihnen das Tag „TRAINING“ zuweisen, damit die Charaktere leicht einen Platz für das Training finden können. Aber stellen wir uns vor, einer von ihnen ist ein Schießstand für Bogenschützen und der andere eine Schule von Zauberern. In jedem dieser Fälle müssen wir unsere Animation zeigen, da sie unter dem allgemeinen Namen "Training" unterschiedliche Aktionen darstellen und nicht jeder Abenteurer an beiden Trainingsarten interessiert ist. Sie können noch tiefer gehen und ARCHERY-TRAINING- und MAGIC-TRAINING-Tags erstellen, Trainingsverfahren voneinander trennen und sie in die einzelnen Animationen einbetten. Dies hilft, das Problem zu lösen. Aber stell dir vordass die Designer später erklären werden "Lassen Sie uns eine Robin Hood Schule haben, in der Sie Bogenschießen und Schwertkampf lernen können"! Und dann, wenn wir den Schwertkampf hinzufügen, bitten sie um die Schaffung der Gandalf-Akademie für Zaubersprüche und Schwertkämpfe. Infolgedessen müssen wir mehrere Tags für jeden Ort speichern und nach verschiedenen Animationen suchen, je nachdem, welchen Aspekt des Trainings der Charakter benötigt usw.

Eine andere Möglichkeit besteht darin, Informationen zusammen mit dem Einfluss, den sie auf den Spieler haben, direkt im Objekt zu speichern, sodass der KI-Akteur einfach mögliche Optionen auflisten und entsprechend den Anforderungen des Agenten aus ihnen auswählen kann. Danach kann er an den entsprechenden Ort ziehen, die entsprechenden Animationen (oder andere obligatorische Aktionen) ausführen, wie im Objekt angegeben, und die entsprechende Belohnung erhalten.

	Animation ausführen	Benutzerergebnis
Schießstand	Schusspfeil	+10 Bogenschießen Fähigkeit
Schule der Magie	Schwertduell	+10 Schwertfertigkeit
Robin Hood Schule	Schusspfeil	+15 Bogenschießen Fähigkeit
	Schwertduell	+8 Schwertfertigkeit
Gandalf Akademie	Schwertduell	+5 Schwertfertigkeit
	Zauber wirken	+10 Magische Fähigkeit

Der Bogenschütze neben diesen 4 Orten hat 6 Optionen, von denen 4 nicht auf ihn zutreffen, wenn er kein Schwert oder keine Magie benutzt. Wenn wir das Ergebnis in diesem Fall mit einer Verbesserung der Fähigkeiten anstelle eines Namens oder Tags vergleichen, können wir die Möglichkeiten der Welt leicht durch neue Verhaltensweisen erweitern. Sie können Hotels hinzufügen, um sich auszuruhen und Ihren Hunger zu stillen. Sie können die Charaktere in die Bibliothek gehen lassen und sich über Zaubersprüche und fortgeschrittene Bogenschießtechniken informieren.

Der Name des Objekts	Animation ausführen	Endergebnis
Hotel	Kaufen	-10 zu hungern
Hotel	Schlaf	-50 bis zur Müdigkeit
Die Bibliothek	Buch lesen	+10 Zauberfertigkeit
Die Bibliothek	Buch lesen	+5 Bogenschießen Fähigkeit

Wenn wir bereits das Verhalten "Bogenschießen üben" haben und selbst wenn wir die Bibliothek als Ort für ARCHERY-TRAINING markieren, benötigen wir höchstwahrscheinlich einen Sonderfall für die Verarbeitung der Lesebuchanimation anstelle der üblichen Schwertkampfanimation. Dieses System gibt uns mehr Flexibilität, indem wir diese Assoziationen auf Daten verschieben und Daten in der Welt speichern.

Die Existenz von Objekten oder Orten - Bibliotheken, Hotels oder Schulen - sagt uns, welche Dienstleistungen sie anbieten, welche Charaktere sie erhalten können und wie Sie eine kleine Anzahl von Animationen verwenden können. Durch die Möglichkeit, einfache Entscheidungen über Ergebnisse zu treffen, können Sie eine Vielzahl interessanter Verhaltensweisen erstellen. Anstatt passiv auf eine Anfrage zu warten, können diese Objekte eine Fülle von Informationen darüber liefern, wie und warum sie verwendet werden.

Reaktionskurven

Oft gibt es eine Situation, in der ein Teil des Zustands der Welt als kontinuierlicher Wert gemessen werden kann. Beispiele:

• Der „Prozentsatz der Gesundheit“ reicht normalerweise von 0 (tot) bis 100 (absolut gesund).
• "Entfernung zum nächsten Feind" variiert von 0 bis zu einem beliebigen positiven Wert

Darüber hinaus kann das Spiel einen Aspekt des KI-Systems aufweisen, der die Eingabe kontinuierlicher Werte in einem anderen Intervall erfordert. Um beispielsweise eine Entscheidung zur Flucht zu treffen, kann ein Dienstprogramm-Bewertungssystem sowohl die Entfernung zum nächsten Feind als auch die aktuelle Gesundheit des Charakters erfordern.

Das System kann jedoch nicht einfach zwei Werte des Zustands der Welt addieren, um ein bestimmtes Maß an „Sicherheit“ zu erreichen, da diese beiden Maßeinheiten unvergleichlich sind. Die Systeme gehen davon aus, dass sich ein fast toter Charakter 200 Meter vom Feind entfernt in derselben Sicherheit befindet, die absolut gesund ist Charakter 100 Meter vom Feind entfernt. Während der prozentuale Wert der Gesundheit im weitesten Sinne linear ist, ist die Entfernung nicht so - der Unterschied in der Entfernung vom Feind 200 und 190 Meter ist weniger signifikant als der Unterschied zwischen 10 Metern und Null.

Idealerweise benötigen wir eine Lösung, bei der zwei Indikatoren in ähnliche Intervalle umgewandelt werden, damit sie direkt verglichen werden können. Und wir brauchen Designer, die steuern können, wie diese Transformationen berechnet werden, um die relative Bedeutung jedes Werts zu steuern. Zu diesem Zweck werden Reaktionskurven (Antwortkurven) verwendet.

Die Reaktionskurve lässt sich am einfachsten als Diagramm mit Eingabe entlang der X-Achse, beliebigen Werten, z. B. „Entfernung zum nächsten Feind“ und Ausgabe entlang der Y-Achse (normalerweise ein normalisierter Wert im Bereich von 0,0 bis 1,0) erklären. Eine Linie oder Kurve im Diagramm bestimmt die Bindung der Eingabe an die normalisierte Ausgabe, und Designer passen diese Linien an, um das gewünschte Verhalten zu erhalten.

Um das Sicherheitsniveau zu berechnen, können Sie die Linearität der prozentualen Gesundheitswerte beibehalten - beispielsweise 10% mehr Gesundheit. Dies ist normalerweise gut, wenn der Charakter schwer verletzt ist und wenn er leicht verletzt wird. Daher ordnen wir diese Werte auf einfache Weise dem Intervall von 0 bis 1 zu:


Die Entfernung zum nächsten Feind ist etwas anders, so dass wir über eine bestimmte Entfernung (z. B. 50 Meter) hinaus überhaupt nicht von Feinden gestört werden und uns viel mehr für Unterschiede auf kurze Distanz als auf lange Distanz interessieren.

Hier sehen wir, dass die Ausgabe von "Sicherheit" für Feinde auf 40 und 50 Metern fast gleich ist: 0,96 und 1,0.


Es gibt jedoch einen viel größeren Unterschied zwischen dem Feind auf 15 Metern (ungefähr 0,5) und dem Feind auf 5 Metern (ungefähr 0,2). Ein solcher Zeitplan spiegelt besser die Bedeutung der Annäherung des Feindes wider.

Durch Normalisieren dieser beiden Werte im Bereich von 0 bis 1 können wir den Gesamtsicherheitswert als Durchschnitt dieser beiden Eingabewerte berechnen. Ein Charakter mit 20% Gesundheit und ein Feind auf 50 Metern haben eine Sicherheitsbewertung von 0,6. Ein Charakter mit 75% Gesundheit und einem Feind in nur 5 Metern Entfernung hat eine Sicherheitsbewertung von 0,47. Ein schwer verletzter Charakter mit 10% Gesundheit und einem Feind von 5 Metern hat einen Sicherheitsindex von nur 0,145.

Folgendes sollte hier berücksichtigt werden:

• — , .
• — , , 50 — , , .
• , ( ) . , — , Unity AnimationCurve , .

Blackboards

Oft befinden wir uns in einer Situation, in der die KI des Agenten beginnen muss, das während des Spiels erhaltene Wissen und die Informationen zu überwachen, damit sie für weitere Entscheidungen verwendet werden können. Beispielsweise muss sich ein Agent möglicherweise merken, welchen letzten Charakter er angegriffen hat, um sich für kurze Zeit auf die Angriffe dieses Charakters zu konzentrieren. Oder er muss sich daran erinnern, wie viel Zeit vergangen ist, nachdem er ein Geräusch gehört hat, so dass er nach einer gewissen Zeit aufhört, nach seinen Gründen zu suchen, und zu seinen früheren Studien zurückkehrt. Sehr oft ist das Datenaufzeichnungssystem stark vom Datenlesesystem getrennt, daher sollte es für den Agenten leicht zugänglich sein und nicht direkt in verschiedene KI-Systeme integriert sein. Das Lesen kann einige Zeit nach dem Schreiben erfolgen, daher müssen die Daten irgendwo gespeichert werden.damit sie später abgerufen werden können (und nicht bei Bedarf berechnet werden, was möglicherweise nicht möglich ist).

In einem fest codierten KI-System kann die Lösung darin bestehen, die erforderlichen Variablen im Prozess des Bedarfs hinzuzufügen. Diese Variablen beziehen sich auf Instanzen des Charakters oder Agenten, die entweder direkt in ihn integriert sind oder eine separate Struktur / Klasse zum Speichern solcher Informationen erstellen. KI-Prozeduren können angepasst werden, um diese Daten zu lesen und zu schreiben. In einem einfachen System funktioniert dies gut, aber wenn weitere Informationen hinzugefügt werden, wird dies umständlich und erfordert normalerweise jedes Mal eine Neuerstellung des Spiels.

Ein besserer Ansatz besteht darin, das Data Warehouse in eine Struktur umzuwandeln, mit der Systeme beliebige Daten lesen und schreiben können. Mit dieser Lösung können Sie neue Variablen hinzufügen, ohne die Datenstruktur ändern zu müssen, und so die Anzahl der Änderungen erhöhen, die an Datendateien und Skripten vorgenommen werden können, ohne dass eine erneute Zusammenstellung erforderlich ist. Wenn jeder Agent einfach eine Liste von Schlüssel-Wert-Paaren speichert, von denen jedes ein separates Wissen ist, können verschiedene KI-Systeme zusammenarbeiten, indem sie diese Informationen bei Bedarf hinzufügen und lesen.

Bei der Entwicklung der KI werden solche Ansätze als „Tafeln“ („Tafeln“) bezeichnet, da jeder Teilnehmer - in unserem Fall handelt es sich um KI-Verfahren (z. B. Wahrnehmung, Wegfindung und Entscheidungsfindung) - an die „Tafel“ schreiben kann, aus der er liest Daten für die Erfüllung ihrer Aufgabe können beliebige andere Teilnehmer sein. Sie können sich dies als ein Expertenteam vorstellen, das sich um das Board versammelt und etwas Nützliches darauf schreibt, das Sie mit der Gruppe teilen müssen. Gleichzeitig können sie die vorherigen Notizen ihrer Kollegen lesen, bis sie zu einer gemeinsamen Entscheidung oder einem gemeinsamen Plan kommen. Eine fest codierte Liste allgemeiner Variablen im Code wird manchmal als "statische Tafel" bezeichnet (da die Elemente, in denen die Informationen gespeichert sind, während der Programmausführung konstant sind), und eine beliebige Liste von Schlüssel-Wert-Paaren wird häufig als "dynamische Tafel" bezeichnet.Sie werden jedoch in etwa auf die gleiche Weise verwendet - als Zwischenverbindung zwischen Teilen des KI-Systems.

In der traditionellen KI wird normalerweise der Schwerpunkt auf die Zusammenarbeit verschiedener Systeme für die gemeinsame Entscheidungsfindung gelegt, aber in der Spiel-KI sind relativ wenige Systeme vorhanden. Ein gewisses Maß an Zusammenarbeit kann jedoch noch vorhanden sein. Stellen Sie sich in einem Action-Rollenspiel Folgendes vor:

• Das Wahrnehmungssystem scannt regelmäßig den Bereich und schreibt die folgenden Einträge an die Tafel:
  
  • Nächster Feind: Goblin 412
    
  • "Entfernung zum nächsten Feind": 35.0
    
  • "Enger Freund": "Krieger 43"
    
  • "Entfernung zum engsten Freund": 55.4
    
  • "Zeit des letzten Geräusches bemerkt": 12:45 Uhr
• Systeme wie ein Kampfsystem können wichtige Ereignisse an einer Tafel aufzeichnen, zum Beispiel:
  
  • Letzter Schaden: 12:34 Uhr

Viele dieser Daten sehen möglicherweise redundant aus. Am Ende können Sie immer die Entfernung zum nächsten Feind ermitteln, indem Sie einfach wissen, wer dieser Feind ist, und indem Sie eine Anfrage nach seiner Position erfüllen. Wenn sie jedoch mehrmals pro Frame wiederholt wird, um zu entscheiden, ob eine Agentin etwas bedroht oder nicht, wird dies zu einer potenziell langsamen Operation, insbesondere wenn sie eine räumliche Abfrage durchführen muss, um den nächsten Feind zu bestimmen. Und die Zeitstempel des „zuletzt wahrgenommenen Geräusches“ oder des „zuletzt erlittenen Schadens“ können immer noch nicht sofort angezeigt werden. Sie müssen die Zeit aufzeichnen, zu der diese Ereignisse stattgefunden haben, und die Tafel ist hierfür ein geeigneter Ort.

Unreal Engine 4 verwendet ein dynamisches Blackboard-System zum Speichern von Daten, die von Verhaltensbäumen übertragen werden. Dank dieses gemeinsamen Datenobjekts können Designer auf der Grundlage ihrer Blaupausen (visuelle Skripte) problemlos neue Werte an die Tafel schreiben, und der Verhaltensbaum kann diese Werte später lesen, um das Verhalten auszuwählen. All dies erfordert keine Neukompilierung der Engine.

Einflusskarten

Die Standardaufgabe in AI besteht darin, zu entscheiden, wohin sich der Agent bewegen soll. Im Shooter können wir die Aktion „In Schutz gehen“ wählen, aber wie kann man entscheiden, wo sich der Schutz unter den Bedingungen bewegt, in denen sich Feinde bewegen? Ähnlich wie bei der Aktion „Escape“ - wo ist der sicherste Weg zu entkommen? Oder in RTS müssen die Truppen möglicherweise eine Schwachstelle in der Verteidigung des Feindes angreifen - wie bestimmen wir, wo sich diese Schwachstelle befindet?

Alle diese Fragen können als geografische Aufgaben betrachtet werden, da wir eine Frage zur Geometrie und Form der Umgebung und zur Position der Entitäten darin stellen. In unserem Spiel sind all diese Daten höchstwahrscheinlich bereits verfügbar, aber es ist keine leichte Aufgabe, ihnen einen Sinn zu geben. Wenn wir zum Beispiel eine Schwachstelle in der Verteidigung des Feindes finden wollen, ist es nicht gut genug, einfach die Position des schwächsten Gebäudes oder der schwächsten Befestigung zu wählen, wenn zwei mächtige Waffensysteme an den Flanken sind. Wir brauchen einen Weg, um die Umgebung zu berücksichtigen und die Situation besser zu analysieren.

Dafür ist die Datenstruktur „Einflusskarte“ gedacht. Es beschreibt den „Einfluss“, den eine Entität auf die Umgebung haben kann. Durch die Kombination des Einflusses mehrerer Entitäten schaffen wir einen realistischeren Blick auf die gesamte Landschaft. Unter dem Gesichtspunkt der Implementierung approximieren wir die Spielwelt, indem wir ein 2D-Gitter überlagern. Nachdem wir festgestellt haben, in welcher Zelle des Gitters sich die Entität befindet, wenden wir eine Folgenabschätzung auf diese und die umgebenden Zellen an, die den Aspekt des Spiels angeben, den wir simulieren möchten. Um ein vollständiges Bild zu erhalten, akkumulieren wir diese Werte im selben Raster. Danach können wir verschiedene Rasterabfragen durchführen, um die Welt zu verstehen und über Positionierung und Zielpunkte zu entscheiden.

Nehmen Sie zum Beispiel "den schwächsten Punkt in der Verteidigung des Feindes". Wir haben eine Verteidigungsmauer, auf deren Angriff wir Fußsoldaten schicken wollen, aber dahinter befinden sich 3 Katapulte - 2 links nebeneinander, 1 rechts. Wie wählen wir eine gute Angriffsposition?

Zunächst können wir allen Zellen des Gitters innerhalb des Katapultangriffs +1 Schutzpunkte zuweisen. Das Zeichnen dieser Punkte auf der Einflusskarte für ein Katapult sieht folgendermaßen aus:


Das blaue Rechteck begrenzt alle Zellen, in denen Sie einen Angriff auf die Wand starten können. Rote Quadrate zeigen einen Einfluss von +1 Katapult an. In unserem Fall bedeutet dies den Angriffsbereich und die Bedrohung für angreifende Einheiten.

Nun fügen wir den Effekt des zweiten Katapults hinzu:


Wir haben einen dunklen Bereich, in dem der Einfluss von zwei Katapulten gebildet wird, was diesen Zellen +2 Schutz bietet. Zelle +2 in der blauen Zone kann ein besonders gefährlicher Ort sein, um die Wand anzugreifen! Fügen Sie den Einfluss des letzten Katapults hinzu:


[Symbole: CC-BY: https://game-icons.net/heavenly-dog/originals/defensive-wall.html ]

Jetzt haben wir eine vollständige Bezeichnung des von den Katapulten abgedeckten Gebiets. In der potenziellen Angriffszone gibt es eine Zelle mit +2 Katapult-Einflüssen, 11 Zellen mit +1 Einfluss und 2 Zellen mit 0 Katapult-Einflüssen - dies sind die Hauptkandidaten für die Angriffsposition. In ihnen können wir die Wand angreifen, ohne Angst vor Katapultfeuer zu haben.

Der Vorteil von Einflusskarten besteht darin, dass sie einen kontinuierlichen Raum mit einer nahezu unendlichen Menge möglicher Positionen in eine diskrete Menge ungefährer Positionen umwandeln, über die wir sehr schnell Entscheidungen treffen können.

Diesen Vorteil haben wir jedoch nur durch die Auswahl einer kleinen Anzahl potenzieller Angriffspositionen erlangt. Warum sollten wir hier die Einflusskarte verwenden, anstatt die Entfernung von jedem Katapult zu jeder dieser Positionen manuell zu überprüfen?

Erstens kann die Berechnung einer Einflusskarte sehr kostengünstig sein. Nachdem die Einflusspunkte auf die Karte gelegt wurden, muss sie erst geändert werden, wenn sich die Objekte bewegen. Dies bedeutet, dass wir nicht ständig Entfernungsberechnungen durchführen oder jede mögliche Einheit iterativ abfragen müssen - wir „backen“ diese Informationen in die Karte und können beliebig oft Anfragen an sie senden.

Zweitens können wir verschiedene Einflusskarten überlappen und kombinieren, um komplexere Abfragen zu erfüllen. Um beispielsweise einen sicheren Ort für die Flucht auszuwählen, können wir eine Karte des Einflusses unserer Feinde erstellen und die Karte unserer Freunde subtrahieren. Die Gitterzellen mit dem größten negativen Wert werden als sicher betrachtet.


Je roter, gefährlicher und grüner, desto sicherer. Bereiche, in denen sich Einflussüberschneidungen ergeben, können ganz oder teilweise neutralisiert werden, um widersprüchliche Einflussbereiche widerzuspiegeln.

Schließlich sind Einflusskarten beim Rendern in der Welt leicht zu visualisieren. Sie können ein wertvoller Hinweis für Designer sein, die KI basierend auf sichtbaren Eigenschaften anpassen müssen, und sie können in Echtzeit beobachtet werden, um zu verstehen, warum die KI die Entscheidungen wählt, die sie trifft.

Fazit

Ich hoffe, der Artikel gab Ihnen einen Überblick über die beliebtesten Tools und Ansätze, die in der Gaming-KI verwendet werden, sowie über Situationen, in denen sie angewendet werden können. Der Artikel berücksichtigte nicht viele andere Techniken (sie werden seltener verwendet, könnten aber möglicherweise genauso effektiv sein), einschließlich der folgenden:

• Algorithmen für Optimierungsaufgaben, einschließlich Aufstieg nach oben, Gradientenabstieg und genetische Algorithmen.
• Wettbewerbsfähige Such- / Planungsalgorithmen wie Minimax und Alpha-Beta-Clipping
• Klassifikationstechniken, zum Beispiel Perzeptrone, neuronale Netze und die Unterstützungsvektormethode
• Agentenwahrnehmungs- und Speicherverarbeitungssysteme
• Architekturansätze für KI wie Hybridsysteme, prädikative Architekturen (Brooks-Architekturen) und andere Methoden zur Zerlegung von KI-Systemen in Schichten
• Animationswerkzeuge wie Bewegungsplanung und Bewegungsanpassung
• Leistungsaufgaben wie Detaillierungsgrad, jederzeitige Algorithmen und Zeitsteuerung

Um mehr über diese Themen sowie die in diesem Artikel behandelten Themen zu erfahren, können Sie die folgenden Quellen studieren.

• GameDev.net bietet Artikel und Tutorials zur künstlichen Intelligenz sowie ein Forum zur künstlichen Intelligenz .
• Auf AiGameDev.com hat viele Präsentationen und Artikel über ein breites Spektrum von Themen der künstlichen Intelligenz im Zusammenhang mit der Entwicklung von Spielen
• GDC Vault hat Berichte mit GDC AI Summit, von denen viele kostenlos verfügbar sind: https://www.gdcvault.com/
  
• Darüber hinaus enthält die AI Game Programmers Guild eine Reihe von Links zu alten Artikeln und Präsentationen dieses Gipfels: http://gameai.com/
  
• Der KI-Forscher und Spieleentwickler Tommy Thompson hat einen YouTube-Kanal, der sich der Erklärung und Erforschung der KI in kommerziellen Spielen widmet: https://www.youtube.com/user/tthompso

Viele der Materialien von höchster Qualität sind in Büchern enthalten, darunter die folgenden:

• Die Game AI Pro-Serie ist eine Sammlung kurzer Artikel, in denen erläutert wird, wie bestimmte Funktionen implementiert oder bestimmte Probleme gelöst werden. Unter http://www.gameaipro.com/ wurden kostenlose Ausschnitte aus früheren Büchern veröffentlicht.
  
  • Game AI Pro: Gesammelte Weisheit von Game AI-Profis
    
  • Game AI Pro 2: Gesammelte Weisheit von Game AI-Profis
    
  • Game AI Pro 3: Gesammelte Weisheit von Game AI-Profis
    
  
  
• AI Game Programming Wisdom Game AI Pro. , . , !
  
  
  • AI Game Programming Wisdom 1
    
  • AI Game Programming Wisdom 2
    
  • AI Game Programming Wisdom 3
    
  • AI Game Programming Wisdom 4
    
• Artificial Intelligence: A Modern Approach — , . , , , .

Darüber hinaus gibt es mehrere gute Bücher über Gaming-KI im Allgemeinen, die von Fachleuten der Branche verfasst wurden. Es ist schwierig, jemandem den Vorzug zu geben - lesen Sie die Bewertungen und wählen Sie diejenige aus, die zu Ihnen passt.