Ubah fungsi distribusi acak :: Jadikan lebih kecil kemungkinannya untuk mendapatkan beberapa nilai yang serupa secara berurutan

8

Saya ingin menghasilkan urutan angka untuk menghasilkan planet secara prosedural di sektor galaksi. Setiap planet harus ditempatkan secara acak, namun sangat kecil kemungkinannya bahwa dua planet secara langsung bersebelahan. Bagaimana saya bisa mencapainya?

Saya tahu bahwa Anda dapat memodifikasi peluang dengan menerapkan fungsi distribusi, tetapi bagaimana saya bisa mengendalikannya untuk membuat nilai tertentu lebih / kurang mungkin?

Gif menunjukkan gagasan memodifikasi kurva probabilitas tergantung pada nilai yang sudah dihasilkan.

API-Beast
sumber
2
Cukup menambahkan jarak minimum akan memastikan planet tidak di sebelah yang lain. Saya perkirakan ini sederhana sehingga dapatkah Anda menjelaskan lebih lanjut?
Madmenyo
@MennoGouw Ya, itu akan menyelesaikannya untuk kasus khusus ini, meskipun saya ingin meningkatkan pemahaman saya tentang probabilitas jadi saya mencari solusi yang "lebih lembut" tanpa batas keras / membuang nomor yang dihasilkan.
API-Beast
Klarifikasi solusi "lunak". Ini semua tentang pengaturan aturan. Saat Anda membutuhkan aturan tertentu untuk pembuatan prosedural, Anda perlu menambahkan aturan ini. Jika Anda memiliki kasus khusus, Anda menetapkan aturan lebih atau berbeda untuk ini.
Madmenyo
Saya tidak yakin mengapa Anda tidak hanya menggunakan generator yang memiliki reputasi bagus tentang distribusinya? (Saya pikir twister Mersenne tidak buruk.)
Vaillancourt
2
Saya setuju. Generasi acak itu sendiri bukan masalah. Melakukan ini bahkan dapat menghancurkan generator acak Anda dengan membuatnya dapat diprediksi. Generasi aturan adalah cara untuk melangkah.
ashes999

Jawaban:

8

Jika Anda tahu distribusi yang Anda inginkan, Anda dapat menggunakan sampel penolakan .

Cara termudah: Pada grafik di atas, pilih titik secara acak hingga Anda menemukan satu di bawah kurva. Maka gunakan saja x-coordinate.

Untuk distribusi aktual, ada berbagai pendekatan yang masuk akal. Misalnya, untuk nomor planet idi lokasi p, dan beberapa parameter kekuatan k(misalnya 0.5), tentukan fungsi f_i(x)=abs(p-x)^k, lalu gunakan fungsi distribusi g(x)=f_1(x)*f_2(x)*...*f_n(x).

Dalam praktiknya, hitung dan simpan hasil g(x)to array t( t[x]=g(x)); ingat nilai tertinggi yang terlihat hjuga. Pilih posisi acak xdi t, memilih nilai acak yantara 0dan h, ulangi if y>t[x]; jika tidak nilai pengembaliannya adalah x.

yarr
sumber
Bisakah Anda sedikit lebih mendalam tentang mendefinisikan fungsi distribusi? Sisanya harus jelas.
API-Beast
Misalnya, jika planet saat ini berada pada posisi 0,1, 0,3 dan 0,8, g (x) = (abs (x-0,1) * abs (x-0,3) * abs (x-0,8)) ^ 0,5, di mana "^" berarti eksponensial. (Ini sedikit berbeda dari rumus sebelumnya, tetapi setara.) Fungsi distribusi ini terlihat seperti gif dalam pertanyaan Anda dan tidak didasarkan pada apa pun secara khusus. (String kueri untuk WolframAlpha: "plot dari 0 hingga 1 (abs (x-0,1) * abs (x-0,3) * abs (x-0,8)) ^ 0,5")
yarr
Wow, fungsi itu sangat keren. Tidak tahu bahwa fungsi seperti itu sebenarnya sesederhana itu :) Tautan untuk malas: bit.ly/1pWOZMJ
API-Beast
1

Saya tidak yakin masalahnya ditentukan sepenuhnya oleh pertanyaan, tetapi saya dapat memberikan beberapa ide sederhana, yang kedua ini akan memberikan angka kira-kira sesuai dengan apa yang ditunjukkan gambar yang Anda inginkan.

Apa pun cara Anda menyadari fungsi distribusi berubah setelah setiap angka yang dihasilkan, dan memiliki memori (yaitu: itu non-Markovian ) dan salah satu dari metode ini terbukti tidak praktis ketika 'memori' (jumlah angka yang diambil sebelumnya) mendapat sangat besar.

  1. Sederhana:
    Hasilkan angka acak dari distribusi datar, bandingkan dengan angka sebelumnya yang ditarik, ulangi jika 'terlalu dekat'

  2. Jawaban ini lebih seperti sosok Anda (dengan asumsi kami ingin menggambar dari 0..1):

    • buat daftar berurutan baru, masukkan 0 dan 1
    • menghasilkan angka acak dari fungsi distribusi datar: N_0
      • tambahkan nomor ini ke daftar
    • pada panggilan berikutnya, buat nomor lain N_1,
    • jika N_1> N_0
      • menggambar angka Gaussian Acak baru dengan mean = 1 dan deviasi standar dari apa pun yang Anda inginkan, angka yang lebih kecil (dibandingkan dengan 1-N_1) akan membuat angka acak lebih jauh terpisah. Ini tidak akan menjamin jarak minimum antara pengundian, tetapi sekali lagi sosok Anda tampaknya juga tidak.
    • kasus sebaliknya dari N_1 <N_0 ditangani dengan cara yang sama
    • pada pengundian berikutnya terus menghasilkan angka acak (N_i) dari distribusi datar
    • melintasi daftar Anda untuk melihat di mana dua angka yang ditarik sebelumnya yang terletak antara angka baru (N_-, N_ +)
    • buat angka acak Gaussian baru dengan rata-rata (N_- + N _ +) / 2
    • tambahkan nomor distribusi datar (N_i) ke daftar (daftar yang dipesan) Anda

