Nos ocupamos del algoritmo de colapso de la función de onda

Desde la llegada de DeBroglie y Tessera, muchas veces me han pedido que explique cómo funcionan. Generar puede parecer magia, pero las reglas detrás de esto son realmente simples.

Entonces, ¿qué es el algoritmo de colapso de función de onda (WFC)? Fue desarrollado por Maxim Gumin para crear imágenes "en mosaico" basadas en una configuración simple o muestras de imágenes. El algoritmo puede hacer mucho: mira los ejemplos proporcionados por Maxim y Twitter #wavefunctioncollapse , mira este video . La variedad es asombrosa.


Maxim en README explicó brevemente el trabajo de WFC, pero me parece que este problema requiere una divulgación más detallada, desde lo más básico. Dado que el algoritmo está relacionado con la programación en restricciones , la mayor parte del artículo está dedicado a explicar el concepto de programación en restricciones, y al final volveremos a WFC .

La programación restringida es una forma de instruir a las computadoras. A diferencia de la programación imperativa, cuando especifica una lista de funciones explícitas, o programación funcional, cuando especifica funciones matemáticas, aquí proporciona a la computadora una descripción estricta del problema, y ​​utiliza los algoritmos integrados para encontrar una solución.

Nota:Esta guía describe varios conceptos, no métodos y código. Si está más interesado en la implementación, puede usar mi biblioteca de código abierto WFC ( github , documentación ). Aunque es mejor comenzar el estudio con la implementación de Maxim . Si usa Unity, puede comprar Tessera , esta es mi herramienta para aplicar WFC en este motor.

Mini sudoku

Como tarea ilustrativa, tomé un mini Sudoku . Este es un rompecabezas que parece una cuadrícula de 4 × 4 con números en algunas celdas.


El objetivo es llenar cada celda vacía con un número del 1 al 4 de acuerdo con las reglas:

• Cada número del 1 al 4 debe estar presente en cada fila en una sola copia.
• Cada número del 1 al 4 debe estar presente en cada columna en una sola copia.
• Cada número del 1 al 4 debe estar presente en cada cuadrado de esquina 2 × 2 en una sola copia.

De acuerdo con estas reglas, la solución será la siguiente:


Es posible que haya resuelto fácilmente este rompecabezas. Pero estamos interesados ​​en cómo una computadora puede hacer esto. El problema se puede dividir en dos partes: una descripción de las condiciones para la computadora, y luego una solución usando el algoritmo.

Descripción de condiciones

Por lo general, se usa un lenguaje de programación con restricciones para esto. Existen varios lenguajes de este tipo, y sus principios de acción son similares.

Primero definimos las variables . Aquí no son lo mismo que en la programación convencional. En el contexto de un solucionador de problemas, una variable es un valor desconocido que debe resolverse para resolver un problema. En nuestro ejemplo de Sudoku, crearemos variables para todas las celdas vacías. Para mayor comodidad, también puede crear variables para celdas rellenas.

Luego, para cada variable definimos un dominio : un conjunto de valores posibles. En nuestro sudoku, para cada celda vacía, el dominio será {1, 2, 3, 4}. Y para una celda en la que ya se ingresó 1, el dominio será {1}.

Finalmente, establecemos las restricciones: reglas que vinculan nuestras variables. En la mayoría de los lenguajes de programación, ya existe una función con restricciones all_distinct(..)que necesita pasar valores únicos. Por lo tanto, las reglas de Sudoku se pueden traducir en 12 restricciones all_distinct, una para cada fila y columna, así como para cuadrados de esquina de 2 × 2. Solo necesitamos un tipo de restricción para resolver este problema, sin embargo, los solucionadores de problemas para satisfacer las restricciones generalmente vienen con una gran biblioteca de diferentes tipos de restricciones para describir su problema.

Nota : en la práctica, los lenguajes de programación admiten matrices en restricciones, por lo que hay formas más precisas de formular esta tarea. Hay muchos artículos en la red sobre la resolución de sudoku.

Algoritmos para resolver problemas de satisfacción de restricciones

Existen varias técnicas de solución diferentes. Pero consideraré el más simple de ellos para demostrarte el principio de su trabajo. Los dominios para cada celda se muestran aquí:


Todos estos son valores posibles en dominios variables.

Ahora toma la primera limitación. Requiere que todos los valores en la fila superior sean únicos. En una celda, el valor 4 ya está inscrito, por lo tanto, en otras celdas de la serie este valor no puede ser . Lo eliminamos de los dominios de estas células.


