BSP dungeons: mazmorras roguelike clásicas

0. El algoritmo que sostiene a Rogue

Rogue (1980) generaba un dungeon distinto cada partida. Tres décadas después, su descendencia — NetHack, ToME, DCSS, ADOM — sigue usando una variante del mismo algoritmo: Binary Space Partitioning para dungeons.

La idea es brutalmente simple:

1. Empieza con un AABB (rectángulo del nivel completo).
2. Pártelo en dos sub-rectángulos por una línea horizontal o vertical.
3. Recursea sobre cada sub-rectángulo hasta que sean lo bastante chicos.
4. En cada hoja, coloca una habitación más chica con padding aleatorio.
5. Conecta cada par hermano del árbol con un corredor.

Resultado: dungeon variado pero garantizado conexo. Cada habitación es alcanzable desde cualquier otra.

1. Split2. Rooms3. Corridors

⏸ Pausar↻ Seed: 11

Nivel revelado: 0 / 5

Fase 1 — Split: el AABB se parte recursivamente en dos hasta llegar a tamaño mínimo. Fase 2 — Rooms: dentro de cada hoja, se coloca una habitación con padding aleatorio. Fase 3 — Corridors: las habitaciones de cada par hermano se conectan, subiendo por el árbol. Resultado: dungeon totalmente conexo.

Figura 1 — Las tres fases. Pulsa “Auto” para verlo en loop, o cambia de fase manualmente con los botones. Cada nivel del árbol tiene un color distinto.

1. Por qué BSP y no otra cosa

Algoritmo	Conectividad	Variedad	Estructura
Random rooms + delaunay	Casi siempre	Alta	Caótica
Cellular automata	A veces (a verificar)	Alta	Orgánica
WFC	Si las reglas lo garantizan	Alta	Por reglas
BSP	Siempre, por construcción	Media-alta	Cuadricular

BSP gana cuando necesitas:

• Dungeons con habitaciones definidas (no cuevas amorfas).
• Conectividad garantizada sin tener que verificarla post-hoc.
• Implementación simple (~100 líneas).
• Performance — milisegundos para mapas de 100×100.

Pierde cuando quieres formas no-cuadriculares, geometrías muy variables, o estructura específica (templos, ciudades). Para esos casos, WFC o handcrafted.

2. La fase 1: split recursivo

function split(node):
    if node.size < minNodeSize: return  # hoja
    dir = pickSplitDirection(node)        # h o v, sesgada por aspect ratio
    pos = pickSplitPosition(node, dir)    # centro ± jitter

    if dir == 'vertical':
        node.left  = newNode(x, y, pos - x, h)
        node.right = newNode(pos, y, w - (pos - x), h)
    else:  # horizontal
        node.left  = newNode(x, y, w, pos - y)
        node.right = newNode(x, pos, w, h - (pos - y))

    split(node.left)
    split(node.right)

2.1 Eligiendo dirección

Si el nodo es claramente más ancho que alto (ratio ≥ 1.25), partir vertical. Si más alto que ancho, horizontal. Si cuadrado, aleatorio. Esto evita habitaciones extremadamente alargadas.

2.2 Eligiendo posición

Tres opciones:

• Centro exacto: árbol perfectamente balanceado, pero predecible.
• Centro + jitter aleatorio: balance + variedad. Es el standard.
• Aleatorio puro entre min y max: máxima variedad, pero a veces sale un nodo enano y uno gigante.

Lo común: jitter del 30–40%. pos = center + (rand - 0.5) * 2 * range * jitter.

2.3 Cuándo parar

minNodeSize es el tamaño bajo el cual no se sigue partiendo. Define el tamaño mínimo de habitación.

minNodeSize: 80px↻ Seed: 7

17 habitaciones·16 corredores·profundidad árbol: 5

Bajo (30–60): laberinto denso, muchas habitaciones chicas — tipo Rogue puro. Medio (80–120): balance clásico de roguelike. Alto (150+): pocas habitaciones grandes — más estilo "boss arena" o "templo abierto". Lo elegís según el feel del juego.

Figura 2 — Slider de minNodeSize en vivo. Bajo: muchas habitaciones chicas (Rogue clásico). Alto: pocas habitaciones grandes (templos, boss arenas).

Tradeoff:

• Demasiado bajo (< 6×6): habitaciones que no caben ni una mesa. Pasillos como única estructura.
• Demasiado alto (~ tamaño del nivel): el árbol no se ramifica, queda una sola habitación.
• Sweet spot: típicamente 6–12 cells por lado mínimo, con jitter para variedad.

3. La fase 2: room placement

Cada hoja del árbol coloca una habitación dentro de su AABB:

function placeRoom(leaf):
    pad = roomPadding
    minW = max(3, leaf.w - pad * 2 - 2)
    minH = max(3, leaf.h - pad * 2 - 2)
    roomW = randInt(minW, leaf.w - pad * 2)
    roomH = randInt(minH, leaf.h - pad * 2)

    # ubicar la habitación dentro del AABB
    slackX = leaf.w - roomW - pad * 2
    slackY = leaf.h - roomH - pad * 2
    roomX = leaf.x + pad + randInt(0, slackX)
    roomY = leaf.y + pad + randInt(0, slackY)

    leaf.room = Rect(roomX, roomY, roomW, roomH)

