👨🏽‍🚒 💇🏻 💆🏾 Consejos para usar el algoritmo de colapso de la función de onda 💃🏿 ⚓️ 😷

Recientemente, he experimentado mucho con la generación basada en restricciones de procedimiento. En particular, con la función de contracción Wave algoritmo (WFC, onda colapso de la función). Incluso escribí mi propia biblioteca de código abierto y activo de la unidad .

WFC es un algoritmo muy flexible, especialmente con las mejoras que desarrollé. Pero al mismo tiempo, me resultó difícil crear niveles prácticos aplicables a los juegos de computadora con su ayuda . La principal dificultad es que el WFC no tiene ninguna estructura global. Todo lo que hace es hacer que la generación de salida parezca localmente similar a la entrada, por ejemplo, mirando pequeños rectángulos individuales de la salida.

En este artículo, le contaré lo que aprendí y lo que podrá elevar los generadores en función de las restricciones a un nuevo nivel.

Los basicos

Es difícil usar WFC si no sabes cómo funciona. Este es un algoritmo de generación de procedimientos basado en restricciones al que se le ha prestado mucha atención recientemente. De hecho, prácticamente no tiene nada que ver con el concepto de física cuántica en cuyo honor fue nombrado.

WFC es fácil de configurar: simplemente le da al algoritmo una tarjeta de ejemplo, después de lo cual genera nuevas tarjetas que se parecen a la tarjeta original debido al uso repetido de sus pequeños fragmentos.

Tiene dos tipos: con una disposición contigua o con una superposición de elementos. Se puede hacer en 2D o 3D, e incluso en cuadrículas de hexágonos o desiguales.rejillas La mayoría de mis consejos se aplican independientemente de cómo utilice el algoritmo.

Le sugiero que juegue con esta demostración para tener una idea sobre el algoritmo, y lea esta introducción [ traducción en Habré] si está interesado en detalles técnicos.

Diseño de azulejos

El algoritmo WFC está basado en mosaicos. En este sentido, su calidad depende de los mosaicos que le transfieras para trabajar. No soy artista, por lo que puedo ayudar poco a dibujar hermosos mosaicos (aunque puedes verlo aquí ), pero un buen mosaico también requiere conocimientos técnicos.

Cubos marchando

Marching cubes es un algoritmo que selecciona qué mosaicos establecer en función de si cada vértice del mosaico está lleno o vacío. Aquí está la lista de mosaicos utilizados para 2D.

Si construye mosaicos para que las esquinas en blanco y negro siempre coincidan, las líneas rojas siempre se conectarán correctamente.

Aquí no necesitamos comprender todo el algoritmo, pero debe tenerse en cuenta que la idea de diseñar mosaicos teniendo en cuenta solo su comportamiento en las esquinas es una técnica muy poderosa. Se utiliza en muchos de los mejores conjuntos de mosaicos, ya que garantiza que los mosaicos siempre se conecten bien.

Esta técnica es especialmente poderosa para WFC. Sucedió, porque si fallas algunas fichas, WFC no importará. Evitará este problema y nunca creará configuraciones que requieran mosaicos faltantes. Esto es muy conveniente para 3D, ya que hay docenas de mosaicos potenciales, y algunos de ellos solo se requieren en situaciones muy difíciles. Vea la sección "Fundación" a continuación, en la que uso este truco aún más ampliamente.

Conocer otros patrones de mosaico también puede ser útil , pero Marching Cubes es lo mejor.

Las habitaciones

A veces es más fácil trabajar con mosaicos simples. Esta combinación de 4 fichas (una ficha está vacía) genera fácilmente habitaciones cuadradas.

El tamaño de las habitaciones se puede cambiar fácilmente cambiando el peso de cada mosaico. Después de agregar las baldosas de puertas y pasillos, puede crear la diversidad que es característica de los planos de planta de las personas.

Fundación

Cuando se trabaja con WFC, es interesante experimentar con los conjuntos de fichas. Si simplemente coloca un mosaico, WFC busca exprimir al máximo el espacio restante. A veces esto lleva a resultados radicalmente diferentes, como se puede ver en la imagen de Maxim Gumin:

Podemos usar este comportamiento para estimular a WFC a generar muchas estructuras reconocibles.

Aquí hay un ejemplo de un castillo (inspirado en @greentecq ):

En él, utilicé el siguiente mosaico:

Estas fichas tienen una propiedad importante: todas las fichas en la base tienen un ancho no menor que en la parte superior. Esto significa que no es posible construir estos mosaicos de una manera no compatible. El WFC responde de inmediato a esto y crea edificios con una buena base.

Aproximación Fractal Split

Al estudiar el tema de estimular ciertos comportamientos eligiendo el conjunto de mosaicos apropiado, descubrí que si el conjunto de mosaicos consiste en caminos rectos y ramas, pero sin esquinas, puede obtener una buena aproximación de la división recursiva (sin la parte "recursiva"). Esto es bastante bueno para los niveles de cuadrícula.

Grandes azulejos

Puede agregar WFC para admitir mosaicos que son varias veces más grandes que un mosaico normal. Por ejemplo, esto es compatible con mi complemento Tessera .

Los azulejos grandes se pueden usar de varias maneras. Dado que se extienden más allá de los límites de la cuadrícula, puede usarlos para agregar curvas más suaves y anchas de lo que normalmente es posible cuando se ajusta a la cuadrícula. También son excelentes para elementos de una gran cantidad de mosaicos, o simplemente para enmascarar que la generación se basa en mosaicos.

