Apa itu generasi prosedural?

Generasi prosedural mencakup banyak algoritma generatif, prinsipnya bukan untuk membuat data secara manual, tetapi secara algoritmik: alih-alih secara manual membuat apa yang ingin kita buat (peta, musik, medan ...), sebuah algoritma ditulis yang dapat berhasil membuat berbagai contoh tanpa melakukan proses yang sama beberapa kali. Pendekatan ini sangat berguna dalam permainan video di mana seluruh peta atau level dapat dihasilkan secara acak (misalnya, peta di Minecraft, Terraria atau Factorio, atau skema level di sebagian besar roguelike).

Algoritma runtuhnya fungsi gelombang dan cakupannya

Pada artikel ini, kami menguji algoritma runtuhnya fungsi gelombang (WaveFunctionCollapse, WFC) yang diajukan oleh Maxim Gumin (Twitter-nya memiliki koleksi konten menakjubkan yang dibuat menggunakan algoritme ini oleh pengembang lain!) Untuk menghasilkan gambar atau medan secara prosedural dengan membuat gambar yang secara lokal mirip dengan yang masuk gambar dalam kotak ukuran tertentu.

Algoritma ini didasarkan pada ide penciptaan langkah-demi-langkah dari gambar yang sudah selesai dengan pelacakan yang ubin "sesuai" dengan gambar yang sudah sebagian dibangun. Untuk deskripsi terperinci dari algoritma, kami menyarankan Anda merujuk ke repositori WFC asli di Github dan bagian keempat artikel " WaveFunctionCollapse adalah Kendala Pemecahan di Alam Liar ".


Contoh gambar seed yang dihasilkan secara prosedural

Selain membuat gambar yang serupa, bidang lain penerapan algoritma WFC adalah pembuatan kartu ubin. Pembuatan peta ubin akan menjadi topik utama artikel ini, karena lebih mudah digunakan untuk menjelaskan ide-ide kami dengan jelas. Alih-alih gambar contoh, Anda hanya dapat menyimpan ubin dan pasangan ubin yang dapat dihubungkan satu sama lain secara bergantian. Dalam hal ini, algoritme dapat digunakan untuk membuat gambar yang mirip dengan yang ditunjukkan di bawah ini.


Contoh ubin yang dihasilkan secara acak

Tantangan dan solusi kami

Kami mengambil tugas menghasilkan kartu ubin berdasarkan permainan papan Carcassonne ("Carcassonne"), di mana bidang dihasilkan oleh para pemain "secara manual" (lihat animasi di bawah) dari ubin yang harus dikombinasikan satu sama lain.


Anehnya, secara konseptual, ini sangat mirip dengan algoritma WFC untuk membuat kartu ubin sewenang-wenang dengan menambahkan komponen baru ke solusi yang tidak lengkap. Dan karena WaveFunctionCollapse dapat digunakan sebagai generator kartu ubin, ia juga dapat menghasilkan bidang "Carcassonne"!

Namun, dalam permainan itu sendiri ada terlalu banyak ubin yang berbeda, dan mengkode semua rasio mereka adalah tugas yang terlalu berat untuk hackathon 24 jam. Karena itu, kami memutuskan untuk memainkan versi "Carcassonne" yang sangat sederhana tanpa kastil dan sungai, hanya dengan jalan, rumput, dan biara. Jadi kami mendapat 6 ubin yang mungkin dengan rotasi dan simetri mereka. Tetapi bahkan dalam kondisi seperti itu, hasilnya terlihat indah dan terlihat seperti permainan nyata di Carcassonne!


Visualisasi pengisian dalam algoritma bidang Carcassonne


Contoh aturan dimasukkan ke dalam algoritma

