Geekly articles weekly

Runtuhnya fungsi gelombang: algoritma yang terinspirasi oleh mekanika kuantum

gambar

Algoritma Wave Function Collapse menghasilkan bitmap yang secara lokal mirip dengan bitmap input.

Kemiripan lokal berarti itu

  • (C1) Setiap pola piksel NxN dalam output harus muncul setidaknya sekali dalam input.
  • (Kondisi lemah C2) Distribusi pola NxN dalam input harus sama dengan distribusi pola NxN dalam sejumlah besar set output yang signifikan. Dengan kata lain, probabilitas pertemuan pola tertentu dalam output harus dekat dengan kepadatan pola tersebut dalam input.





Dalam contoh, nilai standar N adalah 3.


Algoritma WaveFunctionCollapse (WFC) menginisialisasi bitmap output sebagai keadaan yang sama sekali tidak dapat diobservasi di mana nilai setiap pixel adalah superposisi dari warna bitmap input (jadi jika gambar input berwarna hitam dan putih, maka status unobservable ditampilkan sebagai warna abu-abu yang berbeda). Koefisien dari superposisi ini adalah nyata, bukan bilangan imajiner, sehingga algoritme tidak menggunakan mekanika kuantum nyata, melainkan diilhami olehnya. Kemudian program masuk ke siklus observasi-propagasi:

  • Pada setiap tahap pengamatan, di antara ruang yang tidak teramati, wilayah NxN dengan entropi Shannon terendah dipilih. Keadaan wilayah ini kemudian runtuh ke keadaan kepastian sesuai dengan koefisien dan distribusi pola NxN dalam data input.
  • Pada setiap tahap distribusi, informasi baru yang diperoleh selama runtuhnya tahap sebelumnya disebarluaskan sesuai dengan output.

Pada setiap tahap, total entropi menurun, dan pada akhirnya kita mendapatkan kondisi yang dapat diamati sepenuhnya, keruntuhan fungsi gelombang berakhir.

Bisa terjadi bahwa selama proses propagasi semua koefisien untuk piksel tertentu menjadi sama dengan nol. Ini berarti bahwa algoritme telah mencapai kontradiksi dan tidak dapat dieksekusi lebih lanjut. Tugas menentukan apakah bitmap yang diberikan memberikan kondisi memuaskan bitmap nontrivial lainnya (C1) adalah NP-hard, sehingga tidak mungkin untuk membuat solusi cepat yang selalu melengkapi algoritma. Namun, dalam praktiknya, algoritma ini jarang sekali menemukan kontradiksi.

Algoritma runtuhnya fungsi gelombang diimplementasikan dalam C ++ , Python , Kotlin , Rust , Julia , Haxe , JavaScript dan diadaptasi untuk Unity . File yang dapat dieksekusi resmi dapat diunduh dari itch.io atau dijalankan di browser . WFC menghasilkan level di Bad North , Caves of Qud , beberapa gim kecil , dan juga banyak prototipe. Penciptaannya menyebabkan studi baru . Untuk pekerjaan terkait lainnya , penjelasan , demo interaktif , panduan , tutorial, dan contoh, lihat bagian port, fork, dan spin-off .

Tonton demonstrasi algoritma WFC di YouTube: https://youtu.be/DOQTr2Xmlz0

Algoritma


  1. Baca bitmap yang masuk dan hitung jumlah pola NxN.
    1. (opsional) Tambahan data pola dengan pola yang diputar dan dipantulkan.
  2. Buat array dengan ukuran data output (disebut "gelombang" di sumber). Setiap elemen dari array ini menunjukkan keadaan wilayah ukuran NxN dalam output. Keadaan wilayah NxN adalah superposisi pola NxN dari data input dengan koefisien Boolean (yaitu, keadaan piksel dalam output adalah superposisi warna yang masuk dengan koefisien nyata). Koefisien False berarti bahwa pola yang sesuai dilarang, koefisien benar berarti bahwa pola yang sesuai belum dilarang.
  3. Inisialisasi gelombang dalam keadaan yang sama sekali tidak dapat diobservasi, yaitu, di mana semua koefisien Boolean benar.
  4. Ulangi langkah-langkah berikut:
    1. Pengamatan:
      1. Temukan elemen gelombang dengan entropi bukan nol minimal. Jika tidak ada elemen seperti itu (jika semua elemen memiliki entropi nol atau tidak terbatas), maka selesaikan siklus (4) dan lanjutkan ke langkah (5).
      2. Perkecil elemen ini ke dalam tingkat kepastian sesuai dengan koefisiennya dan distribusi pola NxN dari data input.
    2. Penyebaran: menyebarluaskan informasi yang diperoleh pada langkah pengamatan sebelumnya.
  5. Pada titik ini, semua elemen gelombang memiliki keadaan yang dapat diamati sepenuhnya (semua koefisien, kecuali satu, sama dengan nol) atau berada dalam keadaan kontradiksi (semua koefisien sama dengan nol). Dalam kasus pertama, kembalikan hasilnya. Dalam kasus kedua, keluar tanpa mengembalikan apa pun.

