Bagaimana cara membagi hex grid secara merata di antara n pemain?

15

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?

manabreak
sumber
Cellata automata adalah cara sederhana, mirip dengan ini: Peta sederhana, empat bioma, dan cara mendistribusikannya
MichaelHouse

Jawaban:

3

Inilah yang akan saya lakukan:

  1. Tetapkan semua sel ke pemain acak. Pada peta besar, ini seharusnya sangat mungkin untuk menghasilkan jumlah ubin yang cukup merata untuk semua pemain, pada peta yang lebih kecil Anda mungkin perlu melakukan beberapa koreksi.
  2. Pecah bongkahan yang terlalu besar. Hal termudah untuk dilakukan adalah mengambil semua ubin dalam potongan dan menetapkan lagi setiap ubin secara acak.
  3. Dalam hal jumlah sel yang tidak seimbang (mis. Pemain A memiliki 24 sel, pemain B memiliki 16 sel), menugaskan kembali beberapa sel dari pemain yang terlalu terwakili ke pemain yang kurang terwakili.
  4. Periksa lagi untuk potongan. Jika langkah 3 memperkenalkan bongkahan baru, kembali ke langkah 2. Jika tidak, peta bagus!
Junuxx
sumber
PS Saya tidak berpikir masalah ini tidak pernah mungkin, masalah pewarnaan peta sangat berbeda (untuk satu hal itu sebaliknya, bentuk-> warna alih-alih warna-> tugas ubin).
Junuxx
Saya suka pendekatan ini cukup banyak, tetapi tidak adakah kemungkinan untuk itu berjalan untuk waktu yang lama, mencoba menyeimbangkan ukuran area?
manabreak
1
@manabreak: Saya membuat sesuatu untuk mencobanya. Dengan perubahan kecil ke langkah 2 (ditugaskan kembali dengan bersepeda melalui semua pemain alih-alih ditugaskan kembali secara acak) itu bekerja dengan cukup baik. Saya akan mencoba menuliskannya ketika ada waktu.
Junuxx
1
Itu terlihat persis seperti apa yang saya cari. :)
manabreak
1

Dengan asumsi Anda memiliki hexmap nsel secara total, dan ppemain, di mana p <= 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. Sejakp <= n , ini seharusnya tidak menjadi masalah.

Automata seluler

Anda memerlukan konektivitas penuh antara sel hex Anda. Saya akan menyarankan array 6-tetangga per sel:

class Cell
{
   //... other members...
   Cell[6] neighbours = new Cell[6];
}

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:

count number of neutral cells in entire map, minus those starting cells taken by players
while neutral cells remain (or while true)
   for each player
      if player has not yet reached expected territory size in cells
         for each cell already constituting this player's territory
           if territory can grow by one cell into a neutral neighbour
              grow into neighbour
              reduce neutral cell count for entire map by one
              if no more neutral cells remain in map
                 break out of outermost while loop immediately
              else
                 continue to next player immediately
begin game

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.

Insinyur
sumber
Meskipun Anda memberikan dokumentasi dan pseudocode yang sangat baik untuk algoritma Anda, saya tidak yakin ini cocok dengan apa yang ditanyakan si penanya. Pertanyaannya menyebutkan 'bongkahan terbesar' masing-masing tidak boleh lebih dari empat sel, sedangkan algoritma Anda menciptakan kelompok terhubung sebanyak mungkin.
fnord
@nord Tidak, tidak. Anda tidak membaca jawaban saya dengan benar. Saya secara eksplisit menetapkan batas dalam pseudocode: "jika pemain belum mencapai ukuran wilayah yang diharapkan dalam sel". Harap hapus downvote Anda. Jangan ragu untuk memeriksa riwayat revisi pada pertanyaan untuk meyakinkan diri sendiri bahwa ini adalah masalahnya sejak sebelum komentar dan downvote Anda.
Insinyur
Pertanyaannya meminta memiliki "tidak lebih dari empat sel yang berdekatan", namun untuk setiap pengguna memiliki bagian peta yang diharapkan. Ini, bagi saya, menyiratkan bahwa e akan mencari sesuatu yang lebih mirip dengan bagaimana game Risiko membagi-bagikan peta secara acak untuk semua pemain. Jawaban Anda membagi peta menjadi "wilayah rumah" yang berukuran maksimal "". Benar, algoritme Anda berhenti ketika batas ukuran wilayah yang diharapkan tercapai, tetapi saya tidak melihat cara bagi pemain itu untuk mendapatkan "pulau" baru, meskipun Anda menyebutkannya dalam teks selanjutnya.
fnord
@fnord Logika Anda salah. Dalam kalimat terakhir Anda, Anda mengakui bahwa algoritme saya berhenti pada ukuran pulau 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 membatasi n1) 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?
Insinyur
Saya akan mengedit komentar saya di atas, tetapi sudah terlambat. "Saya tidak melihat cara dalam algoritme Anda ". meskipun Anda menyebutkan konsep dalam teks selanjutnya.
fnord
0

Pendekatan lain akan dimulai dengan distribusi yang 'adil' tapi teratur, dan kemudian menggunakan appraoch mirip dengan Simulated Annealing untuk memecah keteraturan tanpa kehilangan keadilan:

  • Mulailah dengan menetapkan warna ke semua sel kisi Anda dalam pola reguler (misalnya, memiliki pola '123412341234' berulang di baris pertama, diikuti oleh '341234123412' di baris berikutnya, dll.). Hal ini dapat menyebabkan distribusi non-seragam warna jika peta Anda terutama buruk berbentuk, tapi aku menganggap bahwa Anda mulai dengan peta tetap, sehingga Anda harus dapat menemukan beberapa pewarna biasa equidistributed itu.
  • Kemudian ulangi langkah-langkah berikut untuk sebanyak mungkin langkah yang Anda inginkan (tidak ada kriteria 'kematangan' yang nyata, jadi eksperimen akan memberi tahu Anda berapa langkah minimum yang masuk akal):
    • Pilih dua elemen dari grid secara acak
    • Jika mereka memiliki warna yang sama, coba lagi (tidak ada gunanya sebaliknya, sejak itu bertukar akan menjadi no-op. Anda hanya memiliki peluang 1/4 memukul warna yang sama, dan peluang 1/16 mengenai memukul warna yang sama dua kali berturut-turut, jadi Anda tidak perlu mencoba terlalu banyak)
    • Tukar warna kedua elemen tersebut secara sementara
    • Uji ukuran daerah yang baru terbentuk di lokasi elemen setelah swap:
      • lakukan pengisian banjir sederhana keluar dari tempat baru setiap elemen untuk menentukan seberapa besar wilayah dengan warna yang akan dibuat swap.
    • Jika salah satu dari kedua wilayah ini lebih besar dari ambang Anda, batalkan swap sementara; jika tidak, 'selesaikan' swap warna kedua elemen '.

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.

Steven Stadnicki
sumber
Pendekatan stokastik tidak efisien. Untuk pendekatan seperti saya yang mengambil langkah-langkah yang dipertimbangkan, runtime mendekati O (n) untuk n memetakan sel. Untuk algoritme Anda, ini O (n * m), di mana m adalah jumlah sel yang diinginkan per pulau (sebenarnya, untuk setiap pulau potensial). Selalu yang terbaik untuk membidik algoritma yang memiliki runtime yang siap diperkirakan. Alih-alih memperbaiki peta yang dibuat sembarangan, lebih baik untuk menghasilkan peta yang tidak rusak atau serampangan di awal, dalam n langkah, sehingga menjaga proses yang terkontrol dan efisien.
Insinyur