Markov-Ketten zur prozeduralen Gebäudeerzeugung

Hinweis: Den vollständigen Quellcode dieses Projekts finden Sie [ hier ]. Da es Teil eines größeren Projekts ist, empfehle ich, das Commit zum Zeitpunkt der /source/helpers/arraymath.h dieses Artikels oder die Datei /source/helpers/arraymath.h sowie /source/world/blueprint.cpp .

In diesem Artikel möchte ich detailliert auf die Prinzipien der Verwendung von Markov-Ketten und Statistiken für die prozedurale Generierung von 3D-Gebäuden und anderen Systemen eingehen.

Ich werde die mathematischen Grundlagen des Systems erläutern und versuchen, die Erklärung so allgemein wie möglich zu gestalten, damit Sie dieses Konzept auch in anderen Situationen anwenden können, beispielsweise um 2D-Dungeons zu generieren. Die Erklärung wird von Bildern und Quellcode begleitet.

Diese Methode ist eine verallgemeinerte Methode zur prozeduralen Generierung von Systemen, die bestimmte Anforderungen erfüllen. Ich empfehle daher, mindestens bis zum Ende des ersten Abschnitts zu lesen, damit Sie verstehen, ob diese Technik in Ihrem Fall nützlich sein kann, da ich im Folgenden die erforderlichen Anforderungen erläutere.

Die Ergebnisse werden in meiner Voxel-Engine verwendet, damit Task-Bots Gebäude und dann Städte bauen können. Ganz am Ende des Artikels steht ein Beispiel!


Ein paar Beispiele mit den Ergebnissen.

Die Grundlagen

Markov-Ketten

Markov-Ketten sind eine Folge von Zuständen, entlang derer sich ein System bewegt, beschrieben durch zeitliche Übergänge. Übergänge zwischen Zuständen sind stochastisch, dh sie werden durch Wahrscheinlichkeiten beschrieben, die ein Merkmal des Systems sind.

Das System wird durch den Zustandsraum definiert, der den Raum aller möglichen Systemkonfigurationen darstellt. Wenn das System richtig beschrieben ist, können wir die Übergänge zwischen Zuständen auch als diskrete Schritte beschreiben.

Es ist zu beachten, dass es von einem Zustand des Systems häufig mehrere mögliche diskrete Übergänge gibt, von denen jeder zu einem anderen Zustand des Systems führt.

Die Übergangswahrscheinlichkeit vom Zustand i zum Zustand j ist gleich:

$$

$$P_ {ij}$$

Der Markov-Prozess ist der Prozess des Studierens dieses Zustandsraums mit Hilfe von darauf übertragenen Wahrscheinlichkeiten.

Wichtig ist, dass Markov-Prozesse „kein Gedächtnis haben“. Dies bedeutet lediglich, dass die Wahrscheinlichkeiten des Übergangs vom aktuellen zum neuen Zustand nur vom aktuellen Zustand und nicht mehr von anderen zuvor besuchten Bedingungen abhängen.

$$

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

Beispiel: Textgenerierung

Ein System ist eine Folge von Bits. Der Zustandsraum besteht aus allen möglichen Folgen von Bits. Ein diskreter Übergang ändert ein Bit von 0 auf 1 oder 1 auf 0. Wenn das System n Bits hat, haben wir von jedem Zustand n mögliche Übergänge in einen neuen Zustand. Der Markov-Prozess besteht in der Untersuchung des Zustandsraums durch Ändern der Werte von Bits in einer Sequenz unter Verwendung bestimmter Wahrscheinlichkeiten.

Beispiel: Wettervorhersage

Das System ist die aktuelle Wetterlage. Der Zustandsraum ist alle möglichen Zustände, in denen das Wetter sein kann (z. B. "regnerisch", "bewölkt", "sonnig" usw.). Der Übergang wird ein Wechsel von einem Zustand in einen anderen sein, in dem wir die Wahrscheinlichkeit des Übergangs festlegen können (zum Beispiel: "Wie groß ist die Wahrscheinlichkeit, dass es morgen regnet, wenn es heute sonnig ist, unabhängig vom Wetter von gestern?").

Monte-Carlo-Methode für Markov-Ketten

Da die Übergänge zwischen den Zuständen durch Wahrscheinlichkeiten bestimmt werden, können wir auch die Wahrscheinlichkeit festlegen, dass sich ein „stabiler“ Zustand in einem beliebigen Zustand befindet (oder, wenn die Zeit gegen unendlich geht, die durchschnittliche Zeit, in der wir uns in einem bestimmten Zustand befinden). Dies ist eine interne Verteilung von Zuständen.

