Rantai Markov untuk pembuatan bangunan prosedural

Catatan: kode sumber lengkap dari proyek ini dapat ditemukan [di sini ]. Karena ini adalah bagian dari proyek yang lebih besar, saya sarankan untuk menonton komit pada saat artikel ini dirilis, atau file /source/helpers/arraymath.h , serta /source/world/blueprint.cpp .

Pada artikel ini saya ingin berbicara secara rinci tentang prinsip-prinsip menggunakan rantai Markov dan statistik untuk generasi prosedural bangunan 3D dan sistem lainnya.

Saya akan menjelaskan dasar-dasar matematika dari sistem dan mencoba untuk membuat penjelasan sealami mungkin sehingga Anda dapat menerapkan konsep ini dalam situasi lain, misalnya, untuk menghasilkan ruang bawah tanah 2D. Penjelasan akan disertai dengan gambar dan kode sumber.

Metode ini adalah metode umum untuk pembuatan prosedural sistem yang memenuhi persyaratan tertentu, jadi saya sarankan membaca setidaknya sampai akhir bagian pertama sehingga Anda dapat memahami apakah teknik ini dapat berguna dalam kasus Anda, karena di bawah ini saya menjelaskan persyaratan yang diperlukan.

Hasilnya akan digunakan di mesin voxel saya sehingga bot tugas dapat membangun gedung, dan kemudian kota. Di akhir artikel ada sebuah contoh!


Beberapa contoh dengan hasilnya.

Dasar-dasarnya

Rantai Markov

Rantai Markov adalah urutan negara di mana sistem bergerak, dijelaskan oleh transisi dalam waktu. Transisi antar negara adalah stokastik, yaitu, mereka digambarkan oleh probabilitas, yang merupakan karakteristik dari sistem.

Sistem didefinisikan oleh ruang keadaan, yang merupakan ruang dari semua konfigurasi sistem yang mungkin. Jika sistem dideskripsikan dengan benar, maka kita juga dapat menggambarkan transisi antar status sebagai langkah-langkah terpisah.

Perlu dicatat bahwa dari satu keadaan sistem sering ada beberapa kemungkinan transisi terpisah, yang masing-masing mengarah ke keadaan sistem yang berbeda.

Probabilitas transisi dari kondisi i ke kondisi j sama dengan:

$$

$$P_ {ij}$$

Proses Markov adalah proses mempelajari ruang keadaan ini dengan bantuan probabilitas yang ditransfer ke sana.

Yang penting adalah bahwa proses Markov "tidak memiliki memori". Ini hanya berarti bahwa probabilitas transisi dari kondisi saat ini ke yang baru hanya bergantung pada kondisi saat ini dan tidak lagi pada kondisi lain yang dikunjungi sebelumnya.

$$

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

Contoh: pembuatan teks

Suatu sistem adalah urutan bit. State space adalah semua kemungkinan urutan bit. Transisi diskrit akan mengubah satu bit dari 0 ke 1 atau 1 menjadi 0. Jika sistem memiliki n bit, maka dari setiap keadaan, kami memiliki n kemungkinan transisi ke keadaan baru. Proses Markov akan terdiri dalam studi tentang ruang keadaan dengan mengubah nilai bit secara berurutan menggunakan probabilitas tertentu.

Contoh: peramalan cuaca

Sistem adalah kondisi cuaca saat ini. Ruang keadaan adalah semua keadaan yang memungkinkan di mana cuaca bisa (misalnya, "hujan", "berawan", "cerah", dll.). Transisi akan menjadi peralihan dari negara mana saja ke negara lain tempat kita dapat mengatur probabilitas transisi (misalnya, "berapa probabilitas bahwa jika hari ini cerah, maka besok akan hujan, terlepas dari cuaca kemarin?").

Metode Monte Carlo untuk Rantai Markov

Karena transisi antar negara ditentukan oleh probabilitas, kita juga dapat mengatur probabilitas keberadaan "stabil" di negara mana pun (atau, jika waktu cenderung tak terhingga, waktu rata-rata bahwa kita akan berada dalam keadaan tertentu). Ini adalah distribusi internal negara.