Pembuatan Kartu Tile


Kasus non-sepele yang paling sederhana dari algoritma adalah pola NxN = 1x2 (lebih tepatnya, NxM). Jika kita lebih menyederhanakannya, menjaga bukan probabilitas pasangan warna, tetapi probabilitas warna itu sendiri, maka kita akan mendapatkan apa yang disebut "model ubin sederhana". Fase propagasi dalam model ini hanyalah penyebaran ketergantungan lingkungan. Lebih mudah menginisialisasi model ubin sederhana dengan daftar ubin dan data lingkungan mereka (data lingkungan dapat dianggap sebagai sejumlah besar sampel yang sangat kecil), daripada bitmap sampel.

GIF | GIFV

Daftar semua pasangan ubin yang mungkin ada di dalam ubin praktis bisa sangat panjang, jadi untuk mempersingkat penghitungan, saya menerapkan sistem simetri untuk ubin. Dalam sistem ini, setiap ubin harus diberi jenis simetri.


Perhatikan bahwa ubin memiliki simetri yang sama dengan huruf yang diberikan kepadanya (dengan kata lain, tindakan kelompok D4 dihedral adalah isometrik untuk ubin dan huruf yang sesuai). Berkat sistem ini, cukup untuk membuat daftar pasangan ubin tetangga hanya dengan simetri mereka, mempersingkat daftar tetangga untuk tileset dengan banyak ubin simetris beberapa kali (bahkan di ubin di medan Musim Panas, walaupun faktanya gambarnya tidak simetris, sistem menganggap ubin seperti itu simetris).









Perhatikan bahwa ubin yang tidak terbatas yang diatur dari node (di mana semua 5 ubin itu valid) tidak menarik untuk algoritma WFC, karena Anda tidak bisa masuk ke situasi di mana tidak mungkin untuk menempatkan ubin. Kami menyebut tileset dengan properti ini "sederhana". Tanpa heuristik yang kompleks, tileset sederhana tidak menciptakan struktur global yang menarik, karena korelasi dalam tileset sederhana pada jarak cepat berkurang. Banyak ubin sederhana dapat ditemukan di cr31 . Lihat di sana di tileset "Dual" dua sisi. Bagaimana dia bisa membuat node (tanpa koneksi berbentuk T, itu sulit), sementara pada saat yang sama menjadi sederhana? Jawabannya adalah ia hanya dapat menghasilkan jenis simpul yang sempit dan tidak dapat membuat simpul sembarang.

Juga patut dicatat bahwa Circuit, Summer, dan Rooms tilesets bukan ubin Van. Artinya, data lingkungan mereka tidak dapat dihasilkan dari pewarnaan tepi. Misalnya, dalam rangkaian ubin sirkuit (sirkuit terpadu), dua sudut tidak dapat berdekatan, meskipun mereka dapat dihubungkan dengan koneksi (Sambungan), dan trek diagonal tidak dapat mengubah arah.

Dimensi yang lebih tinggi


Algoritma WFC dalam dimensi yang lebih tinggi bekerja persis sama dengan dua dimensi, tetapi kinerja menjadi masalah di sini. Model voxel ini dihasilkan pada N = 2 dalam model ubin dengan tumpang tindih menggunakan blok 5x5x5 dan 5x5x2 dan heuristik tambahan (ketinggian, kepadatan, kelengkungan ...).


Tangkapan layar dimensi lebih tinggi: 1 , 2 , 3 .

Model Voxel yang dihasilkan menggunakan WFC dan algoritma lainnya akan berada dalam repositori terpisah.

Sintesis Terbatas


Algoritma WFC mendukung pembatasan. Oleh karena itu, dapat dengan mudah dikombinasikan dengan algoritma generatif lain atau pembuatan manual.

Inilah cara WFC secara otomatis menyelesaikan level yang diprakarsai orang:

GIF | GIFV

