Prosedural… rumah dengan generator kamar

74

Saya telah melihat beberapa algoritma dan artikel tentang cara membuat dungeon secara prosedural. Masalahnya adalah, saya mencoba membuat rumah dengan kamar, dan sepertinya tidak sesuai dengan kebutuhan saya.

Pertama, ruang bawah tanah memiliki koridor, di mana rumah-rumah memiliki aula. Dan meskipun pada awalnya mereka mungkin tampak sama, sebuah aula tidak lebih dari area yang bukan ruangan, sedangkan koridor dirancang khusus untuk menghubungkan satu area ke area lainnya.

Perbedaan penting lainnya dengan sebuah rumah adalah bahwa Anda memiliki lebar dan tinggi yang spesifik, dan Anda harus mengisi semuanya dengan kamar dan aula, sedangkan dengan ruang bawah tanah, ada ruang kosong.

Saya pikir aula di sebuah rumah adalah sesuatu di antara koridor penjara bawah tanah (membawa Anda ke kamar lain) dan ruang kosong di penjara bawah tanah (itu tidak didefinisikan secara eksplisit dalam kode).

Lebih khusus lagi, persyaratannya adalah:

  • Ada satu set kamar standar yang
    tidak bisa saya buat dinding dan pintu dengan cepat.
  • Kamar dapat diputar tetapi tidak diubah ukurannya
    lagi, karena saya memiliki seperangkat kamar yang telah ditentukan, saya hanya bisa memutarnya, bukan mengubah ukurannya.
  • Dimensi rumah diatur dan harus sepenuhnya diisi dengan kamar (atau aula)
    Yaitu saya ingin mengisi rumah 14x20 dengan kamar yang tersedia memastikan tidak ada ruang kosong.

Berikut ini beberapa gambar untuk membuatnya lebih jelas:

Generator penjara bawah tanah yang umum Penjara bawah tanah tanpa koridor Hasil generator rumah

Seperti yang Anda lihat, di dalam rumah, "ruang kosong" masih bisa dilalui dan membawa Anda dari satu ruangan ke ruangan lain.

Jadi, setelah mengatakan semua ini, mungkin sebuah rumah hanyalah penjara bawah tanah yang benar-benar sangat padat dengan koridor. Atau itu sesuatu yang lebih mudah daripada penjara bawah tanah. Mungkin ada sesuatu di luar sana dan saya belum menemukannya karena saya tidak benar-benar tahu apa yang harus dicari.

Di sinilah saya ingin bantuan Anda: dapatkah Anda memberi saya petunjuk tentang cara mendesain algoritma ini? Adakah pemikiran tentang langkah apa yang akan diambil? Jika Anda telah membuat generator penjara bawah tanah, bagaimana Anda memodifikasinya agar sesuai dengan kebutuhan saya? Anda dapat spesifik atau generik yang Anda inginkan. Saya mencari untuk memilih otak Anda, sungguh.

