- Proyecto que genera automáticamente un mapa insular de estilo medieval compuesto por unas 4,100 losetas hexagonales usando el algoritmo Wave Function Collapse (WFC)
- Cada loseta incluye información de terreno como caminos, ríos, costa, acantilados, bosques y aldeas, y se genera en unos 20 segundos con Three.js WebGPU y shaders TSL
- Para resolver los fallos que aparecen en rejillas grandes, se divide en 19 subrejillas hexagonales, y con un sistema de backtracking y recuperación Local-WFC se asegura una tasa de éxito superior al 86%
- En lo visual, aplica materiales PBR, shaders basados en WebGPU, reflejos y oleaje en el agua, y posprocesado (iluminación, profundidad de campo y grano) para reforzar la sensación de volumen
- Con renderizado BatchedMesh y un solo material compartido, renderiza miles de losetas a 60 fps, mostrando el potencial de combinar generación procedural con gráficos en tiempo real
Resumen de la generación procedural de mapas
- El proyecto está inspirado en el método de generación con dados de mazmorra de AD&D, con un enfoque en el que el algoritmo construye el mundo por sí mismo sin que el usuario tenga que diseñarlo manualmente
- El mapa generado tiene forma de isla medieval con caminos, ríos, línea costera, acantilados, bosques y aldeas, y está compuesto por unas 4,100 celdas hexagonales
- Usa Three.js WebGPU y shaders TSL para completar el mapa entero en unos 20 segundos
Algoritmo Wave Function Collapse (WFC)
- WFC construye el terreno con base en la restricción de que los bordes (edges) de las losetas adyacentes deben coincidir
- Como una loseta hexagonal tiene 6 bordes, tiene 50% más restricciones que una cuadrada
- Cada loseta define tipos de borde en 6 direcciones y un peso (
weight); por ejemplo, una intersección de caminos en 3 direcciones alterna bordes de camino y de pasto
- El algoritmo
- Inicializa todas las celdas con todos los estados posibles
- Elige la celda más restringida y la “colapsa” a un solo estado
- Propaga eliminando los estados imposibles en las celdas vecinas
- Repite hasta resolver toda la rejilla
Rejillas grandes y solución modular
- En rejillas pequeñas funciona de forma estable, pero por encima de 4,000 celdas la probabilidad de fallo aumenta con fuerza
- Para resolverlo, se divide en 19 subrejillas hexagonales y cada una se resuelve de forma independiente manteniendo las losetas de borde como restricciones fijas
- Si las restricciones de borde entran en conflicto, no se puede resolver solo con backtracking
Sistema de backtracking y recuperación
- El backtracking revierte elecciones incorrectas para probar otra loseta, hasta un máximo de 500 veces
- Sin embargo, los conflictos entre rejillas se manejan con un sistema de recuperación aparte
- Paso 1: Unfixing — la celda en conflicto vuelve a un estado variable y las celdas de alrededor se fijan como nuevas restricciones
- Paso 2: Local-WFC — se vuelve a resolver un área de radio 2 celdas (19 celdas) para asegurar compatibilidad en los bordes, con hasta 5 intentos
- Paso 3: Drop & Hide — si falla, se elimina esa celda y se cubre con una loseta montañosa para disimularlo de forma natural
- Con esta recuperación multicapa se logra una tasa de éxito de aproximadamente 86% en la generación completa del mapa
Manejo de elevación en 3D
- El mapa tiene 5 niveles de elevación, y las losetas de pendiente y acantilado conectan niveles superiores e inferiores
- Si se conectan mal, aparecen errores como caminos bloqueados por acantilados o ríos que fluyen cuesta arriba
- La información de elevación se codifica como color de instancia, y el shader mezcla paletas de color de tierras bajas y altas
Sistema de coordenadas hexagonales
- Por su estructura de 6 direcciones, calcular adyacencias en hexágonos es complicado con un sistema 2D simple
- Se usa el sistema de coordenadas cúbicas (q, r, s) para simplificar la búsqueda de vecinos
- Como WFC se enfoca más en la estructura de grafo para emparejar bordes que en la geometría real, el sistema de coordenadas se usa sobre todo en el renderizado y en la colocación de múltiples rejillas
Colocación de árboles y edificios
- WFC es fuerte en patrones locales, pero no es adecuado para distribuciones a gran escala
- La densidad de árboles y edificios se decide con un campo de ruido Perlin, lo que permite formar agrupaciones naturales de bosques y aldeas
- Con lógica adicional, se colocan edificios al final de los caminos, puertos y molinos en la costa, y henge sobre las colinas
Implementación de los efectos del agua
- El mar no es un plano simple, sino que incluye destellos y oleaje en la costa
- Los destellos (Sparkles) se implementan con una textura pequeña en desplazamiento + máscara de ruido en vez de ruido Voronoi, reduciendo la carga en la GPU
- Las olas costeras (Coast Waves) generan bandas sinusoidales basadas en distancia al difuminar la máscara costera
- En el problema de las caletas (Cove), el cálculo de distancia basado en blur resulta impreciso, así que la CPU inspecciona celdas cercanas para crear una máscara de áreas donde las olas deben verse más delgadas
Creación y alineación de losetas
- El modelo base usa KayKit Medieval Hexagon Pack, pero las losetas de conexión faltantes (río en pendiente, variantes de acantilado, etc.) se modelaron manualmente en Blender
- Todas las losetas se unifican a un ancho de 2 unidades, y si hay errores en la alineación UV, las uniones quedan visibles, por lo que se necesita un mapeo preciso
Efectos visuales y renderizado
- Implementado con Three.js WebGPU + shaders TSL, usando shaders basados en nodos en lugar de GLSL
- Pila de posprocesado
- GTAO para reforzar el sombreado
- Profundidad de campo (Depth of Field) para dar un efecto miniatura
- Viñeteado y grano de película para una textura analógica
- El mapa de sombras dinámico se reajusta en cada frame según la vista de la cámara, para mantener sombras nítidas incluso al hacer zoom
Optimización de rendimiento
- Con BatchedMesh, las losetas y decoraciones de cada rejilla se agrupan para renderizarse con una sola draw call
- Todas las mallas comparten un solo material, minimizando los cambios de estado del shader
- Como resultado, logra 38 BatchedMesh, más de 4,100 celdas y renderizado a 60 fps
Cifras clave y stack técnico
- 30 tipos de loseta, 19 rejillas, ~4,100 celdas, 500 backtrackings, 5 intentos de Local-WFC, 20 segundos de generación, 100% de tasa de éxito (500 pruebas)
- Usa Three.js r183, shaders TSL, Web Workers, build con Vite, BatchedMesh y Seeded RNG
Demo y código fuente
- En la demo en vivo se puede expandir el mapa y generar uno completo
- El código fuente en GitHub está disponible, y permite ajustar iluminación, color, agua y configuración de WFC con más de 50 parámetros
Resumen
- Ofrece una experiencia donde un algoritmo crea el mundo en lugar de los dados, permitiendo explorar cada vez terrenos distintos y nuevas conexiones de caminos y ríos
- Un experimento de generación de mapas basado en WebGPU que combina generación procedural, optimización gráfica y técnicas de shaders
1 comentarios
Comentarios en Hacker News
Aunque en el artículo se dice que el backtracking simplemente se limitó a 500 pasos, en realidad la programación con restricciones es un campo muy interesante y complejo
Usando Algorithm X de Knuth y dancing links, parece que se podría resolver la zona de "Layer 2" mencionada en el artículo con una tasa de éxito superior al 86%
Además, aplicando varias heurísticas se puede explorar mucho más rápido que con brute force simple. Cualquiera que haya hecho un solver de Sudoku sabe muy bien lo lento que puede volverse el brute force
Por ejemplo, MiniZinc ofrece un lenguaje de modelado de alto nivel compatible con varios backends de solver
En vez de escribir el algoritmo a mano, es más eficiente modelar el problema usando este tipo de solvers industriales y dejar que el solver encuentre la respuesta mediante búsqueda aleatoria o exhaustiva
Así, en lugar de gastar tiempo escribiendo el solver, puedes concentrarte en ajustar la definición del problema para crear mapas más interesantes
En mi laptop (Core i5 de 11.ª generación, Iris Xe, última versión de Chrome), el demo corre a 5 FPS. Parece que el cuello de botella es la GPU
Como el artículo decía que corría a 60 FPS en móvil, esperaba que fuera un poco más eficiente
El mapa es hermoso, pero las restricciones por tile de WFC producen resultados poco naturales, porque es difícil reflejar influencia no local (non-local influence)
Está bien para juegos donde exploras tile por tile, pero no es ideal para generar el mapa completo
El enfoque basado en ruido de Red Blob Games da mejores resultados. Si los ríos se manejan con seguimiento de humedad y los caminos o puentes con una pasada aparte, resulta más rápido y robusto
Aun así, WFC es un problema de programación interesante, así que seguramente implementarlo fue divertido. En general, fue un gran artículo y un demo impresionante
Oskar Stålberg ha usado Wave Function Collapse (WFC) en varios juegos. Uno representativo es Townscaper
Se puede ver una charla relacionada en SGC21 - Beyond Townscapers
Me recordó al tutorial de Unity Hex Terrain de Jasper Flick
Mientras que este proyecto hace coincidir tiles prefabricados según restricciones, el tutorial de Jasper genera dinámicamente los bordes de los tiles
Ambos enfoques son interesantes y da gusto leerlos
Fue un proyecto realmente genial
Por cierto, si el autor llega a verlo, me pregunto si consideró representar el estado de superposición del tile (el conjunto de opciones posibles) como un bitfield
Cuando implementé WFC hace tiempo, cambiarlo a bitfield dio una mejora de velocidad enorme. Recalcular el chunk completo terminó siendo más rápido que hacer backtracking
Funciona guardando el estado en la pila cada cierto tiempo y, si se atasca, vuelve al último estado
Ver que una variable se llama
tenperme hace guardar un poquito de rencor hacia mi yo del pasadoParece que la parte más difícil es encontrar una disposición que satisfaga las restricciones
Me hace pensar si habría una alternativa usando un SAT solver. Aunque en ese caso quizá siempre encontraría soluciones “fáciles” y se perdería aleatoriedad
Algunos SAT solvers pueden inicializar las variables de forma aleatoria, pero eso no significa necesariamente una solución aleatoria. Me pregunto si alguien ha intentado algo parecido
En cambio, WFC usa un enfoque de brute force simple, así que es fácil de implementar y, si no hay demasiados callejones sin salida, el costo computacional es bajo
En juegos no hace falta una solución perfecta; basta con algo “suficientemente bueno”, así que WFC puede ser más práctico
Fue un proyecto inspirador. Las referencias también son excelentes y el código fuente está publicado
Creo que quedaría muy bien combinar esto con el estilo visual de Here Dragons Abound
Puede que el OP ya lo sepa, pero la página sobre matemáticas de hexágonos de Red Blob Games tiene muchos ejemplos y código excelentes
Es interesante explorar WFC en grillas no cuadradas (non-square)
Da la impresión de que la complejidad de la propagación de restricciones sería mucho mayor que en los ejemplos habituales
En este tipo de topologías complejas, quizá otros solvers de restricciones como Constraint Logic Programming podrían tener ventajas en expresividad y rendimiento
Me recordó a Dorfromantik. Enlace de Steam