Saya membuat game berbasis hex grid sederhana, dan saya ingin peta dibagi secara merata di antara para pemain. Peta dibuat secara acak, dan saya ingin para pemain memiliki jumlah sel yang sama, dengan area yang relatif kecil. Misalnya, jika ada empat pemain dan 80 sel di peta, masing-masing pemain akan memiliki sekitar 20 sel (tidak harus akurat di tempat). Selain itu, setiap pemain harus memiliki tidak lebih dari empat sel yang berdekatan. Dengan kata lain, ketika peta dibuat, "potongan" terbesar tidak boleh masing-masing lebih dari empat sel.
Saya tahu ini tidak selalu mungkin untuk dua atau tiga pemain (karena ini menyerupai masalah "mewarnai peta"), dan saya OK dengan melakukan solusi lain untuk mereka (seperti membuat peta yang menyelesaikan masalah sebagai gantinya). Tapi, untuk empat hingga delapan pemain, bagaimana saya bisa mendekati masalah ini?
sumber
Jawaban:
Inilah yang akan saya lakukan:
sumber
Dengan asumsi Anda memiliki hexmap
n
sel secara total, danp
pemain, di manap <= n
, cara terbaik untuk mengatasi hal ini adalah melalui distribusi round-robin melalui seluler automata (CA).Inisialisasi
Secara acak (dan / atau menggunakan beberapa atau heuristik lain, seperti jarak dari pusat peta) pilih sel awal untuk setiap pemain. Sejak
p <= n
, ini seharusnya tidak menjadi masalah.Automata seluler
Anda memerlukan konektivitas penuh antara sel hex Anda. Saya akan menyarankan array 6-tetangga per sel:
Penggunaan array ukuran tetap memungkinkan konsep arah topografi antar sel ada, yang tidak akan ada dalam daftar atau vektor. Saya merekomendasikan ini, karena dapat membuat operasi navigasi tertentu lebih mudah.
Anda juga dapat menyimpan hexmap Anda dalam array 2D, dengan offset per baris. Namun ini mungkin sedikit kurang intuitif daripada menyimpan array tetangga per sel, hanya karena offset geometris pada setiap baris lainnya.
Pastikan setiap sel terhubung ke semua yang tetangga. Anda dapat melakukan baris ini demi baris, sel demi sel saat Anda menghasilkan hexmap penuh. NB. Jika pada akhirnya Anda menginginkan hexmap yang tidak dibatasi empat persegi panjang, Anda dapat dengan mudah menghapus masing-masing sel dan referensi ke sel-sel tersebut, untuk membentuk ruang negatif, memungkinkan Anda untuk membuat garis besar peta organik.
Distribusi round-robin
Kodesemu:
Algoritma ini akan memberikan setiap pemain kesempatan untuk menumbuhkan wilayahnya satu per satu, secara bundar, asalkan wilayah pemain masih memiliki ruang tumbuh yang valid. Jika pemain tertentu diblokir dari tumbuh lebih lanjut, algoritma akan terlepas dari ini terus menumbuhkan wilayah pemain yang melakukannya masih memiliki ruang tumbuh valid. Anda dapat dengan mudah membatasi setiap pemain ke jumlah sel yang sama segera setelah salah satu dari mereka mencapai batas, tetapi itu seharusnya cukup mudah bagi Anda untuk mencari tahu, jika diinginkan.
Ini akan memberikan "wilayah rumah" berukuran maksimal untuk setiap pemain. Jika Anda ingin memiliki wilayah "pulau" sebagai tambahan, untuk memenuhi kuota jumlah sel untuk pemain itu, maka setelah pemain kehabisan ruang lokal untuk tumbuh, Anda kemudian dapat memilih sel awal baru dari daftar sel netral dan lanjutkan dengan proses "pertumbuhan" yang sama, dari sana. Dengan cara ini, Anda akan berakhir dengan set pulau yang berukuran bagus dan koheren untuk masing-masing pemain, daripada kebisingan acak.
sumber
n
, dan setelah itu bertentangan dengan diri Anda dengan mengatakan bahwa Anda "tidak melihat cara" namun saya memang "menyebutkan [cara mendapatkan pulau] dalam teks selanjutnya". Sudahkah saya atau belum saya jawab pertanyaannya? Algoritma umum ini dapat digunakan untuk menyebarkan sel (dengan membatasin
1) atau membuat pulau (dengan menetapkan n> 1). Jadi, Anda memiliki, dalam satu algoritma tunggal, tidak hanya kemampuan untuk menyebar, tetapi juga ke grup. Bagaimana ini tidak menjawab pertanyaan OP? Bagaimana layaknya downvote?Pendekatan lain akan dimulai dengan distribusi yang 'adil' tapi teratur, dan kemudian menggunakan appraoch mirip dengan Simulated Annealing untuk memecah keteraturan tanpa kehilangan keadilan:
Kuncinya di sini adalah kenyataan bahwa Anda bertukar dua tempat berarti Anda tidak pernah menyeimbangkan warna, dan juga tes yang Anda lakukan sebelum menyelesaikan swap Anda memastikan bahwa Anda tidak pernah membuat daerah yang terlalu besar. Jika Anda memiliki beberapa cara untuk menampilkan kisi-kisi Anda, Anda bahkan dapat memvisualisasikan proses ini untuk menyaksikan bagaimana ia 'membangun' wilayahnya melalui swap berulang.
Jika Anda tidak dapat memulai dengan pewarnaan biasa yang disumbangkan secara merata, secara kebetulan, maka Anda harus tetap dapat melakukan sesuatu yang serupa dengan menyamakan distribusi pewarnaan: sementara pewarnaan Anda tidak merata, pilih suatu unsur secara acak; kemudian, jika itu adalah salah satu warna yang terlalu terwakili, tentukan warnanya untuk salah satu warna yang kurang terwakili dan kemudian periksa untuk memastikan bahwa itu tidak membuat wilayah warna baru yang terlalu besar.
sumber