Pembuatan peta acak - strategi untuk hamburan / pengelompokan node acak

Saya sedang melakukan permainan strategi 4X sederhana di ruang angkasa di mana setiap node adalah point-of-interest (planet, asteroid dan lain-lain).

Untuk menghasilkan peta secara acak, saya akan mengikuti langkah-langkah di bawah ini

1. Putuskan berapa banyak jenis setiap node yang akan dimiliki peta (mungkin, katakanlah, 5 planet mirip Bumi, 10 planet gundul, dll.)

2. Tempatkan setiap jenis simpul pada peta.

Untuk langkah 2 saya ingin memiliki penyebaran yang merata dari setiap jenis simpul. Jadi misalnya, saya akan mulai dengan menempatkan semua planet yang menyerupai bumi. Jika saya cukup melakukan rand (map.width, map.height) untuk menentukan posisi, saya mungkin berakhir dengan semua planet yang mirip bumi yang bersatu, yang akan memberi keuntungan bagi pemain yang memulai di area itu.

Apakah ada metode, seperti menggunakan fungsi grafik yang berbeda atau fungsi noise, yang dapat menghasilkan urutan koordinat (x, y) yang tersebar dari satu sama lain. Demikian juga, adakah cara untuk menghasilkan koordinat yang dekat satu sama lain?

Masalah yang Anda hadapi adalah bahwa pemilihan acak tidak membeda-bedakan, dan itu bisa berarti bahwa itu kurang cocok untuk apa yang perlu Anda lakukan. Tapi, setidaknya ada satu cara mudah untuk mengatasi ini:

1. Bagilah ruang Anda menjadi beberapa sektor (mis., Jika Anda memiliki luas 100 hingga 100, dan Anda perlu menghasilkan 100 dari sistem tata surya ini, maka bagi wilayah Anda menjadi 10 dengan 10 kotak sektor)

2. Ulangi setiap Sektor dan ulangi langkah 3 (yang pada gilirannya akan mengulangi langkah 4 beberapa kali)

3. Secara acak tentukan jumlah planet untuk tata surya saat ini (mis. Untuk kisaran 3 hingga 7 planet, dapatkan saja angka acak mulai dari 0 hingga 4, dan tambahkan 3) di Sektor saat ini (jika Anda memiliki lebih dari satu matahari sistem dalam suatu sektor, ini adalah tempat Anda akan mengatur lingkaran lain)

4. Tetapkan planet Anda secara acak dalam Tata Surya saat ini yang diidentifikasi oleh loop Anda (Anda juga dapat menggunakan angka acak untuk meningkatkan jarak minimum antar planet); di sinilah Anda akan menentukan jenis planet, yang juga dapat ditentukan secara acak dengan berbagai bobot atau metode apa pun yang Anda sukai untuk digunakan

Anda mungkin juga ingin mendefinisikan area "di luar batas" di sekitar tepi setiap sektor untuk mencegah planet-planet dari sektor tetangga melakukan kontak langsung satu sama lain (kalau-kalau mereka secara efektif terletak berdampingan secara acak), atau. ..

Solusi lain mungkin pada titik menentukan lokasi setiap tata surya dan / atau setiap planet, untuk hanya menjalankan pemeriksaan kedekatan cepat terhadap sektor-sektor tetangga dan menyesuaikan sesuai (misalnya, menjauh dari tepi dengan jarak minimum ditambah jarak acak) ).

Cara terbaik untuk memastikan pemerataan adalah dengan memperlakukan setiap simpul sebagai semacam partikel fisik. Pertama lakukan distribusi acak melintasi bidang xy kontinu (titik mengambang). Dengan menerapkan gaya tolak antara masing-masing pasangan partikel individu di pesawat, Anda akan menemukan mereka perlahan-lahan menyebar terpisah. Dalam arti itu seperti resolusi tabrakan, hanya saja tidak ada kontak yang sebenarnya untuk dibicarakan. Maka masalah sederhana untuk mengubah pesawat itu ("rasterize" itu) kembali menjadi grid integer-indexed. Anda cukup melakukan ini dari grid integer-indexed untuk memulainya, tetapi mungkin akan sedikit lebih sulit untuk mendapatkan hal-hal yang "baik" - ini tergantung pada seberapa tinggi resolusi grid Anda ... semakin tinggi, semakin baik , pada kasus ini.

Tentunya Anda mungkin ingin menerapkan semacam kekuatan dari tepi bidang persegi juga, atau Anda mungkin menemukan banyak partikel "mencuci di pantai". Atau Anda dapat membuat bidang yang jauh lebih besar dari yang Anda butuhkan, kemudian mengambil snapshot dari area kecil itu - ini menghindari masalah yang disebutkan di atas.

Ketika Anda ingin memastikan yang sebaliknya, yaitu bahwa pengelompokan memang terjadi, maka lihatlah distribusi "standar" atau "gaussian". Inilah sebabnya mengapa starfield yang dibuat secara acak sering terlihat palsu; mereka menggunakan distribusi acak murni daripada model distribusi yang lebih naturalistik.

Anda bisa menggunakan yang sederhana algoritma distribusi disk-Poisson untuk mendapatkan distribusi "gangguan biru". Ini menghasilkan titik-titik pada bidang yang jaraknya kira-kira sama satu sama lain. Ini berfungsi tidak hanya dalam contoh 2D Anda tetapi juga dalam 3D, dan juga dalam ruang non-Euclidean, tetapi perhitungan dapat dengan cepat menjadi sulit digunakan.

Ide dasar dari algoritma tersebut adalah bahwa Anda mulai dengan titik "seed" pertama, kemudian kerjakan sendiri dengan menambahkan titik acak atau pseudo-acak dalam annulus antara jarak max dan min yang ingin Anda miliki dari titik ke depan dan menghilangkan yang terletak terlalu dekat satu sama lain. Algoritme Anda kemudian bekerja keluar sedemikian rupa, sampai jumlah poin yang dibutuhkan ditambahkan (yang memberi Anda awan titik melingkar kira-kira), atau ruang yang tersedia terisi.

Algoritme alternatif yang cepat dan elegan untuk menghasilkan derau 2D seperti itu, serta diskusi singkat tentang sifat-sifatnya, dapat ditemukan di " Struktur Data Spasial untuk Pembuatan Sampel Disk-Poisson-Cepat " oleh Daniel Dunbar dan Greg Humphreys dari Universitas dari Virginia.