Colapso de la función de onda: un algoritmo inspirado en la mecánica cuántica

El algoritmo Wave Function Collapse genera mapas de bits que son localmente similares al mapa de bits de entrada.

Semblanza local significa que

• (C1) Cada patrón de píxeles NxN en la salida debe ocurrir al menos una vez en la entrada.
• (Condición débil C2) La distribución de los patrones de NxN en la entrada debe ser similar a la distribución de los patrones de NxN en un número significativamente grande de conjuntos de salida. En otras palabras, la probabilidad de que un determinado patrón se encuentre en la salida debe estar cerca de la densidad de dichos patrones en la entrada.

En los ejemplos, el valor estándar de N es 3.


El algoritmo WaveFunctionCollapse (WFC) inicializa el mapa de bits de salida como un estado completamente no observable en el que el valor de cada píxel es una superposición de los colores del mapa de bits de entrada (por lo tanto, si la imagen de entrada es en blanco y negro, los estados no observables se muestran como diferentes tonos de gris). Los coeficientes de estas superposiciones son números reales, no imaginarios, por lo que el algoritmo no utiliza mecánica cuántica real, sino que se inspiró en él. Luego el programa entra en el ciclo de observación-propagación:

• En cada etapa de observación, entre el espacio no observado, se selecciona la región NxN con la entropía de Shannon más baja. El estado de esta región luego colapsa a un estado de certeza de acuerdo con los coeficientes y la distribución de los patrones de NxN en los datos de entrada.
• En cada etapa de distribución, la nueva información obtenida durante el colapso de la etapa anterior se difunde de acuerdo con el resultado.

En cada etapa, la entropía total disminuye, y al final obtenemos un estado completamente observable, termina el colapso de la función de onda.

Puede suceder que durante el proceso de propagación todos los coeficientes para un píxel particular se vuelvan iguales a cero. Esto significa que el algoritmo ha llegado a una contradicción y no se puede ejecutar más. La tarea de determinar si un mapa de bits dado proporciona otros mapas de bits no triviales que satisfacen la condición (C1) es NP-hard, por lo que es imposible crear una solución rápida que siempre complete el algoritmo. Sin embargo, en la práctica, el algoritmo encuentra contradicciones sorprendentemente raramente.

El algoritmo de colapso de la función de onda se implementa en C ++ , Python , Kotlin , Rust , Julia , Haxe , JavaScript y se adapta para Unity . Los archivos ejecutables oficiales pueden descargarse desde itch.io o ejecutarse en un navegador . WFC genera niveles en Bad North , Caves of Qud , varios juegos más pequeños , así como muchos prototipos. Su creación condujo a un nuevo estudio . Para otros trabajos relacionados , explicaciones , demostraciones interactivas , guías , tutoriales y ejemplos, consulte la sección de puertos, bifurcaciones y spin-offs .

Vea una demostración del algoritmo WFC en YouTube: https://youtu.be/DOQTr2Xmlz0

Algoritmo

1. Lea el mapa de bits entrante y cuente el número de patrones NxN.
   
   1. (opcional) Complemente los datos del patrón con patrones rotados y reflejados.
2. Cree una matriz con los tamaños de los datos de salida (llamada "onda" en la fuente). Cada elemento de esta matriz indica el estado de una región de tamaño NxN en la salida. El estado de la región NxN es una superposición de patrones NxN de datos de entrada con coeficientes booleanos (es decir, el estado de un píxel en la salida es una superposición de colores entrantes con coeficientes reales). El coeficiente False significa que el patrón correspondiente está prohibido, el coeficiente verdadero significa que el patrón correspondiente aún no está prohibido.
3. Inicialice la onda en un estado completamente inobservable, es decir, donde todos los coeficientes booleanos sean verdaderos.
4. Repita los siguientes pasos:
   
   1. Observación:
      
      1. Encuentre el elemento de onda con una entropía no nula mínima. Si no hay tales elementos (si todos los elementos tienen entropía cero o indefinida), complete el ciclo (4) y vaya al paso (5).
      2. Contraiga este elemento en un estado de certeza de acuerdo con sus coeficientes y la distribución de los patrones NxN de los datos de entrada.
   2. Difusión: difundir la información obtenida en el paso de observación anterior.
5. En este punto, todos los elementos de la onda tienen un estado totalmente observable (todos los coeficientes, excepto uno, son iguales a cero) o están en un estado de contradicción (todos los coeficientes son iguales a cero). En el primer caso, devuelva la salida. En el segundo caso, salga sin devolver nada.

Generación de tarjetas de mosaico

