Kebisingan acak berdasarkan biji

16

Saat ini saya sedang mengerjakan sebuah program yang seharusnya menghasilkan derau acak di layar berdasarkan 'koordinat' piksel. Koordinat harus memiliki warna yang sama setiap kali Anda me-restart program. Namun, menggunakan util Java. Secara acak, hasil yang saya dapatkan tidak acak seperti yang saya inginkan:

layar cetak

Saya berpikir bahwa jika saya menggunakan koordinat gabungan (seperti dalam satu bilangan bulat yang terbentuk dari kedua koordinat di sebelah satu sama lain) setiap koordinat akan memiliki angka yang berbeda. Dengan menggunakan angka itu sebagai seed, saya berharap mendapatkan angka acak yang berbeda untuk setiap koordinat yang digunakan untuk nilai rgb koordinat itu.

Ini adalah kode yang saya gunakan:

public class Generate {

static Random Random;

    public static int TileColor(int x, int y){          
        Random = new Random(Integer.valueOf(Integer.toString(x)+Integer.toString(y)));
        int b = 1 + Random.nextInt(50);
        int g = 1 + Random.nextInt(50);
        int r = 1 + Random.nextInt(50);
        int color = -Color.rgb888(r, g, b);
        return color;
    }
}

Apakah pola yang dibuat oleh program karena cara fungsi acak java bekerja atau apakah saya melakukan sesuatu yang salah dan haruskah saya mencoba pendekatan yang berbeda?

Pembaruan: Saya sekarang mencoba untuk menyingkirkan masalah seputar rangkaian dengan menggunakan kode berikut:

public static int TileColor(int x, int y){  
            Randomy = new Random(y);
            Randomx = new Random(x);
            Random = new Random(Integer.valueOf(Integer.toString(Randomx.nextInt(1234))+Integer.toString(Randomy.nextInt(1234))));
            int b = 1 + Random.nextInt(100);
            int g = 1 + Random.nextInt(100);
            int r = 1 + Random.nextInt(100);
            int color = -Color.rgb888(r, g, b);
            return color;
}

Entah bagaimana, ini juga memberikan gambar acak (menurut saya):

gambar mew

Namun kode ini menghasilkan ulang tiga kali per piksel. Meskipun ini bukan masalah bagi saya saat ini, saya mempertimbangkan untuk mengubah kode ini jika saya membutuhkan kinerja yang lebih baik nantinya.

capung
sumber
3
Tidak yakin tentang Java's Random tapi saya cukup yakin itu bukan random yang asli ... Baca en.wikipedia.org/wiki/Pseudorandom_number_generator Anda akan mengerti mengapa Anda melihat pola-pola itu.
Salketer
23
Sesuatu yang penting yang hilang dari jawaban lain: jangan pasang ulang RNG untuk setiap piksel. Benih sekali dan menghasilkan nilai berturut-turut untuk semua piksel dalam gambar Anda berdasarkan itu.
Konrad Rudolph
4
Catatan: generaot angka pseudorandom mungkin terdistribusi secara seragam dalam satu dimensi , tetapi gagal saat menggunakan lebih dari satu dimensi ... Anda secara efektif menghasilkan titik dalam 3D (r, g dan b dan 3 koordinat berbeda) sehingga Anda memerlukan generator acak yang menjamin tidak hanya bahwa nilai yang dihasilkannya terdistribusi secara seragam, tetapi juga kembar tiga yang dihasilkannya terdistribusi secara seragam di ruang 3D.
Bakuriu
6
@ Bakuriu Jika X, Y dan Z adalah variabel acak seragam independen, maka saya cukup yakin (X, Y, Z) seragam dalam ruang 3d.
Jack M
2
Anda dapat bereksperimen dengan menggunakan RNG yang berbeda, seperti Twister Mersenne .
Kevin

Jawaban:

21

java.util.RandomKelas Java biasanya memberi Anda urutan nomor pseudorandom yang cukup baik untuk digunakan dalam gim 1 . Namun, karakteristik itu hanya berlaku untuk urutan beberapa sampel berdasarkan benih. Saat Anda menginisialisasi ulang RNG dengan nilai benih tambahan dan hanya melihat nilai pertama dari setiap urutan, karakteristik keacakan tidak akan sama baiknya.

