Chaînes de Markov pour la génération de bâtiments procéduraux

Remarque: le code source complet de ce projet peut être trouvé [ ici ]. Comme il fait partie d'un projet plus vaste, je recommande de regarder la validation au moment de la /source/helpers/arraymath.h cet article, ou le fichier /source/helpers/arraymath.h , ainsi que /source/world/blueprint.cpp .

Dans cet article, je veux parler en détail des principes d'utilisation des chaînes et des statistiques de Markov pour la génération procédurale de bâtiments 3D et d'autres systèmes.

Je vais expliquer les fondements mathématiques du système et essayer de rendre l'explication aussi générale que possible afin que vous puissiez appliquer ce concept dans d'autres situations, par exemple, pour générer des donjons 2D. L'explication sera accompagnée d'images et de code source.

Cette méthode est une méthode généralisée pour la génération procédurale de systèmes qui satisfont certaines exigences, je recommande donc de lire au moins jusqu'à la fin de la première section afin que vous puissiez comprendre si cette technique peut être utile dans votre cas, car ci-dessous j'explique les exigences nécessaires.

Les résultats seront utilisés dans mon moteur voxel afin que les robots de tâches puissent construire des bâtiments, puis des villes. À la toute fin de l'article, il y a un exemple!


Quelques exemples avec les résultats.

Les bases

Chaînes de Markov

Les chaînes de Markov sont une séquence d'états le long desquels un système se déplace, décrit par des transitions dans le temps. Les transitions entre états sont stochastiques, c'est-à-dire qu'elles sont décrites par des probabilités, qui sont une caractéristique du système.

Le système est défini par l'espace d'état, qui est l'espace de toutes les configurations système possibles. Si le système est décrit correctement, nous pouvons également décrire les transitions entre les états comme des étapes discrètes.

Il convient de noter qu'à partir d'un état du système, il existe souvent plusieurs transitions discrètes possibles, chacune conduisant à un état différent du système.

La probabilité de transition de l'état i à l'état j est égale à:

$$

$$P_ {ij}$$

Le processus de Markov est le processus d'étude de cet espace d'états à l'aide de probabilités qui lui sont transférées.

L'important est que les processus de Markov «n'aient pas de mémoire». Cela signifie simplement que les probabilités de transition de l'état actuel au nouvel état dépendent uniquement de l'état actuel et non plus d'autres conditions visitées précédemment.

$$

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

Exemple: génération de texte

Un système est une séquence de bits. L'espace d'état est toutes les séquences possibles de bits. Une transition discrète changera un bit de 0 à 1 ou de 1 à 0. Si le système a n bits, alors de chaque état nous avons n transitions possibles vers un nouvel état. Le processus de Markov consistera à étudier l'espace d'état en modifiant les valeurs des bits dans une séquence en utilisant certaines probabilités.

Exemple: prévisions météorologiques

Le système est les conditions météorologiques actuelles. L'espace d'état est l'ensemble des états possibles dans lesquels le temps peut être (par exemple, «pluvieux», «nuageux», «ensoleillé», etc.). La transition sera un passage de n'importe quel état à un autre état dans lequel nous pouvons définir la probabilité de la transition (par exemple, "quelle est la probabilité que s'il fait beau aujourd'hui, alors il pleuvra demain, quelle que soit la météo d'hier?").

Méthode de Monte Carlo pour les chaînes de Markov

