Secara prosedural menghasilkan daerah di pulau

29

Saat ini saya memiliki pulau yang terlihat seperti ini:

pulau

Dan saya ingin membagi secara prosedural ke daerah, seperti ini:

pulau dengan daerah

Algoritme apa yang saya cari? Apakah Anda punya saran tentang cara membuat wilayah yang koheren seperti di gambar bawah. Bantuan Anda dihargai.

domisum
sumber
Bagaimana Anda mendapatkan citra pulau itu? Apakah Anda menghasilkannya, dan jika demikian, bagaimana Anda mencapainya?
Vaillancourt
Saya mendapatkannya dari generator peta online.
domisum
Maaf atas keterlambatan memperbarui jawaban saya - butuh waktu lebih lama untuk pulang daripada yang direncanakan. Saya menambahkan beberapa ilustrasi & tautan.
Pikalek
Jika Anda mendapatkannya dari generator online, Anda harus melihat Generator Peta Fantasi Azgaar . Ini memiliki wilayah dan nama, dengan parameter yang dapat disesuaikan, dan WB.SE menyapa. Ini github, jadi Anda mungkin dapat memeriksa kode mereka.
Anoplexian

Jawaban:

40

Di dunia nyata, perbatasan provinsi itu akan sering mengikuti fitur geologis seperti sungai.

Jadi mungkin pendekatan yang baik adalah dengan memodelkan geologi pulau dan membuat perbatasan jatuh dari ini?

Red Blob Games memiliki beberapa artikel bagus tentang hal ini, dengan hasil yang terlihat bagus.

Nya pendekatan tampaknya melibatkan menggunakan Voronoi tessellation , dan menentukan sungai sebagai batas-batas antara sel-sel.

Lihat artikel-artikel lain di situsnya, ia telah banyak menulis tentang masalah pembuatan peta .

pulau

Bram
sumber
3
Perhatikan bahwa di dunia nyata, divisi politik atau administratif juga terkadang memiliki divisi sewenang-wenang, biasanya garis lurus (misalnya sepanjang garis latitud / longitud, garis antara puncak gunung, dll.).
Pablo H
2
@PabloH Poin bagus, meskipun garis lurus tampaknya merupakan fenomena era kolonial pasca-mediaval. Tapi karena kita tidak tahu pengaturan masalah OP, mungkin relevan
Sentry
27

Saya akan memecahkan masalah ini dengan dua lintasan diagram Voronoi:

Lulus Pertama: Partisi Wilayah

Lulus pertama akan menggunakan distribusi titik yang agak jarang (yaitu jarak antara titik-titik tersebut harus relatif besar) untuk membagi pulau secara kasar menjadi beberapa wilayah (lihat catatan di bawah mengenai pembangkitan titik). Selanjutnya buat diagram Voronoi berdasarkan poin-poin ini. Ini akan membagi pulau menjadi daerah poligon di sekitar setiap titik seperti yang ditunjukkan di bawah ini:

masukkan deskripsi gambar di sini

Lulus Kedua: Pengacakan Batas

Sekarang pulau itu telah dibagi menjadi beberapa wilayah, maka langkah selanjutnya adalah 'mengacaukan' batas antara mereka. Untuk melakukannya, hasilkan lapisan poin baru menggunakan distribusi titik yang lebih kompak (yaitu jarak antara titik harus kecil) dan lagi gunakan titik-titik ini untuk membuat diagram Voronoi lain. Selanjutnya untuk setiap wilayah yang lebih kecil, tetapkan ke wilayah yang lebih besar dengan memeriksa titik 'seed' -nya. Ini akan menghasilkan batas yang lebih bergerigi antara subdivisi yang lebih besar. Berikut ini adalah tampilan dari apa yang tampak dengan kedua diagram Voronoi:

masukkan deskripsi gambar di sini

Dan inilah area yang sama yang hanya menunjukkan batas akhir:

masukkan deskripsi gambar di sini

Komentar tentang Point Generation

Mengenai pembuatan poin, saya suka menggunakan distribusi disk Poisson untuk mendapatkan distribusi poin yang relatif bagus & merata. Pilihan umum lainnya adalah untuk mendapatkan distribusi genap yang sama adalah dengan menggunakan algoritma Lloyd pada set poin acak 'reguler'. LLoyd lebih mudah untuk dikodekan, tetapi dapat mengambil beberapa percobaan & kesalahan untuk menentukan berapa banyak pass yang diperlukan untuk memberikan hasil yang diinginkan.

Satu potensi masalah dengan pendekatan ini adalah bahwa partisi pass pertama dapat menghasilkan beberapa daerah yang sangat kecil. Jika Anda tidak menginginkan mereka dalam hasil akhir Anda, saya hanya akan menggabungkannya dengan wilayah yang berdekatan secara acak.

Catatan Akhir

