Kami berurusan dengan algoritma runtuhnya fungsi gelombang

Sejak kedatangan DeBroglie dan Tessera, saya telah diminta berkali-kali untuk menjelaskan cara kerjanya. Menghasilkan mungkin terlihat seperti sihir, tetapi aturan di baliknya sebenarnya sederhana.

Jadi apa algoritma Wave Function Collapse (WFC)? Ini dikembangkan oleh Maxim Gumin untuk membuat gambar "ubin" berdasarkan konfigurasi sederhana atau sampel gambar. Algoritme dapat melakukan banyak hal: lihat contoh yang diberikan oleh Maxim dan Twitter #wavefunctioncollapse , tonton video ini . Varietasnya luar biasa.


Maxim dalam README secara singkat menjelaskan pekerjaan WFC, tetapi bagi saya tampaknya masalah ini membutuhkan pengungkapan yang lebih rinci, dari dasar-dasarnya. Karena algoritme tersebut terkait dengan pemrograman kendala , sebagian besar artikel dikhususkan untuk menjelaskan konsep pemrograman kendala, dan pada akhirnya kami akan kembali ke WFC .

Pemrograman terbatas adalah cara menginstruksikan komputer. Tidak seperti pemrograman imperatif, ketika Anda menentukan daftar fungsi eksplisit, atau pemrograman fungsional, ketika Anda menentukan fungsi matematika, di sini Anda memberikan komputer dengan deskripsi masalah yang ketat, dan menggunakan algoritma bawaan untuk menemukan solusi.

catatan:Panduan ini menjelaskan berbagai konsep, bukan metode dan kode. Jika Anda lebih tertarik pada implementasinya, maka Anda dapat menggunakan perpustakaan opensource WFC saya ( github , dokumentasi ). Meskipun lebih baik untuk memulai studi dengan implementasi Maxim . Jika Anda menggunakan Unity, Anda dapat membeli Tessera , ini adalah alat saya untuk menerapkan WFC di mesin ini.

Mini sudoku

Sebagai tugas ilustrasi, saya mengambil Sudoku mini . Ini adalah teka-teki yang terlihat seperti kotak 4 × 4 dengan angka di beberapa sel.


Tujuannya adalah untuk mengisi setiap sel kosong dengan angka dari 1 hingga 4 sesuai dengan aturan:

• Setiap angka dari 1 hingga 4 harus ada di setiap baris dalam satu salinan.
• Setiap angka dari 1 hingga 4 harus ada di setiap kolom dalam satu salinan.
• Setiap angka dari 1 hingga 4 harus ada di setiap sudut sudut 2 × 2 dalam satu salinan.

Menurut aturan ini, solusinya adalah sebagai berikut:


Anda mungkin dengan mudah memecahkan teka-teki ini. Tetapi kami tertarik pada bagaimana komputer dapat melakukan ini. Masalahnya dapat dibagi menjadi dua bagian: deskripsi kondisi untuk komputer, dan kemudian solusi menggunakan algoritma.

Deskripsi kondisi

Biasanya, bahasa pemrograman dalam batasan digunakan untuk ini. Ada beberapa bahasa seperti itu, dan prinsip aksi mereka serupa.

Pertama kita mendefinisikan variabel . Di sini mereka tidak sama dengan pemrograman konvensional. Dalam konteks pemecah masalah, variabel adalah nilai yang tidak diketahui yang harus dipecahkan untuk menyelesaikan masalah. Dalam contoh Sudoku kami, kami akan membuat variabel untuk semua sel kosong. Untuk kenyamanan, Anda juga dapat membuat variabel untuk sel yang diisi.

Kemudian untuk setiap variabel, kami mendefinisikan domain : satu set nilai yang mungkin. Di sudoku kami, untuk setiap sel kosong, domain akan menjadi {1, 2, 3, 4}. Dan untuk sel di mana 1 sudah dimasukkan, domain akan menjadi {1}.

Akhirnya, kami mengatur kendala: aturan mengikat variabel kami. Di sebagian besar bahasa pemrograman, sudah ada fungsi dengan batasan all_distinct(..)yang harus melewati nilai unik. Jadi aturan Sudoku dapat diterjemahkan ke dalam 12 batasan all_distinct- satu untuk setiap baris dan kolom, serta untuk kotak sudut 2 × 2. Kami hanya membutuhkan satu jenis kendala untuk menyelesaikan masalah ini, namun, pemecah masalah untuk memenuhi kendala biasanya datang dengan perpustakaan besar berbagai jenis kendala untuk menggambarkan masalah Anda.

