Google
 

lunes, junio 26, 2006

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();

5 comentarios:

Anónimo dijo...

Geniales estos posts de generación de mapas ;)

Un saludo

Javi Santana dijo...

Falta una imagen o algo para tener una idea clara no? Muy interesante!

Victor M. dijo...

La imagen la tenia preparada pero se me olvido subirla, alla va.

Jove Chiere dijo...

Adoro este tipo de mapas a lo rogue-like. (si, un grafista 3d que le gusta el ascii)

Por supuesto del codigo, poco tengo que opinar ya que poco (o nada) entiendo lo que pone.

Buen post.

Victor M. dijo...

Es que mi afición por la generación automática de mapas viene de juegos como el Nethack o Angband (todos rogue-like), de ahi que estén hechos todos con caracteres.