Ilustrasi yang saya berikan kebetulan merupakan gambar raster, tetapi teknik ini juga berfungsi dengan representasi poligon / vektor.

Pikalek
sumber
1
Untuk denah lantai prosedural inilah yang saya lakukan, lakukan diagram Voronoi dari titik-titik di dalam wilayah (pulau), buat kisi-kisi (tidak harus persegi panjang, untuk kasus Anda kisi-kisi cacat) yang melingkupi wilayah yang sama kemudian menghitung persimpangan boolean dari kisi dan Voronoi, menghitung area dan menetapkan ke pohon data (daftar daftar, array bergerigi, dll ... struktur data apa pun yang Anda inginkan) sesuai dengan persentase 0,6 dari sel kotak terkecil, Anda akan mendapatkan beberapa sel yang hilang, tetapi Anda dapat membandingkan kisi yang dimusnahkan dengan yang asli untuk ditemukan dan dipindahkan ke pohon Anda.
Felipe Gutierrez
Anda menambahkan gambar! Inilah yang saya lakukan untuk tujuan yang berbeda
Felipe Gutierrez
4

MineCraft melakukan ini dengan baik, dan algoritma generasi dunianya telah dianalisis dan didokumentasikan secara menyeluruh.

Ada berbagai deskripsi algoritma, salah satunya di sini: https://github.com/UnknownShadow200/ClassiCube/wiki/Minecraft-Classic-map-generation-algorithm

Inti dari algoritma ini adalah generator noise Perlin . Ini mengontrol ketinggian secara langsung (lebih atau kurang, karena langkah selanjutnya untuk mengukir gua dapat mengubah permukaan juga), serta generasi bioma. Sesuatu seperti generator bioma mungkin adalah apa yang ingin Anda gunakan untuk membuat area Anda.

(Versi lama) didokumentasikan , pada dasarnya ia bekerja dengan menggunakan dua generator Perlin Noise yang berbeda, satu untuk "suhu", satu untuk "presipitasi", lalu memilih bioma dari keduanya. Variabel itu sendiri (suhu dan curah hujan) tidak benar-benar digunakan dalam permainan nanti; misalnya, gurun tidak memiliki hujan, tetapi permainan menentukan ini dari properti "gurun", bukan dari nilai curah hujan asli.

Ada berbagai alat online untuk menghasilkan peta bioma dari benih acak, salah satunya adalah mineatlas.com . Saya kira itu, secara internal, mereka menggunakan server java yang menggunakan kelas internal MineCraft itu sendiri; Saya tidak tahu apakah ada kode sumber mereka yang tersedia secara langsung.

Guntram Blohm mendukung Monica
sumber
4

Algoritma tipikal yang digunakan, misalnya, oleh Azgaar ( kode sumber ). Kira-kira seperti ini:

  1. Bagi daratan Anda menjadi area yang lebih kecil, misalnya melalui triangulasi delauny atau sel voronoi.
  2. tentukan (secara acak atau tidak langsung) lokasi "permulaan" untuk budaya, alam, agama atau apa pun yang ingin Anda tiru.
  3. tentukan (secara acak atau tidak) "faktor pertumbuhan" untuk masing-masing faktor tersebut. Semakin banyak perbedaan dalam faktor pertumbuhan yang Anda miliki, semakin tidak seragam peta akhir Anda.
  4. Sekarang beralih ke wilayah Anda (dll) dan, tergantung pada faktor pertumbuhan, buat mereka menyebar ke sekitarnya, ubin kosong sampai seluruh peta diisi.
  5. Anda mungkin ingin mengakhiri sedikit dengan meluruskan batas, dengan mengganti sel yang hanya memiliki satu tetangga dalam warna mereka sendiri dan sebaliknya dikelilingi oleh yang berbeda dengan warna itu.
Tom
sumber
3

Jika Anda tertarik melakukan ini dalam format vektor daripada pendekatan berbasis raster, saya telah menulis posting blog beberapa waktu yang lalu tentang hal ini.

http://blog.particracy.com/worlds-and-their-geography/

Idenya adalah Anda mulai dengan jaring (biasanya berbasis Voronoi) dan menumbuhkan daerah secara konsentris dari titik yang diunggulkan secara acak yang berjarak cukup terpisah.

Wouter Lievens
sumber
2

Apa pertanyaan yang menyenangkan :) Pendekatan ini agak didasarkan pada sel Vornoi tetapi metrik jarak tidak cukup Euclidian (saya menggunakan kekuatan 1,5 bukannya 2.0) dan memiliki beberapa keacakan dibangun ke dalamnya. Mungkin melompati air yang tidak ideal.

Daerah terdekat dapat digabung bersama untuk mendapatkan bentuk yang lebih menarik, di sini saya menggunakan N tetangga terdekat untuk menentukan ini.

Jika Anda tertarik, saya bisa masuk ke rincian lebih lanjut dan berbagi kode Python.

peta 1 peta 2

NikoNyrh
sumber