Catatan : dalam praktiknya, bahasa pemrograman mendukung array dalam batasan, jadi ada cara yang lebih akurat untuk merumuskan tugas ini. Ada banyak artikel di internet tentang pemecahan sudoku.

Algoritma untuk memecahkan masalah kepuasan kendala

Ada beberapa teknik solusi yang berbeda. Tetapi saya akan mempertimbangkan yang paling sederhana dari mereka untuk menunjukkan kepada Anda prinsip kerja mereka. Domain untuk setiap sel ditampilkan di sini:


Ini semua adalah nilai yang mungkin dalam domain variabel.

Sekarang ambil batasan pertama. Semua nilai di baris atas harus unik. Dalam satu sel, nilai 4 sudah tertulis, oleh karena itu, di sel lain dari seri nilai ini tidak bisa . Kami menghapusnya dari domain sel-sel ini.


Ulangi proses ini dengan 12 batasan. Ini disebut propagasi pembatasan , karena informasi didistribusikan dari variabel ke variabel lain melalui pembatasan.


Dan lihat, kami memiliki variabel, di domain yang ada satu nilai yang tersisa. Ini harus menjadi solusi yang tepat untuk variabel-variabel ini.


Tampaknya kita bisa mendapatkan lebih banyak manfaat dari distribusi pembatasan: unit merah baru menunjukkan bahwa kita akan memiliki lebih banyak variabel dengan satu domain, dan ini juga akan berkontribusi pada distribusi. Ulangi prosedur ini hingga puzzle terpecahkan.

Kami menyulitkan tugas

Sayangnya, tidak semua teka-teki logika dapat diselesaikan dengan cepat. Ini adalah sudoku besar, kerjanya dengan cara yang sama, kecuali sekarang kita memiliki 9 nilai berbeda, 9 baris, 9 kolom, dan 9 kotak 3 × 3.


Jika kami mencoba menerapkan teknik di atas, maka kami akan mandek:


Sekarang semua pembatasan adalah umum, tetapi masih ada variabel yang tidak ditentukan.

Seseorang akan memutuskan ini, tetapi algoritma komputer tidak akan bisa. Manual untuk orang mengatakan bahwa sekarang kita perlu mencari kesimpulan logis yang semakin rumit. Tetapi kita tidak memerlukan algoritma komputer untuk melakukan ini, karena rumit, tetapi kita membutuhkan algoritma universal yang dapat bekerja dengan seperangkat batasan apa pun, dan tidak hanya sesuai dengan aturan sudoku.

Karena itu, komputer melakukan hal yang paling bodoh: mereka berasumsi . Pertama, kami merekam keadaan puzzle saat ini. Kemudian kami memilih variabel arbitrer dan mengaturnya ke salah satu nilai yang mungkin. Katakanlah kita menetapkan nilai 1 ke sel pusat.

Sekarang kita dapat menyebarkan pembatasan lebih sedikit. Inilah yang saya dapatkan untuk kolom tengah:


Nilai biru adalah kesimpulan yang kami buat setelah asumsi. Seperti yang Anda lihat, sesuatu terjadi. Kami meletakkan beberapa variabel lagi, tetapi lihat sel tengah atas. Kosong: di domainnya tidak ada nilai yang mungkin memenuhi batasan (tidak boleh ada 5, karena nilai ini sudah ada di kotak 3 × 3 yang sama, dan semua angka lainnya sudah ada di kolom ini).

Jika kami mendapatkan variabel dengan domain kosong, ini berarti bahwa kami tidak dapat menetapkan nilai apa pun. Artinya, teka-teki tidak dapat dipecahkan. Ternyata anggapan kami salah .

Menghadapi kontradiksi seperti itu, kami melakukan proses pencarian kembali(mundur). Pertama, kita mengembalikan keadaan sebelum asumsi kita. Lalu kami menghapus dari domain nilai yang kami gunakan sebagai asumsi - itu tidak bisa lagi menjadi jawaban yang benar.


