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

imagen

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



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 .


Source: https://habr.com/ru/post/437604/


All Articles