Cadenas de Markov para la generación de edificios procesales

Nota: el código fuente completo de este proyecto se puede encontrar [ aquí ]. Como es parte de un proyecto más grande, recomiendo ver el commit en el momento en que se lanzó este artículo, o el archivo /source/helpers/arraymath.h , así como /source/world/blueprint.cpp .

En este artículo quiero hablar en detalle sobre los principios del uso de las cadenas de Markov y las estadísticas para la generación de procedimientos de edificios 3D y otros sistemas.

Explicaré los fundamentos matemáticos del sistema e intentaré hacer la explicación lo más general posible para que puedas aplicar este concepto en otras situaciones, por ejemplo, para generar mazmorras 2D. La explicación irá acompañada de imágenes y código fuente.

Este método es un método generalizado para la generación de procedimientos de sistemas que satisfacen ciertos requisitos, por lo que recomiendo leer al menos hasta el final de la primera sección para que pueda comprender si esta técnica puede ser útil en su caso, porque a continuación le explico los requisitos necesarios.

Los resultados se usarán en mi motor de vóxel para que los bots de tareas puedan construir edificios y luego ciudades. ¡Al final del artículo hay un ejemplo!


Un par de ejemplos con los resultados.

Los fundamentos

Cadenas de Markov

Las cadenas de Markov son una secuencia de estados a lo largo de los cuales se mueve un sistema, descritos por transiciones en el tiempo. Las transiciones entre estados son estocásticas, es decir, se describen por probabilidades, que son una característica del sistema.

El sistema está definido por el espacio de estado, que es el espacio de todas las configuraciones posibles del sistema. Si el sistema se describe correctamente, también podemos describir las transiciones entre estados como pasos discretos.

Cabe señalar que a partir de un estado del sistema a menudo hay varias posibles transiciones discretas, cada una de las cuales conduce a un estado diferente del sistema.

La probabilidad de transición del estado i al estado j es igual a:

$$

$$P_ {ij}$$

El proceso de Markov es el proceso de estudiar este espacio de estado con la ayuda de las probabilidades transferidas a él.

Lo importante es que los procesos de Markov "no tienen memoria". Simplemente significa que las probabilidades de transición del estado actual al nuevo dependen solo del estado actual y ya no de otras condiciones visitadas anteriormente.

$$

$$P_ {ij} = P (i, j)$$

Ejemplo: generación de texto

Un sistema es una secuencia de bits. El espacio de estado es todas las posibles secuencias de bits. Una transición discreta cambiará un bit de 0 a 1 o de 1 a 0. Si el sistema tiene n bits, entonces de cada estado tenemos n posibles transiciones a un nuevo estado. El proceso de Markov consistirá en el estudio del espacio de estado cambiando los valores de bits en una secuencia usando ciertas probabilidades.

Ejemplo: pronóstico del tiempo

El sistema es las condiciones climáticas actuales. El espacio de estado es todos los estados posibles en los que el clima puede ser (por ejemplo, "lluvioso", "nublado", "soleado", etc.). La transición será un cambio de cualquier estado a otro estado en el que podamos establecer la probabilidad de la transición (por ejemplo, "¿cuál es la probabilidad de que si hace sol hoy, mañana lloverá, independientemente del clima de ayer?").

Método de Monte Carlo para las cadenas de Markov

Dado que las transiciones entre estados están determinadas por las probabilidades, también podemos establecer la probabilidad de que un "estable" esté en cualquier estado (o, si el tiempo tiende al infinito, el tiempo promedio que estaremos en un estado particular). Esta es una distribución interna de estados.

Entonces, el algoritmo de Monte Carlo para las cadenas de Markov (Markov-Chain Monte-Carlo, MCMC) es una técnica para obtener una muestra del espacio de estados. El muestreo (muestreo) significa la elección del estado en función de la probabilidad de selección, teniendo en cuenta la distribución interna.