El caso no trivial más simple del algoritmo es el patrón NxN = 1x2 (más precisamente, NxM). Si lo simplificamos aún más, preservando no las probabilidades de los pares de colores, sino las probabilidades de los colores mismos, obtendremos lo que se llama un "modelo de mosaico simple". La fase de propagación en este modelo es simplemente la propagación de una dependencia del vecindario. Es conveniente inicializar un modelo de mosaico simple con una lista de mosaicos y sus datos de vecindad (los datos de vecindad pueden considerarse como una gran cantidad de muestras muy pequeñas), en lugar de un mapa de bits muestreado.

GIF | GIFV

Las listas de todos los pares posibles de mosaicos vecinos en prácticos conjuntos de mosaicos pueden ser bastante largas, por lo que para acortar la enumeración, implementé un sistema de simetría para los mosaicos. En este sistema, a cada mosaico se le debe asignar su tipo de simetría.


Tenga en cuenta que los mosaicos tienen la misma simetría que las letras asignadas a ellos (en otras palabras, las acciones del grupo diédrico D4 son isométricas para los mosaicos y las letras correspondientes). Gracias a este sistema, es suficiente enumerar los pares de mosaicos vecinos solo por su simetría, acorta la lista de vecinos para mosaicos con muchos mosaicos simétricos varias veces (incluso en los mosaicos del relieve de verano, a pesar de que las imágenes no son simétricas, el sistema considera que dichos mosaicos son simétricos).









Tenga en cuenta que un conjunto de mosaicos ilimitado de nodos (en el que los 5 mosaicos son válidos) no es interesante para el algoritmo WFC, porque no puede entrar en una situación en la que es imposible colocar un mosaico. Llamamos tilesets con esta propiedad "simple". Sin heurísticas complejas, los mosaicos simples no crean estructuras globales interesantes, porque las correlaciones en mosaicos simples a distancia disminuyen rápidamente. Se pueden encontrar muchos mosaicos simples en cr31 . Mire allí el juego de fichas "doble" de doble cara. ¿Cómo puede crear nodos (sin conexiones en forma de T, es decir, difícil), mientras que al mismo tiempo es simple? La respuesta es que solo puede generar un tipo estrecho de nodos y no puede crear un nodo arbitrario.

También vale la pena señalar que los mosaicos Circuito, Verano y Salas no son mosaicos Van. Es decir, los datos de su vecindario no se pueden generar a partir de la coloración de los bordes. Por ejemplo, en el conjunto de mosaicos Circuito (circuito integrado), dos esquinas no pueden ser adyacentes, aunque pueden conectarse con una conexión (Conexión), y las pistas diagonales no pueden cambiar de dirección.

Mayores dimensiones

El algoritmo WFC en dimensiones superiores funciona exactamente igual que en dos dimensiones, pero el rendimiento se convierte en un problema aquí. Estos modelos de vóxel se generaron en N = 2 en el modelo de mosaico con superposición utilizando bloques de 5x5x5 y 5x5x2 y heurísticas adicionales (alturas, densidades, curvaturas ...).


Capturas de pantalla de dimensiones superiores: 1 , 2 , 3 .

Los modelos de Voxel generados usando WFC y otros algoritmos estarán en un repositorio separado.

Síntesis restringida

El algoritmo WFC admite restricciones. Por lo tanto, se puede combinar fácilmente con otros algoritmos generativos o creación manual.

Así es como el WFC completa automáticamente un nivel iniciado por la persona:

GIF | GIFV

El algoritmo ConvChain satisface la versión estricta de la condición (C2): la distribución de los límites de los patrones NxN en los datos de salida que crea es exactamente la misma que la distribución de los patrones en los datos de entrada. Sin embargo, ConvChain no satisface (C1): a menudo crea artefactos notables. Es lógico iniciar ConvChain primero para obtener una configuración bien muestreada y luego WFC para corregir los artefactos locales. Esto es similar a una estrategia común en la optimización: primero ejecutamos el método Monte Carlo para encontrar el punto. cerca del óptimo global, y luego realice un descenso de gradiente desde este punto para una mayor precisión.

El algoritmo de síntesis de textura de P.F. Harrison es mucho más rápido que WFC, pero tiene problemas con correlaciones largas (por ejemplo, este algoritmo es difícil de sintetizar texturas de pared de ladrillos con ladrillos construidos correctamente). Es en tales casos que WFC demuestra su superioridad, y el algoritmo de Harrison admite limitaciones. Tiene sentido generar primero el esquema de pared de ladrillo ideal usando WFC, y luego realizar un algoritmo de síntesis de textura limitado para este esquema.

Comentarios

¿Por qué se utiliza la heurística de entropía mínima? Me di cuenta de que cuando las personas dibujan algo, a menudo siguen la heurística de la entropía mínima. Es por eso que el algoritmo es tan interesante de ver.

El modelo superpuesto corresponde a un modelo simple de la misma manera que las cadenas de Markov de alto orden corresponden a las cadenas de Markov de primer orden.

