Secara prosedural menghasilkan bangunan dari area tertentu

15

Saya dan tim sedang mengerjakan permainan pembuat pabrik yang memberikan pemain pabrik acak pada awal permainan. Untuk mencoba memastikan ada rasa "keadilan," idealnya pabrik yang dihasilkan secara acak akan memiliki area dalam beberapa unit (nilai placeholder) 30.

Ini relatif sederhana untuk menulis generator persegi panjang acak dasar untuk memenuhi spesifikasi ini, tetapi tujuan kami adalah agar pabrik menjadi lebih kompleks, mungkin terdiri dari 2, 3, atau bahkan 4 persegi panjang berpotongan, menghasilkan bentuk yang lebih kompleks (pikirkan L, Bangunan berbentuk U, dan O).

Saya sudah mencoba membuat persegi panjang acak dan kemudian menggunakan aljabar dasar untuk mengisi persegi panjang ke-2, tapi sejauh ini saya tidak beruntung menerapkan lebih dari 2 persegi panjang, dan bahkan kemudian saya tidak senang dengan hasilnya hanya untuk desain 2 persegi panjang. .

Beberapa info yang lebih relevan: 2D top down Beberapa mekanik adalah gaya faktorio sehingga kamar harus memiliki panjang dan lebar yang masuk akal untuk memungkinkan ruang untuk mesin Saat ini di Jawa dan Lua (dapat menggunakan perpustakaan built in baik jika diperlukan)

Terima kasih sebelumnya!

EDIT: Ketika saya mengatakan output "baik" atau "buruk", output yang buruk adalah output yang memiliki ruang yang tidak dapat digunakan oleh pemain. Batas bentuk pabrik di mana pemain dapat menempatkan mesin pabrik seperti ban berjalan. Idealnya, pabrik tidak boleh memiliki area yang hanya 1-2 blok lebar, bentuknya tidak boleh satu atau dua persegi panjang besar dengan garis 1-2 blok "menggantung" ke satu sisi. Output yang baik adalah di mana semua ruang lantai "bisa dikerjakan", sehingga semua area memiliki lebar setidaknya 3-4 blok. Output yang baik tidak selalu harus kompleks (1 atau 2 persegi panjang tidak apa-apa), tetapi harus memiliki peluang yang adil jika terdiri dari lebih dari 1-2 persegi panjang.

pengguna2129189
sumber

Jawaban:

7

Anda bisa menggunakan polyomino yang dibuat sebelumnya sebagai bentuk meta untuk membangun bermacam-macam bangunan.

Katakanlah jarak minimum yang dapat Anda terima adalah 3 blok. Maka unit bangunan terkecil yang dapat kami pertimbangkan adalah 3x3. Untuk kenyamanan, saya akan menyebutnya sel & memberi area 9 blok. Selanjutnya, ambil area awal target Anda & bagi dengan area sel. Dengan menggunakan nilai awal yang Anda berikan, kami mendapatkan 3,333; jadi 3 sel akan memberi Anda sedikit kurang dari yang Anda inginkan & 4 sel akan memberi Anda lebih banyak.

Dari sini Anda memiliki beberapa opsi. Jika Anda fleksibel pada area awal Anda, gunakan metode apa pun yang paling baik bagi Anda untuk memilih jumlah sel yang memberi Anda jumlah yang dapat diterima (yaitu pembulatan ke nilai terdekat, pembulatan, dll). Saya akan menyebut ini jumlah sel.

Selanjutnya, pilih polyomino secara acak dengan jumlah sel yang diinginkan. Ganti setiap kotak pada polyomino dengan sel pembangun & Anda memiliki bentuk akhir.

Sebagai ilustrasi, katakanlah kita memilih untuk membulatkan ke bawah. Berikut ini semua poliomino ukuran 3 (tidak termasuk rotasi / membalik):

masukkan deskripsi gambar di sini

Mari kita asumsikan kita secara acak memilih bentuk L & menerapkan rotasi acak, bangunan Anda akan memiliki tata letak berikut:

masukkan deskripsi gambar di sini

Beberapa masalah. Pertama, ada batasan jumlah sel yang bisa Anda gunakan. Wikipedia akan memberi Anda semua polyomino hingga ukuran 8 ( octomino ). Ini termasuk data ringkasan hingga ukuran 12, tapi saya tidak tahu apakah ada daftar online untuk semuanya. Kedua, solusi di atas hanya bekerja persis untuk ukuran bangunan yang merupakan kelipatan 9. Ada beberapa cara untuk mengatasi beberapa masalah ini:

