Generador automático de mapas cavernosos

El algoritmo para crear este tipo de mapas es, ni más ni menos, que un simple autómata celular. No hace falta tirar de funciones recursivas ni complicados bucles. Una de sus grandes bazas es que tiene multitud de parámetros con los que trastear para amoldarlo a gusto del consumidor. Pero como todo también tiene sus inconvenientes y es que no se garantiza que se pueda tener acceso a todas las regiones del mapa.

Comenzaré explicando una primera versión más sencilla pero que crea demasiadas zonas independientes:

1. Llenad el mapa de paredes a voleo. Lo que mejor me ha funcionado ha sido usar una probabilidad del 45% para que una celda se convierta en pared.

2. Ahora toca pasar el autómata celular. Por cada celda del mapa si la celda es una pared permanece siéndolo si tiene cuatro paredes vecinas (a un punto de distancia) y si es suelo vacío se convierte en pared si tiene, al menos, cinco paredes vecinas.
   
   n = celda actual
   v(n) = numero total de paredes a una unidad de distancia de n
   mapa’[n] = pared si mapa[n] = pared y v(n) >= 5 o v(n) = 4 sino vacío (1)
   

3. Repetir el paso dos unas cinco veces.

Una buena forma de intentar evitar que se creen zonas independientes es intentar no cerrar los pasillos en las zonas demasiado llenas. Para ello en las repeticiones cuatro y cinco podéis retocar un poco el autómata:

n = celda actual
v1(n) = número total de paredes a una unidad de distancia de n
v2(n) = número total de paredes a dos unidades de distancia de n

Para la cuarta repetición:

mapa’[n] = pared si (1) o v2(n) <= 2

Para la quinta repetición:

mapa’[n] = pared si (1) o v2(n) <= 1

Esto no evitará que se creen espacios inaccesibles pero si que los reducirá bastante. Podéis modificar el autómata a vuestro gusto para obtener todo tipo de mapas con las formas más diversas.

using System;

using System.Collections.Generic;
using System.Text;

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

public Level2(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, int p, int[][] values)
{
 randomizeMap(r, p);

 for(int i = 0; i < values.Length; i++)
     automata(values[i][0], values[i][1], values[i][2]);
}

private void randomizeMap(Random r, int p)
{
 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 y = 1; y < height - 1; y++)
     for (int x = 1; x < width - 1; x++)
         map[x, y] = (r.Next() % 100) > p ? '#' : '·';
}

private void automata(int param1, int param2, int param3)
{
 char[,] new_map = new char[width, height];

 for (int y = 0; y < height; y++)
     for (int x = 0; x < width; x++)
         if (x > 0 && x < width - 1 && y > 0 && y < height - 1)
         {
             int neighbors1 = countNeighbors1(x, y);
             int neighbors2 = countNeighbors2(x, y);

             bool wall = (neighbors1 >= param1) || (neighbors2 <= param2)
|| (neighbors1 >= param3 && getCellValue(x, y) == 1);
             new_map[x, y] = wall ? '#' : '·';
         }
         else
             new_map[x, y] = map[x, y];

 map = new_map;
}

private int countNeighbors1(int x, int y)
{
 int count = 0;

 for (int i = -1; i <= 1; i++)
     for (int j = -1; j <= 1; j++)
         if (i != 0 || j != 0)
             count += getCellValue(x + i, y + j);

 return count;
}

private int countNeighbors2(int x, int y)
{
 int count = 0;

 for (int i = -2; i <= 2; i++)
     for (int j = -2; j <= 2; j++)
         if (Math.Abs(i) == 2 || Math.Abs(j) == 2)
             count += getCellValue(x + i, y + j);

 return count;
}

private int getCellValue(int x, int y)
{
 if (x < 0 || x >= width || y < 0 || y >= height)
     return 0;

 return map[x, y] == '#' ? 1 : 0;
}
}
}

Y para usarlo:

Level2 l = new Level2(Console.WindowWidth - 1, Console.WindowHeight - 1);
l.generate(new Random(), 55, new int[][] {
 new int[] { 5, 0, 4 },
 new int[] { 5, 0, 4 },
 new int[] { 5, 0, 4 },
 new int[] { 5, 2, 4 },
 new int[] { 5, 1, 4 }
});
l.print();