Cadeias de Markov para geração processual de edifícios

Nota: o código fonte completo deste projeto pode ser encontrado [ aqui ]. Como faz parte de um projeto maior, recomendo assistir ao commit no momento em que este artigo foi lançado, ou o arquivo /source/helpers/arraymath.h , bem como /source/world/blueprint.cpp .

Neste artigo, quero falar em detalhes sobre os princípios do uso de cadeias e estatísticas de Markov para a geração processual de edifícios em 3D e outros sistemas.

Vou explicar os fundamentos matemáticos do sistema e tentarei tornar a explicação o mais geral possível, para que você possa aplicar esse conceito em outras situações, por exemplo, para gerar masmorras 2D. A explicação será acompanhada de imagens e código fonte.

Este método é um método generalizado para a geração procedural de sistemas que atendem a certos requisitos, por isso recomendo a leitura pelo menos até o final da primeira seção para que você possa entender se essa técnica pode ser útil no seu caso, porque abaixo explico os requisitos necessários.

Os resultados serão usados ​​no meu mecanismo voxel para que os robôs de tarefas possam construir prédios e cidades. No final do artigo, há um exemplo!


Alguns exemplos com os resultados.

O básico

Cadeias de Markov

As cadeias de Markov são uma sequência de estados pelos quais um sistema se move, descrito por transições no tempo. As transições entre estados são estocásticas, ou seja, são descritas por probabilidades, que são uma característica do sistema.

O sistema é definido pelo espaço de estado, que é o espaço de todas as configurações possíveis do sistema. Se o sistema for descrito corretamente, também podemos descrever as transições entre estados como etapas discretas.

Deve-se notar que, a partir de um estado do sistema, muitas vezes existem várias transições discretas possíveis, cada uma das quais leva a um estado diferente do sistema.

A probabilidade de transição do estado i para o estado j é igual a:

$$

$$P_ {ij}$$

O processo de Markov é o processo de estudar esse espaço de estados com a ajuda das probabilidades transferidas para ele.

O importante é que os processos de Markov "não têm memória". Significa apenas que as probabilidades de transição do estado atual para o novo dependem apenas do estado atual e não mais de outras condições visitadas anteriormente.

$$

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

Exemplo: geração de texto

Um sistema é uma sequência de bits. O espaço de estado é todas as sequências possíveis de bits. Uma transição discreta mudará um bit de 0 para 1 ou 1 para 0. Se o sistema tiver n bits, então, de cada estado, temos n transições possíveis para um novo estado. O processo de Markov consistirá no estudo do espaço de estados, alterando os valores dos bits em uma sequência usando determinadas probabilidades.

Exemplo: previsão do tempo

O sistema é as condições climáticas atuais. O espaço de estados é todos os estados possíveis em que o clima pode estar (por exemplo, "chuvoso", "nublado", "ensolarado" etc.). A transição será uma mudança de qualquer estado para outro, no qual possamos definir a probabilidade da transição (por exemplo, "qual é a probabilidade de que, se estiver ensolarado hoje, amanhã chove amanhã, independentemente do clima de ontem?").

Método de Monte Carlo para cadeias de Markov

Como as transições entre estados são determinadas pelas probabilidades, também podemos definir a probabilidade de um "estável" estar em qualquer estado (ou, se o tempo tender ao infinito, o tempo médio em que estaremos em um determinado estado). Esta é uma distribuição interna de estados.

Então o algoritmo de Monte Carlo para cadeias de Markov (Markov-Chain Monte-Carlo, MCMC) é uma técnica para obter uma amostra do espaço de estados. Amostragem (amostragem) significa a escolha do estado com base na probabilidade de seleção, levando em consideração a distribuição interna.

Eles dizem que a probabilidade de estar em um estado é proporcional * a uma determinada função de custo que fornece uma "estimativa" do estado atual em que o sistema está localizado. Acredita-se que, se os custos forem baixos, a probabilidade de estar nesse estado é alta e essa proporção é monótona. A função de custo é definida da seguinte forma:

$$

$$R (i)$$

Nota: não tenho certeza se a palavra "proporcional" é usada corretamente, porque a proporção não é necessariamente linear.

Em seguida, uma amostra da distribuição estadual retornará uma configuração com baixos custos (ou uma boa "estimativa") com maior probabilidade!

Mesmo com um espaço de estado extremamente grande (possivelmente infinito, mas "infinitamente contável"), independentemente da complexidade do sistema, o algoritmo MCMC encontrará uma solução com custos baixos se dermos tempo suficiente para convergir.

Fazer esse estudo do espaço de estados é uma técnica padrão de otimização estocástica e tem muitas aplicações em áreas como aprendizado de máquina.

Distribuição de Gibbs

