Dalam posting ini saya akan menjelaskan algoritma untuk generasi prosedural tingkat dungeon dua dimensi dengan struktur yang telah ditentukan. Di bagian pertama, deskripsi umum akan disajikan, dan di bagian kedua, implementasi algoritma.
Pendahuluan
Algoritma ini ditulis sebagai bagian
dari pekerjaan sarjana dan didasarkan pada artikel oleh
Ma et al (2014) . Tujuan dari pekerjaan ini adalah untuk mempercepat algoritma dan melengkapi dengan fungsi-fungsi baru. Saya cukup senang dengan hasilnya, karena kami membuat algoritma yang cukup cepat untuk menggunakannya selama eksekusi permainan. Setelah menyelesaikan pekerjaan sarjana, kami memutuskan untuk mengubahnya menjadi
sebuah artikel dan mengirimkannya ke konferensi Game-ON 2018.
Algoritma
Untuk membuat level gim, algoritma menerima sebagai input sekumpulan blok bangunan poligonal dan grafik konektivitas level (level topologi). Node pada grafik menunjukkan ruang, dan ujung-ujungnya menentukan koneksi di antara mereka. Tujuan dari algoritma ini adalah untuk menetapkan setiap node dari grafik bentuk dan lokasi ruangan sehingga tidak ada dua bentuk ruangan yang bersilangan, dan setiap pasangan kamar tetangga dapat dihubungkan dengan pintu.
(a)
(b)
(c)
(d)
Gambar (c) dan (d) menunjukkan diagram yang dihasilkan dari grafik input (a) dan blok bangunan (b).
Menggunakan grafik konektivitas, seorang desainer game dapat dengan mudah mengontrol alur permainan. Apakah Anda memerlukan satu jalur umum ke ruang bos dengan beberapa jalur samping opsional? Mulai saja dengan grafik jalur dan kemudian tentukan beberapa node di mana pemain dapat memilih: pergi di sepanjang jalur utama, atau menjelajahi jalur samping, dengan kemungkinan harta dan / atau monster yang menunggunya. Apakah Anda perlu memotong jalan? Cukup pilih dua node dalam grafik dan tambahkan jalan pendek yang menghubungkannya. Kemungkinan skema ini tidak terbatas.
Contoh grafik input. Jalur utama ditunjukkan dengan warna merah, jalur bantu berwarna biru, jalur pendek berwarna oranye.Algoritme ini tidak hanya memungkinkan perancang permainan untuk mengelola struktur tingkat tinggi dari peta yang dihasilkan, tetapi juga menyediakan kemampuan untuk mengontrol tampilan masing-masing kamar dan bagaimana menghubungkannya satu sama lain.
Bentuk berbeda untuk ruangan berbeda
Saya menyebutkan ruang bos di akhir level. Kami tidak ingin ruang bos terlihat seperti kamar biasa lainnya, bukan? Algoritme memungkinkan Anda untuk mengatur formulir untuk setiap kamar. Sebagai contoh, kita dapat membuat ruang di awal level dan ruang bos, yang harus memiliki set bentuk ruangan sendiri, dan satu set umum untuk semua kamar lainnya.
Dua sirkuit dihasilkan dari grafik input, di mana bentuk khusus kamar dikaitkan dengan nomor kamar 8.
Posisi pintu yang ditunjukkan secara eksplisit
Bayangkan bahwa Anda memiliki skrip rapat bos berkualitas tinggi, dan kami membutuhkan pemain untuk memasuki ruang bos dari ubin tertentu. Atau kami mungkin memiliki templat kamar tempat beberapa ubin dicadangkan untuk dinding dan hambatan lainnya. Algoritma ini memungkinkan para desainer untuk secara eksplisit mengatur posisi pintu yang mungkin untuk bentuk ruang individu.
Namun terkadang tujuannya mungkin sebaliknya. Kita bisa membuat templat ruang sedemikian rupa sehingga pintu-pintunya bisa ada di mana saja. Karena itu, kami menerapkan batasan lebih sedikit pada algoritme, oleh karena itu, sering berjalan lebih cepat, dan sirkuit yang dihasilkan mungkin tampak kurang monoton dan lebih organik. Untuk situasi seperti itu, dimungkinkan untuk hanya menunjukkan panjang pintu dan seberapa jauh mereka harus dari sudut. Jarak dari sudut adalah semacam kompromi antara pengaturan manual semua pintu dan keberadaan pintu di mana saja.
(a)
(b)
Gambar (a) menggambarkan berbagai jenis penempatan pintu - ruang persegi memiliki 8 posisi pintu yang jelas, dan ruang persegi panjang menggunakan panjang dan jarak dari sudut. Gambar (b) menunjukkan diagram sederhana yang dihasilkan dengan bentuk ruangan pada Gambar (a).
Koridor antar kamar
Ketika kita berbicara tentang tingkat bawah tanah, kita sering membayangkan kamar yang dihubungkan oleh koridor yang sempit. Saya ingin berasumsi bahwa koneksi pada grafik input menunjukkan koridor, tetapi tidak. Mereka hanya menjamin bahwa semua node tetangga akan terhubung langsung oleh pintu. Jika kita ingin kamar dihubungkan oleh koridor, maka kita perlu memasukkan simpul baru di antara semua pasangan kamar tetangga dan berpura-pura bahwa ini adalah kamar koridor (dengan bentuk kamar tertentu dan posisi pintu tertentu).
(a)
(b)
Sebuah ilustrasi tentang bagaimana kita dapat memodifikasi grafik input untuk menambahkan koridor antar ruangan. Gambar (a) menunjukkan grafik input sebelum menambahkan ruang koridor. Gambar (b) menunjukkan grafik input yang dibuat dari (a) dengan menambahkan kamar baru antara semua kamar yang berdekatan dari grafik asli.
Sayangnya, ini sangat menyulitkan tugas algoritma, karena sering kali jumlah node berlipat ganda. Oleh karena itu, saya menerapkan versi algoritma yang memperhitungkan koridor akun, yang memungkinkan untuk mengurangi penurunan kinerja ketika mengatur ruang koridor. Saat ini, algoritma mendukung baik koridor antara semua kamar, atau tidak adanya koridor, tetapi di masa depan saya berencana untuk membuatnya lebih fleksibel.
Contohnya
Beberapa skema dihasilkan dari set blok bangunan yang berbeda dan dengan koridor dihidupkan.Beberapa skema dihasilkan dari set blok bangunan yang berbeda dengan koridor menyala dan mati.Pada bagian kedua posting saya akan berbicara tentang operasi internal dari algoritma.
Saya juga sedang mengerjakan plugin Unity untuk pembuatan dungeon prosedural, yang akan menyertakan algoritma ini. Saya melakukan ini karena meskipun kemungkinan menggunakan algoritma ini secara langsung dalam Unity (ditulis dalam C #), kenyamanan bekerja dengannya jauh dari ideal. Dibutuhkan banyak waktu untuk membuat templat ruang tanpa GUI, dan banyak kode diperlukan untuk mengubah output dari algoritma ke representasi yang digunakan di dalam gim.
Karena saya sendiri bukan pengembang game, tujuan saya adalah membuat plugin yang cukup baik untuk digunakan orang lain. Jika semuanya berjalan dengan baik, maka saya akan mencoba untuk mempublikasikan pembaruan ketika saya memiliki sesuatu yang menarik untuk dikatakan. Saya sudah punya beberapa ide tentang generator itu sendiri dan tentang pengujian kemampuannya.
Screenshot dari plugin Unity (proyek sedang dalam pengembangan)Bagian 2. Implementasi algoritma
Pada bagian ini saya akan berbicara tentang ide-ide dasar yang diletakkan di dasar algoritma yang dijelaskan di bagian pertama posting. Awalnya, saya ingin menggambarkan konsep dasar bersama dengan perbaikan utama yang diperlukan agar algoritma menjadi cukup cepat. Namun, ternyata, bahkan konsep dasar lebih dari cukup untuk posting ini. Oleh karena itu, saya memutuskan untuk mengungkapkan peningkatan kinerja di artikel mendatang.
Motivasi
Sebelum beralih ke implementasi, saya ingin menunjukkan hasil dari apa yang akan kami lakukan. Video di bawah ini menunjukkan 30 sirkuit berbeda yang dihasilkan dari satu grafik input dan satu set blok bangunan. Algoritme selalu berhenti selama 500 ms setelah menghasilkan rangkaian, dan kemudian mencoba untuk menghasilkan yang berikutnya.
Bagaimana cara kerjanya
Tujuan dari algoritma ini adalah untuk menetapkan bentuk dan posisi ruangan untuk setiap node dalam grafik sehingga tidak ada dua kamar yang bersilangan, dan kamar-kamar tetangga terhubung dengan pintu.
Salah satu cara untuk mencapai ini adalah mencoba semua kemungkinan kombinasi bentuk ruangan dan posisi mereka. Namun, seperti yang Anda duga, ini akan sangat tidak efisien, dan kami mungkin tidak akan dapat menghasilkan sirkuit, bahkan berdasarkan pada grafik input yang sangat sederhana.
Alih-alih mencari semua kemungkinan kombinasi, algoritme ini menghitung cara menghubungkan semua kamar secara tepat (yang disebut ruang konfigurasi) dan menggunakan informasi ini untuk mengarahkan pencarian. Sayangnya, bahkan dengan informasi ini, masih cukup sulit untuk menemukan skema yang tepat. Oleh karena itu, untuk studi ruang pencarian yang efektif, kami menggunakan teknik optimisasi probabilistik (dalam hal ini, simulasi anil). Dan untuk percepatan optimalisasi lebih lanjut, kami memecah tugas input menjadi lebih kecil dan lebih mudah untuk menyelesaikan subtugas. Ini dilakukan dengan membagi grafik menjadi bagian-bagian yang lebih kecil (disebut rantai) dengan pembuatan skema berikutnya untuk masing-masing secara berurutan.
Ruang Konfigurasi
Untuk sepasang poligon di mana satu tetap di tempatnya dan yang lain dapat bergerak bebas, ruang konfigurasi adalah seperangkat posisi poligon bebas di mana dua poligon tidak berpotongan dan dapat dihubungkan dengan pintu. Saat bekerja dengan poligon, setiap ruang konfigurasi dapat direpresentasikan sebagai kumpulan garis yang mungkin kosong dan dihitung dengan alat geometris sederhana.
(a)
(b)
Konfigurasi ruang. Gambar (a) menunjukkan ruang konfigurasi (garis merah) dari persegi panjang bebas relatif terhadap poligon berbentuk L tetap. Ini menentukan semua lokasi pusat alun-alun di mana dua blok tidak bersinggungan dan saling menyentuh. Gambar (b) menunjukkan persimpangan (titik-titik kuning) dari ruang konfigurasi dari bujur sangkar yang bergerak sehubungan dengan dua persegi panjang tetap.
Algoritma berikut digunakan untuk menghitung ruang konfigurasi satu blok tetap dan satu blok gratis. Kami memilih titik referensi pada blok bergerak dan mempertimbangkan semua lokasi di
, sedemikian rupa sehingga ketika memindahkan poligon sehingga titik rujukannya terletak di lokasi ini, baik balok yang dapat bergerak maupun yang sudah terpasang saling bersentuhan, tetapi tidak berpotongan. Himpunan semua titik tersebut membentuk ruang konfigurasi dua blok (Gambar (a) di atas). Untuk mendapatkan ruang konfigurasi blok bergerak sehubungan dengan dua atau lebih blok tetap, persimpangan ruang konfigurasi individu dihitung (Gambar (b) di atas).
Algoritma menggunakan ruang konfigurasi dalam dua cara. Pertama, alih-alih mencoba posisi acak dari masing-masing kamar, kami menggunakan ruang konfigurasi untuk mencari posisi yang mengarah ke jumlah kamar terdekat yang terbesar yang terhubung oleh pintu. Untuk melakukan ini, kita perlu memperoleh persimpangan ruang kosong maksimum dari tetangga. Kedua, kami menggunakan ruang konfigurasi untuk memeriksa apakah semua pasangan kamar tetangga dapat dihubungkan dengan pintu. Ini dilakukan dengan memeriksa apakah posisi ruangan berada di dalam ruang konfigurasi semua tetangganya.
Karena bentuk ruang tidak berubah selama pelaksanaan permainan, kami dapat menghitung pra-ruang konfigurasi semua pasang bentuk ruang sebelum algoritma dimulai. Berkat ini, keseluruhan algoritma dipercepat secara signifikan.
Skema tambahan
Saat memecahkan masalah yang kompleks, salah satu pendekatan yang mungkin adalah membaginya menjadi subtugas yang lebih kecil dan sederhana, dan menyelesaikannya. Inilah tepatnya yang akan kita lakukan dengan tugas menempatkan masing-masing kamar. Alih-alih mengatur semua kamar pada satu waktu, kami akan memecah grafik input menjadi subgraph yang lebih kecil dan mencoba membuat diagram dari mereka satu per satu. Para penulis algoritma asli menyebut subgraph ini "rantai" karena prinsip dari grafik ini, di mana setiap node memiliki tidak lebih dari dua tetangga, dan karena itu cukup mudah untuk membuat skema mereka.
Sirkuit keluaran akhir selalu merupakan satu komponen yang terhubung, sehingga tidak masuk akal untuk menghubungkan masing-masing komponen ke dalam rangkaian, dan kemudian mencoba menggabungkannya, karena proses penggabungannya bisa sangat rumit. Oleh karena itu, setelah menempatkan rantai, rantai terhubung berikutnya akan selalu menjadi yang terhubung ke simpul yang sudah berbaris di sirkuit.
Layout GenerateLayout(inputGraph) { var emptyLayout = new Layout(); var stack = new Stack<Layout>(); stack.Push(emptyLayout); while(!stack.Empty()) { var layout = stack.Pop(); var nextChain = GetNextChain(layout, inputGraph); Layout[] partialLayouts = AddChain(layout, nextChain); if (!partialLayouts.Empty()) { if (IsFullLayout(partialLayouts[0])) { return partialLayouts[0]; } else { stack.Push(partialLayouts); } } } return null; }
Pseudo-code menunjukkan pendekatan inkremental untuk menemukan skema yang tepat.Kode pseudo yang ditunjukkan di atas menunjukkan implementasi skema tambahan. Pada setiap iterasi algoritma (baris 6-18), pertama-tama kita mengambil sirkuit terakhir dari stack (baris 7) dan menghitung rantai mana yang akan ditambahkan berikutnya (baris 8). Ini dapat dilakukan dengan hanya menyimpan jumlah sirkuit terakhir yang ditambahkan ke setiap sirkuit parsial. Pada langkah berikutnya, kami menambahkan rantai berikut ke sirkuit (jalur 9), menghasilkan beberapa sirkuit terperinci, dan menyimpannya. Jika fase ekspansi gagal, tetapi tidak ada skema parsial baru yang ditambahkan ke tumpukan, dan algoritma perlu melanjutkan dengan skema parsial yang terakhir disimpan. Kami menyebut situasi ini sebagai pencarian balik karena algoritme tidak dapat memperpanjang skema parsial saat ini dan harus kembali dan melanjutkan dengan skema tersimpan lainnya. Ini biasanya diperlukan ketika tidak ada cukup ruang untuk menghubungkan sirkuit tambahan ke simpul yang sudah tersusun di sirkuit. Juga, pencarian kembali adalah alasan bahwa kami selalu mencoba untuk menghasilkan beberapa skema lanjutan (baris 9). Kalau tidak, kita tidak akan punya apa-apa untuk dikembalikan. Proses berakhir ketika kita menghasilkan rangkaian lengkap, atau tumpukan kosong.
(a) Input grafik
(b) Diagram sebagian
(c) Diagram sebagian
(d) Garis besar penuh
(e) Garis besar lengkap
Skema tambahan. Gambar (b) dan (c) menunjukkan dua diagram parsial setelah merencanakan rangkaian pertama. Gambar (d) menunjukkan sirkuit lengkap setelah ekspansi (b) oleh sirkuit kedua. Gambar (e) menunjukkan sirkuit lengkap setelah ekspansi (c) oleh sirkuit kedua.
Untuk membagi grafik menjadi beberapa bagian, Anda perlu menemukan embedding datar dari grafik input, yaitu gambar pada bidang di mana ujung-ujungnya hanya bersilangan pada titik akhir. Lampiran ini kemudian digunakan untuk mendapatkan semua wajah grafik. Gagasan utama dari dekomposisi adalah bahwa lebih sulit untuk membuat sirkuit dari siklus, karena node mereka memiliki batasan lebih. Oleh karena itu, kami mencoba mengatur siklus pada awal dekomposisi, sehingga mereka diproses sedini mungkin dan mengurangi kemungkinan perlunya kembali pada tahap berikutnya. Rantai dekomposisi pertama dibentuk oleh wajah terkecil dari lampiran, dan wajah selanjutnya kemudian ditambahkan dalam urutan pencarian pertama. Jika ada wajah lain yang bisa dipilih, maka yang terkecil dari mereka digunakan. Ketika tidak ada lagi wajah yang tersisa, komponen non-siklik yang tersisa ditambahkan. Gambar 4 menunjukkan contoh dekomposisi dalam rantai, yang diperoleh sesuai dengan langkah-langkah ini.
(a)
(b)
Dekomposisi menjadi rantai. Gambar (b) menunjukkan contoh cara meletakkan gambar (a) pada suatu rangkaian. Setiap warna mewakili rantai yang terpisah. Angka menunjukkan urutan pembuatan rantai.
(c) Desain parsial yang baik
(d) Garis besar penuh
(a) Input grafik
(B) Grafik parsial buruk
Cari dengan pengembalian. Gambar (b) menunjukkan contoh sirkuit parsial yang buruk, karena tidak ada ruang yang cukup di dalamnya untuk menghubungkan node 0 dan 9. Untuk menghasilkan sirkuit penuh (d), diperlukan kembali ke sirkuit parsial lain (c).
Simulasi anil
Algoritma simulasi anil adalah teknik optimisasi probabilistik yang tujuannya adalah untuk mempelajari ruang sirkuit yang mungkin. Itu dipilih oleh penulis artikel asli karena ternyata bermanfaat dalam situasi serupa di masa lalu. Ketika mengimplementasikan algoritma, saya memutuskan untuk menggunakan metode yang sama, karena saya ingin memulai dengan apa yang sudah terbukti efektif dalam menyelesaikan masalah ini. Namun, saya pikir itu bisa diganti dengan metode lain dan pustaka saya ditulis sedemikian rupa sehingga proses penggantian metode ini cukup sederhana.
Algoritma simulasi anil secara iteratif mengevaluasi perubahan kecil dalam konfigurasi saat ini, atau sirkuit. Ini berarti bahwa kami membuat konfigurasi baru dengan memilih secara acak satu simpul dan mengubah posisi atau bentuknya. Jika konfigurasi baru meningkatkan fungsi energi, itu selalu diterima. Jika tidak, ada sedikit peluang untuk menerima konfigurasi. Kemungkinan membuat keputusan yang lebih buruk berkurang seiring waktu. Fungsi energi dirancang sedemikian rupa sehingga membebankan denda besar pada titik persimpangan dan titik yang berdekatan tidak saling bersentuhan.
A adalah total luas persimpangan antara semua pasangan blok dalam diagram. D adalah jumlah kuadrat dari jarak antara pusat pasangan blok dalam grafik input yang bertetangga tetapi tidak saling menyentuh. Nilai
mempengaruhi kemungkinan anil yang disimulasikan dibiarkan masuk ke konfigurasi terburuk; parameter ini dihitung dari luas rata-rata blok bangunan.
Setelah memilih simpul untuk diubah, kami mengubah bentuk atau posisinya. Bagaimana kita memilih posisi baru? Anda dapat memilihnya secara acak, tetapi ini akan sering menurunkan fungsi energi, dan algoritma akan menyatu sangat lambat. Bisakah kita memilih posisi yang lebih mungkin meningkatkan fungsi energi? Lihat apa yang saya tuju? Kami menggunakan ruang konfigurasi untuk memilih posisi yang memenuhi batas jumlah kamar tetangga terbesar.
Kemudian, untuk mengubah bentuk, cukup pilih salah satu bentuk ruang yang tersedia. Sementara algoritma tidak mencoba untuk memutuskan bentuk mana yang paling mungkin membawa kita ke skema yang benar. Namun, akan menarik untuk mencoba fitur ini dan melihat apakah itu mempercepat algoritma.
List<Layout> AddChain(chain, layout) { var currentLayout = GetInitialLayout(layout, chain); var generatedLayouts = new List<Layout>(); for (int i = 1; i <= n, i++) { if () { break; } for (int j = 1; j <= m, j++) { var newLayout = PerturbLayout(currentLayout, chain); if (IsValid(newLayout)) { if (DifferentEnough(newLayout, generatedLayouts)) { generatedLayouts.Add(newLayout); } } if () { currentLayout = newLayout; } else if () { currentLayout = newLayout; } } } return generatedLayouts; }
Ini adalah pseudo-code dari metode yang bertanggung jawab untuk membuat rangkaian sirkuit terpisah dengan mensimulasikan annealing.
Untuk mempercepat seluruh proses, kami akan mencoba menemukan konfigurasi awal berenergi rendah. Untuk melakukan ini, kami akan mengatur node dalam rantai saat ini untuk pencarian pertama kali, mulai dari yang berdekatan dengan node yang sudah termasuk dalam skema. Kemudian node yang dipesan ditempatkan satu per satu dan bagi mereka posisi dengan energi terendah dipilih dari ruang konfigurasi. Di sini kita tidak melakukan backtracking - ini adalah proses serakah yang sederhana.
Video Bonus
Video di bawah ini menunjukkan diagram yang dihasilkan dari grafik input yang sama seperti pada video pertama. Namun, kali ini pendekatan tambahan ditampilkan. Anda mungkin memperhatikan bahwa algoritme menambahkan rantai simpul satu per satu. Terlihat juga bahwa kadang-kadang ada dua sirkuit parsial berturut-turut dengan jumlah node yang sama. Ini terjadi ketika algoritma kembali. Jika upaya pertama untuk menambahkan rangkaian lain ke rangkaian parsial pertama gagal, maka algoritma akan mencoba sirkuit parsial lain.
Bahan yang bisa diunduh
Implementasi algoritma pada .NET dapat ditemukan di
github saya . Repositori berisi .NET DLL dan aplikasi WinForms GUI, dikendalikan oleh file konfigurasi YAML.