Gambar di atas berisi contoh aturan input yang ditambahkan ke algoritma. Namun, kita masih perlu mengontrol aspek-aspek tertentu dari penampilan lapangan. Haruskah algoritma menciptakan "jalan" dari jalan yang dipenuhi dengan biara-biara dan mirip dengan kota, atau haruskah lapangan paling banyak terdiri dari rumput dengan desa-desa yang tersebar di sekitarnya? Dalam algoritma asli, tidak ada cara untuk mengontrol kondisi seperti itu (seperti yang lain), tetapi untuk kemungkinan kontrol dimungkinkan untuk membuat perbaikan sederhana.

Bayesian a distribusi probabilitas apriori

Seperti disebutkan di atas, pada setiap langkah, algoritma menambahkan ubin baru ke bidang sehingga cocok dengan ubin yang sudah ditempatkan, tetapi kami tidak mengatakan apa yang akan terjadi jika beberapa ubin berbeda dapat ditempatkan di lokasi yang dipilih (kami juga tidak berbicara tentang bagaimana umumnya memilih tempat ini, tetapi dalam artikel kami tidak akan mempertimbangkannya!). Dalam algoritma asli, setiap ubin yang cocok dipilih secara acak secara seragam. Namun, dalam keputusan kami, kami dapat memilih ubin tertentu, misalnya, rumput, sehingga lebih sering terjadi di lapangan. Hal ini dapat diwujudkan dengan menciptakan distribusi "probabilitas sebelum" ubin yang tidak rata, di mana rumput memiliki peluang lebih besar untuk digunakan daripada jalan, jika kedua jenis ubin dapat digunakan. Ini mengingatkan pada teknik Bayesian. Dalam kasus disederhanakan memilih antara dua opsi, rumput dan jalan, kita dapat menambahkan rumput dengan probabilitas p> 0,5, dan tidak dengan 0,5 biasa, yang diperoleh dengan probabilitas seragam. Tugas ini dapat dengan mudah digeneralisasikan dengan menetapkan nilai prioritas untuk setiap ubin dan menggunakan nilai ini untuk menetapkan probabilitas sebagai nilai yang dibagi dengan jumlah nilai semua ubin yang mungkin. Gambar di bawah ini menunjukkan dua solusi yang cocok dengan nilai koefisien yang sangat berbeda, memberikan pemahaman tentang seberapa sensitif algoritma tersebut.


Solusi berbeda untuk distribusi probabilitas a priori awal yang berbeda

Contoh lain: probabilitas bersyarat dan pengelompokan

Anda dapat memperluas gagasan ini, dan untuk mengilustrasikannya, kami akan menghasilkan, alih-alih bidang Carcassonne, peta dua dimensi bijih Minecraft. Berbagai jenis bijih di Minecraft biasanya ditemukan dalam formasi besar, jadi seiring dengan menetapkan probabilitas setiap bijih, kami akan membuat probabilitas bergantung pada tetangga yang telah ditempatkan di peta. Meskipun tidak ada yang “dilarang” dalam pengaturan besi dekat batubara, batubara lain diberikan prioritas lebih tinggi di samping batubara yang sudah ditempatkan.

Meskipun ini tidak diperhitungkan dalam gambar di bawah ini, dalam permainan probabilitasnya juga tergantung pada ketinggian ubin, sehingga posisi dalam gambar juga dapat memengaruhi kondisi distribusi probabilitas ubin.


Contoh Peta Minecraft Ore Tile Dibuat oleh WFC

Kesimpulan

Generasi prosedural adalah alat yang ampuh yang layak dimiliki dalam persediaan. Secara khusus, WFC secara aktif digunakan dalam generasi dunia, dan perlu mempertimbangkan kemungkinan bahwa distribusi ubin baru mungkin tidak merata dan dapat dipengaruhi oleh faktor-faktor lain, misalnya, tetangga sudah ditempatkan di peta, ubin baru dan posisi pada gambar. Kami telah membuat aplikasi yang sangat sederhana, tetapi kemungkinan untuk pengembangannya hampir tidak terbatas!