Sebagai contoh mengambil peta hex besar (X oleh Y), bagaimana saya bisa membaginya menjadi N wilayah heks terhubung untuk mensimulasikan negara?
Tujuannya adalah untuk menghasilkan peta hex yang terlihat seperti peta kehidupan nyata dengan negara-negara dengan bentuk yang berbeda tetapi ukurannya sama.
mathematics
maps
hexagonal-grid
MadCatPT
sumber
sumber
Satu cara sederhana yang bisa Anda coba.
n
heks secara acak . Masing-masing akan memulai grup.Saya tidak menguji tetapi ini harus menghasilkan Kepulauan dan agak menghindari kawat gigi tipis panjang. Juga, Kemungkinan besar akan ada perbatasan tetangga tetapi belum tentu masing-masing akan berhubungan dengan yang lain, kepadatan itu akan tergantung pada nilai
n
.Beberapa kelompok juga mungkin terpojok oleh yang lain dan mencapai ukuran kurang dari 20, Anda dapat memastikan ruang tumbuh dengan menelurkan heks starter pada jarak minimum satu sama lain.
Tes dan atur sesuai kebutuhan.
Juga, tidak terkait dengan masalah ini tetapi sangat, sangat berguna untuk bekerja dengan hexes, kunjungi halaman ini: http://www.redblobgames.com/grids/hexagons/#basics
Ini mengumpulkan sejumlah besar informasi hex di satu tempat dengan visual yang bagus.
sumber
Saya pasti berpikir beberapa jenis struktur grafik akan memungkinkan ini. Pada dasarnya buat tepi antara dua node Hex jika mereka bersebelahan untuk mensimulasikan seluruh peta. Namun, saya tidak yakin algoritma yang tepat untuk menghasilkan "negara" di dalam peta itu. Masalahnya adalah, tergantung pada bagaimana Anda ingin negara "terlihat" Anda akan membutuhkan algoritma yang berbeda.
Dari atas kepala saya, saya akan merekomendasikan memilih titik dan bergerak keluar dari sana, memilih ubin acak di dalam "negara berkembang" Anda yang memiliki ubin berdekatan yang bukan bagian dari negara.
Pola strategi dapat digunakan untuk mengganti algoritma tergantung pada jenis negara apa yang Anda inginkan. http://en.wikipedia.org/wiki/Strategy_pattern yaitu Anda ingin negara garis pantai ramping seperti Chili? Atau Anda menginginkan sesuatu yang lebih bulat dan berisi?
Properti grafik juga memungkinkan Anda mengubah apa yang Anda inginkan sebagai "negara" akhir: http://en.wikipedia.org/wiki/Eccentricity_(graph_theory)
Ingin negara besar? Tweak properti grafik dan paksa negara yang dihasilkan (yang hanya berupa grafik) untuk memiliki properti yang memberikan "tampilan" yang Anda inginkan.
Last but not least, Grafik juga akan sangat berguna untuk mendefinisikan perbatasan antar negara. Anda bisa membuat grafik yang memiliki koneksi antara dua node jika negara saling berbatasan. Ini mungkin berguna untuk beberapa jenis partisi di game Anda dan akan memungkinkan Anda untuk mengoptimalkan beberapa hal lebih lanjut dalam pengembangan.
sumber
Satu catatan kecil: Anda mengatakan 'terlihat seperti peta kehidupan nyata dengan negara-negara yang bentuknya berbeda tetapi ukurannya sama), tetapi negara-negara' nyata 'sangat berbeda ukurannya bahkan di dalam wilayah tertentu - bahkan negara-negara' besar 'di Eropa dapat sangat bervariasi, misalnya dengan Perancis lebih dari dua kali lebih besar dari Italia. Dengan begitu, jelas ada wilayah permainan untuk mencoba dan mempertahankan ukuran kira-kira sama - hanya perlu diketahui bahwa sedikit variasi di sini mungkin bagus hal yang !
Pendekatan awal saya untuk masalah ini adalah untuk 'mengembangkan' (bukan 'menumbuhkan') wilayah Anda:
Sekarang, selama yang Anda inginkan, jalankan pseudocode berikut:
Ini akan menjaga keseimbangan antara ukuran dua negara tetangga, dan cek 'terputus' (yang dapat dilakukan dengan algoritma pengisian banjir sederhana) memastikan bahwa tidak ada negara yang pernah terbelah menjadi beberapa bagian. Memperbarui daftar batas adalah operasi waktu konstan - hex yang diubah jelas akan selalu berada di batas, dan Anda bisa memeriksa enam tetangganya untuk melihat apakah ada di antara mereka yang telah menjadi sel batas (karena tetangganya sekarang ada di batas negara yang berbeda) atau berhenti menjadi sel batas (karena tetangganya ada di negara yang sama sekarang), memodifikasi batas yang ditetapkan sesuai kebutuhan.
Untuk penyempurnaan dari pendekatan ini, Anda bahkan dapat membuat kondisi hex mana yang berubah sedikit acak - daripada selalu 'menyeimbangkan' kedua negara, Anda selalu dapat membuat swap dengan probabilitas tertentu, dan bahkan secara bertahap mengurangi probabilitas itu lebih dari waktu (mirip dengan proses pendinginan dalam algoritma Annealing Simulatif ) untuk mulai memaksa mereka untuk ukuran yang kira-kira sama.
Perhatikan bahwa ini tidak akan menjamin bahwa semua area berukuran persis sama (yang tidak mungkin kecuali N tetap membagi ukuran grid Anda dengan sempurna), dan itu bahkan tidak akan menjamin bahwa semua negara berada dalam satu hex satu sama lain di area; itu harus menjamin (berjalan selama cukup iterasi) bahwa setiap negara tidak lebih dari satu hex lebih besar atau lebih kecil dari masing-masing tetangganya, meskipun.
sumber