Apa yang bisa Anda lakukan sebagai gantinya:

  • Gunakan seed yang sama untuk menghasilkan potongan piksel secara keseluruhan. Misalnya, ketika Anda membutuhkan nilai warna piksel 425: 487, masukkan koordinat 400: 400 ke dalam RNG, hasilkan 10.000 warna acak dan gunakan warna pada indeks 2587 (25 * 100 + 87). Potongan yang dihasilkan dengan cara itu harus di-cache untuk menghindari menghasilkan kembali 10.000 warna acak untuk setiap piksel dari potongan itu.
  • Alih-alih menggunakan generator angka acak, gunakan fungsi intisari pesan untuk mengubah pasangan koordinat menjadi nilai warna. Hasil dari sebagian besar MDF tidak dapat diprediksi untuk memenuhi sebagian besar uji keacakan. Outputnya biasanya lebih dari 24 bit yang Anda butuhkan untuk nilai RGB, tetapi memotongnya biasanya tidak ada masalah.

    Untuk meningkatkan kinerja, Anda dapat menggabungkan generasi intisari pesan dengan potongan. Hasilkan potongan kecil piksel yang hanya cukup besar untuk menggunakan panjang penuh satu output dari fungsi digest Anda.

1 ketika sangat penting bahwa tidak ada yang bisa memprediksi angka berikutnya, gunakan yang lebih lambat tetapi kurang dapat diprediksijava.security.SecureRandom

Philipp
sumber
13

Koordinat harus memiliki warna yang sama setiap orang yang Anda restart program

Dalam hal ini, Anda akan ingin menggunakan fungsi noise deterministik seperti Perlin noise atau noise simplex .

( Lihat pertanyaan ini untuk informasi lebih lanjut tentang kebisingan Perlin dengan beberapa gambar cantik. )

Sebagian besar, menggunakan built-in random() atau fungsi serupa akan memberi Anda nilai yang berbeda setiap kali Anda menjalankan program, karena mereka dapat menggunakan jam sebagai input atau nilai pseudorandom lainnya.

Pilihan lain adalah membuat "peta kebisingan" satu kali, offline, dan kemudian menggunakannya sebagai sumber angka acak Anda nanti.

Dalam implementasi Anda, Anda merangkai representasi string dari x dan y. Itu buruk karena tidak unik di seluruh domain. Contohnya,

x    y   concatenated
40   20  4020
402   0  4020
10   10  1010
101   0  1010
12   34  1234
123   4  1234
1   234  1234

Semoga berhasil!

3Dave
sumber
1
Poin bagus tentang angka-angka yang disatukan. Namun program ini selalu memberikan hasil yang sama persis jika saya menjalankan program beberapa kali. Saya telah mempertimbangkan kebisingan perlin / simpleks juga, mungkin melihatnya dan melihat apakah itu bekerja lebih baik. Namun saya belum yakin mengapa Jawa menciptakan pola, karena masalah rangkaian tampaknya tidak menyelesaikannya sepenuhnya
capung
1
Apakah tidak cukup hanya dengan seed acak dengan nilai seed konstan sebelum menghasilkan pixel?
Jack M
1
@ JackM Itu tergantung sepenuhnya pada algoritma PRNG yang sedang dimainkan.
3Dave
4
"Saya pernah melihat implementasi rand () yang menggunakan setiap nilai sebagai seed untuk nilai selanjutnya." Bukankah itu cara kerja kebanyakan generator nomor pseudorandom non-kriptografis? Mereka menggunakan nomor acak sebelumnya (atau negara bagian) sebagai input untuk menghasilkan nomor acak / negara bagian berikutnya.
JAB
2
@DavidLively Hampir semua PRNG melakukan ini atau sesuatu yang setara, kecuali keadaan internal mereka lebih besar dari kisaran angka yang mereka hasilkan (mis. Mersenne twister), dan bahkan kemudian urutan angka acak tentu saja sepenuhnya ditentukan oleh seed.
Konrad Rudolph
9

Mari kita lihat apa yang sebenarnya Anda lakukan:

  • Anda mengulangi semua piksel satu per satu
  • Untuk setiap piksel, Anda menggunakan rangkaian koordinatnya sebagai seed
  • Anda kemudian mulai secara acak baru dari seed yang diberikan dan mengambil 3 angka

Semua ini terdengar baik-baik saja, tetapi Anda menerima pola karena:

Pixel pada 1,11 dan pixel pada 11,1 keduanya diunggulkan nomor 111 sehingga mereka yakin memiliki warna yang sama.

Juga, selama Anda selalu siklus dengan cara yang sama, Anda hanya dapat menggunakan satu generator, tidak perlu menggunakan satu untuk setiap piksel. Satu untuk seluruh gambar akan dilakukan! Masih akan ada semacam pola karena pseudo-randomness. @ David Jelas benar tentang menggunakan beberapa algoritma Noise, itu akan membuatnya terlihat lebih acak.

Salketer
sumber
Masalahnya adalah bahwa tampilan gambar harus dapat bergeser (lebih jauh ke koordinat positif). Jadi pendekatan ini tidak akan berfungsi sepenuhnya
capung
4
Sebenarnya "semua ini" tidak terdengar baik-baik saja - mengulangi RNG deterministik untuk setiap piksel adalah strategi yang mengerikan kecuali benih itu sendiri dari RNG kriptografi (dan bahkan itu adalah strategi miring karena alasan yang tidak terkait dengan distribusi).
Konrad Rudolph
Anda mungkin memasukkan cara yang benar untuk meringkaskan angka-angka dalam konteks ini. Yaitu. (x + y * lebar)
Taemyr
1

Buat generator warna, lalu hasilkan warna Anda untuk ubin Anda. Benih hanya sekali! Anda tidak perlu menanam lebih dari itu, setidaknya per ubin.

public class RandomColorGenerator {
  private final int minValue;
  private final int range;
  private final Random random;
  public RandomColorGenerator(int minValue, int maxValue, Random random) {
    if (minValue > maxValue || (long)maxValue - (long)minValue > (long)Integer.MAX_VALUE) {
      throw new IllegalArgumentException();
    }
    this.minValue = minValue;
    this.range = maxValue - minValue + 1;
    this.random = Objects.requireNonNull(random);
  }

  public int nextColor() {
    int r = minValue + random.nextInt(range);
    int g = minValue + random.nextInt(range);
    int b = minValue + random.nextInt(range);
    return -Color.rgb888(r, g, b);
  }
}

public class Tile {
  private final int[][] colors;
  public Tile(int width, int height, RandomColorGenerator colorGenerator) {
    this.colors = new int[width][height];
    for (int x = 0; x < width; x++) {
      for (int y = 0; y < height; y++) {
        this.colors[x][y] = colorGenerator.nextColor();
      }
    }
  }

  public int getColor(int x, int y) {
    return colors[x][y];
  }
}

Dan penggunaannya akan seperti berikut:

RandomColorGenerator generator = new RandomColorGenerator(1, 100, new Random(0xcafebabe));
Tile tile = new Tile(300, 200, generator);
...
// getting the color for x, y:
tile.getColor(x, y);

Dengan ini jika Anda tidak puas dengan hasilnya, ganti Randombenih. Selain itu, Anda hanya perlu menyimpan / mengomunikasikan benih dan ukuran sehingga semua klien memiliki gambar yang sama.

Olivier Grégoire
sumber
1

Alih-alih menggunakan Random, pertimbangkan untuk menggunakan hash digest seperti MD5. Ini memberikan sulit untuk memprediksi nilai 'acak' berdasarkan input tertentu, tetapi selalu nilai yang sama untuk input yang sama.

Contoh:

public static int TileColor(int x, int y){
        final MessageDigest md = MessageDigest.getInstance("MD5");
        final ByteBuffer b = ByteBuffer.allocate(8);
        b.putInt(x).putInt(y);
        final byte[] digest = md.digest(b.array());
        return -Color.rgb888(digest[0], digest[1], digest[2]);
}

CATATAN: Saya Tidak tahu dari mana Color.rgb888 (..) berasal, jadi saya tidak tahu apa kisaran yang diizinkan. 0-255 adalah normal.

Perbaikan untuk dipertimbangkan:

  • Buat variabel MessageDigest dan ByteBuffer di luar kelas, untuk meningkatkan kinerja. Anda harus mengatur ulang ByteBuffer untuk melakukan itu, dan metode ini tidak lagi aman untuk Thread.
  • Array digest akan berisi nilai byte 0-255, jika Anda ingin rentang lain, Anda harus melakukan beberapa matematika pada mereka.
  • Jika Anda menginginkan hasil 'acak' yang berbeda, Anda dapat menambahkan semacam 'benih'. Misalnya, ubah ke ByteBuffer.allocate (12), dan tambahkan .putInt (seed).
