Generar Mundos con Colapso de Funciones de Onda

Generación General Avanzado

Generar mundos con colapso de funciones de onda

Wave Function Collapse (WFC) de @exutumnoes un nuevo algoritmo que puede generar patrones de procedimientos a partir de una imagen de muestra. Es especialmente emocionante para los diseñadores de juegos, ya que nos permite dibujar nuestras ideas en lugar de crear el código a mano. Veremos los tipos de outputs que WFC puede producir y el significado de los parámetros del algoritmo. Después, analizaremos la configuración de WFC en Javascript y en el motor de juegos de Unity.

¡También puedes encontrar el tutorial en GitHub, aqui!

El enfoque tradicional para este tipo de output es crear a mano un código de algoritmos que generan características, y después combinarlos para modificar el mapa del juego. Por ejemplo, podrías colocar algunos árboles en coordenadas al azar, dibujar caminos con un movimiento browniano y agregar salas con una partición de espacio binario. Esto es algo muy útil, pero lleva mucho tiempo, y a veces tu idea original puede perderse por el camino.

El uso de WFC (específicamente el modelo Overlap) hace que este tipo de generación sea intuitiva, tú dibujas un ejemplo y obtienes infinitas variaciones de él. También hay un aspecto de colaboración con la máquina, ya que el output puede ser sorprendente y, a veces, puede hacer que cambies tu diseño.

WFC es especialmente emocionante para la comunidad de Game Jam, porque trabajan con un tiempo limitado. Una vez que tengas todo preparado, podrás crear muchos tipos de patrones procesales en solo minutos.

Cómo Funciona

WFC tiene dos partes: un modelo de input y un resolvedor de restricciones.

El Simple Tiled Model usa un documento xml que declara adyacencias legales para diferentes teselas.
El Overlap Model divide un patrón de input en pedazos de patrón. Es similar a una cadena 2D de Markov.

NOTA: En este tutorial, nos centraremos en el modelo de superposición (overlap), ya que es más fácil crear inputs para él.

El enfoque especial de WFC para la resolución de restricciones es un proceso de eliminación. Cada ubicación de cuadrícula contiene una matriz de booleanos para qué teselas puede y no puede ser. Durante la fase de observación, se selecciona una tesela y se le da una única solución aleatoria de entre las posibilidades restantes. Después, esta opción se propaga por toda la cuadrícula, eliminando las posibilidades adyacentes que no coincidan con el modelo de input.

La característica final es el retroceso. Si una observación y propagación crean una contradicción irresoluble, se revierten y se prueba a hacer una observación diferente.

NOTA: La demostración de web interactiva de Oskar Stålberg es una excelente manera de hacerse una idea de cómo funciona el algoritmo. Te permite realizar la fase de observación y anima la propagación después de que hayas seleccionado un valor de cuadrícula.

Usar WFC

La primera tarea es encontrar un puerto de WFC en el idioma que tú quieras. El algoritmo original se escribió en C #, pero hay muchas implementaciones en otros idiomas. (Si estás interesado en llevar WFC a un nuevo idioma y te gustaría tener un mentor, ponte en contacto.)

Después de haber incluido el código WFC en tu proyecto y de haberte asegurado de que se compila, estarás listo para probar con algunos inputs. La mayor parte de las versiones de WFC funcionan con algún tipo de formato de imagen, tanto para input como para output.

El flujo de trabajo generalmente consiste en:

construir un nuevo ejemplo de modelo a partir de input y parámetros
utilizando model.Run para resolver un patrón de output
guardando o leyendo la imagen de output y utilizándola

Explicación de los parámetros

Constructor de modelos

name/input Input data. Este parámetro suele ser específico para cada implementación. Para el algoritmo original, es una cadena que representa un nombre de archivo ($"samples/{name}.png")
width,depth (int) Dimensiones de los datos de output
N (int) Representa el ancho y alto de los patrones en los que el modelo de superposición divide el input. Según va resolviendo, intenta emparejar estos subpatrones entre sí. Una N más alta capturará características más grandes del input, pero a nivel computacional es un proceso más intensivo y puede requerir una muestra más grande para conseguir soluciones confiables.
periodic input (bool) Representa si el patrón de entrada se está diviendo en teselas. Si es verdadero, cuando WFC digiere el input en pedazos de N, creará patrones que conectan los bordes derechos e inferiores a la parte izquierda y superior. Si utilizas esta configuración, deberás asegurar que el input «tenga sentido» en todos estos bordes.
periodic output (bool) Determina si las soluciones de output se pueden teselar. Es útil para crear cosas como texturas teselables, pero también tiene una influencia sorprendente en el output. Para trabajar con WFC, a menudo es una buena idea activar y desactivar la Salida Periódica (Periodid Output), verificando si algunas de las dos configuraciones influye en los resultados de manera favorable.
symmetry (int) Representa qué simetrías adicionales del patrón de input son digeridas. 0 es solo el input original, 1-8 agrega variaciones giradas y reflejadas. Estas variaciones pueden ayudar a desarrollar los patrones en tu input, pero no son necesarias. Solo funcionan con teselas unidireccionales, y no son recomendables cuando las teselas del juego final tienen gráficos o funciones que dependen de la dirección.
ground (int) Cuando no es 0, esto asigna un patrón para la fila inferior del output. Normalmente es útil para palabras "verticales", cuando quieres una separación clara entre la tierra y el cielo. El valor corresponde a los índices de patrón interno de los modelos de superposición, por lo que hace falta un poco de experimentación para determinar un valor adecuado.