Cabe señalar que la entropía de cualquier nodo no puede aumentar en la etapa de propagación, es decir. las probabilidades no aumentan, pero se pueden restablecer a cero. Cuando la etapa de propagación no puede reducir aún más la entropía, activamos la etapa de observación. Si la etapa de observación no puede reducir la entropía, esto significa que el algoritmo ha terminado el trabajo.

La fase de propagación en el algoritmo WFC es muy similar al algoritmo de propagación de creencias en bucle. De hecho, originalmente programé la propagación de creencias (BP), pero luego cambié a la propagación con restricciones con una distribución fija fija, porque BP es mucho más lenta sin paralelización masiva (en la CPU) y no produjo resultados significativamente mejores para mis tareas.

Tenga en cuenta que las muestras "Nudo simple" y "Nudo trucado" no tienen 2, sino 3 colores.

Una dimensión puede ser el tiempo. En particular, el WFC d-dimensional muestra el comportamiento de cualquier autómata celular (d-1) -dimensional.

Referencias

Este proyecto se basa en el trabajo de Paul Merrell en la síntesis de modelos, en particular, en el capítulo sobre síntesis discreta de modelos a partir de su disertación . Paul difunde las limitaciones del vecindario en lo que hemos llamado un modelo de mosaico simple, con una heurística que busca calcular la propagación en una pequeña área en movimiento.

Mi proyecto también estuvo fuertemente influenciado por el capítulo sobre síntesis declarativa de texturas de la disertación de Paul F. Harrison . Paul establece los datos en la vecindad de los mosaicos, marcando sus límites y utilizando la búsqueda de retorno para llenar el mapa de mosaicos.

Asamblea

WFC es una aplicación de consola que depende solo de la biblioteca estándar. Descarga .NET Core para Windows, Linux o macOS y ejecuta

 dotnet run WaveFunctionCollapse.csproj 

O puede usar las instrucciones de construcción de la comunidad para diferentes plataformas en el tema correspondiente . Casey Marshall creó una solicitud de extracción que simplifica el uso de un programa de línea de comandos e incluye un paquete instantáneo.

Puertos, horquillas y spin-offs interesantes