cranphin
sumber
1

Orang lain telah menunjukkan bahwa salah satu cara untuk mendapatkan perilaku yang Anda inginkan adalah menggunakan fungsi hash, alias "fungsi digest pesan." Masalahnya adalah bahwa ini sering didasarkan pada algoritma seperti MD5, yang aman secara kriptografis (yaitu benar-benar, sangat acak) tetapi sangat lambat. Jika Anda menggunakan fungsi hash kriptografis setiap kali Anda membutuhkan piksel acak, Anda akan mengalami masalah kinerja yang cukup parah.

Namun, ada fungsi hash non-kriptografi yang dapat menghasilkan nilai-nilai yang cukup acak untuk tujuan Anda dan juga cepat. Yang biasanya saya raih adalah murmurhash . Saya bukan pengguna Java tetapi tampaknya setidaknya ada satu implementasi Java yang tersedia. Jika Anda benar-benar perlu memiliki setiap piksel yang dihasilkan dari koordinatnya, daripada menghasilkannya sekaligus dan menyimpannya dalam tekstur, maka ini akan menjadi cara yang baik untuk melakukannya.

Nathaniel
sumber
1

Saya akan menggunakan prime lebih dari 2000 (resolusi khas maks)
Ini akan meminimalkan (atau menghilangkan duplikat benih)

public class Generate {

    static Random Random;

    public static int TileColor(int x, int y){          
        Random = new Random(x + 2213 * y);
        int b = 1 + Random.nextInt(50);
        int g = 1 + Random.nextInt(50);
        int r = 1 + Random.nextInt(50);
        int color = -Color.rgb888(r, g, b);
        return color;
    }
}
paparazzo
sumber
0

Randomcukup acak. Anda salah menggunakannya karena dua alasan utama.

  • Itu tidak dirancang untuk berulang kali diunggulkan. Properti acak hanya berlaku untuk satu urutan nomor acak.
  • Ada korelasi besar Integer.valueOf(Integer.toString(x)+Integer.toString(y))antara piksel yang Anda tanam.

Saya hanya menggunakan beberapa variasi dari kode berikut, di mana Anda dapat memilih fungsi hash (jangan gunakan Integer.getHashCode) dari jawaban di /programming/9624963/java-simplest-integer- hash

public static int TileColor(int x, int y) {
    return hash(x ^ hash(y));
}

di mana fungsi hash bisa

Jimmy
sumber
0

Anda dapat mencoba menggunakan sistem waktu jam saat ini sebagai seed seperti ini:

Random random = new Random(System.currentTimeMillis())

Semoga ini menghasilkan nilai yang lebih acak.

pengembang anonim
sumber
Itu tidak menciptakan nilai dame untuk koordinat dame setiap kali.
Capung
0

Berikut ini adalah fungsi shader statis satu baris yang saya buat - poltergeist (Noisy Ghost).

Dibutuhkan koordinat 2D dan seed, dan dirender secara monoton seperti yang diminta. Ini berjalan pada fps waktu nyata, terlepas dari resolusi layar. Untuk itulah GPU digunakan.

// poltergeist (noisy ghost) pseudo-random noise generator function
// [email protected] 03/24/2015

precision highp float;

float poltergeist(in vec2 coordinate, in float seed) 
{
    return fract(sin(dot(coordinate*seed, vec2(12.9898, 78.233)))*43758.5453); 
}

void mainImage(out vec4 fragColor, in vec2 fragCoord) 
{   
    fragColor = vec4(poltergeist(fragCoord, iGlobalTime)); 
}

Resolusi apa pun, tekstur apa pun, di perangkat apa pun (juga seluler) yang mendukung GL (yang hampir semuanya dengan layar).

Lihat berlari di sini, sekarang!

https://www.shadertoy.com/view/ltB3zD

Anda dapat dengan mudah memasukkan shader ini dalam program java Anda menggunakan OpenGL standar, atau di browser apa pun yang menggunakan webgl standar.

Hanya untuk bersenang-senang, saya melempar tantangan bagi siapa saja untuk mengalahkan Poltergeist dalam kualitas dan kinerja di semua perangkat. Aturan Hantu Bising! Tak terkalahkan!

Birkensocks
sumber