Banyak pekerjaan telah dilakukan, tetapi mereka telah bergerak maju. Namun, bahkan setelah dikeluarkannya 1 dari sel pusat, kita masih berada di pusat kematian. Sudah waktunya untuk membuat asumsi lagi, dan lagi, dan lagi.

Tidak banyak tindakan algoritmik di sini. Setiap kali kami tidak dapat mendistribusikan batasan, kami membuat asumsi dan melanjutkan. Dan karena Anda dapat terjebak beberapa kali sebelum menghadapi kontradiksi, maka Anda akan mengakumulasikan beberapa negara dan asumsi yang tersimpan.

Dengan setiap iterasi dengan pengembalian, Anda mengurangi domain dengan setidaknya satu variabel, sehingga, meskipun banyak kemunduran, algoritma pada akhirnya akan menyelesaikan pekerjaan.

Topik ini jauh lebih luas dari yang saya jelaskan. Dalam praktiknya, optimisasi seperti pilihan asumsi, pemahaman kapan didistribusikan, dan kapan membuat kesimpulan logis yang lebih kompleks dapat berdampak besar pada pelaksanaan program. Dan karena masalah dengan kendala, sebagai suatu peraturan, tumbuh secara eksponensial, Anda bisa mendapatkan jawaban besok, atau setelah 5.000 tahun.

Kami kembali ke keruntuhan fungsi gelombang

Runtuhnya fungsi gelombang adalah tugas yang rumit dengan batasan: ada ribuan solusi yang mungkin. Jika kita membuat asumsi secara acak, maka alih-alih solver, kita mendapatkan generator . Pada saat yang sama, masih akan mematuhi semua pembatasan yang diberikan, yaitu, itu akan jauh lebih mudah dikelola daripada kebanyakan generator prosedural lainnya.

Tugas algoritma WFC adalah untuk mengisi sel dengan ubin sehingga gambar di ubin dikombinasikan satu sama lain. Dalam terminologi yang digunakan di atas, setiap ubin adalah nilai, setiap sel adalah variabel, dan aturan untuk menempatkan ubin adalah kendala.

Maxim, penulis WFC, menemukan bahwa dengan pilihan ubin yang masuk akal dan pengacakan yang tepat, Anda jarang harus menggunakan backtracking, sehingga prosedur ini tidak dapat diimplementasikan. Dengan demikian, esensi WFC adalah sebagai berikut:

• Array boolean dibuat untuk setiap sel, yang mewakili domain dari variabel ini. Domain berisi satu catatan per ubin, dan semuanya diinisialisasi dengan nilai true. Ubin memasuki domain jika nilainya sama true.
• Pada saat yang sama, ada sel di mana domain berisi beberapa elemen:
  
  • Pemilihan sel acak menggunakan metode heuristik "entropi terkecil".
  • Pilih ubin acak dari domain sel dan hapus semua ubin lain dari sana.
  • Memperbarui domain sel lain berdasarkan informasi baru ini adalah penyebaran pembatasan sel. Ini harus dilakukan berulang kali, karena perubahan dalam sel dapat memiliki konsekuensi lebih lanjut.

Catatan : ketentuan saya berbeda dengan ketentuan Maxim. Dia menyebut array domain gelombang, dan memilih ubin acak adalah pengamatan. Artinya, analogi digambar dengan mekanika kuantum. Tetapi perbandingan itu dangkal, jadi kita akan mengabaikannya.

Ada banyak tambahan pada prinsip-prinsip di atas yang menambah rahmat dan kinerja algoritma. Tapi pertama mari kita lihat langkah-langkah yang dijelaskan.

Contoh

Katakanlah kita perlu mengisi kotak 3 dengan 3 dengan empat jenis ubin:


Batasannya adalah: warna ubin yang berdekatan harus cocok satu sama lain.

Seperti pada contoh Sudoku, saya akan menggambarkan konten domain dengan gambar monokrom. Ketika hanya ada satu elemen yang tersisa di domain, saya akan meningkatkan ukurannya dan menunjukkannya dalam warna.

Pertama, di setiap sel, ubin jenis apa pun dapat ditemukan:


Jalankan loop WFC utama. Pilih sel secara acak, misalnya, kiri atas. Sekarang pilih ubin di domain dan hapus yang lainnya.