Nota: se esta seção não estiver clara para você, você pode ignorá-la com segurança. Você ainda pode tirar proveito da implementação do sistema.

Depois de determinarmos os custos de uma possível condição, como determinamos a probabilidade dessa condição?

Solução: A distribuição de Gibbs é a distribuição da entropia máxima para um determinado conjunto de restrições.

Em essência, isso significa que, se definirmos muitas restrições sobre as probabilidades do sistema, a distribuição de Gibbs criará a "menor quantidade de suposições" sobre o formato da distribuição.

Nota: a distribuição de Gibbs também é a distribuição com menor sensibilidade a variações de restrições (de acordo com a métrica de divergência de Kullback-Leibler).

A única restrição que impomos à distribuição de estados é a função de custo; portanto, a usamos na distribuição de Gibbs para calcular a probabilidade de transição entre estados:

$$

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

Onde Z é a função de partição do conjunto de transições do estado i. Esse é um fator de normalização que garante que a soma das probabilidades de transição de qualquer estado seja 1.

$$

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

Observe que, se decidirmos que o próximo estado será o mesmo, os custos relativos serão zero, ou seja, a probabilidade após a normalização será diferente de zero (devido ao formato da distribuição com o indicador)! Isso significa que em muitas transições é necessário incluir a probabilidade de estados inalterados.

Também é importante notar que a distribuição de Gibbs é parametrizada pela "temperatura computacional" T.

Uma das principais vantagens do uso de probabilidades no estudo do espaço de estados é que o sistema pode realizar transições para estados mais caros (já que eles têm uma probabilidade de transição diferente de zero), transformando o algoritmo em um método de otimização "não ganancioso".

Observe que, como a temperatura tende ao infinito, a probabilidade de qualquer transição individual tende a se unir de tal maneira que quando o conjunto de probabilidades de todas as transições do estado é normalizado, elas se tornam igualmente prováveis ​​(ou a distribuição de Gibbs se aproxima da distribuição normal), apesar de seus custos serem maiores!

À medida que a temperatura computacional se aproxima de zero, transições com custos mais baixos se tornam mais prováveis, ou seja, aumenta a probabilidade de transições preferidas.

Ao realizar pesquisa / otimização do espaço de estados, abaixamos gradualmente a temperatura. Esse processo é chamado de "recozimento simulado" . Graças a isso, no começo podemos sair facilmente do mínimo local e, no final, podemos escolher as melhores soluções.

Quando a temperatura é baixa o suficiente, todas as probabilidades tendem a zero, com exceção da probabilidade de não haver transição!

Isso ocorre porque apenas a ausência de uma transição tem uma diferença de custo zero, ou seja, estar no mesmo estado não depende da temperatura. Devido à forma da função exponencial em T = 0, essa é a única probabilidade com um valor diferente de zero, ou seja, após a normalização, ela se transforma em unidade. Conseqüentemente, nosso sistema convergirá para um ponto estável e não será mais necessário um resfriamento adicional. Esta é uma propriedade integral da geração de probabilidade usando a distribuição Gibbs.

O processo de convergência do sistema pode ser ajustado alterando a taxa de resfriamento!

Se o resfriamento for mais lento, como resultado, geralmente chegamos a uma solução com custos mais baixos (até certo ponto), mas ao custo de mais etapas de convergência. Se o resfriamento for mais rápido, é mais provável que o sistema caia na armadilha de uma sub-região com custos mais altos, ou seja, obteremos resultados "menos ótimos".

Conseqüentemente, o processo de Markov não apenas gera resultados aleatórios, mas tenta gerar resultados "bons", e com alta probabilidade de sucesso!

Por definição de funções de custo arbitrárias, um ótimo único não precisa existir. Esse método de otimização probabilística gera apenas aproximando-se do ideal, tentando minimizar a função de custo e, devido à amostragem, gera resultados diferentes a cada vez (se o gerador de números aleatórios tiver uma semente diferente).

O próprio processo de amostragem pode ser realizado usando o método de transformação inversa sobre a função de distribuição de massa do nosso conjunto discreto de transições. Mais tarde mostrarei como isso é feito.

Geração processual

Como esse método é útil para geração de procedimentos?

Em alguns sistemas, geralmente é difícil definir um algoritmo simples que gere bons resultados, especialmente no caso de sistemas complexos.

Definir regras de geração arbitrárias não é apenas difícil, mas também limitado apenas por nossa imaginação e processamento de casos de fronteira.

Se o sistema atender a um determinado conjunto de requisitos, o uso do MCMC nos permite não nos preocupar com a seleção de um algoritmo ou regras. Em vez disso, definimos um método para gerar qualquer resultado possível e escolhemos conscientemente um bom com base em sua "avaliação".

Os seguintes requisitos são apresentados:

• O sistema pode estar em uma configuração de estado discreto (possivelmente infinito).
• Podemos definir transições discretas entre estados.
• Podemos definir uma função de custo que estima o estado atual do sistema.

Abaixo darei outros exemplos nos quais, na minha opinião, esse método pode ser aplicado.

Implementação

Pseudo código

Em nossa implementação, queremos alcançar o seguinte:

• Defina o status do sistema.
• Defina todas as transições possíveis para o próximo estado.
• Calcule os custos do estado atual.
• Calcule os custos de todos os próximos estados possíveis (ou um subconjunto deles).
• Usando a distribuição Gibbs, calcule a probabilidade de transições.
• Transições de amostra (amostra) usando probabilidades.
• Execute uma transição de amostra.
• Reduza a temperatura computacional.
• Repita as etapas até obter resultados satisfatórios.

Na forma de pseudocódigo, o algoritmo MCMC é o seguinte:

 // 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; } 

Geração de edifícios 3D

Espaço de Estado e Transições

Para gerar edifícios em 3D, eu gero muitas salas com o volume especificado pela caixa delimitadora.

 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; } 

Se eu gerar n salas, o estado do sistema é a configuração das caixas delimitadoras no espaço 3D.

Deve-se notar que as configurações possíveis para esses volumes são infinitas, mas consideravelmente infinitas (elas podem ser listadas em uma quantidade infinita de tempo)!

 //  (  !) 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); } //... 

Muitas transições possíveis serão uma mudança de salas em uma das seis direções do espaço em uma etapa, incluindo a ausência de uma transição:

 //... //   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: é importante manter o sistema capaz de permanecer em seu estado atual!

Função de custo

Eu queria que os volumes no espaço 3D se comportassem como "ímãs", ou seja:

• Se seus volumes se cruzam, isso é ruim.
• Se suas superfícies tocarem, isso é bom.
• Se eles não tocam, isso é ruim.
• Se eles tocam o chão, isso é bom.

Para dois cuboides no espaço 3D, podemos definir facilmente uma caixa delimitadora:

 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 a caixa delimitadora de volumes, podemos calcular um vetor 3D que me fornece informações sobre a interseção de dois volumes.

Se o comprimento do paralelepípedo ao longo de um lado for maior que a soma dos comprimentos de dois volumes ao longo desse lado, desse lado eles não se tocarão. Se forem iguais, as superfícies tocam e, se forem menores, os volumes se cruzam.

 //    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; } 

Esse código é usado para calcular o número de quantidades para as quais eu formei uma quantidade ponderada, que é usada como custo.

 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: “volume positivo de interseção” significa que os volumes realmente se cruzam. “Volume negativo de interseção” significa que eles não tocam e a interseção é definida pelo volume no espaço localizado entre os dois pontos mais próximos dos dois cuboides no espaço 3D.

Os pesos são escolhidos de forma a dar prioridade a uma coisa e multa a outras. Por exemplo, aqui refino severamente os cômodos localizados embaixo do piso e também aumento a prioridade daqueles cujas áreas de superfície tocam (mais do que refino a interseção de volumes).

Gosto de custos para todos os pares de quartos, ignorando os quartos que estão emparelhados.

Encontrando uma solução de baixo custo

A convergência é realizada conforme descrito no pseudocódigo. Ao fazer a transição, movo apenas uma sala de cada vez. Isso significa que, com n salas e 7 transições possíveis, preciso calcular 7 * n probabilidades e seleciono de todas elas, movendo apenas a sala, que é provavelmente a mais preferível.

  //  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; // !!! } //!! //... 

; « ».

, (cumulative distribution function, CDF). 0 1. CDF , , « CDF », . :


Em vez de uma função contínua, pode haver etapas discretas. Mais detalhes podem ser lidos aqui .

Além disso, tenho dados de volume da sala no espaço 3D!

Eu os uso para gerar um "esquema" usando a classe blueprint, aplicando um tema a dados em massa conhecidos. Assim, as casas aparecem. A classe blueprint é descrita no artigo anterior [ aqui ] ([ tradução ] em Habré). Para geração completa de uma casa a partir desses volumes, consulte o código-fonte.

Resultados

Os resultados para um método tão generalizado são bastante bons. A única coisa que precisei configurar foi a prioridade correta e os pesos das penalidades na função de custo.


Alguns exemplos de geração de construção usando esse algoritmo e o tema aplicado a eles.


( ).

, (3-5), .

, 3D- , MCMC.

, , , . , , .

. ( ).

, 3D- 2D-, .

, 2D- — , .

, , , , , .

MCMC, , ( , ..).

:

• ; , / .
• , , , .
• , !

: MCMC , « », NP- . — , , — !

Task-

, task- .

, , :


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