Dann ist der Monte-Carlo-Algorithmus für Markov-Ketten (Markov-Chain Monte-Carlo, MCMC) eine Technik zum Erhalten einer Probe aus dem Zustandsraum. Sampling (Sampling) bezeichnet die Auswahl des Zustands anhand der Auswahlwahrscheinlichkeit unter Berücksichtigung der internen Verteilung.

Sie sagen, dass die Wahrscheinlichkeit, sich in einem Zustand zu befinden, proportional * zu einer bestimmten Kostenfunktion ist, die eine „Schätzung“ des aktuellen Zustands liefert, in dem sich das System befindet. Es wird angenommen, dass bei niedrigen Kosten die Wahrscheinlichkeit hoch ist, in diesem Zustand zu sein, und dass dieses Verhältnis eintönig ist. Die Kostenfunktion ist wie folgt definiert:

$$

$$R (i)$$

Hinweis: Ich bin mir nicht sicher, ob das Wort „proportional“ richtig verwendet wird, da das Verhältnis nicht unbedingt linear ist.

Dann liefert eine Stichprobe aus der Zustandsverteilung eine Konfiguration mit geringen Kosten (oder einer guten "Schätzung") mit einer höheren Wahrscheinlichkeit!

Selbst bei einem extrem großen Zustandsraum (möglicherweise unendlich, aber "zählbar unendlich") wird der MCMC-Algorithmus unabhängig von der Komplexität des Systems eine kostengünstige Lösung finden, wenn wir ihm genügend Zeit für die Konvergenz geben.

Eine solche Untersuchung des Zustandsraums ist eine Standardtechnik der stochastischen Optimierung und hat viele Anwendungen in Bereichen wie maschinellem Lernen.

Gibbs-Verteilung

Hinweis: Wenn Ihnen dieser Abschnitt nicht klar ist, können Sie ihn problemlos überspringen. Sie können weiterhin die Implementierung des Systems nutzen.

Wie bestimmen wir die Wahrscheinlichkeit dieses Zustands, nachdem wir die Kosten für einen möglichen Zustand ermittelt haben?

Lösung: Die Gibbs-Verteilung ist die Verteilung der maximalen Entropie für einen bestimmten Satz von Bedingungen.

Im Wesentlichen bedeutet dies, dass, wenn wir die Wahrscheinlichkeiten des Systems stark einschränken, die Gibbs-Verteilung die „geringste Anzahl von Annahmen“ über die Form der Verteilung erzeugt.

Anmerkung: Die Gibbs-Verteilung ist auch die Verteilung mit der geringsten Empfindlichkeit für Änderungen der Abhängigkeiten (gemäß der Kullback-Leibler-Divergenzmetrik).

Die einzige Einschränkung, die wir der Verteilung von Zuständen auferlegen, ist die Kostenfunktion. Daher verwenden wir sie in der Gibbs-Verteilung, um die Wahrscheinlichkeit des Übergangs zwischen Zuständen zu berechnen:

$$

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

Wobei Z die Partitionsfunktion der Menge von Übergängen von Zustand i ist. Dies ist ein Normalisierungsfaktor, der garantiert, dass die Summe der Übergangswahrscheinlichkeiten von jedem Zustand 1 ist.

$$

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

Beachten Sie, dass wenn wir entscheiden, dass der nächste Zustand derselbe ist, die relativen Kosten Null sind, dh die Wahrscheinlichkeit nach der Normalisierung ungleich Null ist (aufgrund der Form der Verteilung mit dem Indikator)! Dies bedeutet, dass in vielen Übergängen die Wahrscheinlichkeit unveränderter Zustände berücksichtigt werden muss.

Erwähnenswert ist auch, dass die Gibbs-Verteilung durch die „Rechentemperatur“ T parametrisiert wird.

Einer der Hauptvorteile der Verwendung von Wahrscheinlichkeiten bei der Untersuchung des Zustandsraums besteht darin, dass das System Übergänge in teurere Zustände durchführen kann (da sie eine Übergangswahrscheinlichkeit ungleich Null haben), wodurch der Algorithmus zu einer „nicht gierigen“ Optimierungsmethode wird.

Beachten Sie, dass, da die Temperatur gegen unendlich tendiert, die Wahrscheinlichkeit eines einzelnen Übergangs gegen eins geht, so dass, wenn die Menge der Wahrscheinlichkeiten aller Übergänge aus dem Zustand normalisiert wird, sie gleich wahrscheinlich werden (oder die Gibbs-Verteilung sich der Normalverteilung nähert), obwohl ihre Kosten höher sind!

Wenn sich die Rechentemperatur Null nähert, werden Übergänge mit geringeren Kosten wahrscheinlicher, d. H. Die Wahrscheinlichkeit bevorzugter Übergänge nimmt zu.