tempat sampah endpoint adalah kasus khusus, tetapi harus cukup sederhana bagi Anda untuk melihat cara menanganinya.

Adam V. Steele
sumber
0

Pikirkan perbedaan antara 1 dadu dan 3 dadu . 1 Dadu memberi Anda probabilitas genap untuk semua nilai, sedangkan 3 dadu cenderung memiliki probabilitas lebih tinggi untuk nilai-nilai ke arah tengah.

Semakin banyak "dadu" dalam persamaan Anda, semakin kuat peluang Anda untuk mendapatkan sesuatu ke tengah. Jadi mari kita mendefinisikan fungsi yang dapat menangani angka apa pun secara merata :

// Takes a random number between floor and ceil
// pow defines how strongly these results should gravitate towards the middle
// We also define a function TrueRand(floor, ceil) elsewhere where you should substitute your own random function
int CenterRandom(int floor, int ceil, int pow = 3)
{
    if(ceil == floor)
        return ceil; // don't care to compare

    int total = 0;
    for(int x = 0; x < pow; x++)
    {
       total += TrueRand(floor, ceil);
    }
    return total / pow;
}

Sekarang kita dapat mendefinisikan fungsi contoh untuk menggunakan ini:

// Distribues a number of points between floor and ceil
// We assume a function PlotPoint(int) exists to aid in creating the planet, etc...
void DistributePoints(int floor, int ceil, int numPoints)
{
    // Could easily output this in the function parameters, but language wasn't specified
    int[numPoints] breaks;
    int numBreaks = 0;

    // Special case for first pair
    breaks[0] = CenterRandom(floor, ceil);
    numBreaks++;

    for(int x = 0; x < numPoints - 1; x++)
    {
        // Generate a random number linearly, this will be used for picking
        // This way we have a greater chance of choosing a random value between larger pairs
        int picker = TrueRandom(floor, ceil);

        // Now we first find the pair of points that our picker exists on
        // For simplicity, we handle the first and last pair separately

        if(picker >= floor && picker < breaks[0])
        {
            breaks[x] = CenterRandom(floor, breaks[0] - 1);
        }
        for(int i = 0; i < numBreaks; i++)
        {
            if(picker > breaks[i] && picker < breaks[i+1])
            {
                breaks[x] = CenterRandom(breaks[i] + 1, breaks[i+1] - 1);
            }
        }
        if(picker > breaks[numBreaks] && picker <= ceil)
        {
            breaks[x] = CenterRandom(breaks[numBreaks] + 1, ceil);
        }

        PlotPoint(breaks[x]); // Plot the point
    }
}

Sekarang yang pertama dicatat adalah bahwa kode ini benar-benar tidak memeriksa apakah pemilih sudah cocok dengan salah satu poin. Jika ya maka itu tidak akan menghasilkan poin, mungkin sesuatu yang mungkin Anda sukai.

Untuk menjelaskan apa yang terjadi di sini adalah bahwa CenterRandom menghasilkan semacam kurva lonceng. Fungsi ini memecah pesawat menjadi beberapa kurva lonceng, satu per pasang poin yang ada. Pemetik memberi tahu kami kurva lonceng mana yang akan dihasilkan. Karena kami memilih secara linear, kami dapat memastikan bahwa pasangan dengan celah yang lebih besar di antara mereka akan dipilih lebih sering, tetapi kami masih membiarkannya sepenuhnya acak.

Semoga ini menunjukkan Anda ke arah yang benar.


sumber
0

Saya tahu Anda bertanya tentang urutan posisi acak, tetapi jika Anda tidak dibatasi untuk menghasilkan set secara berurutan, ada pendekatan lain: menghasilkan serangkaian poin yang memiliki jarak yang diinginkan.

Apa yang saya pikir Anda inginkan adalah seperangkat planet yang cukup masuk akal dengan beberapa keacakan. Alih-alih menghasilkan posisi planet dengan generator angka acak, buat spasi planet dengan generator angka acak. Ini akan memungkinkan Anda mengontrol distribusi jarak secara langsung, dengan menggunakan generator angka acak yang mengambil dari distribusi tersebut. Ini mudah dalam 1 dimensi.

Dalam 2 dimensi, saya telah melihat beberapa pendekatan yang menghasilkan "noise biru" tapi saya tidak tahu cara menghasilkan spasi dengan distribusi sewenang-wenang. Artikel ini membahas pendekatan standar "cobalah menempatkannya dan tolak jika terlalu dekat", tetapi Anda dapat menghasilkan semuanya sekaligus, dengan solusi "lebih lunak" dengan menempatkan semua poin Anda, kemudian menggunakan Lloyd Relaxation untuk memindahkan semua planet ke lebih banyak posisi yang diinginkan. Ini akan memindahkan planet yang terlalu dekat lebih jauh. Ubin Wang Rekursif adalah pendekatan lain yang bisa berguna. Kertas inimemperluas masalah untuk menghasilkan planet dengan satu kerapatan dan beberapa objek lain seperti asteroid dengan kerapatan lain. Anda mungkin juga dapat menghasilkan noise biru dengan menggunakan seri Fourier; Saya tidak yakin. Pendekatan seri Fourier juga akan memungkinkan Anda menggunakan distribusi sewenang-wenang alih-alih hanya noise biru.

amitp
sumber