1) Gunakan ukuran sel yang berbeda. Misalnya 3x4, 4x4, dll.

2) Tambahkan sel tambahan ke polyomino awal. Ini bisa rumit jika Anda harus memastikan semua bentuk memiliki kemungkinan yang sama, tetapi kemungkinannya untuk sebagian besar tujuan pembuat game Anda tidak perlu distribusi bentuk bangunan yang benar-benar seragam.

3) Pad out bangunan untuk membuatnya lebih besar. Kembali ke contoh, jika Anda menggunakan 3 sel, bangunan Anda akan memiliki luas 27 kotak yang membuat Anda kekurangan 3. Anda kemudian dapat memindai perimeter untuk lokasi untuk merekatkan sekelompok kotak ukuran 1x3. Selama grup rias Anda setidaknya AxB di mana A setidaknya jarak minimum yang dapat Anda terima, hasil Anda tidak akan melanggar batasan jarak minimum yang dapat diterima. Membangun contoh di atas, berikut adalah ilustrasi hasil yang mungkin:

masukkan deskripsi gambar di sini

4) Alih-alih membangun sebuah bangunan yang terlalu kecil, Anda bisa memangkas bangunan yang terlalu besar. Memastikan bahwa batasan jarak minimum yang dapat diterima Anda diikuti lebih kompleks daripada opsi padding, tetapi akan memberi Anda lebih banyak alternatif untuk dipertimbangkan.

Beberapa komentar lain:

Hanya karena Anda dapat menggunakan semua kemungkinan poliomino dari ukuran yang diberikan tidak berarti Anda harus melakukannya. Jika beberapa dari mereka tidak menyenangkan, hancurkan tema Anda, menyinggung audiens Anda (pola swastika), atau menyebabkan beberapa masalah lain, bawa keluar. Selain itu, Anda dapat mempertimbangkan rutinitas pilihan Anda jika beberapa pola menarik, tetapi terlalu aneh untuk muncul secara rutin. Akhirnya, Anda dapat menggunakan solusi ini dalam kombinasi dengan strategi Anda saat ini. Mungkin 70% dari waktu Anda menghasilkan bangunan persegi panjang & 30% dari waktu Anda menggunakan pendekatan polyomino. Atau mungkin Anda mulai dengan bangunan persegi panjang & lem polyomino kecil ke luar.

Pikalek
sumber
16

Cara sederhana untuk membangun generator prosedural adalah:

  1. Secara acak membangun sesuatu
  2. Jalankan fungsi yang memeriksa apakah outputnya bagus
  3. Jika outputnya tidak bagus, lanjutkan ke langkah 1

Sekalipun dibutuhkan ribuan proses untuk menyelesaikannya, sebagian besar generator sederhana berhasil dengan baik dengan pendekatan ini. Keuntungannya adalah tidak ada banyak kecerdasan yang diperlukan dalam generator, dan karena memeriksa apakah sesuatu yang baik jauh lebih mudah daripada membangun sesuatu yang baik 100% dari waktu, pendekatan ini sangat mudah.

Anda telah membuat daftar beberapa ukuran obyektif tentang apakah suatu output baik; itu sudah cukup bagi Anda untuk membuat generator yang cepat dan kotor. Tempatkan persegi panjang secara acak di dalam area, dan tolak output jika, misalnya, ada area yang hanya selebar 1-2 blok.

Mulailah dengan itu, perbaiki dan optimalkan sesudahnya.