`model.generate`

seed (int) Todos los valores aleatorios internos se derivan de esta semilla, proporcionando 0 resultados en forma de un número aleatorio.
limit (int) Cuántas iteraciones ejecutar, dado que 0 se seguirá ejecutando hasta que se complete o hasta que haya una contradicción.

Tutorial: Configurar el Algoritmo en Javascript

Descarga una copia de wfc.js en la carpeta de tu proyecto. Estamos usando una versión modificada de kchapelier's javascript port, que se ha editado en un solo archivo para que la configuración resulte más rápida.

Ahora crea un archivo index.html como:


<!DOCTYPE html>
<html>
  <head>
    <script src='wfc.js'></script>
    <style>
      canvas{
        border:1px solid black;
        image-rendering: pixelated;}
    </style>
  </head>
  <body>
    <canvas id="output" width="48" height="48"></canvas>
    <script>

    </script>
  </body>
</html>

La versión js utiliza ImageData para el input y el output. Comenzaremos con una función que carga un elemento de imagen, lo dibuja en un lienzo temporal y extrae ImageData. Como cargar una fuente de imagen no es un proceso instantáneo, usaremos una función de «callback» que se invoca cuando se cargan los datos.


var img_url_to_data = function(path, callback){
  var img = document.createElement("img")
  img.src = path
  img.onload = function(e){
    console.log(this.width, this.height)
    var c = document.createElement("canvas")
    c.width = this.width
    c.height = this.height
    var ctx = c.getContext("2d")
    ctx.drawImage(this,0,0)
    callback(ctx.getImageData(0,0,this.width,this.height))
  }
}

Con un editor de imágenes, crea una pequeña imagen de input y guárdala como test.png en tu directorio de proyectos. Una buena imagen para empezar podría ser algo como:

Carga tu índice en un navegador y después abre la consola de desarrollador y prueba la función img_url_to_data:


> img_url_to_data("test.png", console.log)
ImageData {data: Uint8ClampedArray(1024), width: 16, height: 16}

Si has abierto el archivo index.html directamente en tu navegador, en este momento verás un mensaje de error como por ejemplo:


index.html:25 Uncaught DOMException: Failed to execute 'getImageData' on 'CanvasRenderingContext2D':
The canvas has been tainted by cross-origin data.

Esto se debe a que es una violación de seguridad que Javascript tenga acceso a recursos externos al mismo dominio. Puedes solucionar este problema cargando tu proyecto en alguna parte, o ejecutando un servidor local en tu ordenador. Con Python, esto puede ser tan simple como abrir un terminal en el directorio del proyecto y ejecutar python3 -m http.server 8999 o python2 -m SimpleHTTPServer 8999. Ahora ya puedes cargar tu índice con la URL http://localhost:8999

Ejecución del Modelo de Superposición

Ahora vamos a meter ImageData en un OverlappingModel.


var start = function(id){
  output = document.getElementById("output")
  ctx = output.getContext("2d")
  imgData = ctx.createImageData(48, 48)
  // input, width, height, N, outputWidth, outputHeight, periodicInput, periodicOutput, symmetry, ground
  model = new OverlappingModel(id.data, id.width, id.height, 2, 48, 48, true, false, 1, 0)
  //seed, limit
  var success = model.generate(Math.random, 0)
  model.graphics(imgData.data)
  ctx.putImageData(imgData, 0, 0)
  console.log(success)
}

Por último, utiliza img_url_to_data con el URL de tu imagen y el «callback» inicial:


img_url_to_data("test.png", start)

Si todo funciona bien, deberías poder ver tu output dibujado en el lienzo:

NOTA: Dependiendo del patrón de input, es posible que WFC no pueda terminar de resolver un output. En nuestra demostración, esto dará como resultado un lienzo en blanco, y el success var será false. Aunque puedes ajustar tu input para aumentar las posibilidades de obtener soluciones completas, otra estrategia es volver a probar el algoritmo hasta que se complete. Podemos agregar una función para esto al final de la función de start de esta manera:


if (success == false){start(id)}