pad (padding) deja un margen entre la habitación y los bordes del AABB. Sin pad, las habitaciones pegan a los bordes y el corredor del padre puede no llegar al centro.

4. La fase 3: corredores

function connect(node):
    if node is leaf: return
    connect(node.left)   # post-order
    connect(node.right)
    # tomar la "centerRoom" de cada hijo (su room representativa)
    a = node.left.centerRoom
    b = node.right.centerRoom
    corridor = makeCorridor(a, b)
    node.corridors.append(corridor)
    # propagar: el padre también necesita una centerRoom
    node.centerRoom = pickRandom([node.left.centerRoom, node.right.centerRoom])

La parte clave es post-order: primero conecta los hermanos profundos, después los del medio, finalmente los de arriba. Esto crea una jerarquía de conexiones que respeta la estructura del árbol.

4.1 Estilos de corredor

L-shapeStraightOrganic

↻ Seed: 13

L-shape es el clásico — dos segmentos perpendiculares, todo cuadricular. Straight dibuja una recta diagonal pero solapa pasillos en intersecciones — útil para mapas más caóticos. Organic mete un codo con jitter, da feel más natural pero menos legible.

Figura 3 — Mismo BSP de fondo, distintos estilos de corredor. L-shape es el clásico; straight diagonal puede solapar; organic mete jitter para feel más natural.

L-shape (default): dos segmentos perpendiculares. El “codo” elige aleatoriamente si es horizontal-luego-vertical o al revés. Resultado: pasillos rectangulares clásicos, fáciles de leer.

function corridorL(a, b):
    aCenter = center(a)
    bCenter = center(b)
    if rand < 0.5:
        # primero horizontal, luego vertical
        seg1 = rect(aCenter.x → bCenter.x, en y = aCenter.y)
        seg2 = rect(bCenter.x, aCenter.y → bCenter.y)
    else:
        seg1 = rect(aCenter.x, aCenter.y → bCenter.y)
        seg2 = rect(aCenter.x → bCenter.x, en y = bCenter.y)
    return [seg1, seg2]

Straight: línea recta diagonal. Visualmente más natural pero solapa pasillos en intersecciones — eso a veces es feature, a veces bug.

Organic: 3+ segmentos con un punto intermedio jittered. Da feel más cavernoso, pero la legibilidad espacial baja.

5. Conectividad garantizada

↻ Nueva seed: 33

El agente azul elige una habitación aleatoria, planifica con BFS sobre el grid de piso, y camina hasta allí. Cuando llega, elige otra. La estela muestra dónde ha pasado. Como el BSP conecta cada par hermano, cualquier habitación es alcanzable desde cualquier otra — la conectividad está garantizada por construcción.

Figura 4 — Un agente elige habitaciones aleatorias y camina con BFS. Siempre encuentra path. La conectividad sale gratis del algoritmo.

Por qué: en cada par hermano del árbol, hay un corredor. El centerRoom de cada nodo interno es alguna room de su sub-árbol. Por inducción, todo nodo está conectado a su raíz, y por tanto todos los nodos están conectados entre sí.

Sin BSP, conectar habitaciones random es complicado: tienes que verificar conectividad con BFS post-hoc y agregar conexiones extras donde hay islas. BSP te lo da por construcción.

6. Variantes y mejoras

6.1 Conexiones extra (loops)

BSP puro genera un árbol — exactamente N-1 corredores para N habitaciones. Sin loops. Para algunos roguelikes, eso se siente lineal. Solución: después del BSP, agrega K corredores extra entre habitaciones cercanas que aún no estén directamente conectadas.

6.2 Door placement

En cada intersección corredor↔habitación, marca la celda del borde como puerta (no muro, no piso libre — algo distinguible). Te permite poner cerraduras, trampas, sellar zonas.

6.3 Zone tagging

Cada habitación puede taggearse por su rol: spawn, tesoro, boss, vendor. Heurísticas comunes:

• Spawn: la habitación más alejada del centro del nivel.
• Boss: la habitación más grande o con más profundidad de árbol.
• Tesoros: habitaciones que terminan en un dead-end (1 sola conexión).

6.4 Decoración por tag

Una vez taggeadas las habitaciones, llenas con props apropiados: spawn=neutral, tesoro=cofres, boss=plataformas. La generación procedural se compone con sistemas de spawn determinístico por seed.

7. Implementación en Unity / C#

public class BSPNode {
    public Rect bounds;
    public BSPNode left, right;
    public Rect? room;
    public Rect? centerRoom;
    public int depth;
}

public class BSPGenerator {
    public int minNodeSize = 8;
    public float splitJitter = 0.35f;
    public int roomPadding = 1;
    System.Random rng;

    public BSPNode Generate(Rect bounds, int seed) {
        rng = new System.Random(seed);
        var root = new BSPNode { bounds = bounds, depth = 0 };
        Split(root);
        PlaceRooms(root);
        Connect(root);
        return root;
    }

