IKG2018/Einführung/ Philipp
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Javascript</language>
<h1>Der Dungeon Generator: Prozeduale Content Generierung in Vidospielen</h1><br>
<h2>Der Dungeon Generator</h2><br>
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.<br>
<h2>Erstellung eines Dungeon Generators</h2>
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.<br>
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.
<code id="5a970b4522086">
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 = [];
}
}
</code>
<run id="5a9713f173c46">
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");
</run>
<p id="MapWindow1"></p>
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.
<code id="5a97103fd45d7">
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; }
}
}}
</code>
<run id="5a9713f173cc6">
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");
</run>
<p id="MapWindow2"></p>
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.
<code id="5aa985669ede4">
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; }
}
}
}
</code>
<run id="5aa985669ee96">
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");
</run>
<p id="MapWindow3"></p>
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.
<h2>Beispiele für gute Dungeon Generatoren</h2>
Hier sind einige Beispiele von Spielen die Sehr gute und Komplexe Implementationen solcher Techniken aufzeigen. <br>
<ul>
<li> Rogue (1980)</li>
<li> Die Pokemon Mystery Dungeon Reihe</li>
<li> The Binding of Isaac : Rebirth</li>
<li> Dungeons of Dredmor</li>
</ul>
<run id="5ab2b468ba349">
function Fakultaet(n){
var x= 1;
for(var i=1; i<=n; i++){
x = x*i;
}
return x;
}
function Affe(n){
var k = Math.pow(4,(n*n))*Fakultaet((n*n));
return k;
}
Affe(2);
</run>