Algoritma ConvChain memenuhi versi kondisi ketat (C2): distribusi batas pola NxN dalam data output yang dibuatnya persis sama dengan distribusi pola dalam data input. Namun, ConvChain tidak memuaskan (C1): sering membuat artefak yang terlihat. Adalah logis untuk memulai ConvChain terlebih dahulu untuk mendapatkan konfigurasi sampel yang baik, dan kemudian WFC untuk memperbaiki artefak lokal. Ini mirip dengan strategi umum dalam optimasi: pertama kita jalankan metode Monte Carlo untuk menemukan titik. dekat dengan global optimal, dan kemudian lakukan gradient descent dari titik ini untuk akurasi yang lebih besar.

Algoritma sintesis tekstur P.F. Harrison jauh lebih cepat daripada WFC, tetapi memiliki masalah dengan korelasi yang panjang (misalnya, algoritma ini sulit untuk mensintesis tekstur dinding bata dengan batu bata yang dibuat dengan benar). Dalam kasus seperti itulah WFC menunjukkan keunggulannya, dan algoritma Harrison mendukung keterbatasan. Masuk akal untuk pertama-tama menghasilkan skema dinding bata yang ideal menggunakan WFC, dan kemudian melakukan algoritma sintesis tekstur terbatas untuk skema ini.

Komentar


Mengapa heuristik entropi minimum digunakan? Saya perhatikan bahwa ketika orang menggambar sesuatu, mereka sering mengikuti heuristik dari entropi minimal sendiri. Itu sebabnya algoritma ini sangat menarik untuk ditonton.

Model yang tumpang tindih sesuai dengan model sederhana dengan cara yang sama seperti rantai Markov orde tinggi sesuai dengan rantai Markov orde pertama.

Perlu dicatat bahwa entropi dari simpul apa pun tidak dapat meningkat pada tahap propagasi, mis. probabilitas tidak bertambah, tetapi dapat diatur ulang ke nol. Ketika tahap propagasi tidak dapat mengurangi entropi lebih lanjut, kami mengaktifkan tahap observasi. Jika tahap pengamatan tidak dapat mengurangi entropi, ini berarti bahwa algoritme telah selesai bekerja.

Fase propagasi dalam algoritma WFC sangat mirip dengan algoritma propagasi keyakinan loopy. Sebenarnya, saya awalnya memprogram propagasi kepercayaan (BP), tetapi kemudian saya beralih ke propagasi dengan kendala dengan distribusi stasioner yang tetap, karena BP jauh lebih lambat tanpa paralelisasi masif (dalam CPU) dan tidak menghasilkan hasil yang jauh lebih baik untuk tugas saya.

Perhatikan bahwa sampel "Simpul Sederhana" dan "Simpang Simpul" tidak memiliki 2, tetapi 3 warna.

Satu dimensi mungkin waktu. Secara khusus, WFC d-dimensi menampilkan perilaku dari setiap otomat seluler dimensi (d-1).

Referensi


Proyek ini didasarkan pada karya Paul Merrell pada sintesis model, khususnya, pada bab tentang sintesis model diskrit dari disertasinya . Paul menyebar keterbatasan lingkungan di apa yang kita sebut model ubin sederhana, dengan heuristik yang berupaya menghitung penyebaran di area bergerak kecil.

Proyek saya juga sangat dipengaruhi oleh bab tentang sintesis tekstur deklaratif dari disertasi Paul F. Harrison . Paul menetapkan data pada lingkungan ubin, menandai batas-batas mereka dan menggunakan pencarian kembali untuk mengisi peta ubin.

Majelis


WFC adalah aplikasi konsol yang hanya bergantung pada perpustakaan standar. Unduh .NET Core untuk Windows, Linux, atau macOS dan jalankan

 dotnet run WaveFunctionCollapse.csproj

Atau Anda dapat menggunakan instruksi pembangunan komunitas untuk platform berbeda dalam masalah terkait . Casey Marshall membuat permintaan tarik yang menyederhanakan penggunaan program baris perintah dan termasuk paket snap.

Port, garpu, dan spin-off yang menarik



Ucapan Terima Kasih


Beberapa contoh diambil dari game Ultima IV dan Dungeon Crawl . Lingkaran Tileset diambil dari Mario Klingemann . Gagasan menghasilkan sirkuit terintegrasi diusulkan oleh Moonasaur , dan gaya mereka diambil dari game Ruckingenur II oleh Zachtronics. Contoh tumpang tindih Cat diambil dari video Nyan Cat, contoh Qud dibuat oleh Brian Buckley , Kantor Ajaib + contoh Spiral adalah rid5x, Kota Berwarna + Tautan + Tautan 2 + Mazelike + Red Dot + Senyum overlay Kota contoh adalah Arvi Teikari. Musim Panas Tileset diciptakan oleh Hermann Hillmann. Model Voxel disajikan dalam MagicaVoxel .


Source: https://habr.com/ru/post/id437604/

More articles:


All Articles