Generasi Bawah Tanah Prosedural: Apakah ada algoritma sederhana untuk memastikan semua kamar ini terhubung menggunakan koridor minimal?

Apakah mungkin untuk mendapatkan struktur seperti sarang, yang menghubungkan semua kamar tanpa memiliki terlalu banyak koridor? (Terlalu banyak menjadi 3-4 + koridor yang berasal dari satu kamar)

Di bawah ini adalah output dari bagaimana kamar saya terlihat, pada dasarnya mereka ditempatkan secara acak.

Apa yang saya harapkan dari koridor.

Nah, cara paling sederhana yang bisa saya pikirkan dimulai dengan memastikan semua kamar terhubung oleh setidaknya 1 koridor:

1. Mulailah dengan ruang terakhir, atau pertama.
2. Ambil ruang acak dalam jarak 1, yang belum terhubung ke beberapa ruangan (semua kamar mulai terputus, sehingga Anda akan melacak ini saat Anda pergi).
3. Jika tidak ada ruangan seperti itu, pergi ke jarak +1. Jika tidak masalah untuk terowongan di atas / di bawah ruangan lain, ini lebih mudah, dengan asumsi Anda tidak ingin menghubungkan koridor.
4. Kerjakan cara Anda melalui pseudo-acak hingga semua kamar terhubung.

Sekarang kami tahu Anda dapat mencapai semua kamar, tetapi sekarang jika Anda menginginkan lebih dari labirin linier yang ketat ini, Anda dapat melangkah melalui kamar Anda dan secara acak membuat jalur baru untuk menghubungkan kamar, hingga batas per kamar 2-3, atau sampai persentase kamar tertentu mencapai koneksi maks - dll.

Sebagai langkah terakhir Anda dapat menambahkan aturan yang akan mengubah hasil Anda sesuai dengan berbagai situasi. Misalnya, Anda dapat mengamati bahwa setiap ruangan dengan hanya 1 koridor, menurut definisi, adalah jalan buntu; Anda dapat membuat lebih banyak jalan buntu, atau Anda bisa menghilangkan semuanya dengan memastikan semuanya memiliki setidaknya 2 koneksi. Anda bisa membuat jalan buntu memiliki jalan rahasia. Anda dapat memastikan bahwa ruang bos adalah jalan buntu. Anda dapat memastikan ruang awal Anda buntu, tetapi kemudian memastikan kamar kedua memiliki minimum koneksi X. Ad infinitum.

Setiap asumsi dan aturan dapat secara radikal mengubah tampilan level Anda, tapi itu bagian yang menyenangkan! Setidaknya ini harus membuat Anda kamar sarang / seperti gua untuk memulai.

Cukup bangun kamar Anda yang sudah terhubung. Mulailah dengan satu kamar, lalu bangun 1-3 koridor ke kamar lain. Kemudian muncul kembali sampai Anda telah menambahkan kamar yang cukup.

Karena kamar-kamar ini adalah simpul Grafik yang tertanam di dataran 2d, secara teori ini dapat dilakukan dengan menyelesaikan masalah penjual keliling (yang akan baik-baik saja dengan hanya beberapa kamar). Jelas, heuristik sederhana akan baik-baik saja dan memungkinkan skalabilitas yang masuk akal.

Anda menghitung tepi (panjang koridor) antara semua kamar. Anda mengurutkannya berdasarkan panjang. Anda menambahkan koridor terpendek kecuali jika itu menciptakan siklus atau meningkatkan derajat simpul (ruang) di atas nilai maks yang Anda inginkan (3-4) (Ulangi). Untuk memeriksa siklus, Anda dapat menerapkan UnionFind atau melakukan BFS cepat pada data kecil.