Bagikan batasannya. Satu-satunya aturan berlaku untuk ubin yang berdekatan, jadi kami perlu memperbarui dua sel:


Bisakah kita memperbarui ubin lain mengingat domain menyusut? Iya! Meskipun kami tidak yakin tentang pilihan ubin pertama, kami melihat bahwa opsi yang tersisa mengarah ke kanan. Artinya, beberapa jenis ubin tidak bisa diletakkan di sudut kanan atas. Hal yang sama dengan sudut kiri bawah.


Kami tidak lagi dapat mendistribusikan batasan, jadi kami mengulangi siklus utama: pemilihan sel, pemilihan ubin dan distribusi. Kali ini kami mengambil sel tengah atas:


Siklus lain: ambil sel tengah kiri. Setelah proliferasi pembatasan untuk sel pusat, satu nilai yang mungkin tetap.


Secara umum, Anda memahami ide itu. Anda dapat mengisi sisa sel sendiri.

Jika Anda ingin bereksperimen dengan contoh interaktif yang lebih kompleks , saya sarankan yang ini .

Entropi terkecil

Saat memilih sel berikutnya untuk diisi, beberapa opsi akan lebih disukai. Jika Anda memilih secara acak dari mana saja di dalam kisi, sebuah situasi dapat muncul ketika pada saat yang sama Anda akan memiliki area kisi yang berbeda. Ini dapat menyebabkan masalah: tergantung pada ubin yang tersedia, area yang diisi tidak dapat digabungkan. Jadi lebih baik memilih sel yang cenderung menyebabkan masalah seperti itu di masa depan. Dengan kata lain, Anda perlu mengambil sel dengan jumlah nilai yang paling sedikit dalam domain (tetapi tidak kurang dari dua nilai):

1. Kemungkinan besar, mereka akan berada di sebelah sel-sel yang sudah terisi.
2. Jika kita meninggalkan mereka untuk masa depan, maka kesulitan mungkin timbul, karena nilai yang tersedia sudah sedikit.

Pendekatan domain terkecil bekerja dengan baik jika semua ubin sama kemungkinannya. Tetapi jika Anda memilih dari distribusi acak tertimbang , maka Anda perlu mempertimbangkan hal lain. Maxima merekomendasikan "entropi minimal", yaitu, pilih sel yang meminimalkan:

$$

$$entropy = — \sum p_{i}log(p_{i})$$

Ini adalah penjumlahan ubin di domain tempat $$$p_{i}$- probabilitas untuk ubin ini.

Komputasi yang efisien

Meskipun saya tidak ingin membahas secara rinci, ada dua optimisasi yang memungkinkan saya meningkatkan kecepatan sehingga tidak dapat diabaikan.

Karena satu-satunya aturan kami terkait dengan ubin yang berdekatan, kami hanya dapat memeriksa batasan yang dapat memberikan hasil yang berbeda dari yang sebelumnya. Artinya, saat memperbarui sel, kami menambahkannya ke antrian sel yang menunggu keputusan. Lalu kami menghapus satu sel dari antrian, setiap kali memeriksa sel yang berdekatan. Jika pemeriksaan tersebut menyebabkan pembaruan sel lain, mereka juga masuk ke dalam antrian. Mengulangi prosedur ini sampai antrian kosong, kami memastikan bahwa kami memeriksa semua batasan. Tetapi kami tidak memeriksanya sampai domain dari setidaknya satu sel yang terkait dengan pembatasan ini berubah.

Lebih lanjut, untuk memeriksa batasan adjacency, kita perlu menjawab pertanyaan: "Mengingat ubin di domain sel A, ubin apa yang mungkin dalam domain sel B jika sel berdekatan?"

Terkadang pertanyaan ini disebut "dukungan" sel A. Untuk ubin yang diberikan "b" di domain B, mudah untuk menghitung siklus ubin di domain A. Jika A memiliki setidaknya satu ubin yang dapat ditempatkan di sebelah "b", maka "b" masih cocok, setidaknya untuk pasangan ubin yang dimaksud. Jika dalam A tidak ada ubin seperti itu, maka Anda tidak dapat menempatkan ubin "b" dari domain B, dan kami dapat membuangnya.

