🏰 Generador de Mazmorras Procedurales

La generación BSP divide recursivamente un área rectangular en dos rectángulos más pequeños, alternando entre cortes horizontales y verticales, hasta que cada región es lo bastante pequeña para contener una sala. Luego se coloca una sala dentro de cada nodo hoja, y las salas se conectan con corredores rectos o en forma de L siguiendo el orden en que se crearon. Esto produce mazmorras con una estructura natural en forma de árbol y pocas salas superpuestas, y es una de las técnicas más utilizadas en los roguelikes porque garantiza salas sin solapamiento sin ninguna comprobación de colisiones.

El generador propone repetidamente una sala de ancho y alto aleatorios en una posición aleatoria, y luego la comprueba contra cada sala colocada previamente usando solapamiento de cajas delimitadoras alineadas a los ejes (con un margen de una casilla). Si se superpone con una sala existente, el intento se descarta y se prueba uno nuevo, hasta un número limitado de intentos. Una vez que existen suficientes salas sin solapamiento, se enlazan mediante una cadena voraz de vecino más cercano — en cada paso, la sala no conectada más cercana se une a la red en crecimiento con un corredor en forma de L, similar en espíritu a construir un árbol de expansión mínima.

La cueva comienza como una cuadrícula rellenada aleatoriamente con muros en un porcentaje elegido (35–60%). Luego se suaviza durante un número de pasadas: en cada pasada, cada casilla cuenta cuántos de sus 8 vecinos circundantes son muros, y se convierte en muro si 5 o más vecinos son muros, de lo contrario se convierte en suelo. Repetir esto varias veces erosiona el ruido aislado y convierte pequeños grupos de muros en paredes de cueva suaves y orgánicas — el mismo principio detrás del Juego de la Vida de Conway, aplicado a la generación de niveles en lugar de simular células vivas.

La simulación utiliza un generador congruencial lineal (LCG): una fórmula simple que transforma repetidamente un estado interno de 32 bits mediante multiplicación y suma con constantes fijas, produciendo un flujo determinista de números pseudoaleatorios. Como el generador se reinicia al mismo valor de semilla cada vez que se pulsa "Generar", introducir la misma semilla con el mismo algoritmo y parámetros siempre produce un diseño de mazmorra idéntico, razón por la cual el campo de semilla y el botón "Nueva semilla" permiten guardar o reproducir un mapa específico.

Después de generar una mazmorra, la simulación ejecuta una búsqueda en anchura desde una casilla de suelo para encontrar la casilla alcanzable más lejana, y luego ejecuta una segunda BFS desde esa casilla para encontrar el verdadero diámetro de la región conectada — esta es la clásica técnica de "doble BFS" para encontrar el camino más corto más largo en un grafo no ponderado. Los dos extremos se convierten en los marcadores de inicio y salida, la longitud del camino entre ellos se muestra como "Camino más largo", y "Conectividad" indica qué porcentaje de todas las casillas de suelo son alcanzables desde el inicio, lo que señala si la cueva o mazmorra tiene bolsas aisladas e inalcanzables.