Dicen que la probabilidad de estar en un estado es proporcional * a una determinada función de costo que proporciona una "estimación" del estado actual en el que se encuentra el sistema. Se cree que si los costos son bajos, entonces la probabilidad de estar en este estado es alta, y esta relación es monótona. La función de costo se define de la siguiente manera:

$$

$$R (i)$$

Nota: No estoy seguro si la palabra "proporcional" se usa correctamente, porque la relación no es necesariamente lineal.

¡Entonces una muestra de la distribución estatal devolverá una configuración con bajos costos (o una buena "estimación") con una mayor probabilidad!

Incluso con un espacio de estado extremadamente grande (posiblemente infinito, pero "infinitamente contable"), independientemente de la complejidad del sistema, el algoritmo MCMC encontrará una solución con bajos costos si le damos suficiente tiempo para converger.

Hacer tal estudio del espacio de estado es una técnica estándar de optimización estocástica y tiene muchas aplicaciones en áreas como el aprendizaje automático.

Distribución de Gibbs

Nota: si esta sección no le resulta clara, puede omitirla de manera segura. Aún puede aprovechar la implementación del sistema.

Después de determinar los costos de una posible afección, ¿cómo determinamos la probabilidad de esta afección?

Solución: La distribución de Gibbs es la distribución de la entropía máxima para un conjunto dado de restricciones.

En esencia, esto significa que si establecemos muchas restricciones en las probabilidades del sistema, entonces la distribución de Gibbs creará la "menor cantidad de suposiciones" sobre la forma de la distribución.

Nota: la distribución de Gibbs también es la distribución con la menor sensibilidad a las variaciones en las restricciones (de acuerdo con la métrica de divergencia Kullback-Leibler).

La única restricción que imponemos a la distribución de estados es la función de costo, por lo que la usamos en la distribución de Gibbs para calcular la probabilidad de transición entre estados:

$$

$$P_ {ij} = \ exp (- \ frac {R (j) -R (i)} {T}) * \ frac {1} {Z_i}$$

Donde Z es la función de partición del conjunto de transiciones del estado i. Este es un factor de normalización que garantiza que la suma de las probabilidades de transición de cualquier estado es 1.

$$

$$Z_i = \ sum_j (P_ {ij})$$

Tenga en cuenta que si decidimos que el siguiente estado será el mismo, entonces los costos relativos son cero, es decir, la probabilidad después de la normalización será distinta de cero (debido a la forma de la distribución con el indicador). Esto significa que en muchas transiciones es necesario incluir la probabilidad de estados sin cambios.

También vale la pena señalar que la distribución de Gibbs está parametrizada por la "temperatura computacional" T.

Una de las ventajas clave de usar probabilidades en el estudio del espacio de estado es que el sistema puede realizar transiciones a estados más caros (ya que tienen una probabilidad de transición distinta de cero), convirtiendo el algoritmo en un método de optimización "no codicioso".

Tenga en cuenta que a medida que la temperatura tiende al infinito, la probabilidad de cualquier transición individual tiende a la unidad de tal manera que cuando el conjunto de probabilidades de todas las transiciones desde el estado se normaliza, se vuelven igualmente probables (o la distribución de Gibbs se aproxima a la distribución normal), ¡a pesar de que sus costos son mayores!

A medida que la temperatura computacional se acerca a cero, las transiciones con menores costos se vuelven más probables, es decir, la probabilidad de transiciones preferidas aumenta.

Al realizar una investigación / optimización del espacio de estado, disminuimos gradualmente la temperatura. Este proceso se llama "recocido simulado" . Gracias a esto, al principio podemos salir fácilmente del mínimo local, y al final podemos elegir las mejores soluciones.

Cuando la temperatura es lo suficientemente baja, todas las probabilidades tienden a cero, ¡con la excepción de la probabilidad de no transición!

Esto se debe a que solo la ausencia de una transición tiene una diferencia de costo cero, es decir, estar en el mismo estado no depende de la temperatura. Debido a la forma de la función exponencial en T = 0, esta resulta ser la única probabilidad con un valor distinto de cero, es decir, después de la normalización, se convierte en unidad. En consecuencia, nuestro sistema convergerá a un punto estable y ya no será necesario un enfriamiento adicional. Esta es una propiedad integral de la generación de probabilidad utilizando la distribución de Gibbs.