Repita este proceso con las 12 restricciones. Esto se llama propagación de restricciones , porque la información se distribuye de una variable a otra a través de restricciones.


Y mira, tenemos variables, en los dominios de los cuales queda un valor. Estas deberían ser las soluciones correctas para estas variables.


Parece que podemos obtener aún más beneficios de la distribución de restricciones: las nuevas unidades rojas indican que tendremos aún más variables con un solo dominio, y esto también contribuirá a la distribución. Repita el procedimiento hasta que se resuelva el rompecabezas.

Complicamos la tarea

Desafortunadamente, no todos los acertijos lógicos se pueden resolver tan rápido. Aquí hay un gran sudoku, funciona de la misma manera, excepto que ahora tenemos 9 valores diferentes, 9 filas, 9 columnas y 9 cuadrados de 3 × 3.


Si intentamos aplicar la técnica anterior, nos quedaremos atascados:


Ahora todas las restricciones son comunes, pero todavía hay variables indefinidas.

Una persona decidirá esto, pero un algoritmo informático no podrá hacerlo. Los manuales para personas dicen que ahora necesitamos buscar conclusiones lógicas cada vez más complicadas. Pero no necesitamos un algoritmo informático para hacer esto, porque es difícil, pero necesitamos un algoritmo universal que pueda funcionar con cualquier conjunto de restricciones, y no solo de acuerdo con las reglas de sudoku.

Por lo tanto, las computadoras hacen lo más estúpido: asumen . Primero, registramos el estado actual del rompecabezas. Luego seleccionamos una variable arbitraria y la configuramos en uno de los valores posibles. Digamos que asignamos el valor 1 a la celda central.

Ahora podemos extender las restricciones un poco más. Esto es lo que obtuve para la columna central:


Los valores azules son las conclusiones que hicimos después de la suposición. Como puede ver, sucedió algo. Anotamos algunas variables más, pero echemos un vistazo a la celda superior media. Está vacío: en su dominio no hay valores posibles que satisfagan las restricciones (no puede haber 5, porque este valor ya existe en el mismo cuadrado de 3 × 3, y todos los demás números ya están en esta columna).

Si obtenemos una variable con un dominio vacío, esto significa que no podemos asignarle ningún valor. Es decir, el rompecabezas no se puede resolver. Resulta que nuestra suposición era errónea .

Ante tal contradicción, realizamos el proceso de búsqueda de retorno(retroceso). Primero, restauramos el estado anterior a nuestra suposición. Luego eliminamos del dominio el valor que usamos como suposición: ya no puede ser la respuesta correcta.


Se ha hecho mucho trabajo, pero han avanzado. Sin embargo, incluso después de la exclusión de 1 de la celda central, todavía estamos en un punto muerto. Es hora de hacer una suposición una y otra vez.

No hay muchas acciones algorítmicas aquí. Cada vez que no podemos distribuir restricciones, hacemos una suposición y seguimos adelante. Y dado que puede quedar atrapado varias veces antes de encontrar una contradicción, acumulará varios estados y suposiciones guardados.

Con cada iteración con un retorno, reduce el dominio en al menos una variable, de modo que, a pesar de las numerosas reversiones, el algoritmo finalmente completará el trabajo.

Este tema es mucho más extenso de lo que describo. En la práctica, las optimizaciones como la elección de supuestos, la comprensión de cuándo distribuir y cuándo sacar conclusiones lógicas más complejas pueden tener un gran impacto en la ejecución del programa. Y dado que los problemas con restricciones, como regla, crecen exponencialmente, puede obtener una respuesta mañana o después de 5000 años.

Volvemos al colapso de la función de onda.

El colapso de la función de onda es una tarea difícil con una limitación: hay miles de posibles soluciones. Si hacemos suposiciones al azar, entonces en lugar de un solucionador, obtenemos un generador . Al mismo tiempo, seguirá cumpliendo con todas las restricciones dadas, es decir, será mucho más manejable que la mayoría de los otros generadores de procedimientos.

La tarea del algoritmo WFC es llenar celdas con mosaicos para que las imágenes en los mosaicos se combinen entre sí. Dentro de la terminología utilizada anteriormente, cada mosaico es un valor, cada celda es una variable y las reglas para colocar mosaicos son restricciones.

Maxim, el autor de WFC, descubrió que con una selección razonable de mosaicos y una aleatorización adecuada, rara vez tiene que usar el seguimiento, por lo que este procedimiento no se puede implementar. Por lo tanto, la esencia de WFC es la siguiente:

• Se crea una matriz booleana para cada celda, que representa el dominio de esta variable. Los dominios contienen un registro por mosaico, y todos ellos se inicializan con un valor true. Un mosaico ingresa a un dominio si su valor es igual true.
• Al mismo tiempo, hay celdas en las que los dominios contienen varios elementos:
  
  • Selección de una celda aleatoria utilizando el método heurístico de "menos entropía".
  • Seleccione un mosaico aleatorio del dominio de celda y elimine todos los demás mosaicos de allí.
  • La actualización de los dominios de otras células en función de esta nueva información es la propagación de la restricción celular. Esto debe hacerse repetidamente, ya que los cambios en las células pueden tener más consecuencias.

Nota : mis términos son diferentes de los términos de Maxim. Él llama a la matriz de dominios una ola, y elegir un mosaico aleatorio es una observación. Es decir, se dibuja una analogía con la mecánica cuántica. Pero la comparación es superficial, por lo que la ignoraremos.

Hay muchas adiciones a los principios anteriores que agregan gracia y rendimiento al algoritmo. Pero primero veamos los pasos descritos.

Ejemplo

Digamos que necesitamos llenar una cuadrícula de 3 por 3 con cuatro tipos de mosaicos:


Las limitaciones son: los colores de las fichas adyacentes deben coincidir entre sí.

Como en el ejemplo de Sudoku, ilustraré el contenido de dominios con imágenes monocromas. Cuando solo quede un elemento en el dominio, lo aumentaré de tamaño y lo mostraré en color.

Primero, en cada celda, se pueden ubicar mosaicos de cualquier tipo:


Ejecute el bucle principal de WFC. Seleccione aleatoriamente una celda, por ejemplo, la esquina superior izquierda. Ahora seleccione un mosaico en el dominio y elimine todos los demás.


Distribuir las restricciones. La única regla se aplica a los mosaicos adyacentes, por lo que debemos actualizar dos celdas:


¿Podemos actualizar otros mosaicos dados los dominios reducidos? ¡Si! Aunque no estamos seguros acerca de la elección del primer mosaico, vemos que las opciones restantes conducen a la derecha. Es decir, algunos tipos de mosaicos no se pueden colocar en la esquina superior derecha. Lo mismo con la esquina inferior izquierda.


Ya no podemos distribuir las restricciones, por lo que repetimos el ciclo principal: selección de celdas, selección de mosaicos y distribución. Esta vez tomamos la celda media superior:


Otro ciclo: tome la celda media izquierda. Después de la proliferación de restricciones para la célula central, queda un valor posible.


En general, entiendes la idea. Puede completar el resto de las celdas usted mismo.

Si desea experimentar con un ejemplo interactivo más complejo , le recomiendo este .

La entropía más pequeña

Al elegir la siguiente celda para completar, algunas opciones serán preferibles. Si elige al azar desde cualquier lugar de la cuadrícula, puede surgir una situación en la que al mismo tiempo tendrá diferentes áreas de la cuadrícula llena. Esto puede generar problemas: dependiendo de los mosaicos disponibles, las áreas rellenas no se pueden unir. Por lo tanto, es mejor elegir celdas que tengan menos probabilidades de provocar tales problemas en el futuro. En otras palabras, debe tomar celdas con el menor número de valores posibles en el dominio (pero no menos de dos valores):

1. Lo más probable es que estén al lado de las celdas ya llenas.
2. Si los dejamos para el futuro, pueden surgir dificultades, porque los valores disponibles ya son pocos.

El enfoque de dominio más pequeño funciona bien si todos los mosaicos son igualmente probables. Pero si elige entre una distribución aleatoria ponderada , entonces debe considerar otra cosa. Maxima recomienda "entropía mínima", es decir, elija una celda que minimice:

$$

$$entropy = — \sum p_{i}log(p_{i})$$

Esta es una suma de mosaicos en el dominio donde $$$p_{i}$- probabilidad de esta ficha.

Computación eficiente

Aunque no quiero entrar en detalles, sin embargo, hay dos optimizaciones que me permiten aumentar la velocidad tanto que no se pueden ignorar.

Como nuestra única regla está relacionada con los mosaicos adyacentes, solo podemos verificar aquellas restricciones que pueden dar resultados que difieren de los anteriores. Es decir, al actualizar una celda, la agregamos a la cola de celdas en espera de una decisión. Luego eliminamos una celda de la cola, comprobando cada vez sus celdas adyacentes. Si dichos controles conducen a la renovación de otras celdas, también entran en la cola. Repitiendo este procedimiento hasta que la cola esté vacía, nos aseguramos de verificar todas las restricciones. Pero no los verificamos hasta que cambie el dominio de al menos una celda asociada con estas restricciones.

