Generasi prosedural ruang bawah tanah 3D bertingkat

Baru-baru ini, saya bermain beberapa roguelike, jadi saya memutuskan untuk mencoba menulis generator ruang bawah tanah prosedural saya sendiri. Ada banyak cara untuk mengatasi masalah ini, dan saya memilih algoritma dari penulis TinyKeep yang dijelaskan di sini . Saya telah mengembangkan algoritme ini sehingga berfungsi dalam 3D dan dapat membuat ruang bawah tanah bertingkat.

Kode contoh diposting di repositori Github . Untuk demonstrasi, saya menggunakan Unity3D, tetapi konsep-konsep ini, tentu saja, berlaku untuk mesin lain.

Dua dimensi

Pertama, saya perlu menulis algoritma untuk dua dimensi. Secara umum, ini bekerja sama dengan algoritma TinyKeep, tetapi memiliki perbedaan untuk membuat level yang lebih menarik.

Adegan untuk contoh ini disebut Dungeon2D. Kode untuk itu ada di folder Scripts2D.

Algoritma

Dunia dibagi menjadi kotak persegi panjang. Saya berasumsi bahwa 1 unit akan cukup untuk menunjukkan koridor. Dalam permainan penuh, 1 unit Unity dapat sesuai dengan, misalnya, 5 meter. Untuk kisi-kisi, saya memilih ukuran 30 × 30.

1. Kami mengatur kamar secara sewenang-wenang, tetapi agar tidak saling tumpang tindih. Lokasi tidak masalah, jadi dalam contoh ini saya hanya memberi mereka lokasi dan ukuran acak. Juga, di setiap sisi, saya menambahkan buffer 1 unit lebar (sehingga kamar tidak saling bersinggungan), tetapi ini tidak diperlukan agar algoritma bekerja.


Persegi panjang merah adalah kamar

2. Buat grafik triangulasi Delaunay untuk kamar. Saya menggunakan algoritma Bower-Watson untuk ini. Ada banyak implementasi dari algoritma ini dalam banyak bahasa, saya memilih satu yang akan mudah diport ke C #.


Triangulasi Delaunay

3. Buat pohon rentang minimum (MST) dari triangulasi. Saya menggunakan algoritma Prim untuk ini.


Koridor MST

4. Kami membuat daftar koridor, dimulai dengan setiap tepi pohon dari tahap 3. Pohon berisi semua kamar, sehingga jalur ke setiap kamar dijamin ada. Tambahkan tepi secara acak dari triangulasi ke daftar. Jadi kita akan membuat beberapa loop di koridor. Dalam kode saya, saya menggunakan probabilitas menambahkan setiap sisi hingga 12,5%.


Koridor setelah menambahkan beberapa tepi ke MST. Perhatikan bahwa loop telah muncul.

5. Untuk setiap koridor dalam daftar, gunakan algoritma A * untuk menemukan jalur dari awal koridor hingga akhir. Setelah menemukan satu jalan, itu mengubah keadaan dunia sehingga koridor masa depan selalu dapat melewati yang ada.

Fungsi biaya yang saya gunakan membuatnya lebih murah untuk bergerak di sepanjang koridor memotong dalam iterasi yang berbeda daripada membuat koridor baru. Ini merangsang algoritma pencarian jalur untuk menggabungkan koridor yang melewati satu ruang. Gerakan melalui ruangan itu mungkin, tetapi mahal. Oleh karena itu, dalam kebanyakan kasus, algoritma pencarian jalur lebih memilih untuk menghindari ruangan.


Persegi panjang biru adalah koridor

Berikut adalah beberapa contoh algoritma yang menggunakan sumber daya grafis nyata (sumber daya dan kode untuk penempatannya tidak ada dalam repositori):

Tiga dimensi

Setelah membuat generator bawah tanah 2D yang berfungsi, saya mulai mentransfernya ke 3D. Semua algoritma yang digunakan memiliki versi 3D, jadi harus sederhana, bukan?

Algoritma

Grid sekarang memiliki ukuran 30x5x30.

1. Perubahan pertama adalah generasi kamar dalam 3D. Perubahan ini sepele.


Harap dicatat bahwa kamar-kamar dapat memiliki beberapa lantai.