Cómo Utilizar el Output

WFC generalmente crea algún tipo de tipo de datos de imagen para su output. Esto es perfecto para una inspección rápida o para la generación de texturas, pero para un proyecto de juego normalmente tenemos un formato de datos específico con el que nos gusta trabajar para describir nuestros mundos. Probemos esto para nuestra demostración, convirtiendo ImageData en una matriz de matrices simple, que contenga un solo número que representa su tipo de tesela.

Primero, agrega esta función para obtener un valor de píxel de ImageData:


function get_pixel(imgData, x, y) {
  var index = y*imgData.width+x
  var i = index*4, d = imgData.data
  return [d[i],d[i+1],d[i+2],d[i+3]]
}

Ahora vamos a crear una tabla de búsqueda para traducir de un valor de color a un único número entero. Como los mapas js solo pueden tener claves de cadena, asumiremos que la matriz de colores se ha unido con ":"


var colormap = {
  "0:0:0:255":1, //black
  "255:255:255:255":0 //white
}

Por último, en nuestra función de inicio, construimos una matriz de matrices con las mismas dimensiones que nuestro ImageData, utilizando el código del número entero para cada píxel:


  if (success == false){
    start(id)
  } else {
    var world = []
    for (var y = 0; y < 48; y++) {
      var row = []
      for (var x = 0; x < 48; x++) {
        var color = get_pixel(imgData, x, y).join(":")
        row.push(colormap[color])
      }
      world.push(row)
    }
    console.log(world)
  }

Tutorial: Configurar el Algoritmo en Unity

Echemos un vistazo rápido al uso de WFC con el motor de juego Unity utilizando unity-wave-function-collapse. En lugar de utilizar archivos de imagen para en input y output, funciona con arreglos de GameObjects prefabricados. También está configurado con componentes, por lo que no hace falta crear código para un uso básico.

Comienza un nuevo proyecto de Unity y, o importa el .unitypackage o clona el repositorio GitHub en el directorio Assets. También necesitaremos un directorio de Resources (Recursos) para nuestros objetos de teselas.

Y ahora necesitaremos un grupo de teselas. Para simplificar las cosas, simplemente crearemos un cubo y lo arrastraremos al directorio de recursos para convertirlo en un prefab. UnityWFC requiere que sus teselas tengan una orientación con una Y vertical y X horizontal, por eso, si estás importando modelos 3D, es posible que tengas que reconfigurar la exportación de malla (mesh export).

Crea un objeto vacío llamado input y agrega un componente de Training (Capacitación). El algoritmo leerá los child prefabs colocados dentro de los límites de «Training» (Capacitación). Arrastra los prefabs al objeto en la ventana de jerarquía. Dependiendo de las dimensiones de tu tesela, es posible que tengas que cambiar la propiedad Gridsize (tamaño de cuadrícula) en el componente de Training. Deberías poder ver un artilugio azul redondo en el centro de cada tesela dentro de sus límites.

NOTA: El componente Tile Painter puede acelerar la creación de inputs, permitiéndote hacer clic y dibujar teselas desde una paleta de elementos prefabricados. El añadir prefabs a tu propiedad de palette(paleta) los mostrará debajo del área de la imagen, donde se pueden probar haciendo clic con la tecla S. Incluso puedes arrastrar una carpeta de prefabs a tu propiedad de palette (paleta) para cargarlos todos a la vez.

Crea una entrada vacía de output con nombre y añádele un componente de Overlap WFC. Su componente de Training (Capacitaicón) debe conectarse al input que has creado. Ahora puedes entrar en el modo de reproducción y éste generará outputs para las dimensiones dadas. También puedes hacer clic en generate (generar) y RUN (ejecutar) para ver el output en el modo de edición.

Consejos y Trucos

Cuando empieces a usar WFC, comenzarás a tener una mejor idea de cómo convierte los patrones de input en ouput. Aunque te recomiendo que explores la relación entre el input y output, aquí tienes algunos trucos descubiertos por la comunidad que pueden darte más control sobre los resultados.

En este ejemplo, nos gustaría tener monedas al estilo Mario, algunas teselas por encima de las plataformas. Como el espaciado es mayor que nuestro ajuste N, todo lo que el algoritmo sabe es que las monedas están rodeadas de espacio vacío, y que nuestro output contiene una dispersión aleatoria de monedas.

Usando variantes de teselas vacías, podemos forzar la estructura deseada. Visto a través de la lente de las superposiciones de N trozos de patrón, el algoritmo sabe que a veces variant1 está por encima de una tesela de plataforma, variant2 está siempre por encima de variant1, y una moneda está siempre por encima de variant2.

Este truco también funciona para la estructura general de tus patrones. Si estás diseñando una mazmorra, se pueden incluir variantes de piso para animar a la aparición de salas más grandes.