Aus ProgrammingWiki

Inhaltsverzeichnis 1 Der Dungeon Generator: Prozeduale Content Generierung in Vidospielen 1.1 Der Dungeon Generator 1.2 Erstellung eines Dungeon Generators 1.3 Beispiele für gute Dungeon Generatoren

Der Dungeon Generator: Prozeduale Content Generierung in Vidospielen

Der Dungeon Generator

Zuffalsgenerierter Spielinhalt spielt in den Videospielen von Heute eine größere Rolle als je zuvor. Von einzelnen Gegenständen zu ganzen Welten können viele Dinge so kostensparender erstellt werden. In vielen Spielen existieren Strukturen wie Höhlen, Verließe, Festungen und Türme deren innenleben leicht Zufallsgeneriert werden können, man fasst diese heutzutage unter dem Englischen Begriff für Verließ zusammen: Dungeon.

Erstellung eines Dungeon Generators

Es gibt mehrere Methoden einen Dungeon Generator zu schreiben, welche man nimmt kommt auf das Game Design an. So kann man zum Beispiel Handgemachte Räume in zufälliger Anordnung aneinanderreihen da es dem Designer Bestimmte Vorteile gibt Kämpfe und Schätze vorsichtiger zu Verteilen. Man kann jedoch auch alles von Grund auf zufallsgenerieren zu lassen.
Ein erster Schritt sollte sein ein Perfektes Labyrinth zu generieren. Dazu gibt es einfache Methoden. Das hier ist Flood Fill mit Zuffalszahlen. Der Rekursive Algorithmus nimmt die Zufallszahlen aus einer vorher erstellten Reihe, dem Seed. Daraufhin füllt er die komplette Fläche mit Gängen, indem er einen weg gemäß des Seedes entlanggeht bis er in eine Sackgasse kommt. Dann dreht er um geht andere Wege bis die Fläche gefüllt ist. Beliebige zwei Punkte in diesem Labyrinth sind durch nur einen Einzelnen Pfad miteinander verbunden.

var Randdir = []; for (var h = 0; h < 500; h++) { var tem=[1,2,3,4]; Randdir[h] =tem; Randdir[h]=Shuffle(Randdir[h]); } function Generate(glocation){ for (var i = 0; i <x; i++) { var arr = []; for (var j = 0 ; j < y; j++) { arr[j] = 1; } map[i] = arr; } for (var k = 0; k < map.length; k++) { var para = document.createElement("DIV"); para.id=("para"+k); for (var l = 0 ; l < map[0].length ; l++) { var img = document.createElement("IMG"); img.setAttribute("src", "http://programmingwiki.de/images/1/19/Philipp_Malchin_Tile_12.png"); img.setAttribute("height", 24); img.setAttribute("width", 24); img.id = (glocation + k + "a" + l); para.appendChild(img); } document.getElementById(glocation).appendChild(para); } } function FloodGenerate(xcor, ycor, dep, curdep) { map[xcor][ycor]= 2; for (var i = 0; i < 4; i++) { if (Randdir[curdep][i] == 1) { if (xcor + 2 < map.length-1) { if (map[xcor + 2][ ycor] != 2) { map[xcor + 1][ ycor]= 2; FloodGenerate(xcor + 2, ycor, dep, curdep + 1); }}} if (Randdir[curdep][i] == 2){ if (ycor + 2 < map[0].length-1){ if (map[xcor][ ycor + 2]!= 2){ map[xcor][ ycor + 1] = 2; FloodGenerate(xcor, ycor + 2, dep, curdep + 1); }}} if (Randdir[curdep][i] == 3){ if (xcor - 2 > 0){ if (map[xcor - 2][ ycor] != 2){ map[xcor - 1][ ycor]= 2; FloodGenerate(xcor - 2, ycor, dep, curdep + 1); }}} if (Randdir[curdep][i] == 4){ if (ycor - 2 > 0){ if (map[xcor][ ycor - 2] != 2){ map[xcor][ ycor - 1] = 2; FloodGenerate(xcor, ycor - 2, dep, curdep + 1); }}} } return; } function Shuffle(array) { var currentIndex = array.length, temporaryValue, randomIndex; while (0 !== currentIndex) { randomIndex = Math.floor(Math.random() * currentIndex); currentIndex -= 1; temporaryValue = array[currentIndex]; array[currentIndex] = array[randomIndex]; array[randomIndex] = temporaryValue; } return array; } function update(ulocation) { for (var xd = 0; xd < x; xd++) { for (var yd = 0 ; yd <y ; yd++) { if (map[xd][yd]==2){ path="http://programmingwiki.de/images/7/7e/Philipp_Malchin_Tile_2.png"; } else{ path="http://programmingwiki.de/images/1/19/Philipp_Malchin_Tile_12.png"; } var img = document.getElementById(ulocation + xd + "a" + yd); img.setAttribute("src", path ); } } } function Reset(rlocation){ if (document.getElementById(rlocation + "0a0")!=null ) { for (var i = 0; i < x; i++) { for (var j = 0 ; j < y ; j++) { var img = document.getElementById(rlocation + i + "a" + j); img.parentNode.removeChild(img); } var para = document.getElementById("para" + i); para.parentNode.removeChild(para); } map = []; } }