2. Kemudian kita menemukan triangulasi 3D Delaunay dari kamar-kamar ini, atau lebih tepatnya tetrahedral Delaunay. Setelah mencari informasi tentang "triangulasi 3D Delaunay" atau "Delaunay tetrahedralization", saya menemukan banyak artikel penelitian, tetapi tidak satu contoh kode tunggal.

Yang paling dekat dengan yang saya butuhkan adalah implementasi triangulasi 3D CGAL, tetapi ada dua masalah dengan itu. Pertama, modul ini hanya tersedia di bawah lisensi GPL. Yang kedua - kodenya begitu banyak template dan tidak jelas sehingga saya tidak tahu di mana algoritma tersebut diterapkan.

Pada akhirnya, saya harus mempelajari sendiri prinsip algoritma Bower-Watson untuk mengubahnya sendiri. Saya masih tidak benar-benar mengerti mengapa lingkaran yang dibatasi begitu penting, tetapi setidaknya saya dapat menulis ulang algoritme dengan bola yang dijelaskan menggunakan halaman ini dengan Wolfram MathWorld. Karena ini terutama operasi dengan matriks 4x4, saya menetapkan semua pekerjaan kompleks ke tipe Matrix4x4 dari Unity3D.

Versi baru ini terletak di Scripts3D/Delaunay3D.cs , kalau-kalau ada yang membutuhkan kode yang mudah dipahami dengan lisensi MIT.


Sulit untuk diperhatikan, tetapi alih-alih sebuah segitiga dengan tiga simpul, algoritma sekarang menciptakan tetrahedron dengan 4 simpul. Setidaknya salah satu dari puncak ini akan terletak di lantai lain, karena jika tidak tetrahedron akan merosot. Ini memberikan tahap pencarian banyak peluang untuk bergerak di antara lantai.

3 dan 4. Tepi dari tahap 2 dengan perubahan yang benar-benar sepele dapat diteruskan ke algoritma Prim.


Koridor 3D-MST


Koridor dengan beberapa tulang rusuk ditambahkan lagi

5. Kesulitan dimulai ketika diimplementasikan dalam algoritma 3D A *. Versi 2D sangat sederhana, ini adalah implementasi standar A *. Untuk mentransfernya ke 3D, saya perlu menambahkan kemampuan ke algoritma pencarian jalur untuk bergerak naik dan turun dan menghubungkan kamar di lantai yang berbeda. Saya memutuskan untuk menghubungkan lantai bukan dengan tangga vertikal, tetapi dengan penerbangan tangga.

Ini masalahnya. Naik tangga lebih rumit dari sekadar memanjat. Untuk bergerak secara vertikal, tangga harus bergerak secara horizontal. Artinya, dia memiliki pendakian dan rentang . Lihatlah gambar di bawah ini. Sel saat ini adalah kotak biru solid. Kemungkinan tetangga adalah kotak kosong. Algoritma pencarian jalur tidak dapat bergerak ke sel langsung di atas sel saat ini. Sebagai gantinya, ia harus bergerak secara horizontal dan vertikal.


Tampak samping. Anda dapat membuat simpul di samping, tetapi bukan simpul di atas.

Untuk membuat algoritma pencarian jalur untuk tangga, saya harus memilih bentuknya. Rasio tinggi ke panjang 1: 1 akan terlalu curam, jadi saya memilih rasio 1: 2. Untuk setiap unit ukuran vertikal, tangga menggerakkan dua unit horizontal. Selain itu, untuk karakter yang akan ditempatkan, harus ada ruang di atas tangga, yaitu, dua sel di atas tangga juga harus terbuka. Secara umum, satu tangga menempati empat sel:


Tangga dan ruang kosong di atasnya

Harus ada koridor di bagian atas dan bawah tangga. Algoritma pencarian jalur seharusnya tidak dapat datang ke tangga dari samping atau dari arah yang berlawanan. Akan menjadi tidak praktis dan aneh jika tangga menabrak koridor, seperti yang ditunjukkan di bawah ini.



Artinya, pada akhirnya, format tangga harus terlihat seperti gambar di bawah ini. Algoritma pencarian jalur harus memastikan keberadaan koridor dalam dua kotak biru.


Tangga dimulai dengan kotak biru solid dan bergerak naik satu lantai.

