Esta publicación describe el algoritmo utilizado en
Generate Worlds , una herramienta que permite a los usuarios crear y explorar mundos de procedimiento mediante la construcción de pequeños conjuntos de mosaicos de vóxel. Daré una breve descripción del algoritmo, y en las siguientes publicaciones hablaré sobre sus ventajas en velocidad y flexibilidad en comparación con otros métodos. Para obtener más información sobre qué es la generación de procedimientos basada en restricciones y en qué es interesante, recomiendo leer mi
publicación anterior .
Si desea probar sus puntos fuertes en la creación de mundos de procedimiento utilizando este sistema, puede
comprar Generar mundos. Si el precio es demasiado alto para usted, continúe leyendo: esta publicación le dará información sobre cómo implementar de manera independiente el algoritmo Generate Worlds.
Juegos de azulejos
En Generate Worlds, cada mundo se ensambla a partir de un
conjunto de mosaicos (mosaico). En esencia, los mosaicos son solo modelos voxel pequeños. Comencemos con un ejemplo. La imagen a continuación se compone de 9 fichas. Como puede ver, cada mosaico consta de vóxeles que aparecen como cubos de colores.
Si organiza estos modelos de vóxel de manera lógica, puede crear una hermosa escena pastoral, como en la animación a continuación. Por "lógica" me refiero a que las fichas encajan si sus colores coinciden con el borde de la unión.
La tarea del algoritmo Generate Worlds es completar rápida y automáticamente dicho ensamblaje. Antes de embarcarse en el algoritmo, veamos el enunciado del problema.
Conectamos fichas entre ellos
Echa un vistazo al conjunto de fichas que contiene 4 fichas:
Estas fichas son similares a las fichas tridimensionales que se muestran arriba.
El algoritmo Generar mundos crea
combinaciones de mosaicos válidos utilizando una regla simple:
si dos mosaicos se tocan, todos los colores a lo largo del borde del toque deben coincidir . Esta regla formaliza el enfoque utilizado por un diseñador vivo para crear un mundo 3D a partir de mosaicos voxel.
En una combinación permisible de las 4 fichas presentadas anteriormente, las celdas claras a lo largo de los bordes deben tocar solo las celdas claras, y una celda oscura debe tocar solo las celdas oscuras. Por ejemplo:
Ejemplos de conexiones correctas e incorrectas.El ejemplo de la derecha es inaceptable, porque a lo largo del borde del toque de mosaico, el cuadrado claro toca el cuadrado oscuro. A continuación se muestran dos combinaciones válidas generadas para este conjunto de mosaicos:
En el caso general, crear combinaciones de mosaicos válidos no es una tarea trivial. Por ejemplo, considere la siguiente estrategia simple "codiciosa": comenzamos con una cuadrícula vacía. En cada iteración, colocamos el mosaico en algún momento, eligiendo un mosaico que sea aceptable teniendo en cuenta los mosaicos ya colocados. El siguiente diagrama muestra los problemas de dicha estrategia.
Si colocaremos mosaicos sin prever cómo la ubicación afectará las elecciones futuras, entonces el algoritmo "codicioso" se detendrá rápidamente; en el diagrama de arriba, no se puede colocar un mosaico válido en el cuadrado rojo. Y este es el problema principal: los mosaicos publicados anteriormente pueden reducir el número de opciones actuales a cero. Necesitamos alguna forma de protección contra la colocación de fichas, lo que nos puede llevar a un callejón sin salida. El algoritmo implementado en Generate Worlds comienza considerando todas las fichas posibles para colocar en todos los puntos de la cuadrícula. Si colocamos un mosaico en la cuadrícula, entonces es obvio que algunas de las opciones futuras se vuelven inaccesibles. Después de que el algoritmo elimina estas opciones, podemos volver a examinar las opciones restantes y eliminar otras fichas que ahora son incompatibles con el menor número de fichas posibles restantes en los puntos vecinos.
Considere el siguiente ejemplo. El algoritmo comienza con una cuadrícula de 3x3, en el centro de la cual hay un único mosaico. La ubicación de este mosaico implica que no se permiten 9 mosaicos posibles en puntos de cuadrícula vecinos, por lo que los descarta y ya no los considera. Después de eliminar estos mosaicos, puede eliminar mosaicos que son incompatibles con todos los mosaicos considerados candidatos para la colocación en puntos de cuadrícula vecinos. Los cuadrados rojos en el diagrama marcan los puntos en los que se eliminan los mosaicos, porque son incompatibles con todos los vecinos que todavía se están considerando. Si el algoritmo continúa este proceso hasta que haya fichas que se puedan eliminar, volverá al estado que se muestra en la esquina inferior izquierda del circuito. Como puede ver, muchos mosaicos fueron excluidos de la consideración. Si la estrategia de colocar fichas consistiera solo en elegir fichas de estos grupos restantes, entonces la probabilidad de entrar en un callejón sin salida sería mucho menor que en el enfoque "codicioso" descrito anteriormente.
El problema con este enfoque es que cada vez que se coloca un mosaico, requiere un proceso iterativo costoso. Pero tenga en cuenta que cada vez que coloco un mosaico con una T invertida, esos 19 mosaicos que eliminé en el ejemplo anterior se pueden eliminar de la consideración en torno a esta ubicación. Llamo a la colección de mosaicos, que siguen siendo opciones válidas alrededor del mosaico alojado, un
vecindario válido de este mosaico.
Colocación rápida de mosaicos gracias al almacenamiento en caché de información
El principio más importante del algoritmo Generate Worlds es que la información recopilada sobre posibles vecinos de mosaico se puede reutilizar cada vez que se coloca este mosaico. Por ejemplo, en el caso de una T invertida para los ocho cuadrados circundantes de la cuadrícula, podemos eliminar 19 fichas inmediatamente después de colocar esta ficha mirando la versión en caché de la vecindad permitida para esta ficha.
Por ejemplo, en el ejemplo a continuación, el algoritmo llena la cuadrícula de 5x5 con mosaicos utilizando una vecindad permitida en caché de 4 mosaicos. Después de colocar la primera ficha, elimina de la consideración 19 fichas que eran imposibles en el ejemplo anterior. Después de colocar cada mosaico, todas las opciones que están ausentes en el vecindario aceptable del mosaico colocado se eliminan de la consideración.
Continuando de esta manera, podemos llenar toda la cuadrícula con solo actualizaciones locales rápidas para el conjunto de mosaicos, que siguen siendo opciones válidas para cada uno de los puntos.
Los vecindarios permitidos pueden ser del tamaño que necesite, por lo que puede eliminar fichas incompatibles distantes cada vez que coloque una ficha. Aunque la generación de un vecindario aceptable es bastante lenta, debe hacerse solo una vez, después de lo cual cada uno depende linealmente del tamaño del vecindario para acomodar cada mosaico.
Expandiendo el sistema en 3D
El algoritmo Generate Worlds se expande naturalmente a mundos que tienen una tercera dimensión. En lugar de mosaicos 2D que coinciden en color con 4 mosaicos vecinos a lo largo de caras comunes, ahora tenemos mosaicos 3D que deben coincidir en color con sus vecinos a lo largo de 6 caras. Considere los siguientes mosaicos 3D:
El ensamblaje de estos mosaicos en 3D es el siguiente:
En este caso, las vecindades admisibles no son cuadrículas bidimensionales, sino tridimensionales, y el algoritmo las genera en un caso 2D similar.
Galería de resultados
A continuación se muestran los mundos generados por las implementaciones de este algoritmo junto con breves descripciones.
Captura de pantalla de Generate Worlds mostrando sala con salida. Las repisas en el techo coinciden con los bordes de las tejas.Una captura de pantalla de otra herramienta que creo que también usa el algoritmo Generate Worlds; Se muestran diferentes tipos de habitaciones y pasillos.Un mundo similar al anterior, pero ahora en una hermosa vista isométrica.El mundo, cuya creación me inspiró el noveno círculo del Infierno de Dante: pecadores que se congelaron en el hielo. Rendido en MagicaVoxel.El mundo, cuya creación me inspiró en la segunda ronda del infierno de Dante: el paisaje, regado por la lluvia ardiente, que cruza el puente. Rendido en MagicaVoxel.Un mundo de plataformas cubiertas de hierba con cascadas y ríos. Rendido en MagicaVoxel.Paisaje de una ciudad medieval con edificios y murallas. Rendido en MagicaVoxel.