Loop membuatnya mudah untuk menerapkan ini dalam kode, tetapi akan bekerja sangat lambat. Dan jika kita menyimpan informasi dalam struktur data tambahan, kita dapat dengan cepat menjawab pertanyaan seperlunya. Data baru adalah array besar dengan entri untuk setiap sisi setiap sel dan setiap ubin. Dalam contoh kami, ada 9 sel, masing-masing dengan 4 sisi, dan 4 jenis ubin. Jadi kita membutuhkan 9 * 4 * 4 catatan. Kami akan menyimpan penghitung dukungan dalam array: untuk setiap sel / ubin / sisi, kami menghitung jumlah ubin di domain sel yang berdekatan yang dapat ditempatkan di sebelah ubin yang dimaksud. Jika penghitung turun ke nol, maka ubin ini tidak dapat diletakkan, karena tidak ada yang bisa berdekatan dengannya.

Ekstensi Algoritma

Karena WFC didasarkan pada pemahaman yang lebih umum tentang masalah yang dibatasi, ada banyak cara untuk memperluas algoritma dengan mengubah kendala yang digunakan.

Salah satu perubahan yang jelas adalah bahwa tidak ada yang memaksa kita untuk menggunakan sel kuadrat. WFC bekerja sangat baik pada sel heksagonal, dalam tiga dimensi atau bahkan permukaan yang lebih tidak biasa .




Anda dapat memperkenalkan batasan tambahan: memperbaiki ubin tertentu, atau membuat "modul" dari beberapa sel.

Pengenalan pembatasan tambahan dapat memainkan peran yang sangat penting dari sudut pandang praktis. Karena WFC hanya membatasi ubin yang berdekatan, jarang menghasilkan struktur besar yang memberikan tingkat homogenitas tinggi dan terlihat tidak biasa. Algoritma ini bekerja paling baik ketika memilih ubin, tetapi untuk bekerja dengan beberapa struktur besar, lebih baik menggunakan teknik yang berbeda atau memperkenalkan batasan lain.

Dalam artikel lain, saya berbicara tentang bagaimana Anda dapat mencapai hasil terbaik dari WFC.

Tumpukan WFC

Salah satu ekstensi menarik untuk algoritma adalah WFC "tumpang tindih". Dalam contoh di atas, batasan utama terkait dengan pasangan ubin yang berdekatan. Ini cukup untuk memastikan koneksi garis dan membuat struktur sederhana seperti gua, kamar, dll. Tetapi pada saat yang sama banyak informasi yang hilang. Jika kita perlu, katakanlah, bahwa ubin merah selalu terletak di sebelah biru, tetapi tidak pernah bersebelahan dengan mereka, maka akan sulit untuk mengungkapkan dalam hal kedekatan saja.

Maxim mengusulkan konsep tumpang tindih WFC: kami mengganti kendala kedekatan dengan kendala baru yang memengaruhi beberapa ubin sekaligus. Sebagai contoh, sehingga pada output setiap grup 3 × 3 sel sesuai dengan grup 3 × 3 dari sampel grid. Pola-pola yang ada dalam sampel akan diulang-ulang dalam variasi yang berbeda pada output:


Pembatasan ini jauh lebih sensitif daripada pembatasan kedekatan "sederhana". Dan karena itu tergantung pada sampel yang diberikan, sangat cocok untuk menyelesaikan beberapa jenis tugas artistik. Sejauh ini, saya belum menemukan sesuatu yang menarik. Mungkin alasannya adalah bahwa algoritma seperti itu lebih sulit untuk diterapkan, atau bekerja lebih lambat, atau kadang-kadang mereproduksi sampel asli dengan baik, yang menyebabkan beberapa jenis kealamian dan kealamian menjadi hilang.

Apa berikutnya?

Memecahkan masalah dengan pembatasan adalah bidang ilmu komputer yang besar dan aktif berkembang, dan saya hanya menyentuhnya. WFC - sama seperti algoritma generasi prosedural lainnya untuk menyelesaikan masalah yang terbatas - masih baru. Saya sarankan membaca r / proseduralgeneration , #wavefunctioncollapse , @exutumno dan @osksta untuk mendapatkan gambaran tentang kasus penggunaan baru-baru ini.

Anda juga dapat membaca artikel saya tentang WFC , bereksperimen dengan perpustakaan opensource saya atau alat Unity . Jangan lupa tentang artikel saya yang lain tentang pembuatan prosedural .