¡El proceso de convergencia del sistema se puede ajustar cambiando la velocidad de enfriamiento!

Si el enfriamiento es más lento, entonces, como resultado, generalmente llegamos a una solución con costos más bajos (hasta cierto punto), pero a costa de más pasos de convergencia. Si el enfriamiento ocurre más rápido, entonces es más probable que el sistema en las primeras etapas caiga en la trampa de una subregión con mayores costos, es decir, obtendremos resultados "menos óptimos".

En consecuencia, el proceso de Markov no solo genera resultados aleatorios, sino que intenta generar resultados "buenos", ¡y con alta probabilidad tendrá éxito!

Por definición de funciones de costo arbitrarias, no es necesario que exista un óptimo único. Este método de optimización probabilística genera solo acercarse al óptimo, tratando de minimizar la función de costo, y debido al muestreo, generará resultados diferentes cada vez (si el generador de números aleatorios tiene una semilla diferente).

El proceso de muestreo en sí se puede realizar utilizando el método de transformación inversa sobre la función de distribución de masa de nuestro conjunto discreto de transiciones. Más tarde mostraré cómo se hace esto.

Generación procesal

¿Cómo es útil este método para la generación de procedimientos?

En algunos sistemas, a menudo es difícil definir un algoritmo simple que genere buenos resultados, especialmente en el caso de sistemas complejos.

Establecer reglas de generación arbitrarias no solo es difícil, sino que también está limitado solo por nuestra imaginación y el procesamiento de casos límite.

Si el sistema cumple un cierto conjunto de requisitos, entonces el uso de MCMC nos permite no preocuparnos por la selección de un algoritmo o reglas. En su lugar, definimos un método para generar cualquier resultado posible y elegimos conscientemente uno bueno en función de su "evaluación".

Se presentan los siguientes requisitos:

• El sistema puede estar en una configuración de estado discreta (posiblemente infinita).
• Podemos definir transiciones discretas entre estados.
• Podemos establecer una función de costo que estima el estado actual del sistema.

A continuación daré algunos otros ejemplos en los que, en mi opinión, este método se puede aplicar.

Implementación

Pseudocódigo

En nuestra implementación, queremos lograr lo siguiente:

• Establece el estado del sistema.
• Establezca todas las transiciones posibles al siguiente estado.
• Calcule los costos del estado actual.
• Calcule los costos de todos los estados siguientes posibles (o un subconjunto de ellos).
• Usando la distribución de Gibbs, calcule la probabilidad de transiciones.
• Muestra de transiciones (muestra) usando probabilidades.
• Realice una transición muestreada.
• Reduce la temperatura computacional.
• Repita los pasos hasta obtener resultados satisfactorios.

En forma de pseudocódigo, el algoritmo MCMC es el siguiente:

 // MCMC    T = 200; //     State s = initialState(); Transitions t[n] = {...} //n   thresh = 0.01; //  ( ) // ,      while(T > thresh){ //    curcost = costfunc(s); newcost[n] = {0}; // newcost   0 probability[n] = {0}; //     0 //  for(i = 0; i < n; i++){ newcost[i] = costfunc(doTransition(s, t[i])); probability[i] = exp(-(newcost[i] - curcost)/T); } //  probability /= sum(probability); //  sampled = sample_transition(t, probability); //  s = doTransition(s, sampled); //  T *= 0.975; } 

Generación de edificios en 3D

Espacio de Estado y Transiciones