Kemudian algoritma Monte Carlo untuk rantai Markov (Markov-Chain Monte-Carlo, MCMC) adalah teknik untuk mendapatkan sampel dari ruang keadaan. Pengambilan sampel (sampling) berarti pemilihan keadaan berdasarkan probabilitas pemilihan, dengan mempertimbangkan distribusi internal.

Mereka mengatakan bahwa kemungkinan berada dalam keadaan sebanding * dengan fungsi biaya tertentu yang memberikan "perkiraan" keadaan saat ini di mana sistem berada. Dipercaya bahwa jika biayanya rendah, maka kemungkinan berada dalam kondisi ini tinggi, dan rasio ini monoton. Fungsi biaya didefinisikan sebagai berikut:

$$

$$R (i)$$

Catatan: Saya tidak yakin apakah kata "proporsional" digunakan dengan benar, karena rasionya tidak harus linier.

Kemudian sampel dari distribusi negara akan mengembalikan konfigurasi dengan biaya rendah (atau "perkiraan" yang baik) dengan probabilitas yang lebih tinggi!

Bahkan dengan ruang keadaan yang sangat besar (mungkin tak terbatas, tetapi "tak terhingga tak terhitung"), terlepas dari kompleksitas sistem, algoritma MCMC akan menemukan solusi dengan biaya rendah jika kami memberikan waktu yang cukup untuk konvergensi.

Melakukan studi seperti itu tentang ruang keadaan adalah teknik standar optimasi stokastik dan memiliki banyak aplikasi di bidang-bidang seperti pembelajaran mesin.

Distribusi Gibbs

Catatan: jika bagian ini tidak jelas bagi Anda, Anda dapat melewatinya dengan aman. Anda masih bisa memanfaatkan implementasi sistem.

Setelah kami menentukan biaya untuk kondisi yang memungkinkan, bagaimana kami menentukan kemungkinan kondisi ini?

Solusi: Distribusi Gibbs adalah distribusi entropi maksimum untuk sekumpulan kendala tertentu.

Pada dasarnya, ini berarti bahwa jika kita menetapkan banyak kendala pada probabilitas sistem, maka distribusi Gibbs akan menciptakan "asumsi paling sedikit" tentang bentuk distribusi.

Catatan: distribusi Gibbs juga distribusi dengan sensitivitas paling sedikit terhadap variasi kendala (menurut metrik divergensi Kullback-Leibler).

Satu-satunya batasan yang kami berikan pada distribusi negara adalah fungsi biaya, jadi kami menggunakannya dalam distribusi Gibbs untuk menghitung probabilitas transisi antar negara:

$$

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

Di mana Z adalah fungsi partisi dari himpunan transisi dari keadaan i. Ini adalah faktor normalisasi yang menjamin bahwa jumlah probabilitas transisi dari keadaan apa pun adalah 1.

$$

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

Perhatikan bahwa jika kita memutuskan bahwa keadaan selanjutnya adalah keadaan yang sama, maka biaya relatif adalah nol, yaitu, probabilitas setelah normalisasi akan menjadi nol (karena bentuk distribusi dengan indikator)! Ini berarti bahwa dalam banyak transisi perlu untuk memasukkan kemungkinan kondisi tidak berubah.

Perlu juga dicatat bahwa distribusi Gibbs diparameterisasi oleh "suhu komputasi" T.

Salah satu keuntungan utama menggunakan probabilitas dalam studi ruang keadaan adalah bahwa sistem dapat melakukan transisi ke keadaan yang lebih mahal (karena mereka memiliki probabilitas transisi bukan nol), mengubah algoritme menjadi metode optimisasi "non-serakah".

Perhatikan bahwa karena suhu cenderung tak terbatas, probabilitas setiap transisi individu cenderung bersatu sedemikian rupa sehingga ketika serangkaian probabilitas semua transisi dari negara dinormalisasi, mereka menjadi sama-sama memungkinkan (atau distribusi Gibbs mendekati distribusi normal), meskipun faktanya biayanya lebih besar!

Ketika suhu komputasi mendekati nol, transisi dengan biaya yang lebih rendah menjadi lebih mungkin, yaitu, probabilitas transisi yang disukai meningkat.