congusbongus
sumber
Terima kasih! Saya ingat mempertimbangkan hal ini, tetapi pikiran bahwa ada kesempatan untuk beberapa detik waktu muat menghentikan saya. Sekarang saya menyadari betapa kecilnya peluang itu. Saya harus mencobanya, tetapi saya mungkin menunggu untuk melihat apakah seseorang memiliki solusi yang lebih langsung terlebih dahulu.
user2129189
@ user2129189 Ketika generator Anda aktif, Anda masih dapat mengubah rentang angka acaknya untuk menghindari menghasilkan tata letak yang tidak mungkin lulus uji. Juga dimungkinkan untuk memparalelkan algoritma generasi percobaan-dan-kesalahan ini pada beberapa core dengan meminta setiap core menghasilkan satu layout pada satu waktu.
Philipp
3
Saya sendiri bukan penggemar metode menolak dan mencoba lagi. Mereka cukup cepat ketika generator Anda melakukan hanya satu hal sederhana, tetapi untuk level game biasanya kita mulai melapiskan lebih banyak fitur dan langkah generasi untuk membuat peta yang lebih kaya. Pada titik itu, probabilitas untuk memukul peta yang layak adalah produk dari probabilitas setiap langkah yang berhasil, yang dapat menyusut dengan cepat. Ini bukan hanya masalah akademis - Saya sudah bicara dengan para devs yang harus menerapkan sistem caching benih yang baik / buruk untuk menghindari waktu pembuatan berlebih, ketika generator lintasan tunggal yang benar dengan konstruksi akan lebih mudah.
DMGregory
@ DMGregory ya saya pasti bisa melihatnya. Generator acak dasar akan bekerja seperti 99% dari waktu dalam beberapa lintasan untuk kasus saya, tetapi jika saya ingin menambahkan lebih banyak kerumitan nanti, itu bisa melambat secara signifikan. Adakah yang tahu tentang aplikasi pemrograman / permainan kehidupan nyata dari model tebak dan seperti cek?
user2129189
Mungkin ada tingkatan fungsi generasi dan pemeriksaan, berhati-hati untuk mencocokkan ungkapan kondisi dengan tingkat generasi saat ini. Dengan begitu, seluruh level tidak perlu dihasilkan kembali secara keseluruhan hanya dari kesalahan yang ditemukan menempatkan item sedikit salah.
Pysis
7

Mengingat batasan "semua area setidaknya memiliki lebar 3-4 blok" ide pertama yang muncul di benak saya adalah sesuatu seperti berikut:

  1. pilih salah satu dari 3x3, 3x4, 4x3 atau 4x4
  2. letakkan balok sebesar itu di tengah-tengah kisi
  3. pilih arah (atas, kiri, kanan, bawah)
  4. coba letakkan blok 3x3 di samping blok yang sebelumnya ditempatkan ke arah itu
  5. jika berhasil, dengan beberapa kemungkinan, cobalah untuk memperluas blok ke blok 4x3 di salah satu arah yang tidak Anda pilih
  6. dengan beberapa probabilitas, pindahkan a ke tepi acak dari blok yang diisi
  7. ulangi langkah 3 hingga 6 hingga area cukup besar

Ide dasarnya adalah, mengingat Anda ingin semua area memiliki setidaknya ukuran tertentu, hanya bekerja di area dengan ukuran tersebut. Lebih umum, jika Anda ingin sesuatu menjadi benar dari semua output yang dihasilkan, lihat apakah itu dapat dibuat benar dari semua output yang dihasilkan sebagian.

Ryan1729
sumber
4
Saya menyederhanakan segala sesuatunya dengan selalu mulai dari blok 3x3, lalu menambahkan blok 3x1 dalam posisi acak di mana setiap kotak berdekatan dengan yang sudah ada. Menambahkan ke blok 3x3, ada empat posisi yang memungkinkan. Semua memberi Anda blok 3x4, dengan enam posisi yang memungkinkan untuk yang berikutnya. Dari sana semakin rumit, tapi tidak terlalu buruk.
JollyJoker
0

Pertimbangkan untuk menggunakan booleans NOT dan UNION dan memilih di antara mereka secara acak.

  1. Tempatkan persegi panjang acak.
  2. Tempatkan persegi panjang acak kedua.
  3. Pilih secara acak apakah akan menyatukan mereka atau MENGUNDANG yang kedua dari yang pertama.
  4. Ulangi untuk beberapa persegi panjang. Meskipun, hanya dua atau tiga yang dapat memberikan hasil yang cukup masuk akal.

Kemudian, saya akan menghitung luas dan skala itu naik atau turun untuk lebih cocok dengan ukuran perkiraan yang Anda cari, dan kemudian menguji bahwa tidak ada dimensi kurang dari jumlah minimum yang diperlukan.

Gurita
sumber
Gagasan penskalaan Anda untuk mendapatkan area yang diinginkan sebenarnya cukup cerdas. Saya mungkin menerapkan sesuatu yang agak tenang seperti ini.
user2129189