Para generar edificios en 3D, genero muchas habitaciones con el volumen especificado por el cuadro delimitador.

 struct Volume{ //   glm::vec3 a; glm::vec3 b; void translate(glm::vec3 shift); int getVol(); }; //   int Volume::getVol(){ return abs((bx-ax)*(by-ay)*(bz-az)); } //    void Volume::translate(glm::vec3 shift){ a += shift; b += shift; } 

Si genero n habitaciones, el estado del sistema es la configuración de los cuadros delimitadores en el espacio 3D.

¡Debe tenerse en cuenta que las configuraciones posibles para estos volúmenes son infinitas, pero infinitamente infinitas (se pueden enumerar en una cantidad de tiempo infinita)!

 //  (  !) std::vector<Volume> rooms; // N  for(int i = 0; i < n; i++){ //  Volume x; xa = glm::vec3(0); xb = glm::vec3(rand()%4+5); //   //  . rooms.push_back(x); } //... 

Muchas transiciones posibles serán un cambio de habitaciones en una de las seis direcciones del espacio por un paso, incluida la ausencia de una transición:

 //... //   std::array<glm::vec3, 7> moves = { glm::vec3( 0, 0, 0), //   ! glm::vec3( 1, 0, 0), glm::vec3(-1, 0, 0), glm::vec3( 0, 1, 0), glm::vec3( 0,-1, 0), glm::vec3( 0, 0, 1), glm::vec3( 0, 0,-1), }; //... 

Nota: ¡es importante que mantengamos el sistema capaz de permanecer en su estado actual!

Función de costo

Quería que los volúmenes en el espacio 3D se comportaran como "imanes", es decir:

• Si sus volúmenes se cruzan, entonces esto es malo.
• Si sus superficies se tocan, entonces esto es bueno.
• Si no se tocan en absoluto, entonces esto es malo.
• Si tocan el suelo, está bien.

Para dos cuboides en el espacio 3D, podemos definir fácilmente un cuadro delimitador:

 Volume boundingBox(Volume v1, Volume v2){ //   Volume bb; //   bb.ax = (v1.ax < v2.ax)?v1.ax:v2.ax; bb.ay = (v1.ay < v2.ay)?v1.ay:v2.ay; bb.az = (v1.az < v2.az)?v1.az:v2.az; //   bb.bx = (v1.bx > v2.bx)?v1.bx:v2.bx; bb.by = (v1.by > v2.by)?v1.by:v2.by; bb.bz = (v1.bz > v2.bz)?v1.bz:v2.bz; return bb; } 

Usando el cuadro delimitador de volúmenes, podemos calcular un vector 3D que me da información sobre la intersección de dos volúmenes.

Si la longitud del paralelepípedo a lo largo de un lado es mayor que la suma de las longitudes de dos volúmenes a lo largo de este lado, entonces desde este lado no se tocan. Si son iguales, entonces las superficies se tocan, y si es menor, entonces los volúmenes se cruzan.

 //    3  glm::vec3 overlapVolumes(Volume v1, Volume v2){ //      Volume bb = boundingBox(v1, v2); //  glm::vec3 ext1 = glm::abs(v1.b - v1.a); // v1  3  glm::vec3 ext2 = glm::abs(v2.b - v2.a); // v2  3  glm::vec3 extbb = glm::abs(bb.b - bb.a); //   //  return ext1 + ext2 - extbb; } 

Este código se usa para calcular la cantidad de cantidades para las que formo una cantidad ponderada, que finalmente se usa como costo.

 int volumeCostFunction(std::vector<Volume> rooms){ // int metric[6] = { 0, //   0, //   0, //     0, //     0, // ,   0};//    int weight[6] = {2, 4, -5, -5, -5, 5}; //    for(unsigned int i = 0; i < rooms.size(); i++){ //     for(unsigned int j = 0; j < rooms.size(); j++){ //    ,  . if(i == j) continue; //    . glm::vec3 overlap = overlapVolumes(rooms[i], rooms[j]); //   glm::vec3 posOverlap = glm::clamp(overlap, glm::vec3(0), overlap); metric[0] += glm::abs(posOverlap.x*posOverlap.y*posOverlap.z); //   //   glm::vec3 negOverlap = glm::clamp(overlap, overlap, glm::vec3(0)); metric[1] += glm::abs(negOverlap.x*negOverlap.y*negOverlap.z); //   //   if(overlap.y == 0){ metric[2] += overlap.x*overlap.z; } //   (X) if(overlap.x == 0){ //      0,   , .. overlap.z = 0 metric[3] += overlap.z*overlap.y; } //   (Z) if(overlap.z == 0){ //      0,   , .. overlap.x = 0 metric[4] += overlap.x*overlap.y; } } //  ,   -   . if(rooms[i].ay == 0){ //  ,  ,    . metric[4] += rooms[i].ax*rooms[i].az; } //,     ! if(rooms[i].ay < 0){ //,        if(rooms[i].by < 0){ metric[5] += rooms[i].getVol(); } else{ metric[5] += abs(rooms[i].ay)*(rooms[i].bz-rooms[i].az)*(rooms[i].bx-rooms[i].ax); } } } // Metric * Weights return metric[0]*weight[0] + metric[1]*weight[1] + metric[2]*weight[2] + metric[3]*weight[3] + metric[4]*weight[4] + metric[5]*weight[5]; } 

Nota: "volumen de intersección positiva" significa que los volúmenes realmente se cruzan. "Volumen de intersección negativa" significa que no se tocan en absoluto y la intersección se define por el volumen en el espacio ubicado entre los dos puntos más cercanos de dos cuboides en el espacio 3D.

Los pesos se eligen de manera tal que den prioridad a una cosa y multen a otras. Por ejemplo, aquí reduzco severamente las habitaciones ubicadas debajo del piso, y también aumento la prioridad de aquellos cuyas superficies se tocan (más de lo que reduzco la intersección de volúmenes).

Genero costos para todos los pares de habitaciones, ignorando las habitaciones que están emparejadas entre sí.

Encontrar una solución de bajo costo

La convergencia se realiza como se describe en el pseudocódigo. Al hacer la transición, solo me muevo de una habitación a la vez. Esto significa que con n habitaciones y 7 posibles transiciones, necesito calcular 7 * n probabilidades, y selecciono de todas ellas, moviendo solo esa habitación, que es probablemente la más preferible.

  //  float T = 250; while(T > 0.1){ //   std::vector<std::array<double, moves.size()>> probabilities; //   () int curEnergy = volumeCostFunction(rooms); //      ... for(int i = 0; i < n; i++){ //    std::array<double, moves.size()> probability; //      ,     for(unsigned int m = 0; m < moves.size(); m++){ //        . rooms[i].translate(moves[m]); //      ! probability[m] = exp(-(double)(volumeCostFunction(rooms) - curEnergy)/T); //   rooms[i].translate(-moves[m]); } //       probabilities.push_back(probability); } //  ( ) double Z = 0; for(unsigned int i = 0; i < probabilities.size(); i++){ for(unsigned int j = 0; j < probabilities[i].size(); j++){ Z += probabilities[i][j]; } } //  for(unsigned int i = 0; i < probabilities.size(); i++){ for(unsigned int j = 0; j < probabilities[i].size(); j++){ probabilities[i][j] /= Z; } } //    (CDF) ( ) std::vector<double> cdf; for(unsigned int i = 0; i < probabilities.size(); i++){ for(unsigned int j = 0; j < probabilities[i].size(); j++){ if(cdf.empty()) cdf.push_back(probabilities[i][j]); else cdf.push_back(probabilities[i][j] + cdf.back()); } } //      std::random_device rd; std::mt19937 e2(rd()); std::uniform_real_distribution<> dist(0, 1); double uniform = dist(e2); int sampled_index = 0; //   CDF for(unsigned int i = 0; i < cdf.size(); i++){ //    ,   ... if(cdf[i] > uniform){ sampled_index = i; break; } } //     int _roomindex = sampled_index/moves.size(); int _moveindex = sampled_index%moves.size(); //  rooms[_roomindex].translate(moves[_moveindex]); // T T *= 0.99; // !!! } //!! //... 

El muestreo se realiza mediante la formación de una función de distribución acumulativa sobre la función de distribución de masa de todas las transiciones posibles; esta operación se llama "muestreo de transformación inversa".

Esto se logra al generar la suma acumulativa de las probabilidades de transición, lo que nos da la función de distribución acumulativa (CDF). Para el muestreo, generamos una variable aleatoria con una distribución uniforme entre 0 y 1. Como el primer elemento del CDF es cero y el último, solo necesitamos encontrar "en qué índice de la matriz CDF está nuestra variable muestreada con distribución uniforme", y esto será índice de transición muestreado. Aquí hay una ilustración:


En lugar de una función continua, puede haber pasos discretos. Más detalles se pueden leer aquí .

Además, ¡tengo datos de volumen de sala en espacio 3D!

Los uso para generar un "esquema" usando la clase blueprint, aplicando un tema a datos masivos conocidos. Entonces las casas tienen su apariencia. La clase blueprint se describe en el artículo anterior [ aquí ] ([ traducción ] en Habré). Para la generación completa de una casa a partir de estos volúmenes, consulte el código fuente.

Resultados

Los resultados para un método tan generalizado son bastante buenos. Lo único que tuve que configurar fue la prioridad correcta y los pesos de penalización en la función de costo.


Algunos ejemplos de generación de edificios usando este algoritmo y el tema aplicado a ellos.


Vista lateral (otros edificios).

La convergencia en sí misma es muy rápida, especialmente para un pequeño número de habitaciones (3-5), porque calcular cuadros delimitadores y estimar la función de costo es muy simple.

En la versión actual, las casas no tienen puertas y ventanas, pero esto es más una cuestión de interpretar datos de volumen 3D, en lugar de una tarea para el algoritmo MCMC.

A veces, el método da resultados feos, ya que este es un proceso estocástico, por lo que antes de colocar un edificio en el mundo, debe verificar su corrección, especialmente si la función de costo no es muy confiable. Sospecho que la fealdad ocurre principalmente en los primeros pasos cuando la temperatura es alta.

Por lo general, los defectos aparecen como habitaciones o habitaciones separadas del edificio. colgando en el aire (sobre pilotes altos).

Extensiones y otros sistemas.

Obviamente, mi técnica con volúmenes 3D es fácil de transferir al mundo 2D simplemente reduciendo la dimensión de la tarea en uno.

Es decir, se puede usar para tareas como la generación de procedimientos de mazmorras o salas en juegos 2D con una vista superior: la conexión de salas entre sí utiliza una función de costo similar a la descrita anteriormente.

Una posible forma de hacer que la generación sea más interesante es generar primero un gráfico de habitaciones, cada una de las cuales tiene su propio tipo, y luego establecer una función de costo que estimule la conexión de habitaciones conectadas en el gráfico en superficies físicas.

El gráfico en sí se puede generar utilizando el algoritmo MCMC, donde la creación y destrucción de conexiones entre habitaciones se considerarán transiciones separadas que estimulan las conexiones entre habitaciones de ciertos tipos (las habitaciones tienen más probabilidades de conectarse a los corredores y menos al medio ambiente, etc.).

Otras posibles aplicaciones:

• Generación de laberintos; los costos se establecen en función de la tortuosidad del laberinto, y las transiciones son la colocación / eliminación de paredes o pasillos.
• Redes de carreteras, instalación y destrucción de conexiones entre nodos del gráfico en función de la distancia, el terreno u otros factores utilizados como costos.
• ¡Probablemente muchos otros!

Una nota interesante: el recocido simulado y los algoritmos MCMC se pueden usar para tareas como el "problema del vendedor ambulante", el famoso problema NP-hard. El estado del sistema es una ruta, las transiciones pueden estar cambiando los nodos de la ruta y los costos pueden ser la distancia total.

Solicitud de bots de tareas

Espero que gracias a este sistema de tareas, los bots puedan crear su propio conocimiento en el futuro de acuerdo con sus necesidades.

Aquí hay un video de cómo el bot construye una casa generada por este algoritmo:


( , ). . ( ) . , . , . - , , .