Bagaimana cara menghasilkan peta bintang?

Saya mencoba membuat peta bintang.

Percobaan saya adalah:

1. Memiliki lebar dan tinggi untuk peta.
2. Tempatkan titik (bintang) secara acak melintasi area lebar dan tinggi.

Pendekatan yang sederhana, tetapi memiliki masalah menempatkan bintang secara acak sangat dekat satu sama lain.

Untuk mengatasi masalah ini, satu pendekatan adalah memiliki jarak minimum dan ketika menghasilkan bintang, Anda membandingkan jarak dari bintang baru ke setiap bintang yang dihasilkan dan jika di bawah jarak minimum, Anda menghasilkan yang baru, tetapi saya tidak tahu apakah itu efisien. Ada tips?

Sebuah Poisson-Disk pengambilan sampel distribusi akan memungkinkan Anda untuk memilih titik acak jarak minimum terpisah & algoritma Bridson ini secara efisien dapat memecahkan masalah di O (n) - cukup cepat untuk real time yang disediakan menghitung bintang Anda tidak terlalu besar.

Algoritma Bridson membagi wilayah keluaran menjadi kisi-kisi sel yang berukuran relatif terhadap jarak minimum yang diizinkan, sehingga hanya satu titik yang dapat muncul di setiap sel. Kemudian, ketika Anda mempertimbangkan untuk menambahkan titik baru, Anda hanya perlu memeriksa koleksi sel tetangga yang berbentuk disk sebagai lawan dari seluruh daftar titik. Misalnya, perhatikan gambar berikut:

Saat memeriksa untuk melihat apakah kandidat titik biru terlalu dekat dengan titik yang ada, Anda tidak perlu memeriksa setiap titik yang ada. Alih-alih, Anda dapat membatasi pencarian ke titik-titik di sel tetangga (yang dapat Anda temukan dengan cepat menggunakan tabel pencarian). Mike Bostock memiliki animasi yang bagus yang menunjukkan algoritma sedang berlangsung.

Implementasi standar hanya berkaitan dengan jarak minimal tetap antara titik. Artikel pengambilan sampel Poisson Disk Herman Tulleken (termasuk kode sumber) membahas adaptasi untuk memvariasikan jarak minimum di berbagai bagian gambar; pada dasarnya seperti algoritma dithering . Menggunakan perlin noise / simplex noise seperti yang ditunjukkan dalam artikel cloud mungkin memberikan peta bintang yang tampak lebih alami. Misalnya, saya menggunakan gambar di sebelah kiri untuk menghasilkan yang benar:

Untuk melakukan ini, ketika mempertimbangkan kandidat poin, saya pertama-tama memeriksa nilai gambar input, yang menghasilkan nilai dari 0 hingga 1. Saya kemudian skala ini ke jarak min & max yang diinginkan antara titik; dalam hal ini saya memilih 5 & 20 piksel. Jadi ketika menempatkan sebuah titik di daerah gelap, bintang-bintang saya bisa sedekat 5 piksel satu sama lain & ketika menempatkan bintang di daerah terang, mereka bisa terpisah hingga 20 piksel.

Perlu dicatat bahwa percepatan Bridson tidak tepat bekerja dengan pengambilan sampel jarak variabel karena titik keluaran tidak menggunakan jarak minimum seragam. Namun Anda masih dapat menggunakan kotak keluaran untuk mengurangi pencarian. Kotak yang lebih kecil menghasilkan pencarian yang lebih cepat untuk tetangga terdekat dengan mengorbankan peningkatan memori untuk tabel pencarian yang lebih besar.

Salah satu solusi yang sangat naif tetapi sederhana adalah dengan selalu melompat jarak "minimum", dan kemudian menambahkan jumlah acak di atas itu. Ini berarti bintang tidak akan pernah menjadi teman baik, dan Anda setidaknya akan mendapatkan sedikit penyimpangan.

misalnya

for (int x = 0; x < MAX_WIDTH; x+= MIN_SEPERATION_X)
{
  x += generateRandom();

  for (int y = 0; y < MAX_HEIGHT; y+= MIN_SEPERATION_Y)
  {
    y += generateRandom();

    if (x < MAX_WIDTH && y < MAX_HEIGHT)
    {
      image[x + y * width] = STAR;
    }
  }
}

(Memasukkan fungsi pembuatan nomor acak favorit Anda)

Jika Anda tahu ukuran XYZ ruang bermain Anda, Anda bisa memilih tempat acak di ruang itu

dan kemudian lakukan SphereCast untuk memeriksa apakah ada sesuatu yang sudah terlalu dekat.

//pseudo code

SpawnStar(){
 Vector3 spot = new vector3(random(0,world size),random(0,world size,random(0,world size)

  while(true){
  SphereCast(spot, radius)
   if(hit something){
      spot = get new random spot
    }else{
     SpawnStar();
     brake;
    }
  } 
}

Masalah dengan ini adalah bahwa itu mungkin tidak akan sangat baik untuk waktu nyata, namun untuk pra dihasilkan itu baik dan cukup cepat.