Además, para verificar la restricción de adyacencia, debemos responder la pregunta: "Dadas las fichas en el dominio de la celda A, ¿qué fichas son posibles en el dominio de la celda B si las celdas son adyacentes?"

A veces, esta pregunta se llama el "soporte" de la celda A. Para un mosaico dado "b" en el dominio B, es fácil calcular los ciclos para los mosaicos en el dominio A. Si A tiene al menos un mosaico que se puede colocar al lado de "b", entonces "b" sigue siendo adecuado, al menos para el par de fichas en cuestión. Si en A no existe ese mosaico, entonces no puede colocar el mosaico "b" del dominio B, y podemos descartarlo.

Los bucles facilitan la implementación de esto en el código, pero funcionarán extremadamente lentamente. Y si almacenamos información en una estructura de datos adicional, podemos responder rápidamente la pregunta según sea necesario. Los nuevos datos son una gran matriz con entradas para cada lado de cada celda y cada mosaico. En nuestro ejemplo, hay 9 celdas, cada una con 4 lados y 4 tipos de mosaicos. Entonces necesitamos 9 * 4 * 4 registros. Guardaremos contadores de soporte en la matriz: para cada celda / mosaico / lado, contamos el número de mosaicos en el dominio de celda adyacente que se puede colocar al lado del mosaico en cuestión. Si el contador cae a cero, entonces esta ficha no se puede poner, porque nadie puede estar adyacente a ella.

Extensiones de Algoritmo

Debido a que WFC se basa en una comprensión más general de los problemas restringidos, hay muchas formas de extender el algoritmo cambiando las restricciones utilizadas.

Uno de los cambios obvios es que nadie nos obliga a usar celdas cuadradas. WFC funciona muy bien en celdas hexagonales, en tres dimensiones o incluso en superficies más inusuales .




Puede introducir restricciones adicionales: arreglar ciertos mosaicos o crear "módulos" a partir de varias celdas.

La introducción de restricciones adicionales puede desempeñar un papel muy importante desde un punto de vista práctico. Dado que WFC limita solo los mosaicos adyacentes, rara vez genera grandes estructuras que proporcionan un alto nivel de homogeneidad y se ven inusuales. Este algoritmo funciona mejor al elegir mosaicos, pero para trabajar con algunas estructuras grandes, es mejor usar una técnica diferente o introducir otras restricciones.

En otro artículo, hablé sobre cómo puedes lograr los mejores resultados de WFC.

WFC superpuesto

Una de las extensiones interesantes para el algoritmo es el WFC "superpuesto". En los ejemplos anteriores, la limitación principal estaba relacionada con pares de fichas adyacentes. Esto es suficiente para garantizar la conexión de líneas y crear estructuras simples como cuevas, habitaciones, etc. Pero al mismo tiempo se pierde mucha información. Si necesitamos, digamos, que los mosaicos rojos siempre se encuentran junto al azul, pero nunca fueron adyacentes a ellos, entonces esto será difícil de expresar solo en términos de contigüidad.

Maxim propuso el concepto de WFC superpuesto: reemplazamos la restricción de adyacencia con una nueva restricción que afecta a varios mosaicos a la vez. Por ejemplo, para que en la salida cada grupo de celdas 3 × 3 corresponda a un grupo 3 × 3 de una muestra de cuadrícula. Los patrones presentes en la muestra se repetirán una y otra vez en diferentes variaciones en la salida:


Esta restricción es mucho más sensible que las restricciones de adyacencia "simples". Y dado que depende de una muestra dada, es muy adecuado para resolver algún tipo de tareas artísticas. Hasta ahora, no he encontrado nada tan interesante. Quizás la razón es que dicho algoritmo es más difícil de implementar, o funciona más lentamente, o a veces reproduce la muestra original demasiado bien, lo que hace que se pierda algún tipo de naturalidad y naturalidad.

¿Que sigue?

Resolver problemas con restricciones es un campo grande y de desarrollo activo de la informática, y solo lo mencioné. WFC, al igual que cualquier otro algoritmo de generación de procedimientos para resolver problemas restringidos, todavía es nuevo. Recomiendo leer r / proceduralgeneration , #wavefunctioncollapse , @exutumno y @osksta para tener una idea de los casos de uso recientes.

También puede leer mi artículo sobre WFC , experimentar con mi biblioteca de código abierto o herramienta Unity . No te olvides de mis otros artículos sobre generación de procedimientos .