    void Split(BSPNode node) {
        if (node.bounds.width < minNodeSize * 2 && node.bounds.height < minNodeSize * 2) return;

        bool vertical;
        float ratio = node.bounds.width / node.bounds.height;
        if (ratio >= 1.25f) vertical = true;
        else if (ratio <= 0.8f) vertical = false;
        else vertical = rng.NextDouble() < 0.5;

        if (vertical && node.bounds.width < minNodeSize * 2) vertical = false;
        if (!vertical && node.bounds.height < minNodeSize * 2) vertical = true;

        float dim = vertical ? node.bounds.width : node.bounds.height;
        float center = vertical ? node.bounds.x + dim / 2 : node.bounds.y + dim / 2;
        float range = (dim / 2 - minNodeSize) * splitJitter;
        float pos = center + ((float)rng.NextDouble() - 0.5f) * 2 * range;

        if (vertical) {
            node.left  = new BSPNode { bounds = new Rect(node.bounds.x, node.bounds.y, pos - node.bounds.x, node.bounds.height), depth = node.depth + 1 };
            node.right = new BSPNode { bounds = new Rect(pos, node.bounds.y, node.bounds.x + node.bounds.width - pos, node.bounds.height), depth = node.depth + 1 };
        } else {
            node.left  = new BSPNode { bounds = new Rect(node.bounds.x, node.bounds.y, node.bounds.width, pos - node.bounds.y), depth = node.depth + 1 };
            node.right = new BSPNode { bounds = new Rect(node.bounds.x, pos, node.bounds.width, node.bounds.y + node.bounds.height - pos), depth = node.depth + 1 };
        }
        Split(node.left); Split(node.right);
    }

    void PlaceRooms(BSPNode node) {
        if (node.left != null && node.right != null) {
            PlaceRooms(node.left);
            PlaceRooms(node.right);
            node.centerRoom = rng.NextDouble() < 0.5 ? node.left.centerRoom : node.right.centerRoom;
            return;
        }
        // hoja
        int pad = roomPadding;
        int rw = (int)(node.bounds.width - pad * 2 - rng.Next(0, 3));
        int rh = (int)(node.bounds.height - pad * 2 - rng.Next(0, 3));
        var r = new Rect(node.bounds.x + pad, node.bounds.y + pad, rw, rh);
        node.room = r;
        node.centerRoom = r;
    }

    void Connect(BSPNode node) {
        if (node.left == null || node.right == null) return;
        Connect(node.left); Connect(node.right);
        var a = node.left.centerRoom.Value;
        var b = node.right.centerRoom.Value;
        // L-corridor entre centros — exercise para el lector
    }
}

8. Errores comunes

1. Sin minNodeSize — recursión infinita o nodos de 1 pixel donde no cabe nada.
2. roomPadding = 0 — habitaciones pegadas a los bordes. Cuando el corredor llega, el muro no existe → habitaciones se fusionan visualmente.
3. Conectar leaves directamente (no por hermanos) — pierde la garantía de conectividad si tu lógica no es exhaustiva.
4. Splits sin jitter — todas las habitaciones tienen el mismo tamaño. Aburrido.
5. No verificar conectividad después de extras — si agregas conexiones loop pero alguna corta una habitación incorrectamente, puedes terminar con islas. BFS post-hoc para confirmar.

9. Quiz

Pon a prueba lo que entendiste

Responde una por una. La explicación aparece al elegir, correcta o no.

1. ¿Cuál es la propiedad clave que BSP garantiza por construcción?

   • AConectividad: cualquier habitación es alcanzable desde cualquier otra.
   • BQue cada habitación sea exactamente del mismo tamaño.
   • CQue no haya pasillos largos.

2. Bajas minNodeSize de 80 a 30. ¿Qué cambia?

   • AEl árbol se vuelve más profundo, hay más habitaciones pequeñas, parece un laberinto.
   • BLas habitaciones se hacen más grandes.
   • CEl árbol se vuelve menos profundo.

3. ¿Cuándo NO conviene usar BSP?

   • ACuando necesitas formas no rectangulares (cuevas orgánicas, círculos, ríos).
   • BCuando el mapa es chico (menos de 50×50).
   • CCuando solo hay 2-3 habitaciones.

4. Quieres que tu dungeon tenga loops (más de un camino entre habitaciones). ¿Cómo lo agregás a BSP puro?

   • ADespués del BSP estándar, conectás K pares de habitaciones cercanas adicionales.
   • BCambiás el algoritmo a uno más sofisticado.
   • CNo es posible con BSP, hay que usar cellular automata.

10. Siguientes pasos

Con BSP cierra la tanda de generación procedural. Ahora tenés tres herramientas complementarias: Perlin para terrenos suaves, WFC para tilemaps con reglas, BSP para dungeons con habitaciones. Las tres se combinan: un mundo open-world realista usa Perlin para el terreno base, WFC para los biomas, y BSP para las cuevas y ruinas.

Lo que viene en próximas tandas: diferenciadores avanzados — Utility AI, GOAP, percepción. Las herramientas que separan una IA correcta de una que se siente viva.