• Emil Ernerfeld creó un puerto en C ++ .
• Max Eller creó la Biblioteca Kotlin (JVM) llamada Kollapse . Joseph Roscopf creó un puerto de línea por puerto en la versión optimizada de Kotlin del algoritmo 2018. Edwin Jacobs creó otra biblioteca de Kotlin .
• Kevin Chapelier creó un puerto en JavaScript .
• Oscar Stalberg ha programado un modelo de mosaico tridimensional, un modelo de mosaico bidimensional para cuadrículas irregulares en una esfera. Aquí están los hermosos juegos de fichas 3D para ellos: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 .
• Joseph Parker adaptó WFC para Unity y lo usó para generar skateparks en el juego Proc Skater 2016 , mesetas fantásticas en el juego Swapland 2017 y niveles de plataforma en el juego Bug with a Gun 2018.
• Martin O'Leary aplicó un algoritmo similar a WFC para generar poesía: 1 , 2 , 3 , 4 .
• Nick Nenov creó un juego de fichas de voxel tridimensional basado en mi juego de fichas Castle. Nick usa la opción de salida de texto para el modelo de mosaico para recrear modelos 3D en Cinema 4D.
• Sean Lefler ha implementado un modelo con una superposición en Rust .
• rid5x crea una versión de WFC en OCaml .
• Publiqué un modelo de mosaico tridimensional simple para que las personas puedan crear sus propios mosaicos 3D sin esperar un repositorio completo de un algoritmo tridimensional.
• Creé un modelo interactivo del modelo superpuesto. El ejecutable de la GUI se puede descargar desde las páginas de WFC en itch.io.
• Brian Buckley ensambló una tubería de generación de niveles para el juego Caves of Qud , que usa WFC en varios pases: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 .
• Danny Wine ha implementado un modelo de mosaico tridimensional .
• Arvi Teikari ha programado un algoritmo de síntesis de textura heurística de entropía en Lua. Headchant lo portó para trabajar con LÖVE.
• Isaac Curt creó un puerto en el modelo de Python con superposición.
• Oscar Stalberg ha creado una versión interactiva del modelo de mosaico que se ejecuta en el navegador.
• Matt Ricks implementó un modelo de mosaico tridimensional ( 1 , 2 , 3 , 4 ) y creó un modelo de mosaico tridimensional en el que una de las dimensiones es el tiempo ( 1 , 2 , 3 , 4 , 5 ).
• Nick Nenov creó una guía visual para el sistema de simetría de mosaico.
• Isaac Curt y Adam M. Smith escribieron un artículo de investigación en el que formulan WFC como una tarea ASP, usan el solucionador de restricciones generales de clingo generalizado para generar mapas de bits, experimentan con restricciones globales, rastrean la historia de WFC y proporcionan una descripción detallada del algoritmo.
• Sylvain Lefebvre creó una implementación en C ++ de la síntesis de modelos tridimensionales, describió el proceso de pensamiento de crear una muestra y mostró un ejemplo en el que las restricciones de vecindario aseguran que la salida esté conectada (puede omitirla).
• Generalicé el WFC tridimensional para que funcione con el grupo de simetría de cubo y cree un conjunto de fichas que genere escenas al estilo de Escher .
• Hay muchas formas de visualizar estados de onda parcialmente observables. En el código, los valores de color de las posibles opciones se promedian para obtener el color final. Oscar Stalberg muestra estados parcialmente observables como rectángulos translúcidos: cuantas más opciones, mayor será el rectángulo. En un esquema de vóxel, visualizo los estados de onda mediante votación píxel por píxel.
• Remy Devo implementó el modelo de mosaico en PICO-8 y escribió un artículo sobre generación coherente de datos con una explicación de WFC.
• Para su juego Bad North, Oscar Stalberg utiliza una heurística que intenta seleccionar dichos mosaicos para que en cada etapa la zona observada resultante sea transitable.
• William Manning implementó un modelo superpuesto en C #; En primer lugar, trató de hacer que el código fuera legible, y complementó WPF con una interfaz gráfica.
• Joseph Parker escribió un tutorial de WFC para Procjam 2017.
• Aman Tiwari formuló la restricción de conexión como una tarea ASP para clingo.
• MatveyK ha programado un modelo tridimensional con superposición .
• Silvan Lefebvre , Lee Yu Wei y Connelly Barnes están explorando la posibilidad de ocultar información dentro de las texturas. Crearon una herramienta que puede codificar mensajes de texto como mosaicos WFC y decodificarlos de nuevo. Esta técnica permite el uso de mosaicos WFC como códigos QR.
• Mathieu Fer y Nathaniel Kuran mejoraron significativamente el tiempo de ejecución de WFC, para un modelo superpuesto en un orden de magnitud. Integré sus mejoras en el código.
• Vasu Mahesh portó un modelo de mosaico tridimensional a TypeScript, creó un nuevo conjunto de mosaicos y visualizó el proceso de generación en WebGL.
• Kim Huanghee experimentó con WFC tridimensional y creó / adaptó muchos mosaicos de voxel: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 .
• Oscar Stalberg hizo una presentación sobre la generación de niveles en Bad North en la Conferencia de procedimiento Everything 2018.
• Escribí sobre cómo generar (aproximadamente) rutas no distorsionadas entre dos puntos usando WFC y otros algoritmos.
• Aiser Curt y Adam M. Smith publicaron una preimpresión que describe el sistema basado en WFC, que aprende de ejemplos positivos y negativos, y habló sobre ello en el contexto general de los diálogos con generadores de muestras.
• Brandan Anthony usa WFC para generar decoraciones de pared en Rodina .
• Tim Kong ha implementado un modelo superpuesto en Haxe .
• Boris the Brave aplicó el método de cincelado al WFC para generar estructuras conectadas. Ha publicado una biblioteca que admite mallas hexagonales, restricciones adicionales y retroceso.
• Marian Kleineberg creó para Procjam 2018 un generador de ciudad basado en el modelo de mosaico. Escribió un artículo que describe sus enfoques para establecer el vecindario, regresar y las variaciones en línea de WFC.
• Sol Bekic programó un modelo de mosaico basado en GPU usando PyOpenCL. En lugar de almacenar una cola de nodos desde los que se realiza la distribución, este modelo realiza simultáneamente la distribución desde cada nodo de la cuadrícula.
• Wouter van Oortmerssen implementó el modelo de mosaico en una sola función C ++ con una estructura para acelerar la observación, similar a una cola prioritaria.
• Robert Hoenig implementó un modelo con superposición de Julia con la opción de distribuir restricciones solo localmente.
• Edwin Jacobs aplicó WFC a la transferencia de estilo y al tramado .

Agradecimientos

Se toman algunos ejemplos de los juegos Ultima IV y Dungeon Crawl . Tileset Círculos tomados de Mario Klingemann . La idea de generar circuitos integrados fue propuesta por Moonasaur , y su estilo fue tomado del juego Ruckingenur II por Zachtronics. El ejemplo de superposición de Cat está tomado del video de Nyan Cat, el ejemplo de Qud fue creado por Brian Buckley , los ejemplos de Magic Office + Spirals son rid5x, los ejemplos de superposición de Coloured City + Link + Link 2 + Mazelike + Red Dot + Smile City son Arvi Teikari. El verano de Tileset fue creado por Hermann Hillmann. Los modelos de Voxel se representan en MagicaVoxel .