Saat melakukan penelitian / optimalisasi ruang keadaan, kami secara bertahap menurunkan suhu. Proses ini disebut "simulated annealing . " Berkat ini, pada awalnya kita dapat dengan mudah keluar dari minimum lokal, dan pada akhirnya kita dapat memilih solusi terbaik.

Ketika suhunya cukup rendah, maka semua probabilitas cenderung nol, dengan pengecualian kemungkinan tidak ada transisi!

Ini karena hanya tidak adanya transisi memiliki perbedaan biaya nol, yaitu berada dalam keadaan yang sama tidak tergantung pada suhu. Karena bentuk fungsi eksponensial pada T = 0, ini ternyata menjadi satu-satunya probabilitas dengan nilai non-nol, yaitu, setelah normalisasi, itu berubah menjadi kesatuan. Akibatnya, sistem kami akan menyatu ke titik stabil dan pendinginan lebih lanjut tidak lagi diperlukan. Ini adalah properti integral dari pembuatan probabilitas menggunakan distribusi Gibbs.

Proses konvergensi sistem dapat disesuaikan dengan mengubah laju pendinginan!

Jika pendinginan lebih lambat, maka sebagai hasilnya kita biasanya sampai pada solusi dengan biaya lebih rendah (sampai batas tertentu), tetapi dengan biaya lebih banyak langkah konvergensi. Jika pendinginan terjadi lebih cepat, maka kemungkinan besar sistem pada tahap awal akan jatuh ke dalam perangkap subregion dengan biaya lebih besar, yaitu, kita akan mendapatkan hasil yang "kurang optimal".

Akibatnya, proses Markov tidak hanya menghasilkan hasil acak, tetapi mencoba untuk menghasilkan hasil yang "baik", dan dengan probabilitas tinggi itu akan berhasil!

Dengan definisi fungsi biaya sewenang-wenang, optimum unik tidak harus ada. Metode optimasi probabilistik ini hanya menghasilkan mendekati optimal, mencoba meminimalkan fungsi biaya, dan karena pengambilan sampel, ini akan menghasilkan hasil yang berbeda setiap kali (jika generator nomor acak memiliki benih yang berbeda).

Proses pengambilan sampel itu sendiri dapat dilakukan dengan menggunakan metode transformasi terbalik atas fungsi distribusi massa set transisi diskrit kami. Nanti saya akan tunjukkan bagaimana ini dilakukan.

Generasi Prosedural

Bagaimana metode ini berguna untuk pembuatan prosedural?

Dalam beberapa sistem, seringkali sulit untuk mendefinisikan algoritma sederhana yang menghasilkan hasil yang baik, terutama dalam kasus sistem yang kompleks.

Menetapkan aturan generasi yang sewenang-wenang tidak hanya sulit, tetapi juga hanya dibatasi oleh imajinasi dan pemrosesan kasus batas kami.

Jika sistem memenuhi seperangkat persyaratan tertentu, maka penggunaan MCMC memungkinkan kita untuk tidak khawatir tentang pemilihan algoritma atau aturan. Sebaliknya, kami mendefinisikan metode untuk menghasilkan hasil yang mungkin, dan secara sadar memilih yang baik berdasarkan "penilaian" nya.

Persyaratan berikut disajikan:

• Sistem mungkin berada dalam konfigurasi status diskrit (mungkin tak terbatas).
• Kita dapat mendefinisikan transisi diskrit antar negara.
• Kita dapat mengatur fungsi biaya yang memperkirakan kondisi sistem saat ini.

Di bawah ini saya akan memberikan beberapa contoh lain di mana, menurut pendapat saya, metode ini dapat diterapkan.

Implementasi

Kode palsu

Dalam implementasi kami, kami ingin mencapai yang berikut:

• Tetapkan status sistem.
• Atur semua transisi yang mungkin ke status berikutnya.
• Hitung biaya keadaan saat ini.
• Hitung biaya semua kemungkinan status berikutnya (atau sebagian dari mereka).
• Menggunakan distribusi Gibbs, hitung probabilitas transisi.
• Transisi sampel (sampel) menggunakan probabilitas.
• Lakukan transisi sampel.
• Mengurangi suhu komputasi.
• Ulangi langkah-langkah sampai Anda mendapatkan hasil yang memuaskan.

