Creación de mapas con Binary Space Partitioning (BSP)

Antes de empezar, vamos a definir un poco este concepto. BSP es una función que sirve para dividir recursivamente un espacio. Podemos usar este algoritmo para varias finalidades, pero en este caso vamos a usarlo para generar mazmorras de forma aleatoria y procedural. Para más detalle podemos visitar la wikipedia.

El reto de usar la aleatoriedad en la creación de escenarios es que los escenarios se mantengan consistentes a pesar de ser aleatorios. BSP nos permite mantener ambas características, aleatoriedad y solidez. La lógica del algoritmo no es complicada a priori, se basa en subdividir de forma recursiva un espacio en dos sub espacios.

Después, solo debemos usar el árbol (BST) para crear las conexiones de las salas.

Paso uno: Division

Para los ejemplos vamos a usar pseudocódigo que es aplicable a cualquier lenguaje y/o en cualquier motor de videojuegos, como por ejemplo Unity3D, Unreal Engine o Godot Engine

Definimos una clase, por ejemplo "sala".
Declaramos atributos numéricos protegidos para guardar "izquierda" , "derecha" , "arriba" , "abajo".
Declaramos métodos para obtener los valores anteriores.
Declaramos métodos para la obtener la "anchura" y "altura":
Obtenemos la anchura:
    return  derecha  -  izquierda  +  1 ;
Definimos un constructor para inicializar "izquierda , derecha , arriba , abajo".
Definimos método para pintar/renderizar:
{
    Declaramos un objeto que usaremos como contenedor/padre de la sala
    
    for loopcounterX = izquierda to derecha
        for loopcounterY = abajo to arriba
            Declaramos un objeto que usaremos de "tile"
            tile.position = vector(loopcounterX, loopcounterY)
            tile.parent = contenedor/padre
            loopcounterY = loopcounterY + 1
            
            tile.color = randomColor()
        endfor
        
        loopcounterX = loopcounterX + 1
    endfor    
    
    return contenedor/padre
}

El resultado en pantalla será algo así:

En este punto realizamos alguno cambios en la clase anterior haciéndola abstracta y haciendo virtual la función de pintar para luego sobreescribirla.

Dividiremos ahora ese espacio en dos con un corte horizontal, o vertical, al azar.

Para poder hacerlo, crearemos una nueva clase hija de "sala" por ejemplo "binarySala".

Necesitamos definir los máximos y mínimos (minAltura, maxAltura, minAnchura, maxAnchura) de las salas, podemos tenerlos donde mejor nos convenga por ejemplo un script de config's.

Definimos una nueva clase hija de la clase anterior.
Declaramos atributos para minAltura, maxAltura, minAnchura, maxAnchura.
Declaramos dos booleanos corteHorizontal y corteVertical que usaremos para saber si el nodo (sala) es un nodo hoja o no.
Declaramos dos variables del tipo BinarySala (salaDerecha y salaIzquierda)
Modificamos el constructor de la clase madre para inizializar el resto de variables a false y null

Creamos un nuevo método "esHoja" que retorne un booleano:
{
    return (salaDerecha is null && salaIzquierda is  null)
}

Creamos un método "separar":
{
    if random() > 0.5 && obtenerAnchura() >= 2 * minAnchura:
        separarVertical()
    else if obtenerAltura() >= 2 * minAltura:
        separarHorizontal()
}

Sobreescribimos la función de la clase madre "pintar":
{
    if esHoja:
        return super.pintar() //Si es hoja, llamamos la función de la clase madre
    else:
        salaIzquierda.pintar()
        salaDerecha.pintar()
        return 
}

El grafo siguiente podría ser un ejemplo de BST donde podemos ver los diferentes tipos de nodos.

Ahora viene la parte interesante, la función separarVertical y separarHorizontal.

Definimos la función separarHorizontal:
{
    int corte = randomRange(minAltura - obtenerAltura() - minAltura)
    
    salaIzquierda = new binarySala(izquierda, derecha, arriba-corte, abajo);
    salaDerecha = new binarySala(izquierda, derecha, arriba, arriba+1-corte);
}

Deberíamos obtener una imagen parecida a la siguiente:

Paso dos: agregar bordes

Si queremos que las salas no ocupen todo el espacio tendremos que añadir bordes. Añadimos una nueva variable a nuestra clase para poder parametrizar el espacio que queremos dejar entre salas "recortarSala". En este caso usaremos siempre el mismo valor, así que no podremos añadirle aleatoriedad.

Para ello crearemos una nueva función "recortar":
{
    izquierda += recortarSala
    derecha -= recortarSala
    arriba -= recortarSala
    abajo += recortarSala

    if salaIzquierda != null:
        salaIzquierda.recortar()
    if salaDerecha != null:
        salaDerecha.recortar()
}

Si llamamos la función "recortar" antes de pintar obtendremos un resultado parecido a esto:

Paso tres: agregar conexiones

Ahora solo nos falta añadir las conexiones que conectarán las salas. Para hacerlo vamos a conectar de forma recursiva cada nodo con su hermano. Crearemos métodos para encontrar todas las posiciones donde podamos agregar pasillos. También crearemos una nueva clase pasillo para poder definir algunos atributos y su método pintar.

TODO binarySala methods
Declaramos un método que retorne una lista de números enteros "obtenerConexionesDerecha()":
{
  Definimos una lista de números enteros "conexiones"

  if !esHoja():
    if salaDerecha != null:
      conexiones.AddRange(salaDerecha.obtenerConexionesDerecha())
    if corteHorizontal && salaIzquierda != null:
      conexiones.AddRange(salaIzquierda.obtenerConexionesDerecha())
  else:
    for loopcounter = abajo + corridorMargin to top - corridorMargin
      conexiones.Add(loopcounter);
      loopcounter = loopcounter + 1
    endfor
  
  return connections;
}

TODO pasillo class

Al crear los pasillos el resultado del mapa final debería ser algo así:

License

MIT

Free Software, Hell Yeah!

Code & Love