Level Erzeugung per evolutionärem Algorithmus == Grenzenloser Spaß?
Moin moin und hallo,
in diesem Artikel möchte ich mich erneut evolutionären (oder auch genetischen) Algortihmen widmen.
Das werde ich dieses Mal nicht anhand einer Tonleiter machen, sondern versuchen ein Level für ein Jump & Run Spiel zu erzeugen.
Was sind evolutionäre Algorithmen?
Zunächst möchte ich die Funktionsweise von evolutionären Algorithmen kurz zusammenfassen.
Grundsätzlich durchläuft jeder Algorithmus immer die gleiche Schleife:
Im Details heißt das:
1. Wir initialiseren eine Startpopulation
2. Wir prüfen ob die Population bereits eine gesuchte Lösung enthält, falls ja beenden wir den Prozess
3. Andernfalls suchen wir uns die besten Individuen aus und entfernen die schlechtesten
4. Wir kombinieren die gewählten Individuen um neue Kinder zu erzeugen
5. Wir mutieren das Genom der erzeugten Kinder
6. Gehe zu 2.Initialisierung
Der erste Schritt zur Erstellung des Algorithmus ist die Definition des Genoms, denn daraus lässt sich dann die Funktionsweise der Kombination bzw. Mutation ableiten. Für das Spiel Level heißt es:
- Ein Level hat eine gewisse Breite und Höhe
- In einer Position(X,Y) ist ein Block “Fest”, repräsentiert durch ein ‘#’, oder “Leer”, repräsentiert durch ein ‘ ‘, definiert
Beispiel mit Level 100x20:
Das Model sieht als Klasse wie folgt aus:
const FieldGenerator = require("./FieldGenerator");
const Point = require("./Point");
const _ = require("lodash");
class Level {
constructor(width = 100, height = 20, initialize = true) {
this.map = {};
this.width = width;
this.height = height;
this.fieldGen = new FieldGenerator();
this.fitness = false;
if (initialize) {
this.initializeMap();
}
}
initializeMap() {
for (var x = 0; x < this.width; x++) {
this.map[x] = this.map[x] || {};
for (var y = 0; y < this.height; y++) {
let point = new Point(x, y, this.fieldGen.getRandomFieldType());
//obere hälfte ist leer
if (y < this.height / 2 + 4) {
point.type = this.fieldGen.getFieldForValue(0);
}
this.map[x][y] = point;
}
}
}
getPoint(x, y) {
if (!this.map[x]) {
return null;
}
return this.map[x][y];
}
setPoint(p, x, y) {
this.map[x] = this.map[x] || {};
this.map[x][y] = _.clone(p);
}
//für eine schönere Darstellung in der Konsole
inspect(depth, opts) {
let resultString = "Fitness: " + this.fitness + "\r\n";
for (var y = 0; y < this.height; y++) {
for (var x = 0; x < this.width; x++) {
if(this.map[x][y].type) {
resultString += (this.map[x][y].type.display);
}
}
resultString += "\r\n";
}
return resultString;
}
isEmpty(x, y) {
let p = this.getPoint(x, y);
return p && p.type.value === 0;
}
isGround(x, y) {
let p = this.getPoint(x, y);
return p && p.type.value === 1;
}
}
module.exports = LevelDamit unser Algorithmus das gesuchte Levelkonstrukt entwickeln kann, brauchen wir eine ganze Level-Population, bestehend aus 20 Individuen.
Diese Individuen erzeugen wir weitesgehend zufällig, denn ich möchte das die obere Hälfte am Anfang leer bleibt, um Raum für Mutationen zu geben, und die untere Hälfte in jedem Fall Platformen beinhaltet, auf denen der Spieler sich bewegen kann.
Die Populations-Klasse sieht wie folgt aus:
const Level = require("./Level");
const Validator = require("./Validator");
const Kombinator = require('./Kombinator');
const fs = require('fs');
class Population {
constructor(size = 0) {
this.levelList = [];
this.validator = new Validator();
this.kombinator = new Kombinator();
this.size = size;
this.filename = "level/lastPopulation.json";
for (var i = 0; i < size; i++) {
this.levelList.push(new Level())
}
this.validate();
this.sortByFitness();
}
validate() {
this.levelList.forEach(function (level) {
if (!level.fitness) {
level.fitness = this.validator.getFitness(level);
}
}, this)
}
removeUnfittest(amount = 14) {
//remove last x levels
for (var i = 0; i < amount; i++) {
this.levelList.pop();
}
}
sortByFitness() {
this.levelList.sort(function (a, b) {
return b.fitness - a.fitness;
});
}
repopulate() {
const l = (this.size - this.levelList.length) / 2;
for (var i = 1; i < l; i++) {
this.levelList = this.levelList.concat(this.kombinator.combine(this.levelList[0], this.levelList[i]));
}
for (var i = this.levelList.length; i < this.size; i++) {
this.levelList.push(new Level());
}
this.validate();
this.sortByFitness();
}
printPrettyWinner() {
return this.levelList[0];
}
getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
save() {
console.log("Saving population..");
//muss synchron sein, da die while schleifen den haupt-thread blockiert
fs.writeFileSync(this.filename, JSON.stringify(this.levelList))
}
load() {
if (fs.existsSync(this.filename)) {
console.log("Loading population..");
let levelMaps = JSON.parse(fs.readFileSync(this.filename));
levelMaps.forEach(function (lvl, idx) {
this.levelList[idx].map = lvl.map;
this.levelList[idx].fitness = false;
}, this)
} else {
this.save();
}
}
saveTop() {
fs.writeFileSync("level/level_" + this.levelList[0].fitness + "_" + (new Date().getTime()) + ".json", JSON.stringify(this.levelList[0]));
}
}
module.exports = Population;Wie man in der Population sehen kann sortieren wir die Population nach jedem Durchlauf anhand des Fitness-Wertes. Das heißt ab erste Stelle ist immer das Level mit der größten und an letzter Stelle das Level mit der kleinsten Fitness.
Dadurch können wir viele vom Fitnesswert abhängigen Berechnungen vereinfachen.
Evaluierung
Wir brauchen also ein Wertesystem mit dem wir die Fitness einzelner Individuen messen können.
Das machen wir mit Hilfe des folgenden Belohnungssystems:
1. Wir belohnen die Bildung von '#'-Spalten
2. Wir belohnen die Bildung von ' '-Spalten
3. Wir belohnen die Bildung von mindestens zwei '#'-Spalten nebeneinander
4. Wir belohnen wenn zwei '#'-Elemente maximal 3 leere Felder entfernt von einander liegen
5. Wir belohnen die Bildung von HöhlenUm den die Konvergenz zu verstärken, bestrafen wir alle Abweichungen von unserem Belohnungssystem.
Durch das Belohnungssystem können wir jetzt genau einschätzen wie gut sich unsere Population entwickelt und steuern durch die Höhe der Belohnungen die Bildung bestimmte Eigenschaften.
Der Validator sieht wie folgt aus:
class Validator {
constructor() {
}
getFitness(level) {
let fitness = 0;
fitness += this.fitnessForCoherence(level);
return fitness
}
fitnessForCoherence(level) {
let fitness = level.width * level.height;
for (var x = 0; x < level.width; x++) {
for (var y = 0; y < level.height; y++) {
//Wenn über einem feld ein bodenfeld ist, muss darunter auch eins sein
fitness += this.groundShouldBeAColumn(level, x, y);
fitness += this.emptyShouldBeAColumn(level, x, y);
//mindestens 2 nebeneinander liegende Bodenfelder
fitness += this.groundShouldBeAtLeast2Columns(level, x, y);
//In X Ache abstände zwischen zwei Bodenfeldern nicht mehr als 3 felder
fitness += this.distanceBetweenGroundShouldBeMax3Columns(level, x, y);
//wenn eine leere fläche erkannt wird, überprüfe ob es eine höhle ist
if (this.isCave(level, x, y)) {
fitness += 15;
fitness += this.caveShouldBeAtLeast3Columns(level, x, y);
}
}
}
return fitness;
}
isFieldEmpty(level, x, y) {
let p = level.getPoint(x, y);
return p && p.type.value === 0;
}
isFieldGround(level, x, y) {
let p = level.getPoint(x, y);
return p && p.type.value === 1;
}
isCave(level, x, y) {
let result = false;
if (y > 5 && y < level.height - 5) {
//#
//(.)
//.
//.
//#
result = result || this.isFieldGround(level, x, y - 1) && this.isFieldEmpty(level, x, y) && this.isFieldEmpty(level, x, y + 1) && this.isFieldEmpty(level, x, y + 2) && this.isFieldGround(level, x, y + 3);
//#
//.
//(.)
//.
//#
result = result || this.isFieldGround(level, x, y - 2) && this.isFieldEmpty(level, x, y - 1) && this.isFieldEmpty(level, x, y) && this.isFieldEmpty(level, x, y + 1) && this.isFieldGround(level, x, y + 3);
//#
//.
//.
//(.)
//#
result = result || this.isFieldGround(level, x, y - 1) && this.isFieldEmpty(level, x, y) && this.isFieldEmpty(level, x, y + 1) && this.isFieldEmpty(level, x, y + 2) && this.isFieldGround(level, x, y + 3);
}
return result;
}
caveShouldBeAtLeast3Columns(level, x, y) {
let value = 0;
if (x > 4) {
//(.)..
if (this.isCave(level, x + 1, y) && this.isCave(level, x + 2, y)) {
value += 5;
}
//.(.).
if (this.isCave(level, x + 1, y) && this.isCave(level, x - 1, y)) {
value += 10;
}
//..(.)
if (this.isCave(level, x - 1, y) && this.isCave(level, x - 2, y)) {
value += 5;
}
}
return value;
}
groundShouldBeAColumn(level, x, y) {
if (y > 0) {
let point = level.getPoint(x, y);
let upperPoint = level.getPoint(x, y - 1);
if (upperPoint.type.value === 1 && point.type.value !== 1) {
return -10;
}
return 2;
}
return 0;
}
emptyShouldBeAColumn(level, x, y) {
if (y > level.height / 2 && y < level.height - 2 && this.isFieldEmpty(level, x, y)) {
let point = level.getPoint(x, y);
let upperPoint = level.getPoint(x, y - 1);
if (this.isFieldEmpty(level, x, y - 1) && this.isFieldEmpty(level, x, y + 1)) {
if (this.isFieldGround(level, x-1, y) && this.isFieldGround(level, x + 2, y) && this.isFieldEmpty(level, x + 1, y) && this.isFieldEmpty(level, x + 1, y + 1) && this.isFieldEmpty(level, x + 1, y - 1)) {
return 15;
}
return 5;
}
return -10;
}
return 0;
}
groundShouldBeAtLeast2Columns(level, x, y) {
if (x > 0) {
let point = level.getPoint(x, y);
let leftPoint = level.getPoint(x - 1, y);
if (leftPoint.type.value === 1 && point.type.value !== 1) {
return -10;
}
return 1;
}
return 0;
}
distanceBetweenGroundShouldBeMax3Columns(level, x, y) {
if (x > 2 && y > 2 && level.getPoint(x, y).type.value === 1) {
for (var i = x - 2; i < x + 2; i++) {
for (var j = y - 2; j < y + 2; j++) {
if (x != i && y != j) {
if (level.getPoint(i, j) && level.getPoint(i, j).type.value === 1) {
return 5;
}
}
}
}
return -10;
}
return 0;
}
}
module.exports = ValidatorHaben wir eine Lösung unter den Individuen gefunden, terminieren wir das Programm.
Aber woher wissen wir ob überhaupt eine Lösung dabei ist? Das ist anhängig von dem jeweiligen Problem.
Für das Level-Problem konnte ich experimentell die folgendes Terminierungskriterium finden, dass für mich die besten Levelstrukturen erzeugt:
class Terminator {
constructor() {
}
isDone(levelList) {
return levelList[0].fitness >= levelList[0].width * 100 + levelList[0].width * levelList[0].height;
}
}
module.exports = TerminatorFür die aktuell gewählte Levelgröße heißt es also, dass dann eine Lösung gefunden wurde, wenn ein Fitnesswert über 12000 erreicht worden ist.
Selektion
Für die Kombination wählen wir die Top 6 Individuen, d.h. wir entfernen die schlechtesten 14.
In der Population-Klassen gibt es zu diesem Zweck die “removeUnfittest”-Funktion:
removeUnfittest(amount = 14) {
for (var i = 0; i < amount; i++) {
this.levelList.pop();
}
}Kombination
Wie im echten Leben hat unsere Population ohne Kinder keine Zukunft. Aber wie kombinieren wir unsere besten zwei Individuen? In dem vorliegenden Fall trennen wir das Genom der beiden Eltern in jeweils zwei Teile und setzen diese über Kreuz wieder zusammen.
Das heißt wir nehmen den Teil (0 <= x <= 50 und 0 <= y <= 20) von Elternteil 1 und kombinieren diesen mit Teil (51 <= x <= 100 und 0 <= y <= 20) von Elternteil 2 um das erste Kindindividuum zu erzeugen und dann reziprok für das zweite Kind.
Das Gleiche machen wir mit dem besten Individuum für alle Top 6 Individuen.
Die Kombination erfolgt in einer eigenen Klasse:
const Level = require("./Level");
const Mutator = require("./Mutator");
class Kombinator {
constructor() {
this.mutator = new Mutator();
}
combine(level1, level2) {
let child1 = new Level(level1.width, level1.height, false);
let child2 = new Level(level1.width, level1.height, false);
for (var x = 0; x < level1.width; x++) {
for (var y = 0; y < level1.height; y++) {
if (x < level1.width / 2) {
child1.setPoint(level1.getPoint(x, y), x, y)
child2.setPoint(level2.getPoint(x, y), x, y)
} else {
child1.setPoint(level2.getPoint(x, y), x, y)
child2.setPoint(level1.getPoint(x, y), x, y)
}
this.mutator.mutate(child1, x, y);
this.mutator.mutate(child2, x, y);
}
}
return [child1, child2]
}
getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
}
module.exports = KombinatorMutation
Um zu verhindern, dass sich unsere Evolution zu schnell in einer Sackgasse (lokales Maximum oder Minimum) wieder findet, müssen wir die Gene jedes neu erzeugten Kindes mit einer Wahrscheinlichkeit von 2% mutieren.
Das heißt dass selbst wenn wir kurzfristig, über mehrere Generationen, in einem gewissen Zustand (Fitnesswert) verharren, geht es irgendwann doch weiter, weil ein Gen mutiert worden ist.
Man muss hier jedoch auch aufpassen, dass die Mutationsrate nicht zu hoch angesetzt wird, denn das hätte wieder den Effekt dass die Population zu viele Varianzen enthält und die Evolution nicht zu dem von uns gewünschten Zustand konvergiert.
Die Mutation wird bei unserem Level-Beispiel, je Position neu gewürfelt.
const FieldGenerator = require("./FieldGenerator");
class Mutator {
constructor() {
this.fieldGenerator = new FieldGenerator();
}
mutate(level, x, y) {
//Jedes Feld durch gehen und zufällig flippen
if (this.getRandomInt(1, 100) <= 1) {
let p = level.getPoint(x, y);
p.type = this.fieldGenerator.getRandomFieldType();
level.setPoint(p, x, y);
level.fitness = false;
}
return level
}
getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
}
module.exports = MutatorTestlauf
Alle genannten und beschriebenen Zwschenschritte müssen jetzt nur noch zusammen gefasst werden:
const Population = require('./model/Population');
const Terminator = require('./model/Terminator');
let start = new Date();
console.log("Initializing: ", start)
let pop = new Population(20);
let terminator = new Terminator();
let generation = 0;
while (!terminator.isDone(pop.levelList)) {
pop.removeUnfittest();
pop.repopulate();
generation += 1;
if (generation % 200 == 0) {
pop.save();
}
console.log("\r\nGeneration: ", generation, " Pop: ", pop.levelList.length, "\r\n", pop.printPrettyWinner());
}
pop.saveTop();
let end = new Date();
console.log("Runtime: ", (end.getTime() - start.getTime()) / 1000, "s")
console.log("Final: \r\n", pop.printPrettyWinner())Wie sieht das nun im echten Durchlauf aus?
Das obige Video zeigt nur die ersten zwei Minuten, denn der vollständige Prozess dauert ~15 Minuten und lieferte schlussendlich das folgende Resultat:
Aber wie sieht das dann in einem Spiel aus? Zunächst sei gesagt, dass das Level im JSON-Format gespeichert worden ist und von dem Spiel, das ich gleich zeigen werde, importiert worden ist.
Anders als in der Vorschau in der Konsole, sind die Tiles im Spiel breiter als hoch. Es kann deshalb verwirrend aussehen, aber seien Sie versichert, dass folgende Level wurde vollständig (inklusive der Gegenstände und Gegner, auf die ich nicht eingegangen bin) vom Algorithmus erzeugt.
Hier ist der Höhlenmensch Jeff, der einen fremden Planeten erkundet:
Fazit
Wie man den Videos entnehmen kann funktioniert der Algorithmus soweit ganz gut, d.h. wir erhalten nach einer gewissen Zeit ein akzeptables Ergebnis.
Sollten wir eher flachere oder Levels mit weniger Abständen zwischen den Flächen haben wollen, muss man nur an dem Belohnungssystem drehen. Das Finden der richtigen Konfiguration ist, so finde ich, weniger aufwändig als das Level vollständig manuell zu erstellen, das Ergebnis lässt sich wieder verwenden, und es macht mehr Spaß bei der Evolution zu zu schauen (hat etwas vom Aquarium-Effekt).
Nur ist die Laufzeit derzeit noch relativ lang (Im Schnitt 15 - 30 Minuten). Das liegt unter anderem daran dass ich noch gar nicht in die Optimierung eingestiegen bin. Einige Schleifen lassen sich sehr gut zusammenfassen und der Validierungs-Prozess lässt sich auch parallelisieren.
Man muss dies erneut dem manuellen Prozess gegenüberstellen, das Erzeugen des gefundenden Levels hätte manuell sicher ~ 60 Minuten gedauert.
Anders als in einem prozedual generierten Ansatz, gibt es hier keinen Seed, d.h. das Ergebnis der Erzeugung lässt sich nicht 100% zuverlässig reproduzieren.
Wir erhalten jedes Mal ein anderes Level, das aber ähnliche Eigenschaften aufweist. Je größer das Level gewählt wird und je mehr Variationen, Gegenstände, Gegner usw. einführt, desto abwechslungsreicher und komplexer werden dann die finalen Level.
Das ist auch einer der hauptsächlichen Gründe warum man einen evolutionären Algorithmus zur Lösungsfindung wählen würde.
Wenn der gesuchte Lösungsraum unbekannt oder undurchsichtig ist, aber man grundsätzliche Regeln festlegen kann, den eine Lösung genügen muss, dann ist man mit einem evolutionären Algorithmus sehr gut aufgehoben.
#### In diesem Sinne, bis demnächst!