Algoritma penempatan ubin berbasis kendala

Posting ini menjelaskan algoritma yang digunakan dalam Generate Worlds , alat yang memungkinkan pengguna untuk membuat dan menjelajahi dunia prosedural dengan membangun set kecil voxel tile. Saya akan memberikan deskripsi singkat tentang algoritma, dan dalam posting berikut saya akan berbicara tentang kelebihannya dalam kecepatan dan fleksibilitas dibandingkan dengan metode lain. Untuk mempelajari lebih lanjut tentang apa yang dimaksud dengan generasi prosedural berbasis kendala dan apa yang menarik, saya sarankan membaca posting saya sebelumnya .

Jika Anda ingin menguji kekuatan Anda dalam menciptakan dunia prosedural menggunakan sistem ini, Anda dapat membeli Generate Worlds. Jika harga terlalu tinggi untuk Anda, maka lanjutkan membaca: posting ini akan memberi Anda informasi tentang bagaimana menerapkan algoritma Generate Worlds secara mandiri.

Set ubin

Di Generate Worlds, setiap dunia dirakit dari satu set ubin (tileset). Pada dasarnya, ubin hanyalah model voxel kecil. Mari kita mulai dengan sebuah contoh. Gambar di bawah ini terdiri dari 9 ubin. Seperti yang Anda lihat, setiap ubin terdiri dari voxels yang muncul sebagai kubus berwarna.


Jika Anda mengatur model voxel ini dengan cara yang logis, Anda dapat membuat adegan pastoral yang indah, seperti pada animasi di bawah ini. Yang dimaksud dengan "logika" adalah ubin yang cocok jika warnanya di sepanjang tepi sambungan.


Tugas dari algoritma Generate Worlds adalah untuk dengan cepat dan otomatis menyelesaikan perakitan tersebut. Sebelum memulai algoritme, mari kita lihat pernyataan masalahnya.

Kami menghubungkan ubin di antara mereka sendiri

Lihatlah tileset yang berisi 4 ubin:


Ubin ini mirip dengan ubin tiga dimensi yang ditunjukkan di atas.

Algoritma Generate Worlds menciptakan kombinasi ubin yang valid menggunakan satu aturan sederhana: jika dua ubin menyentuh satu sama lain, semua warna di sepanjang tepi sentuhan harus cocok . Aturan ini meresmikan pendekatan yang digunakan oleh desainer hidup untuk membuat dunia 3D dari ubin voxel.

Dalam kombinasi yang diizinkan dari 4 ubin yang disajikan di atas, sel-sel cahaya di sepanjang perbatasan harus hanya menyentuh sel-sel cahaya, dan sel gelap harus hanya menyentuh sel-sel gelap. Sebagai contoh:


Contoh koneksi yang benar dan salah.

Contoh di sebelah kanan tidak dapat diterima, karena di sepanjang tepi ubin menyentuh, kotak cahaya menyentuh kotak gelap. Dua kombinasi valid yang dihasilkan untuk tileset ini ditunjukkan di bawah ini:


Dalam kasus umum, membuat kombinasi ubin yang valid bukanlah tugas yang sepele. Misalnya, pertimbangkan strategi "serakah" sederhana berikut ini: kita mulai dengan kisi kosong. Di setiap iterasi, kami menempatkan ubin di beberapa titik, memilih ubin yang dapat diterima dengan mempertimbangkan ubin yang sudah ditempatkan. Diagram di bawah ini menunjukkan masalah dari strategi semacam itu.


Jika kita akan menempatkan ubin tanpa melihat bagaimana penempatan akan memengaruhi pilihan masa depan, maka algoritma "serakah" dengan cepat terhenti; dalam diagram di atas, tidak ada ubin yang valid dapat ditempatkan di kotak merah. Dan ini adalah masalah utama: ubin yang diposkan sebelumnya dapat mengurangi jumlah opsi saat ini menjadi nol. Kita perlu beberapa cara untuk melindungi dari memasang ubin, yang dapat membawa kita ke jalan buntu. Algoritme yang diimplementasikan dalam Generate Worlds dimulai dengan mempertimbangkan semua petak mungkin untuk ditempatkan pada semua titik kisi. Jika kita menempatkan satu ubin di kotak, maka jelas bahwa beberapa opsi di masa depan menjadi tidak dapat diakses. Setelah algoritma menghilangkan opsi-opsi ini, kami dapat memeriksa kembali opsi yang tersisa dan menghilangkan ubin lain yang sekarang tidak kompatibel dengan jumlah ubin yang tersisa yang lebih kecil di titik-titik tetangga.