Puisque les transitions entre les états sont déterminées par des probabilités, nous pouvons également définir la probabilité qu'une «stable» se trouve dans n'importe quel état (ou, si le temps tend vers l'infini, le temps moyen pendant lequel nous serons dans un état particulier). Il s'agit d'une distribution interne des États.

Ensuite, l'algorithme de Monte Carlo pour les chaînes de Markov (Markov-Chain Monte-Carlo, MCMC) est une technique pour obtenir un échantillon de l'espace d'état. L'échantillonnage (échantillonnage) signifie le choix de l'état en fonction de la probabilité de sélection, en tenant compte de la distribution interne.

Ils disent que la probabilité d'être dans un état est proportionnelle * à une certaine fonction de coût qui donne une «estimation» de l'état actuel dans lequel se trouve le système. On pense que si les coûts sont faibles, la probabilité d'être dans cet état est élevée et ce rapport est monotone. La fonction de coût est définie comme suit:

$$

$$R (i)$$

Remarque: je ne sais pas si le mot «proportionnel» est utilisé correctement, car le rapport n'est pas nécessairement linéaire.

Ensuite, un échantillon de la distribution d'état retournera une configuration à faible coût (ou une bonne «estimation») avec une probabilité plus élevée!

Même avec un espace d'état extrêmement grand (peut-être infini, mais «infiniment infini»), quelle que soit la complexité du système, l'algorithme MCMC trouvera une solution à faible coût si nous lui donnons suffisamment de temps pour converger.

Faire une telle étude de l'espace d'état est une technique standard d'optimisation stochastique et a de nombreuses applications dans des domaines tels que l'apprentissage automatique.

Distribution de Gibbs

Remarque: si cette section n'est pas claire pour vous, vous pouvez la sauter en toute sécurité. Vous pouvez toujours profiter de la mise en œuvre du système.

Après avoir déterminé les coûts d'une condition possible, comment déterminer la probabilité de cette condition?

Solution: La distribution de Gibbs est la distribution de l'entropie maximale pour un ensemble donné de contraintes.

Essentiellement, cela signifie que si nous établissons de nombreuses contraintes sur les probabilités du système, la distribution de Gibbs créera la «moindre quantité d'hypothèses» sur la forme de la distribution.

Remarque: la distribution de Gibbs est également la distribution la moins sensible aux variations de contraintes (selon la métrique de divergence de Kullback-Leibler).

La seule restriction que nous imposons à la distribution des états est la fonction de coût, donc nous l'utilisons dans la distribution de Gibbs pour calculer la probabilité de transition entre les états:

$$

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

Où Z est la fonction de partition de l'ensemble des transitions de l'état i. Il s'agit d'un facteur de normalisation qui garantit que la somme des probabilités de transition de n'importe quel état est 1.

$$

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

Notez que si nous décidons que l'état suivant sera le même état, alors les coûts relatifs sont nuls, c'est-à-dire que la probabilité après normalisation sera non nulle (en raison de la forme de la distribution avec l'indicateur)! Cela signifie que dans de nombreuses transitions, il est nécessaire d'inclure la probabilité d'états inchangés.

Il convient également de noter que la distribution de Gibbs est paramétrée par la «température de calcul» T.

L'un des principaux avantages de l'utilisation des probabilités dans l'étude de l'espace d'états est que le système peut effectuer des transitions vers des états plus chers (car ils ont une probabilité de transition non nulle), transformant l'algorithme en une méthode d'optimisation «non gourmande».

Notez que comme la température tend vers l'infini, la probabilité de toute transition individuelle tend vers l'unité de telle sorte que lorsque l'ensemble des probabilités de toutes les transitions de l'état est normalisé, elles deviennent également probables (ou la distribution de Gibbs se rapproche de la distribution normale), malgré le fait que leurs coûts soient plus élevés!

Lorsque la température de calcul approche de zéro, les transitions à moindre coût deviennent plus probables, c'est-à-dire que la probabilité de transitions préférées augmente.

Lors de la recherche / optimisation de l'espace d'état, nous abaissons progressivement la température. Ce processus est appelé «recuit simulé» . Grâce à cela, au début, nous pouvons facilement sortir du minimum local, et à la fin, nous pouvons choisir les meilleures solutions.

Lorsque la température est suffisamment basse, toutes les probabilités tendent vers zéro, à l'exception de la probabilité d'absence de transition!

En effet, seule l'absence de transition a une différence de coût nulle, c'est-à-dire que le fait d'être dans le même état ne dépend pas de la température. En raison de la forme de la fonction exponentielle à T = 0, cela se révèle être la seule probabilité avec une valeur non nulle, c'est-à-dire qu'après normalisation, elle se transforme en unité. Par conséquent, notre système convergera vers un point stable et un refroidissement supplémentaire ne sera plus nécessaire. C'est une propriété intégrale de la génération de probabilité utilisant la distribution de Gibbs.

Le processus de convergence du système peut être ajusté en modifiant la vitesse de refroidissement!

Si le refroidissement est plus lent, nous arrivons généralement à une solution à moindre coût (dans une certaine mesure), mais au prix de plusieurs étapes de convergence. Si le refroidissement est plus rapide, alors il est plus probable que le système dans les premiers stades tombe dans le piège d'une sous-région avec des coûts plus élevés, c'est-à-dire que nous obtiendrons des résultats "moins optimaux".

Par conséquent, le processus de Markov ne génère pas seulement des résultats aléatoires, mais essaie de générer de «bons» résultats, et avec une forte probabilité, il réussira!

Par définition de fonctions de coût arbitraires, il n'est pas nécessaire qu'il existe un optimum unique. Cette méthode d'optimisation probabiliste génère uniquement en s'approchant de l'optimum, en essayant de minimiser la fonction de coût, et en raison de l'échantillonnage, elle générera des résultats différents à chaque fois (si le générateur de nombres aléatoires a une graine différente).

Le processus d'échantillonnage lui-même peut être effectué en utilisant la méthode de transformation inverse sur la fonction de distribution de masse de notre ensemble discret de transitions. Plus tard, je montrerai comment cela se fait.

Génération procédurale

Comment cette méthode est-elle utile pour la génération procédurale?

Dans certains systèmes, il est souvent difficile de définir un algorithme simple qui génère de bons résultats, en particulier dans le cas de systèmes complexes.

L'établissement de règles de génération arbitraires est non seulement difficile, mais également limité uniquement par notre imagination et le traitement des cas limites.

Si le système satisfait un certain ensemble d'exigences, l'utilisation de MCMC nous permet de ne pas nous soucier de la sélection d'un algorithme ou de règles. Au lieu de cela, nous définissons une méthode pour générer tout résultat possible, et en choisissons consciemment un bon en fonction de son «évaluation».

Les exigences suivantes sont présentées:

• Le système peut être dans une configuration d'état discrète (éventuellement infinie).
• Nous pouvons définir des transitions discrètes entre les états.
• Nous pouvons définir une fonction de coût qui estime l'état actuel du système.

Ci-dessous, je donnerai quelques autres exemples dans lesquels, à mon avis, cette méthode peut être appliquée.

Implémentation

Pseudo code

Dans notre mise en œuvre, nous voulons atteindre les objectifs suivants:

• Définissez l'état du système.
• Réglez toutes les transitions possibles à l'état suivant.
• Calculez les coûts de l'état actuel.
• Calculez les coûts de tous les prochains états possibles (ou d'un sous-ensemble d'entre eux).
• En utilisant la distribution de Gibbs, calculez la probabilité de transitions.
• Échantillon (échantillon) de transitions à l'aide de probabilités.
• Effectuez une transition échantillonnée.
• Réduisez la température de calcul.
• Répétez les étapes jusqu'à ce que vous obteniez des résultats satisfaisants.

Sous forme de pseudocode, l'algorithme MCMC est le suivant:

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

Génération de bâtiments 3D

Espace d'état et transitions

Pour générer des bâtiments en 3D, je génère de nombreuses pièces avec le volume spécifié par le cadre de délimitation.

 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 je génère n pièces, l'état du système est la configuration des boîtes englobantes dans l'espace 3D.

Il convient de noter que les configurations possibles pour ces volumes sont infinies, mais infiniment infinies (elles peuvent être répertoriées dans un temps infini)!

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

De nombreuses transitions possibles seront un déplacement de pièces dans l'une des six directions de l'espace d'un pas, y compris l'absence de transition:

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

Remarque: il est important que nous gardions le système capable de rester dans son état actuel!

Fonction de coût

Je voulais que les volumes dans l'espace 3D se comportent comme des «aimants», c'est-à-dire:

• Si leurs volumes se croisent, c'est mauvais.
• Si leurs surfaces se touchent, c'est bien.
• S'ils ne se touchent pas du tout, c'est mauvais.
• S'ils touchent le sol, tant mieux.

Pour deux cuboïdes dans l'espace 3D, nous pouvons facilement définir un cadre de délimitation:

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

En utilisant la boîte englobante des volumes, nous pouvons calculer un vecteur 3D qui me donne des informations sur l'intersection de deux volumes.

Si la longueur du parallélépipède le long d'un côté est supérieure à la somme des longueurs de deux volumes le long de ce côté, alors de ce côté ils ne se touchent pas. S'ils sont égaux, les surfaces se touchent et, si elles sont inférieures, les volumes se croisent.

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

Ce code est utilisé pour calculer le nombre de quantités pour lesquelles je forme un montant pondéré, qui est finalement utilisé comme coût.

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

Remarque: «volume d'intersection positif» signifie que les volumes se coupent réellement. «Volume d'intersection négatif» signifie qu'ils ne se touchent pas du tout et que l'intersection est définie par le volume dans l'espace situé entre les deux points les plus proches de deux cuboïdes dans l'espace 3D.

Les poids sont choisis de manière à donner la priorité à une chose et à en raffiner d'autres. Par exemple, ici j'amende sévèrement les pièces situées sous le plancher, et augmente également la priorité de celles dont les surfaces se touchent (plus que j'amende l'intersection des volumes).

Je génère des coûts pour toutes les paires de chambres, en ignorant les chambres qui sont jumelées avec elles-mêmes.

Trouver une solution à faible coût

La convergence est effectuée comme décrit dans le pseudo-code. Lors de la transition, je ne déplace qu'une seule pièce à la fois. Cela signifie qu'avec n chambres et 7 transitions possibles, j'ai besoin de calculer 7 * n probabilités, et je sélectionne parmi toutes, en ne déplaçant que cette pièce, qui est probablement la plus préférable.

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

L'échantillonnage est effectué par la formation d'une fonction de distribution cumulative sur la fonction de distribution de masse de toutes les transitions possibles; cette opération est appelée «échantillonnage à transformée inverse».

Ceci est accompli en générant la somme cumulée des probabilités de transition, ce qui nous donne la fonction de distribution cumulative (CDF). Pour l'échantillonnage, nous générons une variable aléatoire avec une distribution uniforme entre 0 et 1. Puisque le premier élément du CDF est zéro et le dernier, nous avons juste besoin de trouver "dans quel indice du tableau CDF est notre variable échantillonnée avec une distribution uniforme", et ce sera indice de transition échantillonné. En voici une illustration:


Au lieu d'une fonction continue, il peut y avoir des étapes discrètes. Plus de détails peuvent être lus ici .

De plus, j'ai des données de volume de pièce dans l'espace 3D!

Je les utilise pour générer un «schéma» à l'aide de la classe blueprint, en appliquant un thème à des données en masse connues. Les maisons ont donc leur apparence. plan de classe décrit dans l'article précédent [ ici ] ([ traduction ] Habré). Pour la génération complète d'une maison à partir de ces volumes, voir le code source.

Résultats

Les résultats d'une telle méthode généralisée sont assez bons. La seule chose que je devais configurer était la priorité correcte et les poids de pénalité dans la fonction de coût.


Quelques exemples de génération de bâtiments utilisant cet algorithme et le thème qui leur est appliqué.


Vue latérale (autres bâtiments).

La convergence elle-même est très rapide, en particulier pour un petit nombre de pièces (3-5), car le calcul des boîtes englobantes et l'estimation de la fonction de coût est très simple.

Dans la version actuelle, les maisons n'ont ni portes ni fenêtres, mais il s'agit davantage d'interpréter des données de volume 3D que d'une tâche pour l'algorithme MCMC.

Parfois, la méthode donne des résultats moches, car il s'agit d'un processus stochastique, donc avant de placer un bâtiment dans le monde, vous devez vérifier son exactitude, surtout si la fonction de coût n'est pas très fiable. Je soupçonne que la laideur se produit principalement dans les premières étapes lorsque la température est élevée.

Les défauts apparaissent généralement sous forme de pièces ou de pièces séparées du bâtiment. suspendu en l'air (sur pilotis).

Extensions et autres systèmes

Évidemment, ma technique avec les volumes 3D est facile à transférer dans le monde 2D en réduisant simplement la dimension de la tâche d'une unité.

Autrement dit, il peut être utilisé pour des tâches telles que la génération procédurale de donjons ou de salles dans des jeux 2D avec une vue de dessus - attacher des salles les unes aux autres utilise une fonction de coût similaire à celle décrite ci-dessus.

Un moyen possible de rendre la génération plus intéressante consiste à générer d'abord un graphique des pièces, chacune ayant son propre type, puis à définir une fonction de coût qui stimule la connexion des pièces connectées dans le graphique sur les surfaces physiques.

Le graphique lui-même peut être généré à l'aide de l'algorithme MCMC, où la création et la destruction de connexions entre les pièces seront considérées comme des transitions distinctes qui stimulent les connexions entre les pièces de certains types (les chambres sont plus susceptibles de se connecter aux couloirs et moins susceptibles à l'environnement, etc.).

Autres applications possibles:

• Génération du labyrinthe; les coûts sont fixés en fonction de la tortuosité du labyrinthe, et les transitions sont le placement / l'enlèvement des murs ou des couloirs.
• Réseaux de routes, installation et destruction des connexions entre les nœuds du graphique en fonction de la distance, du terrain ou d'autres facteurs utilisés comme coûts.
• Probablement beaucoup d'autres!

Remarque intéressante: les algorithmes de recuit simulé et MCMC peuvent être utilisés pour des tâches telles que le "problème du voyageur de commerce", le fameux problème NP-hard. L'état du système est un itinéraire, les transitions peuvent changer de nœud d'itinéraire et les coûts peuvent être la distance totale!

Demande de Task Bots

J'espère que grâce à ce système, les robots de tâches pourront à l'avenir créer leurs propres connaissances en fonction de leurs besoins.

Voici une vidéo de la façon dont le bot construit une maison générée par cet algorithme:


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