var map = []; //Festlegen von Startparametern x=31; y=31; Reset("MapWindow1"); Generate("MapWindow1"); FloodGenerate(1, 1, 10, 0); // x, y, Maximale Tiefe ,Tiefe update("MapWindow1");

ausführen

Da Ein Perfektes Labyrinth jedoch zumeist langweilig ist fügt man Imperfektionen ein, das heißt das Gänge miteinander verbunden werden die es dem Spieler erlauben im kreis zu gehen. Dies wirkt natürlicher. Ein bestimmter Prozentsatz an Wänden mit zwei angrenzenden gegenüberliegenden Gängen wird entfernt. Dieses Labyrinth ist außerdem viel zu voll, ein typischer Dungeon besteht nicht nur aus Gängen sondern vorallendingen aus Räumen. Ein bestimmter Prozentsatz der Sackgassen, also Gängen mit drei angrenzenden Wänden wird Stück für Stück wieder geschlossen. Damit unterschiedlichen Spielumgebungen eine unterschiedliche Ästhetik gegeben werden kann, kann man diese Parameter verändern.

function Imp(percor,imp){ var cw=0; //Zählen der Gänge for (var xl = 0; xl < x; xl++) { for (var yl = 0; yl < y; yl++) { if (map[xl][ yl] == 2) { cw++; } } } var ch = cw; //Ausdünnung cw = Math.round(cw - (cw / 100) * percor); while (ch > cw) { var gxy = []; for (var xl = 0; xl < x; xl++) { for (var yl = 0; yl < y; yl++) { if (map[xl][yl] == 2) { var m=0; if (map[xl + 1][ yl]!= 2) { m++; } if (map[xl - 1][ yl]!= 2) { m++; } if (map[xl][yl-1]!= 2) { m++; } if (map[xl][yl+1]!= 2) { m++; } if (m >= 3) { gxy.push([xl,yl]); } } } } Shuffle(gxy); var gc = gxy.length; for (var i = 0; i < gc; i++) { map[gxy[i][0]][gxy[i][1]] = 1; ch--; if (ch < cw) { break; } } } cw = ch; //Imperfektion cw = Math.round(cw + (cw / 100) * (percor/imp)); while (ch < cw) { var gxy = []; for (var xl = 1; xl < x-1; xl++) { for (var yl = 1; yl < y-1; yl++) { if (map[xl][yl] != 2) { var mx = 0; var my = 0; if (map[xl + 1] [yl]== 2) { my++; } if (map[xl - 1] [yl]== 2) { my++; } if (map[xl] [yl - 1]== 2) { mx++; } if (map[xl] [yl + 1]== 2) { mx++; } if (((mx == 2 && my==0)&&(yl%2==1))||((my==2 && mx==0)&&(yl%2==1))) { gxy.push([xl,yl]) } } } } Shuffle(gxy); var gc = gxy.length; for (var i = 0; i < gc; i++) { map[gxy[i][0]][gxy[i][1]] = 2; ch++; if (ch > cw) { break; } } }}

var map = []; x=31; y=31; Reset("MapWindow2"); Generate("MapWindow2"); FloodGenerate(1, 1, 10, 0); // x, y, Maximale Tiefe ,Tiefe Imp(30,36); // Regression, Imperfektion (in %) update("MapWindow2");

ausführen

Nun fehlen noch die Eigentlichen Räume. Es gibt auch Möglichkeiten diese vor den Gängen zu erstellen, jedoch ist es aufwendiger die Gänge danach zu erstellen. In diesem Beispiel sollen die Räume perfekt in das Gangnetz passen und sich nicht überlappen. Dies simuliert am einen unterirdischen Gangkomplex von Menschenhand erbaut z.B. ein Mausoleum. Ändert man das so erhält man Strukturen die mehr natürlichen höhlen ähneln. Für diesen Zweck können auch noch Raumform und Positionierung geändert werden. Die Räume hier sind Rechtecke zufälliger ungerader Größe und Position.

function Room(rn,rxmax,rymax,rxmin,rymin,ctry){ var count=0; for (var i = 0; i < rn; i++) { //Rooms var rlx = Math.floor((Math.random() * (rxmax - parseInt(rxmin))) + parseInt(rxmin)+1); var rly = Math.floor((Math.random() * (rxmax - parseInt(rxmin))) + parseInt(rymin)+1); var rpx = Math.floor((Math.random() * (x - (2 + rlx)))+1 ); var rpy = Math.floor((Math.random() * (y - (2 + rly)))+1 ); if (rlx % 2 == 0) { rlx--; } if (rly % 2 == 0) { rly--; } if (rpx % 2 == 0) { rpx--; } if (rpy % 2 == 0) { rpy--; } var bul = true; for (var xl = rpx; xl < rpx + rlx; xl++) { for (var yl = rpy; yl < rpy + rly; yl++) { if (map[xl][yl] == 4) { bul = false; } } } if (bul == true) { for (var xl = rpx; xl < rpx + rlx; xl++) { for (var yl = rpy; yl < rpy + rly; yl++) { map[xl][yl] = 4; } } } else { i--; count++ if (count > ctry) { i++; } } } for (var xl = 0; xl < x; xl++) { for (var yl = 0; yl < y; yl++) { if (map[xl][yl] == 4) { map[xl][yl] = 2; } } } }

var map = []; x=40; y=40; var map = []; x=31; y=31; Reset("MapWindow3"); Generate("MapWindow3"); FloodGenerate(1, 1, 10, 0); // x, y, Maximale Tiefe ,Tiefe Imp(30,36); // Regression, Imperfektion (in %) Room(5,9,9,5,5,20) // Anzahl, maximale Große x, y, Minimale Große x, y, versuche einen Raum zu Plazieren update("MapWindow3");

ausführen

Mit den voreingestellten Parametern besteht die Chance das ein Raum nicht mit allen anderen verbunden ist, obwohl diese äußerst gering ist. Dies kann durch einen einfachen Test verhindert werden der zuerst alle vorhanden Gänge zählt und danach alle mit einem beliebigen gang verbundenen Felder zählt. Sind die Zahlen nicht gleich so ist es am einfachsten die Prozedur zu wiederholen anstatt zu versuchen den einsamen Raum zu verbinden. Jetzt können noch dinge wie eine Startposition und ein Ziel, Gegner, Fallen und schätze Platziert werden. Die Vorgänge sind im wesentlichen die selben.

Beispiele für gute Dungeon Generatoren

Hier sind einige Beispiele von Spielen die Sehr gute und Komplexe Implementationen solcher Techniken aufzeigen.

• Rogue (1980)
• Die Pokemon Mystery Dungeon Reihe
• The Binding of Isaac : Rebirth
• Dungeons of Dredmor