Bei der Erforschung / Optimierung des Zustandsraums senken wir die Temperatur allmählich ab. Dieser Vorgang wird "simuliertes Tempern" genannt. Dank dessen können wir am Anfang leicht aus dem lokalen Minimum herauskommen und am Ende die besten Lösungen auswählen.

Wenn die Temperatur niedrig genug ist, tendieren alle Wahrscheinlichkeiten zu Null, mit Ausnahme der Wahrscheinlichkeit, dass kein Übergang stattfindet!

Dies liegt daran, dass nur das Fehlen eines Übergangs eine Kostendifferenz von Null hat, das heißt, dass derselbe Zustand nicht von der Temperatur abhängt. Aufgrund der Form der Exponentialfunktion bei T = 0 stellt sich heraus, dass dies die einzige Wahrscheinlichkeit mit einem Wert ungleich Null ist, dh nach der Normierung wird es zu Eins. Infolgedessen konvergiert unser System zu einem stabilen Punkt, und eine weitere Kühlung ist nicht mehr erforderlich. Dies ist eine integrale Eigenschaft der Wahrscheinlichkeitsgenerierung unter Verwendung der Gibbs-Verteilung.

Der Konvergenzprozess des Systems kann durch Ändern der Abkühlrate angepasst werden!

Wenn die Kühlung langsamer ist, kommen wir in der Regel zu einer Lösung mit geringeren Kosten (bis zu einem gewissen Grad), jedoch auf Kosten von mehr Konvergenzschritten. Wenn die Abkühlung schneller ist, ist es wahrscheinlicher, dass das System in den frühen Stadien mit höheren Kosten in die Falle einer Subregion gerät, das heißt, wir erhalten "weniger optimale" Ergebnisse.

Folglich erzeugt der Markov-Prozess nicht nur zufällige Ergebnisse, sondern versucht, „gute“ Ergebnisse zu erzielen, und mit hoher Wahrscheinlichkeit wird er erfolgreich sein!

Durch die Definition beliebiger Kostenfunktionen muss kein eindeutiges Optimum existieren. Diese Methode der probabilistischen Optimierung erzeugt nur eine Annäherung an das Optimum, wobei versucht wird, die Kostenfunktion zu minimieren, und aufgrund der Abtastung werden jedes Mal andere Ergebnisse erzeugt (wenn der Zufallszahlengenerator einen anderen Startwert hat).

Der Abtastvorgang selbst kann unter Verwendung der inversen Transformationsmethode über die Massenverteilungsfunktion unseres diskreten Satzes von Übergängen durchgeführt werden. Ich werde später zeigen, wie das gemacht wird.

Prozedurale Generierung

Inwiefern ist diese Methode für die prozedurale Generierung nützlich?

In einigen Systemen ist es oft schwierig, einen einfachen Algorithmus zu definieren, der gute Ergebnisse liefert, insbesondere bei komplexen Systemen.

Das Setzen beliebiger Generierungsregeln ist nicht nur schwierig, sondern auch nur durch unsere Vorstellungskraft und Verarbeitung von Grenzfällen begrenzt.

Wenn das System bestimmte Anforderungen erfüllt, können wir uns durch die Verwendung von MCMC keine Gedanken über die Auswahl eines Algorithmus oder von Regeln machen. Stattdessen definieren wir eine Methode zur Generierung eines möglichen Ergebnisses und wählen bewusst eine gute Methode basierend auf ihrer „Bewertung“.

Folgende Anforderungen werden gestellt:

• Das System kann in einer diskreten (möglicherweise unendlichen) Zustandskonfiguration sein.
• Wir können diskrete Übergänge zwischen Zuständen definieren.
• Wir können eine Kostenfunktion festlegen, die den aktuellen Status des Systems schätzt.

Im Folgenden werde ich einige andere Beispiele nennen, in denen diese Methode meiner Meinung nach angewendet werden kann.

Implementierung

Pseudocode

In unserer Implementierung möchten wir Folgendes erreichen:

• Setzt den Systemstatus.
• Alle möglichen Übergänge auf den nächsten Status setzen.
• Berechnen Sie die Kosten des aktuellen Zustands.
• Berechnen Sie die Kosten aller möglichen nächsten Zustände (oder einer Teilmenge davon).
• Berechnen Sie mithilfe der Gibbs-Verteilung die Wahrscheinlichkeit von Übergängen.
• Beispiel (Beispiel) Übergänge mit Wahrscheinlichkeiten.
• Führen Sie einen abgetasteten Übergang durch.
• Rechentemperatur reduzieren.
• Wiederholen Sie die Schritte, bis Sie zufriedenstellende Ergebnisse erhalten.

