¿Qué es la generación procesal?

La generación de procedimientos incluye muchos algoritmos generativos, cuyo principio no es crear datos manualmente, sino algorítmicamente: en lugar de fabricar manualmente lo que queremos crear (mapas, música, terreno ...), se escribe un algoritmo que puede crear con éxito varios ejemplos sin realizando el mismo proceso varias veces. Este enfoque es especialmente útil en videojuegos donde se puede generar aleatoriamente un mapa o nivel completo (por ejemplo, mapas en Minecraft, Terraria o Factorio, o esquemas de nivel en la mayoría de los roguelike).

El algoritmo de colapso de la función de onda y su alcance

En este artículo, examinamos el algoritmo de colapso de la función de onda (WaveFunctionCollapse, WFC) propuesto por Maxim Gumin (su Twitter tiene una colección de contenido sorprendente creado usando este algoritmo por otros desarrolladores). imagen en una cuadrícula de un tamaño dado.

El algoritmo se basa en la idea de la creación paso a paso de una imagen terminada con un seguimiento que los mosaicos "corresponden" a una imagen ya construida parcialmente. Para estudiar la descripción detallada del algoritmo, le recomendamos que consulte el repositorio original de WFC en Github y la cuarta sección del artículo " WaveFunctionCollapse es Restricción de restricciones en la naturaleza ".


Ejemplos de imágenes semilla generadas por procedimientos

Además de crear imágenes similares, otra área de aplicación del algoritmo WFC es la generación de tarjetas en mosaico. La generación de mapas en mosaico será el tema principal del artículo, porque es más fácil de usar para explicar claramente nuestras ideas. En lugar de una imagen de ejemplo, solo puede almacenar mosaicos y pares de mosaicos que se pueden conectar entre sí con turnos. En este caso, el algoritmo se puede utilizar para crear imágenes similares a la que se muestra a continuación.


Ejemplos de mosaicos generados al azar

El desafío y nuestra solución.

Asumimos la tarea de generar una carta de fichas basada en el juego de mesa Carcassonne ("Carcassonne"), en el que los jugadores generan el campo "manualmente" (ver la animación a continuación) a partir de las fichas que deben combinarse entre sí.


Sorprendentemente, conceptualmente, esto es muy similar al algoritmo WFC para crear tarjetas de mosaico arbitrarias al agregar nuevas partes a una solución incompleta. Y como WaveFunctionCollapse se puede usar como un generador de tarjetas de mosaico, ¡también puede generar campos de "Carcasona"!

Sin embargo, en el juego en sí hay muchas fichas diferentes, y codificar todas sus proporciones es una tarea demasiado voluminosa para un hackatón de 24 horas. Por lo tanto, decidimos jugar una versión muy simplificada de "Carcasona" sin castillos y ríos, solo con caminos, pasto y monasterios. Entonces obtuvimos 6 fichas posibles con sus rotaciones y simetría. ¡Pero incluso en tales condiciones, el resultado se ve hermoso y se ve como un juego real en Carcasona!


Visualización del relleno en el algoritmo de campo de Carcasona


Ejemplo de reglas introducidas en el algoritmo.

La imagen de arriba contiene un ejemplo de reglas de entrada agregadas al algoritmo. Sin embargo, aún necesitamos controlar ciertos aspectos de la apariencia del campo. ¿Debería el algoritmo crear "calles" a partir de caminos llenos de monasterios y similares a una ciudad, o el campo como máximo debería consistir en pasto con pueblos dispersos a su alrededor? En el algoritmo original, no hay forma de controlar tales condiciones (como cualquier otra), pero para la posibilidad de control es posible hacer una mejora simple.

Distribución de probabilidad bayesiana a priori

Como se mencionó anteriormente, en cada paso, el algoritmo agrega un nuevo mosaico al campo para que coincida con los mosaicos ya colocados, pero no dijimos qué sucedería si se pudieran colocar varios mosaicos diferentes en la ubicación seleccionada (tampoco hablamos de cómo generalmente elijo este lugar, pero en el artículo no lo consideraremos). En el algoritmo original, cualquier mosaico adecuado se selecciona aleatoriamente de manera uniforme. Sin embargo, en nuestra decisión, podemos preferir mosaicos específicos, por ejemplo, césped, para que ocurra con más frecuencia en el campo. Esto se puede lograr creando una distribución desigual de "probabilidad previa" de las baldosas, en la que el césped tiene una mayor probabilidad de ser utilizado que la carretera, si se pueden usar ambos tipos de baldosas. Esto recuerda a las técnicas bayesianas. En el caso simplificado de elegir entre dos opciones, césped y carreteras, podemos agregar césped con probabilidad p> 0.5, y no con el 0.5 habitual, obtenido con probabilidad uniforme. Esta tarea se puede generalizar fácilmente asignando un valor de prioridad a cada mosaico y utilizando este valor para establecer la probabilidad como un valor dividido por la suma de los valores de todos los mosaicos posibles. La siguiente figura muestra dos soluciones adecuadas con valores de coeficientes muy diferentes, lo que permite comprender cuán sensible puede ser el algoritmo.


Diferentes soluciones para diferentes distribuciones de probabilidad a priori iniciales

Otro ejemplo: probabilidades condicionales y agrupación

Puede ampliar esta idea, y para ilustrar esto, generaremos, en lugar de campos de Carcasona, mapas bidimensionales de mineral de Minecraft. Los diferentes tipos de mineral en Minecraft generalmente se encuentran en formaciones grandes, por lo que, junto con el establecimiento de las probabilidades de cada mineral, haremos que las probabilidades dependan de los vecinos que ya se encuentran en el mapa. A pesar de que no hay nada "prohibido" en la disposición del hierro cerca del carbón, otro carbón tiene mayor prioridad al lado del carbón ya colocado.

Aunque esto no se tiene en cuenta en la imagen a continuación, en el juego la probabilidad también depende de la altura de las fichas, por lo que la posición en la imagen también puede afectar las condiciones de distribución de las probabilidades de las fichas.


Minecraft Ore Tile Map Ejemplo creado por WFC

Conclusión

La generación de procedimientos es una herramienta poderosa que vale la pena tener en stock. En particular, WFC se usa activamente en la generación mundial, y vale la pena considerar la posibilidad de que la distribución de nuevos mosaicos sea desigual y pueda verse influenciada por otros factores, por ejemplo, vecinos ya colocados en el mapa, nuevos mosaicos y posición en la imagen. Hemos creado una aplicación muy simple, ¡pero las posibilidades de desarrollo son casi infinitas!