pek
sumber
2
Rekomendasi yang aneh: Saya sangat merekomendasikan untuk memeriksa buku-buku Christopher Alexander, Cara Abadi Bangunan dan Bahasa Pola , buku-buku arsitektur yang membentuk fondasi asli untuk gagasan pola (perangkat lunak); mereka pada dasarnya menggambarkan bahasa eksplisit untuk bangunan dan ruang hidup yang dapat diubah menjadi metode konstruksi prosedural top-down.
Steven Stadnicki
Secara pribadi, saya akan mencoba membuat algoritma seperti jawaban egarcias. Mulailah dengan menghasilkan penampung ruang (area besar yang dapat diisi dengan jumlah kamar yang berbeda-beda. Masing-masing penampung ruang harus memiliki celah ukuran tertentu (atau acak dengan batas bawah) di antara mereka. Ruang 'celah' adalah apa yang akan dianggap sebagai lorong yaitu ruang yang ada di rumah tetapi tidak di dalam ruangan, dan pemegang tempat kamar akan diisi oleh kamar berukuran acak yang mirip dengan contoh 'ruang bawah tanah tanpa koridor' Anda.
Benjamin Danger Johnson
@ pek Tolong buat jawaban untuk solusi Anda, jangan taruh di pertanyaan.
MichaelHouse
@ Byte56 Selesai. Untuk lebih jelasnya, saya melakukan itu karena saya tidak ingin mendapatkan kredit karena saya hanya melakukan apa yang disarankan orang lain. Saya mengerti mengapa itu tidak ideal untuk format situs, jadi, saya menambahkan jawaban saya.
pek
Terima kasih @pek. Jangan khawatir tentang mendapatkan kredit, itu layak dan itu berguna bagi orang-orang yang datang ke situs untuk melihat solusinya (dan melihatnya di tempat yang diharapkan adalah yang terbaik).
MichaelHouse

Jawaban:

50

Saya pikir ini adalah kasus yang baik untuk menggunakan partisi ruang biner atau terner.

Pada pass pertama, pisahkan ruang rumah menjadi aula dan {blok kamar}. Dapatkan potongan besar berikutnya, pisahkan menjadi {hall and chunk} atau {2 chunks dan hall di antara mereka}. Pada setiap langkah, putar arah pengirisan 90 derajat. Berhentilah ketika {tidak ada lagi potongan besar yang tersisa} atau {total luas aula mencapai batas}.

Pada pass kedua, pisahkan potongan yang tersisa menjadi kamar. Dapatkan potongan besar berikutnya dan membaginya. Lewati membelah beberapa potongan yang tidak terlalu besar secara acak, untuk memiliki beberapa kamar besar.

Jika ada aula yang menghadap aula yang jauh lebih tua, letakkan dinding (atau dinding dengan pintu) di sana.

Hubungkan kamar dengan aula secara langsung atau melalui kamar lain yang sudah terhubung.

Misalnya, Anda dapat melihat hasil buatan saya atau C ++ - mirip dengan pseudo-code yang sebagian sudah selesai . Tembakan terakhir:

tembakan terakhir

Shadows In Rain
sumber
Di situlah hasil penelitian saya, dalam partisi ruang. Contoh Anda dengan kode memberi saya awal yang sangat sangat baik. Saya sedang membaca tentang algoritma. Namun satu pertanyaan: salah satu persyaratan saya adalah kamar sudah ditentukan sebelumnya (yaitu ada 2x2 kamar dengan satu pintu, 1x1 dengan dua pintu, tetapi tidak ada 2x2 dengan tiga pintu), jadi saya tidak dapat memulai partisi dan kemudian memutuskan di mana saya akan menempatkan pintu . Saya pikir saya harus mengingat keterbatasan saya saat mempartisi. Apakah Anda punya saran untuk bagaimana saya akan melakukan ini? Bagaimanapun, terima kasih banyak atas jawaban dan usaha Anda!
pek
@ pek Saya tidak yakin apakah manusia biasa dapat menemukan solusi akademis untuk masalah ini. Anda dapat mencoba mengatur kondisi tambahan untuk chunk-splitter dan box-splitter, dan kemudian menghasilkan dan menjatuhkan level sampai Anda menemukan satu di mana semua kondisi dapat dipenuhi.
Shadows In Rain
ya, saya berharap bahwa saya kehilangan sesuatu. Pendekatan pertama saya adalah dengan menggunakan A * untuk mencari cara menyesuaikan kamar di ruang yang diberikan, tapi itu kurang logika untuk aula. Sekarang saya berpikir bahwa saya dapat menggunakan BSP untuk menempatkan aula, dan kemudian menggunakan A * ke blok. Hal yang paling saya khawatirkan adalah mungkin terlalu mahal dan tidak selalu membuahkan hasil. Tapi saya harus menguji ini dulu. Mungkin itu tidak akan seburuk itu?
pek
2
@ pek saya menemukan sesuatu yang berguna, jika Anda masih tertarik. Lihat ini , juga google L-system.
Shadows In Rain
24

Anda dapat mengambil keuntungan dari kenyataan bahwa desain yang Anda inginkan menggumpalkan kamar-kamar di kamar persegi panjang yang dikelilingi oleh koridor. Dengan mengingat hal itu, saya akan melakukan ini:

  1. Rancang koridor dan "ruang besar" untuk kamar
  2. Isi setiap "ruang besar" dengan kamar

2 langkah

Mengisi ruang besar dengan kamar dapat dilakukan dengan mudah jika Anda mulai dengan kamar di perbatasan - mereka memiliki kendala khusus, misalnya kamar yang menghadap koridor dapat memiliki pintu di dinding itu, tetapi kamar yang menghadap ke "dinding luar" tidak bisa (mereka bisa punya windows, mungkin). Kamar "di dalam" blok-blok besar kamar akan membutuhkan setidaknya satu pintu masuk.

egarcia
sumber
15

Jadi, inilah cara saya memecahkan masalah ini. Tapi pertama-tama, saya ingin mengucapkan terima kasih kepada @Shadows In Rain dan @egarcia atas jawaban mereka. Mereka memberi saya arahan yang baik yang membantu saya mendapatkan beberapa hasil.

Saya menggunakan partisi ruang Shadows In Rain untuk menghasilkan rumah dasar dan kemudian mengikuti saran egarcia untuk mengisi area dengan kamar.

Partisi ruang cukup mudah karena 90% dari kode dilakukan oleh Shadows. Bagian "isi kamar" sedikit lebih menantang. Saya memutuskan untuk menggunakan sistem AI Perencanaan palsu yang menggunakan A * untuk memposisikan kamar dengan tepat. Hal yang baik tentang menggunakan perencanaan dan bukan hanya A * adalah bahwa prasyarat membantu mengurangi ruang pencarian secara signifikan.

Berikut adalah beberapa tangkapan layar dengan hasilnya:

Tahap pembuatan denah lantai Tahap pembuatan denah lantai

Fase penempatan kamar Fase penempatan kamar

Sekarang dengan pintu penghubung!
Sekarang dengan pintu penghubung!

pek
sumber
11

Dahl & Rinde memiliki makalah tesis tentang Generasi Prosedural Lingkungan Dalam Ruangan yang menggunakan pendekatan kerangka & daerah untuk mengisi interior bangunan dengan kamar dan lorong. Makalah ini menyertakan diagram kelas untuk prototipe mereka. Ada juga beberapa referensi bagus dalam bibliografi mereka, termasuk A Pattern Language .

Pekerjaan mereka dirancang berdasarkan asumsi penyederhanaan berikut:

  • hanya berurusan dengan bangunan apartemen
  • tidak ada level split
  • pembatas bentuk bangunan (amplop) harus poligonal
  • tidak ada lubang di amplop
  • ketebalan amplop yang sama atau berubah secara linear (yaitu tidak ada bentuk jam pasir)
  • hanya berurusan dengan bangunan yang membutuhkan koridor

Berikut ini ikhtisar singkat proses mereka:

  • Temukan kerangka untuk amplop. Koridor kemudian ditempatkan di sepanjang kerangka berdasarkan jarak dari selubung, kedekatan dengan pintu atau tangga & kedekatan dengan koridor yang ditempatkan sebelumnya.
  • Selanjutnya, ruang non-koridor yang tersisa dipartisi menjadi area terhubung maksimum, masing-masing dengan batas kontinu tunggal. Dalam beberapa kasus, ini membutuhkan pemasangan dinding.
  • Daerah-daerah ini kemudian dibagi menjadi apartemen yang berusaha mengalokasikan setidaknya satu jendela per apartemen. Dalam beberapa kasus, divisi yang lebih kecil akan bergabung untuk menghindari apartemen yang terlalu kecil. Wilayah tanpa jendela diabaikan begitu saja.
  • Akhirnya, apartemen dibagi menjadi kamar-kamar menggunakan diagram seperti Voronoi tertimbang sebagai dasar sebagai berikut:

    • Bobot biji digunakan untuk mempengaruhi ukuran ruangan. Biji ditambahkan di pintu dan jendela. Benih tambahan ditambahkan, umumnya satu per kamar yang diinginkan; sementara tidak secara eksplisit dinyatakan, sepertinya benih ditempatkan di sepanjang dinding luar apartemen.
    • Dimulai dengan titik terjauh, garis antara benih yang diberikan & semua titik lainnya dihitung dan kemudian membagi jarak relatif terhadap masing-masing bobot titik akhir (EG jika A & B memiliki bobot 1 & 4, titik membagi dua akan menjadi 1/4 jalan dari A ke B). Kumpulan garis pembagi dua, bersama dengan dinding luar kemudian membentuk sel untuk benih.
    • Selanjutnya, kerangka dinding S-Space (sesuai Peponis et al 1997) dibuat dengan mempartisi area tersebut dengan garis-garis yang berasal secara tegak lurus dari titik tengah antara pasangan yang berdekatan dari fitur dinding luar (jendela atau pintu).
    • Akhirnya, dinding dipilih dari kerangka ruang-S yang 'sesuai dan mungkin dengan dinding sel Voronoi.'
Pikalek
sumber
3
Bisakah Anda memasukkan gambar? Itu akan bagus. Saya melakukan skim kertas dan kamar yang mereka hasilkan terlihat bagus dari POV arsitektur.
congusbongus
Metode yang sangat menarik, saya harus memeriksanya sendiri lebih dekat untuk setiap ide yang saya bisa ambil darinya.
Draco18s
Saya datang ke sini untuk bersantai dari pekerjaan ... Kejutan topik penelitian saya keluar. Saya terlalu malas untuk menulis jawaban berdasarkan penelitian saya sendiri (saya hanya mendesain tulang belulang algoirthm, jadi toh itu tidak layak) atau menggambarkan pendekatan Danil Nagy untuk masalah tersebut, jadi saya akan meninggalkan ini di sini autodeskresearch.com/publications/…
Felipe Gutierrez