In Form von Pseudocode lautet der MCMC-Algorithmus wie folgt:

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

3D-Gebäudegenerierung

Zustandsraum und Übergänge

Um Gebäude in 3D zu generieren, generiere ich viele Räume mit dem durch den Begrenzungsrahmen angegebenen Volumen.

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

Wenn ich n Räume generiere, ist der Status des Systems die Konfiguration der Begrenzungsrahmen im 3D-Raum.

Es sollte beachtet werden, dass die möglichen Konfigurationen für diese Volumes endlos sind, aber unzählige (sie können in einer unendlichen Zeitspanne aufgelistet werden)!

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

Viele mögliche Übergänge werden eine schrittweise Verschiebung von Räumen in eine der sechs Raumrichtungen sein, einschließlich des Fehlens eines Übergangs:

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

Hinweis: Es ist wichtig, dass wir das System in der Lage halten, in seinem aktuellen Zustand zu bleiben!

Kostenfunktion

Ich wollte, dass die Volumes im 3D-Raum sich wie „Magnete“ verhalten, das heißt:

• Wenn sich ihre Volumina überschneiden, ist dies schlecht.
• Wenn sich ihre Oberflächen berühren, ist dies gut.
• Wenn sie sich überhaupt nicht berühren, ist dies schlecht.
• Wenn sie den Boden berühren, ist das gut.

Für zwei Quader im 3D-Raum können wir leicht einen Begrenzungsrahmen definieren:

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

Mithilfe des Begrenzungsrahmens für Volumina können wir einen 3D-Vektor berechnen, der Informationen zum Schnittpunkt zweier Volumina liefert.

Wenn die Länge des Parallelepipeds entlang einer Seite größer ist als die Summe der Längen von zwei Volumina entlang dieser Seite, berühren sie sich von dieser Seite nicht. Wenn sie gleich sind, berühren sich die Flächen, und wenn sie kleiner sind, schneiden sich die Volumina.

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

Dieser Code wird verwendet, um die Anzahl der Mengen zu berechnen, für die ich einen gewichteten Betrag bilde, der letztendlich als Kosten verwendet wird.

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

Hinweis: „Positives Schnittvolumen“ bedeutet, dass sich die Volumina tatsächlich schneiden. „Negatives Schnittvolumen“ bedeutet, dass sie sich überhaupt nicht berühren und der Schnittpunkt durch das Volumen im Raum definiert wird, das sich zwischen den zwei nächstgelegenen Punkten von zwei Quadern im 3D-Raum befindet.

Gewichte werden so gewählt, dass das eine Vorrang hat und das andere Vorrang hat. Zum Beispiel feine ich hier die unter dem Boden befindlichen Räume streng ein und erhöhe auch die Priorität derjenigen, deren Oberflächenbereiche sich berühren (mehr als ich den Schnittpunkt der Volumina feine).

Ich generiere Kosten für alle Zimmerpaare und ignoriere Räume, die mit sich selbst gepaart sind.

Eine kostengünstige Lösung finden

Die Konvergenz wird wie im Pseudocode beschrieben durchgeführt. Bei der Umstellung bewege ich jeweils nur einen Raum. Dies bedeutet, dass ich mit n Räumen und 7 möglichen Übergängen 7 * n Wahrscheinlichkeiten berechnen und aus allen auswählen muss, wobei ich nur den Raum bewege, der wahrscheinlich am meisten bevorzugt wird.

  //  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 », . :


Anstelle einer kontinuierlichen Funktion können diskrete Schritte vorhanden sein. Weitere Details finden Sie hier .

Außerdem habe ich Raumvolumendaten im 3D-Raum!

Ich benutze sie, um mithilfe der Blueprint-Klasse ein „Schema“ zu generieren und ein Thema auf bekannte Massendaten anzuwenden. So bekommen Häuser ihr Aussehen. Die Bauplanklasse ist im vorherigen Artikel [ hier ] ([ Übersetzung ] auf Habré) beschrieben. Eine vollständige Erstellung eines Hauses aus diesen Volumes finden Sie im Quellcode.

Ergebnisse

Die Ergebnisse für eine solche verallgemeinerte Methode sind recht gut. Das einzige, was ich einrichten musste, war die richtige Priorität und Strafgewichte in der Kostenfunktion.


Einige Beispiele für die Erstellung von Gebäuden mit diesem Algorithmus und dem auf sie angewendeten Thema.


( ).

, (3-5), .

, 3D- , MCMC.

, , , . , , .

. ( ).

, 3D- 2D-, .

, 2D- — , .

, , , , , .

MCMC, , ( , ..).

:

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

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

Task-

, task- .

, , :


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