Perhatikan contoh berikut. Algoritme dimulai dengan kisi 3x3, di tengahnya terdapat petak tunggal. Lokasi ubin ini menyiratkan bahwa 9 ubin yang mungkin pada titik-titik grid tetangga tidak diperbolehkan, jadi ia membuangnya dan tidak lagi mempertimbangkannya. Setelah menghapus petak ini, ia dapat menghapus petak yang tidak kompatibel dengan semua petak yang dianggap sebagai kandidat untuk penempatan di titik kisi di sebelahnya. Kotak merah di diagram menandai titik di mana ubin dihapus, karena mereka tidak kompatibel dengan semua tetangga yang masih dipertimbangkan. Jika algoritma melanjutkan proses ini hingga ada ubin yang dapat dihapus, itu akan kembali ke keadaan yang ditunjukkan di sudut kiri bawah rangkaian. Seperti yang Anda lihat, banyak ubin dikeluarkan dari pertimbangan. Jika strategi menempatkan ubin hanya terdiri dari memilih ubin dari kelompok-kelompok yang tersisa ini, maka kemungkinan masuk ke jalan buntu akan jauh lebih rendah daripada dalam pendekatan "serakah" yang dijelaskan di atas.


Masalah dengan pendekatan ini adalah bahwa setiap kali ubin ditempatkan, itu membutuhkan proses berulang yang mahal. Tetapi perhatikan bahwa setiap kali saya menempatkan ubin dengan T terbalik, 19 ubin yang saya hapus dalam contoh di atas dapat dihapus dari pertimbangan di sekitar penempatan ini. Saya menyebut kumpulan ubin, yang tetap menjadi opsi yang valid di sekitar ubin yang dihosting, lingkungan ubin yang valid .

Penempatan ubin cepat berkat caching informasi

Prinsip terpenting dari algoritma Generate Worlds adalah bahwa informasi yang dikumpulkan tentang kemungkinan tetangga ubin dapat digunakan kembali setiap kali ubin ini ditempatkan. Misalnya, dalam kasus T terbalik untuk delapan kotak di sekitarnya, kita dapat menghapus 19 ubin segera setelah menempatkan ubin ini dengan melihat versi cache dari lingkungan yang diizinkan untuk ubin ini.

Misalnya, dalam contoh di bawah ini, algoritma mengisi kisi 5x5 dengan ubin menggunakan lingkungan yang diijinkan dalam cache dari 4 ubin. Setelah menempatkan ubin pertama, ia menghilangkan 19 ubin pertimbangan yang tidak mungkin dalam contoh di atas. Setelah menempatkan setiap ubin, semua opsi yang tidak ada di lingkungan yang dapat diterima dari ubin ditempatkan dihapus dari pertimbangan.


Melanjutkan dengan cara ini, kita dapat mengisi seluruh grid dengan hanya pembaruan lokal cepat ke set ubin, yang masih merupakan opsi yang valid untuk masing-masing poin.

Lingkungan yang diizinkan dapat ukuran apa pun yang Anda butuhkan, sehingga Anda dapat menghapus ubin yang tidak kompatibel dari jauh setiap kali Anda menempatkan ubin. Meskipun generasi lingkungan yang dapat diterima agak lambat, perlu dilakukan hanya sekali, setelah itu setiap waktu secara linear tergantung pada ukuran lingkungan untuk mengakomodasi setiap ubin.

Memperluas sistem dalam 3D

Algoritma Generate Worlds secara alami berkembang ke dunia yang memiliki dimensi ketiga. Alih-alih ubin 2D yang cocok dengan warna dengan 4 ubin tetangga di sepanjang wajah yang sama, kami sekarang memiliki ubin 3D yang harus cocok dengan warna di tetangga mereka di sepanjang 6 wajah. Pertimbangkan ubin 3D berikut:


Perakitan ubin ini dalam 3D adalah sebagai berikut:


Dalam hal ini, lingkungan yang dapat diterima bukan berupa jaringan dua dimensi, tetapi tiga dimensi, dan algoritme menghasilkannya dalam kasus 2D yang serupa.

Galeri Hasil

Di bawah ini adalah dunia yang dihasilkan oleh implementasi algoritma ini bersama dengan deskripsi singkat.


Cuplikan layar dari Generate Worlds menunjukkan kamar dengan pintu keluar. Tepian di langit-langit bertepatan dengan batas ubin.


Tangkapan layar dari alat lain yang saya buat yang juga menggunakan algoritma Generate Worlds; berbagai jenis kamar dan koridor ditampilkan.


Dunia yang mirip dengan yang sebelumnya, tetapi sekarang dalam tampilan isometrik yang indah


Dunia, ciptaan yang diilhami saya oleh lingkaran kesembilan Neraka Dante: para pendosa yang membeku di dalam es. Diberikan dalam MagicaVoxel.


Dunia, ciptaan yang diilhami saya oleh putaran kedua neraka Dante: bentang alam, yang diairi oleh hujan yang membakar, yang melintasi jembatan. Diberikan dalam MagicaVoxel.


Dunia platform berumput dengan air terjun dan sungai. Diberikan dalam MagicaVoxel.


Lansekap kota abad pertengahan dengan bangunan dan dinding. Diberikan dalam MagicaVoxel.