Minggu ini saya mulai mengerjakan topik baru: generasi ruang bawah tanah dan gua. Saya menggunakan partisi ruang untuk menghasilkan kamar, algoritma generasi labirin untuk menghasilkan koridor, dan automata seluler untuk memberikan gua tampilan yang lebih alami.

Memisahkan ruang

Ada banyak cara untuk menghasilkan ruang bawah tanah ( penempatan acak , generasi berbasis agen , menggunakan perilaku kemudi terpisah atau mesin fisik , dll.). Tetapi metode favorit saya adalah dengan membagi ruang, karena mudah dikontrol dan diperluas.

Ada juga banyak cara membagi ruang: pembagian ke dalam kisi-kisi, pembagian biner ruang, membagi ruang dengan pohon kuadran, diagram Voronoi, dll. Saya memutuskan untuk menggunakan partisi ruang biner, karena sangat cocok untuk menghasilkan ruang persegi panjang. Metode ini telah mendapatkan popularitas berkat sebuah artikel di RogueBasin.

Satu-satunya kompleksitas dari algoritma ini adalah pilihan posisi pemisahan. Jika kita tidak memaksakan batasan pada posisi pemisahan, kita akan mendapatkan partisi ruang yang aneh:


Ada beberapa cara untuk menghindari perilaku ini. Salah satunya adalah membatasi posisi pemisahan menjadi dua aspek rasio, misalnya, dalam kisaran dari 30% hingga 70% atau dari 40% hingga 60%. Cara lain adalah dengan menggunakan distribusi normal atau binomial daripada seragam, sehingga meningkatkan kemungkinan pemisahan di tengah sisi, dan bukan di tepi. Metode-metode ini memperbaiki masalah, tetapi sulit untuk memahami bagaimana tepatnya parameter mempengaruhi hasil akhir.

Oleh karena itu, saya menggunakan metode lain, yang keuntungannya adalah memiliki satu parameter dan mudah dipahami: rasio maksimum yang diijinkan antara panjang dan lebar sel. Saat mengambil sampel divisi baru, pertama-tama saya menghitung nilai minimum dan maksimum yang dapat dimiliki sehingga rasio untuk dua sel baru kurang dari batas, dan kemudian saya melakukan pengambilan sampel yang seragam antara dua batas ini. Inilah hasilnya ketika memvariasikan rasio maksimum yang diijinkan:


Hasil yang baik diperoleh dengan rasio maksimum 2,0 hingga 3,0:

Kamar Generasi

Tahap berikutnya adalah generasi di setiap sel ruangan. Tidak ada masalah khusus di sini, saya hanya menetapkan batas agar kamarnya tidak terlalu kecil dan tidak terlalu dekat dengan dinding sel.

Inilah hasilnya:

Pilihan tulang rusuk

Dalam generator pembagi ruang bawah tanah biner, pohon biner yang digunakan dalam langkah pembagi biasanya digunakan kembali untuk menghasilkan koridor. Saya tidak melakukan ini, karena pendekatan seperti itu tampaknya membatasi saya.

Alih-alih, pada tahap membagi ruang, saya membangun struktur daftar ujung yang saling terhubung , yang memungkinkan kita untuk mengetahui sel mana yang terletak bersebelahan. Dengan cara ini saya mendapatkan grafik berikut:


Ada tiga keuntungan dari pendekatan ini. Pertama: jika di masa depan saya ingin mengubah cara membagi ruang, sisa generator akan tetap valid, karena hanya menerima struktur data semi-edge pada input. Kedua: sekarang untuk memilih tepi yang akan menjadi koridor, saya dapat menggunakan algoritma apa pun untuk menghasilkan labirin . Ketiga: jika saya ingin menambahkan loop ke penjara bawah tanah, saya dapat dengan mudah menerapkan ini.

Untuk saat ini, saya hanya menggunakan algoritma Kruskal dan jarak blok kota untuk memilih tepi. Inilah hasilnya:

Generasi Koridor

Langkah selanjutnya adalah membuat koridor dari tepi yang dipilih. Ini mungkin bagian yang paling sulit dari generator, karena saya harus berhati-hati agar tidak ada koridor yang bersilangan dengan yang lain.

Inilah hasilnya:

Generasi Gua

Hasil sebelumnya cocok untuk membuat ruang bawah tanah, ruang bawah tanah dan struktur buatan manusia lainnya, tetapi saya ingin memberikan tampilan yang lebih alami pada gua dan tambang. Cara klasik untuk menghasilkan gua adalah dengan menggunakan otomat seluler, seperti yang dijelaskan dalam artikel RogueBasin ini . Masalah besar dengan automata seluler adalah hasilnya tidak sepenuhnya terkontrol.

Lagi pula, saya memutuskan untuk menggunakan automata seluler untuk membuat tampilan alami, tetapi untuk memaksakan pembatasan pada mereka untuk mendapatkan hasil yang terkendali. Alih-alih hanya dua negara: mati dan hidup, saya menggunakan empat: benar-benar mati, mati, hidup, pasti hidup. Status “Sangat akurat” tidak dapat berubah dalam proses, mereka digunakan untuk membatasi hasil.

Kamar-kamar dan koridor-koridor yang dihasilkan pada langkah-langkah sebelumnya dipenuhi dengan sel-sel "yang benar-benar hidup". Artinya, kami masih memiliki kamar pendukung dan kami menjamin bahwa mereka akan terhubung satu sama lain. Tepi yang belum dipilih diisi dengan sel "benar-benar mati" sehingga tidak ada jalur baru muncul di antara kamar. Akhirnya, di sekitar kamar dan koridor, kami secara acak membuat beberapa sel hidup. Ini adalah konfigurasi awal:


Kemudian kita mulai otomat seluler:



Berikut adalah beberapa hasil sampel lainnya:


Nanti saya akan menambahkan isian untuk menghapus bagian yang tidak terjangkau.

Ini adalah langkah pertama dalam perjalanan panjang untuk membuat generator penjara bawah tanah yang menarik. Saya senang dengan hasilnya. Saya terutama bangga dengan metode automata seluler terkendala dalam menciptakan gua yang terkontrol dan alami. Saya juga menyukai kenyataan bahwa setiap tahap generasi terpisah dari yang lain dan dapat dimodifikasi secara individual.

Hapus sel yang terisolasi

Lalu saya menerapkan isian untuk menghapus sel yang tidak dapat diakses:

Beberapa koridor antar kamar

Bereksperimen dengan parameter generator, saya menemukan bahwa jika Anda menambahkan sedikit suara di antara kamar penghubung, Anda mendapatkan hasil yang menarik.

Berikut adalah perbedaan dalam hasil sebelum menerapkan kebisingan ke kamar penghubung dan segera setelah itu, parameter berubah hanya dengan satu unit:



Jika Anda membuat kamar sedikit lebih besar, hasilnya akan lebih menarik:


Sangat menyenangkan bahwa kita mengalami kecelakaan dan struktur yang indah muncul, tetapi pada saat yang sama, struktur grafik dan peruntukan kamar dipertahankan, yang akan berguna:

Generasi Ubin untuk Gua

Saya menghabiskan sebagian besar waktu saya menghasilkan ubin. Ini tidak terlalu sulit, tetapi untuk implementasi yang benar dibutuhkan sedikit trik.

Berikut adalah contoh hasil:


Hal yang hebat adalah Anda dapat dengan mudah beralih dari gua batu ke pasir atau es:


Langkah selanjutnya dalam menghasilkan ruang bawah tanah adalah penambahan pemandangan dan monster.