Algoritme pencarian jalur harus bergerak dari awal ke titik akhir dalam satu langkah. Ini berarti harus bergeser 3 unit secara horizontal dan 1 unit naik atau turun. Algoritma A * dirancang untuk bergerak di setiap langkah dari satu node ke yang berikutnya. Untuk membuat tangga, saya harus "melompat" empat sel tangga.

Kesulitannya adalah entah bagaimana saya perlu mendapatkan algoritma untuk mengelilingi tangga yang dibuatnya. Saya tidak bisa menambahkannya ke set A * tertutup , karena kemudian melalui sel-sel ini cara lain dari arah lain tidak akan bisa pergi. Tapi saya tidak bisa meninggalkan mereka juga, karena dengan itu algoritma pencarian jalur akan dapat bergerak di sepanjang tangga yang baru dibuat, menciptakan situasi yang tidak diinginkan seperti yang ditunjukkan di atas.

Solusinya adalah bahwa setiap node harus melacak semua node sebelumnya di jalurnya. Kemudian, ketika mempertimbangkan node tetangga, itu akan ditolak jika mengacu pada jalur node saat ini. Koridor di ujung tangga akan berisi semua sel yang ditempati oleh tangga, simpul di awal tangga dan semua node dalam perjalanan ke sana, dan seterusnya hingga awal. Algoritma pencarian jalur dapat membuat jalur lain melalui tangga, karena jalur kedua tidak akan tahu tentang tangga.

Perilaku yang dijelaskan di atas diperlukan hanya untuk beberapa jalur potensial dalam panggilan fungsi jalur yang sama. Untuk menghasilkan semua koridor, masih ada banyak tantangan untuk menemukan jalan. Iterasi selanjutnya hanya akan memotong tangga yang ada seperti sebelumnya.

Algoritma pada tahap ini tidak lagi sepenuhnya A *. Ada terlalu banyak kasus khusus di dalamnya hanya untuk tangga akuntansi. Kebutuhan untuk memverifikasi seluruh jalur sebelumnya pada setiap tahap adalah proses yang mahal. Implementasi naif mengikuti semua node sebelum memulai, membacanya sebagai daftar tertaut. Maka akan butuh O (N) waktu untuk memeriksa jalur untuk setiap node tetangga.

Saya memilih implementasi ini: menyimpan tabel hash di setiap node, kuncinya adalah node sebelumnya. Berkat ini, pemeriksaan path dilakukan di O (1), namun, ketika menambahkan node ke path, tabel hash perlu disalin, dan ini adalah O (N). Saya memilih metode ini karena saya menyadari bahwa algoritma akan membaca jalur lebih sering daripada mengubahnya.

Meskipun demikian, kompleksitas keseluruhan akan menjadi sekitar O (N ^ 2), meskipun saya tidak tahu bagaimana menganalisis ini dengan benar. Modifikasi ini adalah "bottleneck" utama dari algoritma generasi dungeon.

Setelah melakukan semua perubahan ini, hasilnya adalah sebagai berikut:


Persegi panjang hijau adalah tangga


Jalur generator bisa sederhana ...


... atau rumit

Inilah yang terlihat seperti ruang bawah tanah 3D dengan sumber daya grafis nyata:


Penjara bawah tanah dengan beberapa lantai


Algoritma generasi dungeon mampu menciptakan perilaku muncul yang menarik.


Dua tangga membentuk tangga lebar ganda


Sulit Menjelaskan Tangga Lebar Tiga Kali Lipat


Sebuah jalan menuruni dua lantai dapat membuat dua tangga dengan platform di tengah


Ketika beberapa jalur melewati satu sama lain, koridornya bisa sangat besar


Dua tangga turun ke satu lantai

Kesimpulan

Bagian tersulit dari proyek ini adalah pembuatan algoritma yang diperlukan untuk versi 3D. Saya tidak dapat menemukan satu implementasi triangulasi 3D Delaunay, jadi saya harus melakukannya sendiri. Persyaratan untuk algoritma pencarian jalur sangat spesifik, jadi saya melakukannya sendiri juga.

Tetapi pekerjaan itu sepadan. Ruang bawah tanah yang dibuat oleh algoritma ini menarik dan dapat menjadi dasar untuk game yang bagus.