Dalam bentuk pseudo-code, algoritma MCMC adalah sebagai berikut:

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

Generasi bangunan 3D

Ruang dan Transisi Negara

Untuk menghasilkan bangunan dalam 3D, saya menghasilkan banyak kamar dengan volume yang ditentukan oleh kotak pembatas.

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

Jika saya menghasilkan n kamar, maka keadaan sistem adalah konfigurasi kotak pembatas dalam ruang 3D.

Perlu dicatat bahwa konfigurasi yang mungkin untuk volume ini tidak terbatas, tetapi tak terhitung jumlahnya (mereka dapat dicantumkan dalam jumlah waktu yang tak terbatas)!

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

Banyak kemungkinan transisi akan menjadi pergeseran kamar di salah satu dari enam arah ruang dengan satu langkah, termasuk tidak adanya transisi:

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

Catatan: penting bahwa kita menjaga sistem agar tetap dalam kondisi saat ini!

Fungsi biaya

Saya ingin volume dalam ruang 3D berperilaku seperti "magnet", yaitu:

• Jika volume mereka bersilangan, maka ini buruk.
• Jika permukaannya bersentuhan, maka ini bagus.
• Jika mereka tidak menyentuh sama sekali, maka ini buruk.
• Jika mereka menyentuh lantai, itu bagus.

Untuk dua kuboid dalam ruang 3D, kita dapat dengan mudah mendefinisikan kotak pembatas:

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

Menggunakan kotak pembatas volume, kita dapat menghitung satu vektor 3D yang memberi saya informasi tentang perpotongan dua volume.

Jika panjang paralelepiped di satu sisi lebih besar dari jumlah panjang dua volume di sepanjang sisi ini, maka dari sisi ini mereka tidak menyentuh. Jika mereka sama, maka permukaannya bersentuhan, dan jika kurang, maka volumenya bersilangan.

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

Kode ini digunakan untuk menghitung jumlah jumlah yang saya bentuk jumlah tertimbang, yang akhirnya digunakan sebagai biaya.

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

Catatan: “volume persimpangan positif” berarti bahwa volume sebenarnya bersinggungan. "Volume negatif dari persimpangan" berarti bahwa mereka tidak menyentuh sama sekali dan persimpangan ditentukan oleh volume di ruang yang terletak di antara dua titik terdekat dari dua kuboid di ruang 3D.

Bobot dipilih sedemikian rupa untuk memberikan prioritas pada satu hal dan mendenda yang lain. Sebagai contoh, di sini saya sangat merapikan kamar-kamar yang terletak di bawah lantai, dan juga meningkatkan prioritas mereka yang area permukaannya bersentuhan (lebih dari saya menghalau persimpangan volume).

Saya menghasilkan biaya untuk semua pasangan kamar, mengabaikan kamar yang dipasangkan dengan diri mereka sendiri.

Menemukan solusi biaya rendah

Konvergensi dilakukan seperti yang dijelaskan dalam pseudo-code. Saat melakukan transisi, saya hanya memindahkan satu kamar sekaligus. Ini berarti bahwa dengan n kamar dan 7 kemungkinan transisi, saya perlu menghitung 7 * n probabilitas, dan saya memilih dari semuanya, hanya memindahkan kamar itu, yang mungkin yang paling disukai.

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

Pengambilan sampel dilakukan oleh pembentukan fungsi distribusi kumulatif atas fungsi distribusi massa semua transisi yang mungkin; operasi ini disebut "inverse transform sampling".

Ini dicapai dengan menghasilkan jumlah kumulatif probabilitas transisi, yang memberi kita fungsi distribusi kumulatif (CDF). Untuk pengambilan sampel, kami menghasilkan variabel acak dengan distribusi seragam antara 0 dan 1. Karena elemen pertama CDF adalah nol dan yang terakhir, kami hanya perlu menemukan "di mana indeks array CDF adalah variabel sampel kami dengan distribusi seragam", dan ini akan menjadi indeks transisi sampel. Berikut ini ilustrasi:


