Generación de cuevas

TDD · Documento técnico

Este algoritmo es mi punto de partida. Lo estoy estudiando todavía, y esta página cambiará cuando decida cómo lo hago.

Cuándo se genera

Cada módulo genera sus cuevas la primera vez que se carga, detrás de la pantalla de carga. La semilla del módulo sale de hash(semilla de partida, índice de módulo), y la semilla de partida se guarda con la partida. Con la misma semilla salen siempre las mismas cuevas, y eso me sirve para repetir un fallo concreto y para escribir tests.

flowchart TD
    A["Semilla del módulo = hash(semilla de partida, índice)"] --> B["Todo sólido"]
    B --> C["Cavernas: ruido fBm 3D"]
    C --> D["Anclas: cámaras de huesos"]
    D --> E["Túneles: gusanos entre anclas y cavernas"]
    E --> F["Máscara de zonas protegidas"]
    F --> G["Limpieza: flood fill y regiones"]
    G --> H{"¿Anclas conectadas y volumen en rango?"}
    H -- "No, y quedan intentos" --> I["Siguiente subsemilla"]
    I --> B
    H -- "Sí" --> J["Ids de región, todas cerradas"]
    J --> K["Colocar vetas"]

Algoritmo

1. Empiezo con el módulo entero sólido.
2. Cavernas. Evalúo ruido simplex 3D en fBm de tres octavas, con noise.snoise de Unity.Mathematics, y vacío los puntos que superan un umbral. Multiplico la Y por 2 antes de evaluar el ruido, de modo que las cavernas salen más anchas que altas. El umbral baja con la profundidad, así que los módulos hondos tienen más volumen de cueva.
3. Anclas. Las cámaras de los huesos las coloco a mano en ModuleDefinition como CaveAnchor (posición y radio). Se tallan como esferas pequeñas.
4. Túneles. Desde cada ancla trazo un gusano hacia la caverna más cercana o hacia la siguiente ancla. Avanza en pasos de 0,5 m y su dirección es una mezcla de la dirección al objetivo y del ruido, para que serpentee sin perderse. El radio varía entre 1,0 y 1,5 m según el ruido, para que el jugador quepa de pie. En cada paso talla una esfera con caída suave.
5. Zonas protegidas. Calculo una máscara con el hueco del ascensor (radio de 1,5 m), una capa de 1 m en las paredes y el suelo de la piscina y el primer metro de arriba del módulo. Todo lo que cae dentro de la máscara vuelve a ser sólido. Si eso corta un túnel, el paso siguiente lo detecta.
6. Limpieza. Hago un flood fill con conectividad 6 sobre los puntos de aire y obtengo las regiones. Las regiones de menos de 64 puntos se rellenan, porque son burbujas sueltas que solo molestan. Después compruebo dos cosas: que cada ancla esté en una región con volumen suficiente, es decir, unida a la red y no aislada, y que el volumen total de cuevas caiga dentro del rango del módulo (por ejemplo, entre un 8 y un 15 % en el módulo 1 y entre un 15 y un 25 % en el 2). Si algo falla, repito con la siguiente subsemilla. Hago como máximo 5 intentos; si ninguno vale me quedo con el mejor y lo anoto en el log.
7. Guardo el id de región de cada punto. Todas las regiones empiezan cerradas.
8. Coloco las vetas, que explico más abajo.

El ruido, el tallado y la máscara son jobs de Burst en paralelo, porque cada punto o cada chunk escribe solo en su zona. El flood fill es un job de un solo hilo, porque recorre vecinos y no se paraleliza bien. No fijo un tiempo de partida: el tiempo de generación es lo que más voy a optimizar, y lo mido en cada iteración con la misma semilla.

Colocar vetas

Las vetas solo aparecen en las paredes de las cuevas.

1. Los candidatos son los puntos de aire que tienen un vecino sólido.
2. La normal de cada candidato sale del gradiente de la densidad y apunta hacia el aire.
3. Recorro los candidatos en un orden barajado con la semilla del módulo y acepto cada uno si no hay otra veta a menos de 3 metros. Es la condición de distancia mínima del muestreo Poisson-disk, aplicada sobre las superficies en lugar de sobre todo el espacio. Una rejilla espacial me da la comprobación de vecinos sin recorrer la lista.
4. La probabilidad de que un candidato dé veta crece con la profundidad.
5. El tipo de mineral se elige con pesos de la MineralTable del ModuleDefinition. En el módulo 1 solo salen cuarzo helado y hierro meteórico, y el cobre se suma desde el 2.
6. Cada veta guarda posición, normal, tipo, número de cristales (de 3 a 6) e integridad.

Las vetas se quedan como datos. No instancio ningún objeto hasta que su región se abre, así que un módulo con mucha cueva cerrada no cuesta nada en escena.

Abrir una cueva

Cuando el job de fundido deja un punto por debajo de 128 junto a un punto de una región cerrada R, anota R. Al terminar el job, R pasa a estar abierta y ocurre lo siguiente:

1. Los chunks de R, que tengo calculados de antemano en una lista por región, se marcan como sucios y se remallan empezando por los más cercanos.
2. Se instancian las vetas de R a partir de sus datos.
3. Se lanza el evento CaveOpened, que escucha el audio.

Una cueva grande puede ensuciar muchos chunks de golpe. El orden por distancia y el límite de 2 chunks por fotograma reparten ese trabajo en varios fotogramas, y lo que miro aparece primero. Es uno de los riesgos técnicos de Guardado, rendimiento y pruebas.

Determinismo y pruebas

Todo el azar sale de Unity.Mathematics.Random con semilla, y el ruido de noise.snoise es determinista. Los jobs en paralelo no comparten acumuladores, de modo que el resultado no depende del orden de los hilos. Un test EditMode genera cada semilla de una lista y compara el hash del campo con el de otra ejecución. Los demás tests están en la página de pruebas.

Depuración

Sandbox_Caves genera un módulo con la semilla que le escriba y lo enseña en cortes horizontales en 2D, con un deslizador para cambiar de altura. A su lado muestra el volumen de cueva en porcentaje, el número de regiones, el número de vetas y los intentos que ha necesitado. Con eso afino los umbrales sin lanzar el juego.

Guardado

La partida guarda la semilla y los chunks que el jugador ha modificado. Al cargar, regenero el módulo desde la semilla y encima aplico los chunks guardados. Como la generación es determinista, las vetas y las regiones salen en el mismo orden, y el guardado puede referirse a ellas por su índice.

Los números de esta página (umbrales, rangos de volumen, radios, distancia entre vetas) son valores iniciales y los ajusto con Sandbox_Caves y con la hoja de balance.

Referencias

• Perlin worms, la técnica de túneles trazados por pasos con dirección guiada por ruido. La uso como idea; el código es mío.
• Robert Bridson, "Fast Poisson Disk Sampling in Arbitrary Dimensions", 2007. Fuente de la condición de distancia mínima de las vetas.