Algoritma untuk peta 2D prosedural dengan jalur yang terhubung

Masalah yang harus dipecahkan: Hasilkan peta ruang bawah tanah 2D acak untuk game berbasis ubin tempat semua kamar terhubung.

Saya mencari solusi yang lebih baik daripada yang saya miliki saat ini.

Solusi saya saat ini adalah saya menjalankan dua algoritma. Yang pertama menghasilkan ruang bawah tanah dengan kamar-kamarnya. Yang kedua pastikan bahwa semua kamar terhubung. Saya ingin tahu solus apa yang mungkin ada. Lebih cepat dan / atau lebih mudah dll. Kecepatan sebenarnya bukan masalah, tetapi jika kecepatan dapat diperoleh tanpa biaya nyata, yah, itu adalah hal yang baik. Lebih penting adalah bahwa saya, dan orang lain yang membaca, dapat belajar berbagai cara untuk mendekati dan menyelesaikan masalah.

Di bawah ini adalah implementasi saya saat ini. Kamar saat ini tidak memiliki jalan keluar atau keluar dalam arah 2, 3 atau 4 mana pun.

Menghasilkan ruang bawah tanah

Pengaturan: Atur ruang saat ini ke ruang kiri atas.

1. Dapatkan tipe kamar yang valid untuk kamar (di mana tipe kamar yang valid adalah tipe tanpa pintu keluar dari ruang bawah tanah dan yang memiliki pintu keluar yang cocok dengan pintu keluar kamar di atas dan ruangan di sebelah kiri. Hanya perlu memeriksa di atas dan ke tersisa karena langkah 2 di bawah).
2. Letakkan ruangan dan maju satu langkah koordinat x. Jika koordinat x melebihi lebar dungeon, atur koordinat x ke 0 dan naikkan satu koordinat y langkah. Jika koordinat y melebihi ketinggian penjara bawah tanah, kita selesai.
3. Ulangi dari # 1.

Saya kemudian memeriksa untuk melihat apakah semua kamar terhubung Jika mereka tidak semua terhubung saya menjalankan algoritma kedua itu, dalam cara non-seksi tapi pasti cukup baik dalam hal tata letak ruang bawah tanah, melewati kamar-kamar dan mengubahnya sehingga semua berakhir terhubung.

Memeriksa untuk melihat apakah semua kamar terhubung

Setup: Buat peta 2D bilangan bulat yang mewakili jalur dan inisialisasi entri ke nilai "belum diproses" (belum dilalui), -1. Menyetel integer indeks jalur awal yang melacak jalur saat ini ke 1. Atur ruang saat ini ke ruang kiri atas dengan menambahkannya ke tumpukan kamar untuk diperiksa.

1. Jika tumpukan berisi kamar untuk diperiksa, letakan setel indeks jalur ruangan ke indeks jalur saat ini. Jika tumpukan tidak berisi ruangan apa pun, tambah indeks jalur dan coba dapatkan kamar dengan memajukan kolom demi kolom, baris demi baris, hingga kami mendapatkan kamar yang belum diproses. Jika tidak ada kamar dapat ditemukan, kita selesai.
2. Periksa untuk melihat apakah ruangan memiliki jalan keluar ke kiri. Jika telah menambahkan ruang kiri ke tumpukan jika belum ada di sana.
3. Ulangi langkah 2 untuk arah bawah, kanan dan atas (karena kami menggunakan tumpukan yang berarti kamar dilintasi dalam urutan searah jarum jam, dimulai dengan arah atas).
4. Ulangi dari langkah 1.
5. Jika jumlah indeks jalur lebih besar dari satu, ada kamar yang terputus.

Jika ada kamar yang terputus maka saya mengelompokkan kamar berdasarkan indeks jalurnya, dapatkan indeks jalur terbesar dan menghubungkan semua kamar lain ke kamar tersebut. Ini adalah pekerjaan yang sedang berjalan, tetapi rencana saya (saat ini, "brutal") adalah untuk melewati setiap kamar dalam grup kamar (kecuali yang pertama) memeriksa untuk melihat apakah ada jalur horizontal atau vertikal ke grup kamar biggeset, dan jika demikian, buat jalur horizontal / vertikal di sana dengan menyuntikkan / memperbarui kamar di antara. Bilas dan ulangi. Jelek, ya, tapi itu adalah sesuatu yang tidak akan terlihat dalam hal pola visual sehingga bekerja dalam pengertian itu.

Salah satu algoritma terbaik, dan paling banyak digunakan, yang pernah saya lihat di luar sana adalah menghasilkan ruang bawah tanah menggunakan Binary Space Partitioning.