Alih-alih fungsi kontinu, mungkin ada langkah-langkah tersendiri. Lebih detail bisa dibaca di sini .

Selain itu, saya memiliki data volume ruang dalam ruang 3D!

Saya menggunakannya untuk menghasilkan "skema" menggunakan kelas cetak biru, menerapkan tema ke data massal yang diketahui. Jadi rumah mendapatkan penampilan mereka. Kelas cetak biru dijelaskan dalam artikel sebelumnya [di sini ] ([ terjemahan ] tentang Habré). Untuk pembuatan rumah yang lengkap dari volume ini, lihat kode sumber.

Hasil

Hasil untuk metode umum semacam itu cukup baik. Satu-satunya hal yang harus saya tetapkan adalah prioritas dan bobot penalti yang benar dalam fungsi biaya.


Beberapa contoh pembuatan generasi menggunakan algoritme ini dan tema yang diterapkan padanya.


Tampak samping (bangunan lain).

Konvergensi itu sendiri sangat cepat, terutama untuk sejumlah kecil kamar (3-5), karena menghitung kotak pembatas dan memperkirakan fungsi biaya sangat sederhana.

Dalam versi saat ini, rumah tidak memiliki pintu dan jendela, tetapi ini lebih merupakan masalah menafsirkan data volume 3D, daripada tugas untuk algoritma MCMC.

Terkadang metode ini memberikan hasil yang buruk, karena ini adalah proses stokastik, jadi sebelum menempatkan bangunan di dunia, Anda perlu memeriksa kebenarannya, terutama jika fungsi biaya tidak terlalu dapat diandalkan. Saya menduga bahwa keburukan terutama terjadi pada beberapa langkah pertama ketika suhunya tinggi.

Biasanya cacat muncul sebagai ruangan atau ruangan yang terpisah dari bangunan. tergantung di udara (di panggung tinggi).

Ekstensi dan sistem lainnya

Jelas, teknik saya dengan volume 3D mudah ditransfer ke dunia 2D dengan hanya mengurangi dimensi tugas satu per satu.

Artinya, dapat digunakan untuk tugas-tugas seperti pembuatan prosedural ruang bawah tanah atau kamar dalam game 2D dengan tampilan atas - melampirkan kamar satu sama lain menggunakan fungsi biaya yang mirip dengan yang dijelaskan di atas.

Cara yang mungkin untuk membuat generasi lebih menarik adalah dengan pertama-tama menghasilkan grafik kamar, masing-masing memiliki tipe sendiri, dan kemudian menetapkan fungsi biaya yang merangsang koneksi kamar yang terhubung dalam grafik di sepanjang permukaan fisik.

Grafik itu sendiri dapat dihasilkan dengan menggunakan algoritma MCMC, di mana penciptaan dan penghancuran koneksi antar kamar akan dianggap sebagai transisi terpisah yang merangsang koneksi antara kamar-kamar jenis tertentu (kamar tidur lebih cenderung terhubung ke koridor dan lebih kecil kemungkinannya ke lingkungan, dll.).

Aplikasi lain yang mungkin:

• Generasi labirin; biaya ditetapkan tergantung pada tortuositas labirin, dan transisinya adalah penempatan / pemindahan dinding atau koridor.
• Jaringan jalan, pemasangan dan penghancuran koneksi antar node grafik berdasarkan jarak, medan atau faktor lain yang digunakan sebagai biaya.
• Mungkin banyak yang lain!

Catatan yang menarik: simulasi anil dan algoritma MCMC dapat digunakan untuk tugas-tugas seperti "masalah salesman keliling", masalah NP-hard yang terkenal. Status sistem adalah rute, transisi dapat beralih node rute, dan biaya dapat menjadi jarak total!

Aplikasi untuk Bot Tugas

Saya berharap bahwa berkat sistem ini, task bot akan dapat membuat pengetahuan mereka sendiri di masa depan sesuai dengan kebutuhan mereka.

Berikut adalah video tentang bagaimana bot membangun rumah yang dihasilkan oleh algoritma ini:


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