Vielleicht sind Sie mit der prozeduralen Levelgenerierung vertraut. In diesem Beitrag dreht sich alles um die prozedurale Missionsgenerierung. Wir werden uns das Gesamtbild der Missionsgenerierung mithilfe von klassischem maschinellem Lernen und rekurrierenden neuronalen Netzwerken für Roguelike-Spiele ansehen.
Hallo zusammen! Mein Name ist Lev Kobelev und ich bin Game Designer bei MY.GAMES. In diesem Artikel möchte ich meine Erfahrungen mit der Verwendung von klassischem ML und einfachen neuronalen Netzwerken teilen. Ich erkläre, wie und warum wir uns für die prozedurale Missionsgenerierung entschieden haben. Außerdem werden wir uns eingehend mit der Implementierung des Prozesses in Zombie State befassen.
Haftungsausschluss: Dieser Artikel dient ausschließlich zu Informations- und Unterhaltungszwecken. Wenn Sie eine bestimmte Lösung verwenden, raten wir Ihnen, die Nutzungsbedingungen einer bestimmten Ressource sorgfältig zu prüfen und sich an die Rechtsabteilung zu wenden!
☝🏻 Zunächst einige Begriffe: „ Arenen “, „ Level “ und „ Standorte “ sind in diesem Kontext Synonyme, ebenso wie „ Bereich “, „ Zone “ und „ Spawn-Bereich “.
Definieren wir nun „ Mission “. Eine Mission ist eine vorgegebene Reihenfolge, in der Feinde nach bestimmten Regeln an einem Ort erscheinen . Wie bereits erwähnt, werden in Zombie State Orte generiert, wir schaffen also keine „inszenierte“ Erfahrung. Das heißt, wir platzieren Feinde nicht an vorgegebenen Punkten – tatsächlich gibt es solche Punkte nicht. In unserem Fall erscheint ein Feind irgendwo in der Nähe eines Spielers oder einer bestimmten Wand. Außerdem sind alle Arenen im Spiel rechteckig, sodass jede Mission in jeder von ihnen gespielt werden kann.
Lassen Sie uns den Begriff „ Spawn “ einführen. Spawnen ist das Erscheinen mehrerer Feinde desselben Typs gemäß vorgegebenen Parametern an Punkten in einer bestimmten Zone . Ein Punkt – ein Feind. Wenn sich in einem Bereich nicht genügend Punkte befinden, wird dieser gemäß speziellen Regeln erweitert. Es ist auch wichtig zu verstehen, dass die Zone nur bestimmt wird, wenn ein Spawn ausgelöst wird. Der Bereich wird durch die Spawn-Parameter bestimmt, und wir werden uns im Folgenden zwei Beispiele ansehen: einen Spawn in der Nähe des Spielers und einen in der Nähe einer Wand.
Die erste Art des Spawnens ist in der Nähe des Spielers . Das Erscheinen in der Nähe des Spielers wird durch einen Sektor festgelegt, der durch zwei Radien beschrieben wird: extern und intern (R und r), die Breite des Sektors (β), den Drehwinkel (α) relativ zum Spieler und die gewünschte Sichtbarkeit (oder Unsichtbarkeit) des Erscheinens des Feindes. Innerhalb eines Sektors befinden sich die erforderliche Anzahl an Punkten für Feinde – und daher kommen sie!
Die zweite Art des Spawnens ist in der Nähe der Wand . Wenn ein Level generiert wird, wird jede Seite mit einem Tag markiert – einer Himmelsrichtung. Die Wand mit dem Ausgang ist immer im Norden. Das Erscheinen eines Feindes in der Nähe einer Wand wird durch das Tag, die Entfernung von ihr (o), die Länge (a), die Breite einer Zone (b) und die gewünschte Sichtbarkeit (oder Unsichtbarkeit) des Erscheinens des Feindes angegeben. Der Mittelpunkt einer Zone wird relativ zur aktuellen Position des Spielers bestimmt.
Spawns kommen in Wellen . Eine Welle ist die Art und Weise, in der Spawns erscheinen, nämlich die Verzögerung zwischen ihnen – wir wollen die Spieler nicht mit allen Feinden auf einmal überhäufen. Wellen werden zu Missionen zusammengefasst und nach einer bestimmten Logik nacheinander gestartet. Eine zweite Welle kann beispielsweise 20 Sekunden nach der ersten gestartet werden (oder wenn mehr als 90 % der Zombies darin getötet wurden). Eine ganze Mission kann also als große Kiste betrachtet werden, und innerhalb dieser Kiste gibt es mittelgroße Kisten (Wellen) und innerhalb der Wellen gibt es noch kleinere Kisten (Spawns).
Bevor wir überhaupt mit der eigentlichen Arbeit an den Missionen begannen, haben wir bereits einige Regeln definiert:
Irgendwann hatten wir etwa hundert Missionen fertig, aber nach einer Weile brauchten wir noch mehr davon. Die anderen Designer und ich wollten nicht viel Zeit und Mühe darauf verwenden, weitere hundert Missionen zu erstellen, also begannen wir, nach einer schnellen und kostengünstigen Methode zur Missionserstellung zu suchen.
Alle Generatoren arbeiten nach einem bestimmten Regelwerk, und unsere manuell erstellten Missionen wurden ebenfalls nach bestimmten Empfehlungen durchgeführt. Wir haben also eine Hypothese über die Muster innerhalb der Missionen aufgestellt, und diese Muster würden als Regeln für den Generator dienen.
✍🏻 Einige Begriffe, die Sie im Text finden:
Beim Clustering geht es darum, eine gegebene Sammlung in sich nicht überlappende Teilmengen (Cluster) aufzuteilen, sodass ähnliche Objekte zum selben Cluster gehören, sich aber Objekte aus verschiedenen Clustern deutlich unterscheiden.
Kategorische Merkmale sind Daten, die einen Wert aus einer endlichen Menge annehmen und keine numerische Darstellung haben. Beispielsweise der Spawn-Wall-Tag: Norden, Süden usw.
Die Kodierung kategorialer Merkmale ist ein Verfahren zur Umwandlung kategorialer Merkmale in eine numerische Darstellung nach zuvor festgelegten Regeln. Beispielsweise Nord → 0, Süd → 1 usw.
Normalisierung ist eine Methode zur Vorverarbeitung numerischer Merkmale, um sie auf eine gemeinsame Skala zu bringen, ohne Informationen über die Unterschiede in den Bereichen zu verlieren. Sie können beispielsweise verwendet werden, um die Ähnlichkeit von Objekten zu berechnen. Wie bereits erwähnt, spielt die Objektähnlichkeit bei Clusterproblemen eine Schlüsselrolle.
Die manuelle Suche nach all diesen Mustern wäre extrem zeitaufwändig, daher haben wir uns für Clustering entschieden. Hier kommt maschinelles Lernen ins Spiel, da es diese Aufgabe gut bewältigt.
Clustering funktioniert in einem N-dimensionalen Raum und ML arbeitet speziell mit Zahlen. Daher würden alle Spawns zu Vektoren:
So wurde beispielsweise der Spawn, der als „Spawne 10 Zombie-Shooter an der Nordmauer in einem Bereich mit einer Vertiefung von 2 Metern, einer Breite von 10 und einer Länge von 5“ beschrieben wurde, zum Vektor [0,5, 0,25, 0,2, 0,8, …, 0,5] (← diese Zahlen sind abstrakt).
Zusätzlich wurde die Macht der Feindesmenge reduziert, indem bestimmte Feinde abstrakten Typen zugeordnet wurden. Zunächst einmal erleichterte diese Art der Zuordnung die Zuordnung eines neuen Feindes zu einem bestimmten Cluster. Dies ermöglichte es auch, die optimale Anzahl an Mustern zu reduzieren und infolgedessen die Generierungsgenauigkeit zu erhöhen – aber dazu später mehr.
Es gibt viele Clustering-Algorithmen: K-Means, DBSCAN, spektral, hierarchisch usw. Sie basieren alle auf unterschiedlichen Ideen, haben aber dasselbe Ziel: Cluster in den Daten zu finden. Unten sehen Sie je nach gewähltem Algorithmus unterschiedliche Möglichkeiten, Cluster für dieselben Daten zu finden.
Der K-Means-Algorithmus erzielte bei Spawns die beste Leistung.
Nun ein kleiner Exkurs für diejenigen, die nichts über diesen Algorithmus wissen (es wird keine streng mathematische Begründung geben, da es in diesem Artikel um Spieleentwicklung und nicht um die Grundlagen von ML geht). K-Means unterteilt die Daten iterativ in K-Cluster, indem die Summe der quadrierten Distanzen von jedem Feature zum Mittelwert des ihm zugewiesenen Clusters minimiert wird. Der Durchschnitt wird durch die intraclustermäßige Summe der quadrierten Distanzen ausgedrückt.
Es ist wichtig, Folgendes über diese Methode zu verstehen:
Lassen Sie uns den zweiten Punkt etwas genauer betrachten.
Die Elbow-Methode wird häufig verwendet, um die optimale Anzahl von Clustern auszuwählen. Die Idee ist sehr einfach: Wir führen den Algorithmus aus und probieren alle K von 1 bis N aus, wobei N eine sinnvolle Zahl ist. In unserem Fall war es 10 – es war unmöglich, mehr Cluster zu finden. Lassen Sie uns nun die Summe der quadrierten Distanzen innerhalb jedes Clusters ermitteln (ein Wert, der als WSS oder SS bezeichnet wird). Wir stellen dies alles in einem Diagramm dar und wählen einen Punkt aus, ab dem sich der Wert auf der Y-Achse nicht mehr signifikant ändert.
Zur Veranschaulichung verwenden wir einen bekannten Datensatz, den
Wenn Sie den Ellenbogen nicht sehen können, können Sie die Silhouettenmethode verwenden. Dies geht jedoch über den Rahmen dieses Artikels hinaus.
Alle Berechnungen oben und unten wurden in Python unter Verwendung von Standardbibliotheken für ML und Datenanalyse durchgeführt: Pandas, Numpy, Seaborn und Sklearn. Ich gebe den Code nicht frei, da der Hauptzweck des Artikels darin besteht, die Funktionen zu veranschaulichen und nicht auf die technischen Details einzugehen.
Nachdem wir die optimale Anzahl an Clustern ermittelt haben, sollten wir jeden einzelnen im Detail untersuchen. Wir müssen sehen, welche Spawns darin enthalten sind und welche Werte sie annehmen. Lassen Sie uns für jeden Cluster unsere eigenen Einstellungen für die weitere Generierung erstellen. Die Parameter umfassen:
Betrachten wir die Cluster-Einstellungen, die verbal wie folgt beschrieben werden können: „das Erscheinen einfacher Feinde irgendwo in der Nähe des Spielers in geringer Entfernung und höchstwahrscheinlich an sichtbaren Punkten.“
Cluster 1-Tabelle
Feinde | Typ | R | R-Delta | Drehung | Breite | Sichtweite |
---|---|---|---|---|---|---|
zombie_common_3_5=4, zombie_heavy=1 | Spieler | 10-12 | 1-2 | 0-30 | 30-45 | Sichtbar=9, Unsichtbar=1 |
Hier sind zwei nützliche Tricks:
Dies wurde mit jedem Cluster durchgeführt. Da es weniger als 10 davon gab, dauerte es nicht lange.
Wir haben dieses Thema nur kurz angesprochen, aber es gibt noch viel Interessantes zu lernen. Hier sind einige Artikel als Referenz; sie bieten eine gute Beschreibung der Prozesse der Datenarbeit, des Clusterings und der Ergebnisanalyse.
Zusätzlich zu den Spawn-Mustern haben wir beschlossen, die Abhängigkeit der Gesamtgesundheit der Feinde innerhalb einer Mission von der voraussichtlichen Zeit ihres Abschlusses zu untersuchen, um diesen Parameter bei der Generierung zu verwenden.
Beim Erstellen manueller Missionen bestand die Aufgabe darin, ein koordiniertes Tempo für das Kapitel zu entwickeln – eine Abfolge von Missionen: kurz, lang, kurz, wieder kurz usw. Wie können Sie die Gesamtgesundheit der Feinde innerhalb einer Mission ermitteln, wenn Sie den erwarteten DPS des Spielers und dessen Zeit kennen?
💡 Lineare Regression ist eine Methode zur Rekonstruktion der Abhängigkeit einer Variablen von einer anderen oder mehreren anderen Variablen mit einer linearen Abhängigkeitsfunktion. Die folgenden Beispiele betrachten ausschließlich die lineare Regression von einer Variablen: f(x) = wx + b.
Lassen Sie uns die folgenden Begriffe einführen:
Also, HP = DPS * Aktionszeit + Freizeit. Beim Erstellen eines manuellen Kapitels haben wir die erwartete Zeit jeder Mission aufgezeichnet. Jetzt müssen wir die Aktionszeit ermitteln.
Wenn Sie die erwartete Missionszeit kennen, können Sie die Aktionszeit berechnen und sie von der erwarteten Zeit abziehen, um die freie Zeit zu erhalten: freie Zeit = Missionszeit – Aktionszeit = Missionszeit – HP * DPS. Diese Zahl kann dann durch die durchschnittliche Anzahl der Feinde in der Mission geteilt werden, und Sie erhalten die freie Zeit pro Feind. Daher bleibt nur noch, eine lineare Regression von der erwarteten Missionszeit zur freien Zeit pro Feind zu erstellen.
Zusätzlich werden wir eine Regression des Anteils der Aktionszeit an der Missionszeit konstruieren.
Schauen wir uns ein Berechnungsbeispiel an und sehen wir, warum diese Regressionen verwendet werden:
Hier ist eine Frage: Warum müssen wir die freie Zeit des Gegners kennen? Wie bereits erwähnt, sind Spawns nach Zeit angeordnet. Daher kann die Zeit des i-ten Spawns als Summe der Aktionszeit des (i-1)-ten Spawns und der freien Zeit innerhalb dieses Spawns berechnet werden.
Und hier stellt sich eine weitere Frage: Warum ist das Verhältnis von Aktionszeit und Freizeit nicht konstant?
In unserem Spiel hängt die Schwierigkeit einer Mission von ihrer Dauer ab. Das heißt, kurze Missionen sind einfacher und lange schwieriger. Einer der Schwierigkeitsparameter ist die freie Zeit pro Gegner. In der obigen Grafik gibt es mehrere gerade Linien mit demselben Steigungskoeffizienten (w), aber einem unterschiedlichen Offset (b). Um die Schwierigkeit zu ändern, reicht es also aus, den Offset zu ändern: Eine Erhöhung von b macht das Spiel einfacher, eine Verringerung macht es schwieriger und negative Zahlen sind zulässig. Diese Optionen helfen Ihnen, die Schwierigkeit von Kapitel zu Kapitel zu ändern.
Ich bin der Meinung, dass sich alle Designer mit dem Problem der Regression befassen sollten, da dies häufig bei der Dekonstruktion anderer Projekte hilfreich ist:
Wir haben also die Regeln für den Generator gefunden und können nun mit dem Generierungsprozess fortfahren.
Wenn Sie abstrakt denken, kann jede Mission als Zahlenfolge dargestellt werden, wobei jede Zahl einen bestimmten Spawn-Cluster widerspiegelt. Beispiel: Mission: 1, 2, 1, 1, 2, 3, 3, 2, 1, 3. Dies bedeutet, dass die Aufgabe, neue Missionen zu generieren, auf die Generierung neuer Zahlenfolgen hinausläuft. Nach der Generierung müssen Sie einfach jede Zahl einzeln gemäß den Clustereinstellungen „erweitern“.
Wenn wir eine triviale Methode zur Generierung einer Sequenz betrachten, können wir die statistische Wahrscheinlichkeit berechnen, mit der ein bestimmter Spawn auf einen beliebigen anderen Spawn folgt. Wir erhalten beispielsweise das folgende Diagramm:
Die Oberseite des Diagramms ist ein Cluster, zu dem es führt, ein Scheitelpunkt, und das Kantengewicht ist die Wahrscheinlichkeit, dass der Cluster der Nächste ist.
Wenn wir einen solchen Graphen durchgehen, könnten wir eine Sequenz erzeugen. Dieser Ansatz hat jedoch eine Reihe von Nachteilen. Dazu gehören beispielsweise fehlendes Gedächtnis (es kennt nur den aktuellen Zustand) und die Möglichkeit, in einem Zustand „hängenzubleiben“, wenn dieser mit hoher statistischer Wahrscheinlichkeit in sich selbst übergeht.
✍🏻 Wenn wir diesen Graphen als Prozess betrachten, erhalten wir eine einfache Markow-Kette.
Wenden wir uns neuronalen Netzwerken zu, und zwar rekurrenten, da sie die Nachteile des Basisansatzes nicht aufweisen. Diese Netzwerke eignen sich gut zum Modellieren von Sequenzen wie Zeichen oder Wörtern bei Aufgaben der natürlichen Sprachverarbeitung. Um es ganz einfach auszudrücken: Das Netzwerk wird darauf trainiert, das nächste Element der Sequenz auf der Grundlage der vorherigen vorherzusagen.
Eine Beschreibung der Funktionsweise dieser Netzwerke liegt jenseits des Umfangs dieses Artikels, da dies ein umfangreiches Thema ist. Schauen wir uns stattdessen an, was für das Training erforderlich ist:
Ein einfaches Beispiel mit N=2, L=3, C=5. Nehmen wir die Folge 1, 2, 3, 4, 1 und suchen darin nach Teilfolgen der Länge L+1: [1, 2, 3, 4], [2, 3, 4, 1]. Teilen wir die Folge in eine Eingabe von L Zeichen und eine Antwort (Ziel) auf – das (L+1)te Zeichen*.* Beispiel: [1, 2, 3, 4] → [1, 2, 3] und [4]. Wir kodieren die Antworten in One-Hot-Vektoren, [4] → [0, 0, 0, 0, 1].
Als Nächstes können Sie mit Tensorflow oder PyTorch ein einfaches neuronales Netzwerk in Python skizzieren. Wie das geht, können Sie unter den folgenden Links sehen. Jetzt müssen Sie nur noch den Trainingsprozess mit den oben beschriebenen Daten starten, warten und... dann können Sie mit der Produktion beginnen!
Modelle für maschinelles Lernen verfügen über bestimmte Kennzahlen, wie z. B. Genauigkeit. Die Genauigkeit zeigt den Anteil der richtig gegebenen Antworten. Sie muss jedoch mit Vorsicht betrachtet werden, da die Daten Klassenungleichgewichte aufweisen können. Wenn es keine (oder fast keine) gibt, können wir sagen, dass das Modell gut funktioniert, wenn es Antworten besser als zufällig vorhersagt, d. h. Genauigkeit > 1/C; wenn sie nahe bei 1 liegt, funktioniert es hervorragend.
In unserem Fall zeigte das Modell eine gute Genauigkeit. Einer der Gründe für diese Ergebnisse ist die geringe Anzahl von Clustern, die durch die Zuordnung der Feinde zu ihren Typen und ihrem Gleichgewicht erreicht wurden.
Hier sind weitere Materialien zu RNN für Interessierte:
Das trainierte Modell ist leicht
Zur Interaktion mit dem Modell wird in Unity ein benutzerdefiniertes Fenster erstellt, in dem die Spieleentwickler alle erforderlichen Missionsparameter festlegen können:
Nach dem Aufrufen der Einstellungen muss nur noch eine Taste gedrückt werden, um eine Datei zu erhalten, die bei Bedarf bearbeitet werden kann. Ja, ich wollte Missionen im Voraus generieren und nicht während des Spiels, damit sie angepasst werden können.
Schauen wir uns den Generierungsprozess an:
Dies ist also ein gutes Tool, mit dem wir die Erstellung von Missionen um ein Vielfaches beschleunigen konnten. Darüber hinaus half es einigen Designern, die Angst vor einer Schreibblockade zu überwinden, da man nun in wenigen Sekunden eine fertige Lösung erhalten kann.
Im Artikel habe ich am Beispiel der Missionsgenerierung versucht zu zeigen, wie klassische Methoden des maschinellen Lernens und neuronale Netze bei der Spieleentwicklung helfen können. Heutzutage gibt es einen großen Trend hin zur generativen KI – aber vergessen Sie nicht andere Zweige des maschinellen Lernens, denn auch diese können viel.
Vielen Dank, dass Sie sich die Zeit genommen haben, diesen Artikel zu lesen! Ich hoffe, Sie haben eine Vorstellung davon, wie Missionen an generierten Orten angegangen werden und wie Missionen generiert werden. Haben Sie keine Angst, Neues zu lernen, entwickeln Sie sich weiter und machen Sie gute Spiele!
Illustrationen von shabbyrtist