Aquí hay un ejemplo para aprender de Oscar Stalberg del juego Bad North . Oscar demuestra cómo utilizó baldosas grandes para agregar costas suavemente curvadas, casas grandes y variabilidad de acantilados.

Limitaciones

En esencia, WFC es un algoritmo basado en restricciones. Esto significa que busca generar niveles que correspondan a un conjunto específico de criterios. En WFC puro, solo hay un criterio: que los niveles se vean localmente como una entrada de muestra. A continuación, hablaré sobre las mejoras de WFC para agregar nuevos tipos de restricciones.

Azulejos fijos

Es muy fácil arreglar mosaicos individuales antes de generar un nivel en WFC. Más tarde se integran perfectamente con el nivel generado.

Antes de la generación

Después de la generación

Esta técnica se puede usar de muchas maneras diferentes. Aquí hay algunas ideas:

- , WFC .
,
/ WFC

Rutas de limitación (restricción de ruta): esta es mi propia contribución al WFC. Esta es una técnica extremadamente poderosa, pero un artículo completo probablemente requerirá un artículo separado.

Esta restricción escanea globalmente toda la salida generada e indica por la fuerza que debe pasar una ruta entre los mosaicos marcados. O, en otras palabras, le dice a un subconjunto de mosaicos que formen un solo componente del gráfico . Debido a su naturaleza global, complementa el comportamiento habitual de WFC, que solo tiene en cuenta los mosaicos locales.

Descubrí que agregar esta restricción afecta fuertemente la apariencia del nivel generado. Sin él, WFC a menudo genera varias habitaciones o áreas divididas que parecen poco realistas y no creadas por humanos.

. .

Otra situación en la que la limitación de ruta es apropiada es ... dibujar rutas. De forma predeterminada, la restricción de ruta solo garantiza que haya una ruta entre los mosaicos. No garantiza que el camino sea lo más simple posible. Por lo tanto, en el caso de ríos y carreteras, a menudo dibuja juntas en forma de T en lugares opcionales. El truco consiste en eliminar simplemente todos los mosaicos de las juntas en T o darles un peso muy bajo, de modo que se seleccionen solo si es absolutamente necesario.

Me encanta usar mosaicos fijos para arreglar los puntos finales de una ruta. Debido a esto, se requiere la restricción de ruta para insertar mosaicos que hacen que el resto de la ruta se conecte.

Las rutas generadas arreglando las cuatro esquinas como los puntos finales de las rutas

Si desea experimentar con rutas, entonces tengo una pequeña demostración de JavaScript que se presenta aquí .

Diversidad

Azulejos Alternativos

Es muy fácil agregar opciones de mosaico al algoritmo WFC. Simplemente agregue los mosaicos a la lista de mosaicos posibles, haciendo que tenga las mismas conexiones que el mosaico que reemplaza. O puede hacerse en la etapa de postprocesamiento, como suele hacerse en otros estilos de generación de procedimientos.

Dos azulejos, uno de ellos con ventana. Son completamente intercambiables y simplemente agregan variabilidad al diseño.

Variabilidad del azulejo por nivel

Si pones mucho esfuerzo en crear un diseño de conjunto de fichas, notarás que la aleatoriedad de WFC comienza a dañarlo. Utiliza todo el conjunto de fichas, es decir, puedes obtener un nivel con lava mixta, nieve y desierto. A menudo esto parece completamente ilógico.

Puede restaurar la integridad de una manera simple: decida de antemano a qué bioma pertenecerá el nivel y luego desactive todas las fichas que no sean adecuadas para este bioma.

Bad North (nuevamente) es un excelente ejemplo de esto. En algunos niveles, las rocas están completamente prohibidas, en otros hay mucha vegetación, en las terceras ruinas y se agregan cementerios. Esto le da a cada nivel un estilo único sin la necesidad de un cambio significativo en el estilo de generación.

Solo alrededor del 10% de las islas tienen elementos de cuevas, visibles en la esquina superior derecha.

Variabilidad de los mosaicos dentro del mapa.

Mezclar juegos de fichas puede ir aún más lejos.

Si usa WFC para generar una tarjeta grande, entonces comienza a verse muy uniforme. Esta es otra consecuencia del hecho de que el algoritmo es un solucionador de restricciones locales .

La mejor solución a este problema la vi en el juego Caves of Qud . En la historia de los desarrolladores sobre la generación ( 1 , 2 ), dicen que dividen el mapa en diferentes áreas y luego inician WFC con parámetros separados para los subconjuntos del mapa. Esto significa que en el mapa puede haber un área de ruinas y un área de una ciudad en la que se usan plantillas y mosaicos completamente diferentes.

Ejemplo de Math para desarrolladores de juegos: generación de mapas basados en mosaicos utilizando el colapso de la función de onda en 'Cuevas de Qud'

Conclusión

El algoritmo WFC, como todas las técnicas de generación basadas en restricciones, tiene el principio de ser cuidadoso con sus deseos . Es fácil de personalizar y obtener resultados hermosos, pero puede ser muy difícil implementar los detalles específicos que se necesitan para su juego.

Espero que las técnicas presentadas por mí te ayuden a domar a este monstruo, pero al final, es mejor crear un diseño de juego basado en las fortalezas de la generación de procedimientos, y no tratar de forzarlo a crear demasiado para ti.

Te recomiendo que juegues Bad North y Caves of Qud . Ambos juegos son excelentes ejemplos del uso de WFC en condiciones reales, y los desarrolladores han pensado bien en el uso óptimo del algoritmo en sus juegos.

Consejos para usar el algoritmo de colapso de la función de onda