Tutorial: generador aleatorio de niveles

Hoy os traigo algo un poco más jugoso que de costumbre, un sencillo tutorial sobre como crear un nivel de forma aleatoria (y no me refiero a típicos cutre-laberintos).

Una de las partes que más me gustan de juegos tipo Nethack o Angband es la capacidad que tienen de generar el mapeado de forma aleatoria y que además quede bien :). Este es un algoritmo sencillo pero efectivo que garantizará que se pueda tener acceso a todo el mapeado. Además es bastante fácil extrapolar las coordenadas de cada habitación, así que no tendreis ningún problema para evitar los pasillos a la hora de generar los objetos y enemigos.

Estaré encantado de intentar aclararos cualquier duda (usad los comentarios para ello).

Pues allá vamos:

1. Genera una habitación vacía que ocupe todo el nivel completo:

###########################################
#·········································#
#·········································#
#·········································#
#·········································#
#·········································#
#·········································#
#·········································#
#·········································#
#·········································#
###########################################

2. Escoge un punto a voleo en la habitacón (que no esté muy cerca de las paredes). Para la primera habitación será todo el mapa para las demás únicamente el espacio que estas ocupen:

###########################################
#·········································#
#·········································#
#·········································#
#·················X·······················#
#·········································#
#·········································#
#·········································#
#·········································#
#·········································#
###########################################

3. Genera un pasillo horizontal o vertical (escógelo de forma aleatoria). Ten cuidado de quitar el trozo de pared de los dos extremos del pasillo. erá igual de largo (o de ancho) que la habitación que estemos usando actualmente:

###########################################
#·········································#
#·········································#
###########################################
···········································
###########################################
#·········································#
#·········································#
#·········································#
#·········································#
###########################################

4. Como puedes ver ahora tienes dos habitaciones separadas pero falta permitir que se pueda acceder a ellas de alguna forma. Para ello crea en las dos paredes del pasillo dos puertas, una por pared, en un punto aleatorio:

###########################################
#·········································#
#·········································#
######+####################################
···········································
############################+##############
#·········································#
#·········································#
#·········································#
#·········································#
###########################################

5. Repite los pasos del 2 al 4 en las dos nuevas habitaciones que se han generado. Tantas veces como complejo quieres que sea el nivel, pero ten cuidado que haya aún espacio libre (fácilmente comprobable porque sabemos el tamaño y las coordenadas de las dos nuevas habitaciones).

Al final os quedará una cosa parecida a esta:

######·####################################
#····+·+··································#
#····#·#··································#
######+####################################
···········································
#################·##########+##############
#···············#·#·······················#
#···············+·+·······················#
#···············#·#·······················#
#···············#·#·······················#
#################·#########################

Por último sólo comentar que si queréis guardar el nivel no hace falta que lo guardéis entero, con que uséis la misma semilla para el generador de números aleatorio será suficiente.

Actualización: Como no he encontrado mi viejo código me he puesto esta mañana y he hecho uno nuevo en C#.

/*
Level
Copyright (C) 2006 samsaga2 (samsaga2@gmail.com)

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
using System;

namespace LevelGenerator
{
class Level
{
private int width;
private int height;
private char[,] map;

public Level(int width, int height)
{
map = new char[width, height];
this.width = width;
this.height = height;
}

public void print()
{
for (int y = 0; y < height; y++)
{
String s = "";

for (int x = 0; x < width; x++)
s += map[x, y];

Console.WriteLine(s);
}
}

public void generate(Random r)
{
clear();
createPassage(r, 1, 1, width - 3, height - 3);
}

private void clear()
{
for (int x = 0; x < width; x++)
{
map[x, 0] = '#';
map[x, height - 1] = '#';
}

for (int y = 0; y < height; y++)
{
map[0, y] = '#';
map[width - 1, y] = '#';
}

for (int x = 1; x < width - 1; x++)
for (int y = 1; y < height - 1; y++)
map[x, y] = '·';
}

private void createPassage(Random r, int room_x, int room_y, int room_w, int room_h)
{
// Comprobar que haya suficiente espacio
if(room_w <= 6 || room_h <= 6)
return;

// Coordenadas del nuevo pasillo
int x = 2 + r.Next() % (room_w - 4);
int y = 2 + r.Next() % (room_h - 4);
int dir = r.Next() % 2;

int room1_x, room1_y, room1_w, room1_h;
int room2_x, room2_y, room2_w, room2_h;
if (dir == 0)
{
// Dibujar el pasillo horizontal
for (int i = 0; i <= room_w; i++)
{
map[room_x + i, room_y + y - 1] = '#';
map[room_x + i, room_y + y + 1] = '#';
}
map[room_x - 1, room_y + y] = '·';
map[room_x + room_w + 1, room_y + y] = '·';

// Crear una puerta en cada pared del pasillo
int door1_x = 1 + r.Next() % (room_w - 1);
int door2_x = 1 + r.Next() % (room_w - 1);

map[room_x + door1_x, room_y + y - 1] = '+';
map[room_x + door2_x, room_y + y + 1] = '+';

// Coordenadas de las dos nuevas habitaciones
room1_x = room_x;
room1_y = room_y;
room1_w = room_w;
room1_h = y - 2;

room2_x = room_x;
room2_y = room_y + y + 2;
room2_w = room_w;
room2_h = room_h - y - 2;
}
else
{
// Dibujar el pasillo vertical
for (int i = 0; i <= room_h; i++)
{
map[room_x + x - 1, room_y + i] = '#';
map[room_x + x + 1, room_y + i] = '#';
}
map[room_x + x, room_y - 1] = '·';
map[room_x + x, room_y + room_h + 1] = '·';

// Crear una puerta en cada pared del pasillo
int door1_y = 1 + r.Next() % (room_h - 2);
int door2_y = 1 + r.Next() % (room_h - 2);

map[room_x + x - 1, room_y + door1_y] = '+';
map[room_x + x + 1, room_y + door2_y] = '+';

// Coordenadas de las dos nuevas habitaciones
room1_x = room_x;
room1_y = room_y;
room1_w = x - 2;
room1_h = room_h;

room2_x = room_x + x + 2;
room2_y = room_y;
room2_w = room_w - x - 2;
room2_h = room_h;
}

createPassage(r, room1_x, room1_y, room1_w, room1_h);
createPassage(r, room2_x, room2_y, room2_w, room2_h);
}
}
}