Penjelasan umum terbaik yang pernah saya baca adalah yang ditemukan di The Chronicles of Doryen (terlampir di bagian akhir untuk keperluan cadangan) karena menjelaskan prosedur tanpa masuk ke dalam kode, sehingga menyerahkan implementasinya kepada pembaca.

Dua tutorial lain tentang hal yang sama, dengan kode, dapat ditemukan di

• Cara Menggunakan Pohon BSP untuk Menghasilkan Peta Game
• Generasi penjara menggunakan pohon BSP

Membangun pohon BSP

Kami mulai dengan ruang bawah tanah persegi panjang yang diisi dengan sel-sel dinding. Kami akan membagi ruang bawah tanah ini secara rekursif sampai setiap sub-ruang bawah tanah memiliki ukuran sekitar ruangan. Pemisahan penjara bawah tanah menggunakan operasi ini:

• Pilih arah acak: pemisahan horizontal atau vertikal
• Pilih posisi acak (x untuk vertikal, y untuk horizontal)
• Bagi dungeon menjadi dua sub-dungeon

Sekarang kita memiliki dua sub-dungeon A dan B. Kita dapat menerapkan operasi yang sama untuk keduanya.

Saat memilih posisi pemisahan, kita harus berhati-hati agar tidak terlalu dekat dengan perbatasan penjara bawah tanah. Kita harus dapat menempatkan kamar di dalam setiap sub-dungeon yang dihasilkan. Kami ulangi sampai ruang bawah tanah terendah memiliki ukuran kira-kira kamar yang ingin kami hasilkan.

Membangun penjara bawah tanah

Sekarang kita membuat ruangan dengan ukuran acak di setiap daun pohon. Tentu saja, ruangan harus terkandung di dalam ruang bawah tanah yang sesuai. Berkat pohon BSP, kami tidak dapat memiliki dua kamar yang tumpang tindih.

Untuk membangun koridor, kita melingkari semua daun pohon, menghubungkan setiap daun dengan saudara perempuannya. Jika kedua kamar memiliki dinding tatap muka, kita bisa menggunakan koridor lurus. Lain kita harus menggunakan koridor berbentuk Z.

Sekarang kita naik satu tingkat di pohon dan ulangi proses untuk sub-wilayah ayah. Sekarang, kita dapat menghubungkan dua sub-wilayah dengan tautan antara dua kamar, atau koridor dan satu kamar atau dua koridor.

Kami ulangi prosesnya sampai kami menghubungkan dua sub-dungeon pertama A dan B

The Metode BSP tampaknya metode yang populer yang paling untuk menghasilkan ruang bawah tanah, tapi itu bukan satu-satunya.

Untuk kelengkapan saya akan menjelaskan generator yang bekerja untuk saya . Saya harus mengakui bahwa saya tidak ingat di mana saya membaca tentang ini jadi saya hanya akan mengatakan bahwa itu bukan penemuan saya (sebuah artikel lama oleh Jamis Buck terdengar sangat akrab).

Labirin dengan kamar

Ide dasarnya adalah bahwa penjara bawah tanah adalah labirin dengan kamar, semacam itu. Jadi langkah pertama untuk algoritma ini, adalah menghasilkan labirin :

Langkah selanjutnya adalah membuatnya jarang (menghapus jalan buntu):

Langkah nomor 3 adalah menambahkan beberapa loop (membuatnya tidak sempurna ) tetapi saya akan melewatkan gambar karena hampir tidak terlihat (saya tidak perlu labirin yang sempurna jadi saya mengambil beberapa pintasan pada algoritma pembuatan labirin, jadi sudah memiliki loop pada titik ini).

Kemudian, untuk langkah 4, kita perlu menghilangkan sel yang terisolasi:

Saat ini kami sudah selesai dengan koridor dan kami siap untuk menambah kamar. Untuk itu kami melakukan hal berikut:

1. Hasilkan satu set kamar (lebar dan tinggi)
2. Untuk setiap kamar kami beralih melalui semua lokasi yang mungkin dan memutuskan lokasi terbaik.
   • Lokasi terbaik dihitung dengan menambahkan bobot pada kondisi (seperti adjacency ke koridor).
3. Kami menempatkan kamar.

Sejauh ini, dungeon kita akan terlihat seperti ini:

Langkah terakhir adalah menambahkan dekorasi.

Beberapa pemikiran terakhir

• Saya menggunakan Algoritma Eller versi strip-down .
• Algoritma labirin yang berbeda dapat menghasilkan tekstur yang berbeda. Anda mungkin lebih suka algoritma lain. Sebagai contoh, gambar berikut menunjukkan tekstur berbeda yang dihasilkan dari "Binary Tree" (bias diagonal) dan variasi dari algoritma "Recursive Division" (koridor panjang):