Zufälliges Rauschen basierend auf Samen

15

Ich arbeite derzeit an einem Programm, das zufälliges Rauschen auf einem Bildschirm basierend auf den 'Koordinaten' eines Pixels erzeugen soll. Die Koordinaten sollten bei jedem Neustart des Programms dieselbe Farbe haben. Wenn ich jedoch das util.Random von Java verwende, sind die Ergebnisse, die ich erhalte, nicht so zufällig, wie ich es gerne hätte:

Druckbildschirm

Ich dachte, wenn ich die kombinierten Koordinaten verwenden würde (wie in einer ganzen Zahl, die aus beiden Koordinaten nebeneinander gebildet wird), hätte jede Koordinate eine andere Nummer. Indem ich diese Zahl als Startwert verwendete, erwartete ich, dass ich für jede Koordinate eine andere Zufallszahl für den RGB-Wert dieser Koordinate erhalten würde.

Dies ist der Code, den ich verwendet habe:

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;
    }
}

Liegt das Muster, das das Programm erstellt, an der Funktionsweise der Zufallsfunktion von Java, oder mache ich etwas falsch und sollte ich einen anderen Ansatz wählen?

Update: Ich habe jetzt versucht, die Probleme mit der Verkettung mithilfe des folgenden Codes zu beseitigen:

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;
}

Irgendwie lieferte dies auch ein (meiner Meinung nach) ausreichend zufälliges Bild:

mew Bild

Dieser Code wird jedoch dreimal pro Pixel neu berechnet. Obwohl dies für mich derzeit kein Problem ist, überlege ich mir, diesen Code zu ändern, falls ich später eine bessere Leistung benötige.

Libelle
quelle
3
Ich bin mir bei Javas Zufall nicht sicher, aber ich bin mir ziemlich sicher, dass er nicht wirklich zufällig ist ... Read en.wikipedia.org/wiki/Pseudorandom_number_generator Du wirst verstehen, warum du diese Muster siehst.
Salketer
23
In den anderen Antworten fehlt etwas Entscheidendes: Verändern Sie die RNG nicht für jedes Pixel. Setzen Sie es einmal und generieren Sie darauf basierend aufeinanderfolgende Werte für alle Pixel in Ihrem Bild.
Konrad Rudolph
4
Hinweis: Eine Pseudozufallszahl kann möglicherweise gleichmäßig in einer Dimension verteilt sein , schlägt jedoch fehl, wenn mehr als eine Dimension verwendet wird. Sie generieren also effektiv Punkte in 3D (r, g und b und 3 verschiedene Koordinaten), sodass Sie einen Zufallsgenerator benötigen garantiert nicht nur, dass die erzeugten Werte gleichmäßig verteilt sind, sondern auch, dass die erzeugten Triplets gleichmäßig im 3D-Raum verteilt sind.
Bakuriu
6
@ Bakuriu Wenn X, Y und Z unabhängige, einheitliche Zufallsvariablen sind, bin ich mir ziemlich sicher, dass (X, Y, Z) im 3D-Raum einheitlich ist.
Jack M
2
Sie könnten mit verschiedenen RNGs experimentieren, wie dem Mersenne Twister .
Kevin - Wiedereinsetzung von Monica

Antworten:

21

In Javas java.util.RandomKlasse erhalten Sie normalerweise Folgen von Pseudozufallszahlen, die für die Verwendung in Spiel 1 ausreichen . Dieses Merkmal gilt jedoch nur für eine Folge von mehreren Proben, die auf einem Samen basieren. Wenn Sie das RNG mit inkrementierenden Startwerten neu initialisieren und nur den ersten Wert jeder Sequenz betrachten, sind die Zufälligkeitseigenschaften bei weitem nicht so gut.

Was Sie stattdessen tun könnten:

  • Verwenden Sie denselben Startwert, um ganze Pixelblöcke gleichzeitig zu generieren. Wenn Sie beispielsweise den Farbwert von Pixel 425: 487 benötigen, geben Sie die Koordinaten 400: 400 in das RNG ein, generieren 10000 zufällige Farben und verwenden Sie die Farbe bei Index 2587 (25 * 100 + 87). Auf diese Weise generierte Chunks sollten zwischengespeichert werden, um zu vermeiden, dass diese 10000 zufälligen Farben für jedes einzelne Pixel dieses Chunks erneut generiert werden.
  • Verwenden Sie anstelle eines Zufallszahlengenerators eine Nachrichtenauszugsfunktion , um ein Koordinatenpaar in einen Farbwert umzuwandeln. Die Ausgabe der meisten MDFs ist nicht vorhersehbar genug, um die meisten Zufallstests zu erfüllen. Die Ausgabe ist normalerweise mehr als die 24 Bit, die Sie für einen RGB-Wert benötigen, aber das Abschneiden ist normalerweise kein Problem.

    Um die Leistung zu verbessern, können Sie die Generierung von Nachrichtenübersichten mit Blöcken kombinieren. Generieren Sie kleine Pixelblöcke, die gerade groß genug sind, um die gesamte Länge einer Ausgabe Ihrer Digest-Funktion zu nutzen.

1 Wenn es unbedingt erforderlich ist, dass niemand die nächste Zahl vorhersagen kann, verwenden Sie die langsamere, aber weniger vorhersagbarejava.security.SecureRandom

Philipp
quelle
13

Die Koordinaten sollten bei jedem Neustart die gleiche Farbe haben

In diesem Fall sollten Sie eine deterministische Rauschfunktion wie Perlin-Rauschen oder Simplex-Rauschen verwenden .

( Weitere Informationen zu Perlin-Rauschen mit einigen schönen Bildern finden Sie in dieser Frage. )

Die Verwendung einer eingebauten random()oder einer ähnlichen Funktion gibt Ihnen zum größten Teil jedes Mal, wenn Sie das Programm ausführen, andere Werte, da sie die Uhr als Eingabe oder einen anderen Pseudozufallswert verwenden können.

Eine andere Möglichkeit ist, eine "Noise Map" einmal offline zu erstellen und diese dann später als Zufallszahlenquelle zu verwenden.

In Ihrer Implementierung verketten Sie die Zeichenfolgendarstellungen von x und y. Das ist schlecht, da es nicht domänenweit eindeutig ist. Zum Beispiel,

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

Viel Glück!

3Dave
quelle
1
Guter Punkt zu den verketteten Zahlen. Das Programm liefert jedoch immer genau das gleiche Ergebnis, wenn ich das Programm mehrmals ausführe. Ich habe auch Perlin / Simplex-Rauschen in Betracht gezogen, könnte das untersuchen und herausfinden, ob es besser funktioniert. Ich bin mir jedoch noch nicht sicher, warum Java Muster erstellt, denn das Verkettungsproblem scheint es nicht vollständig zu lösen
Libelle
1
Reicht es nicht aus, einfach Random mit einem konstanten Startwert zu setzen, bevor die Pixel generiert werden?
Jack M
1
@JackM Das hängt ganz vom verwendeten PRNG-Algorithmus ab.
3Dave
4
"Ich habe einmal eine rand () - Implementierung gesehen, bei der jeder Wert als Ausgangswert für den nächsten Wert verwendet wurde." Funktionieren die meisten nicht kryptografischen Pseudozufallszahlengeneratoren nicht so? Sie verwenden die vorherige Zufallszahl (oder den vorherigen Zustand) als Eingabe, um die nächste Zufallszahl / den nächsten Zustand zu generieren.
JAB
2
@DavidLively Praktisch alle PRNGs tun dies oder etwas Äquivalentes, es sei denn, ihr interner Zustand ist größer als der Bereich der von ihnen erzeugten Zahlen (z. B. Mersenne-Twister), und selbst dann wird die Reihenfolge der Zufallszahlen natürlich vollständig vom Startwert bestimmt.
Konrad Rudolph
9

Mal sehen, was Sie genau tun:

  • Sie durchlaufen nacheinander alle Pixel
  • Für jedes Pixel verwenden Sie die Verkettung seiner Koordinaten als Startwert
  • Sie beginnen dann einen neuen Zufall aus dem gegebenen Samen und nehmen 3 Zahlen heraus

Das klingt alles in Ordnung, aber Sie erhalten ein Muster, weil:

Pixel bei 1,11 und Pixel bei 11,1 haben beide die Nummer 111, sodass sie mit Sicherheit dieselbe Farbe haben.

Solange Sie immer auf die gleiche Weise fahren, können Sie nur einen Generator verwenden, ohne dass Sie einen für jedes Pixel verwenden müssen. Eine für das ganze Bild reicht! Wegen der Pseudozufälligkeit wird es immer noch einige Muster geben. @David_Lively verwendet einen Noise-Algorithmus, der zufällig aussieht.

Salketer
quelle
Die Sache ist, dass sich die Ansicht des Bildes verschieben kann (weiter zu positiven Koordinaten). Dieser Ansatz wird also nicht vollständig funktionieren
Libelle
4
Tatsächlich klingt „all dies“ nicht in Ordnung - die Neueinstufung eines deterministischen RNG für jedes Pixel ist eine schreckliche Strategie, es sei denn, der Startwert selbst stammt von einem kryptografischen RNG (und selbst dann ist es aus Gründen, die nichts mit der Verteilung zu tun haben, eine Wonky-Strategie).
Konrad Rudolph
Sie können in diesem Zusammenhang auch die richtige Art und Weise angeben, die Zahlen zu verketten. Dh (x + y * Breite)
Taemyr
1

Machen Sie einen Farbgenerator und produzieren Sie dann Ihre Farben für Ihre Fliese. Nur einmal säen! Sie müssen nicht mehr als das säen, zumindest nicht pro Fliese.

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];
  }
}

Und die Verwendung wird wie folgt sein:

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);

Wenn Sie mit dem Ergebnis nicht zufrieden sind, ändern Sie einfach den RandomSamen. Außerdem müssen Sie nur den Startwert und die Größen speichern / mitteilen, damit alle Kunden dasselbe Image haben.

Olivier Grégoire
quelle
1

Anstatt Random zu verwenden, sollten Sie einen Hash-Digest wie MD5 verwenden. Es bietet einen schwer vorhersagbaren 'zufälligen' Wert, der auf einer bestimmten Eingabe basiert, aber immer den gleichen Wert für dieselbe Eingabe.

Beispiel:

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]);
}

HINWEIS: Ich weiß nicht, woher Color.rgb888 (..) kommt, daher weiß ich nicht, welcher Bereich zulässig ist. 0-255 ist jedoch normal.

Zu berücksichtigende Verbesserungen:

  • Erstellen Sie MessageDigest- und ByteBuffer-Variablen außerhalb der Klasse, um die Leistung zu verbessern. Dazu müssen Sie den ByteBuffer zurücksetzen, und die Methode ist nicht mehr threadsicher.
  • Das Digest-Array enthält die Bytewerte 0-255. Wenn Sie andere Bereiche wünschen, müssen Sie einige Berechnungen an ihnen durchführen.
  • Wenn Sie unterschiedliche "zufällige" Ergebnisse wünschen, können Sie eine Art "Startwert" hinzufügen. Wechseln Sie beispielsweise zu ByteBuffer.allocate (12), und fügen Sie ein .putInt (seed) hinzu.
Cranphin
quelle
1

Andere haben darauf hingewiesen, dass eine Möglichkeit, das gewünschte Verhalten zu erzielen, die Verwendung einer Hash-Funktion, auch "Message Digest-Funktion" genannt, ist. Das Problem ist, dass diese häufig auf Algorithmen wie MD5 basieren, die kryptografisch sicher (dh wirklich, wirklich, wirklich zufällig), aber sehr langsam sind. Wenn Sie jedes Mal, wenn Sie ein zufälliges Pixel benötigen, eine kryptografische Hash-Funktion verwenden, treten erhebliche Leistungsprobleme auf.

Es gibt jedoch nicht-kryptografische Hash-Funktionen, die Werte erzeugen können, die für Ihren Zweck zufällig und gleichzeitig schnell sind. Das, wonach ich normalerweise greife, ist Murmeln . Ich bin kein Java-Benutzer, aber es scheint, dass mindestens eine Java-Implementierung verfügbar ist. Wenn Sie feststellen, dass wirklich jedes Pixel anhand seiner Koordinaten generiert werden muss, anstatt sie alle auf einmal zu generieren und in einer Textur zu speichern, ist dies eine gute Möglichkeit, dies zu tun.

Nathaniel
quelle
1

Ich würde eine Primzahl über 2000 verwenden (maximale typische Auflösung).
Dies minimiert (oder eliminiert doppelte Samen).

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
quelle
0

Randomist zufällig genug. Sie verwenden es aus zwei Hauptgründen falsch.

  • Es war nicht dafür gedacht, wiederholt ausgesät zu werden. Die Zufallseigenschaften gelten nur für eine einzelne Folge von Zufallszahlen.
  • Integer.valueOf(Integer.toString(x)+Integer.toString(y))Zwischen den Pixeln, mit denen Sie arbeiten, besteht eine enorme Korrelation .

Ich würde nur eine Variante des folgenden Codes verwenden, in der Sie eine Hash-Funktion (verwenden Sie nicht Integer.getHashCode) aus den Antworten unter /programming/9624963/java-simplest-integer- auswählen können. hash

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

wo die Hash-Funktion sein könnte

Jimmy
quelle
0

Sie können versuchen, die aktuelle Uhrzeit des Systems als Startwert zu verwenden:

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

Hoffentlich ergibt sich ein zufälligerer Wert.

anonymer Entwickler
quelle
Dadurch wird jedoch nicht jedes Mal der Dame-Wert für die Dame-Koordinate erstellt.
Libelle
0

Hier ist eine einzeilige statische Shader-Funktion, die ich mir ausgedacht habe - Poltergeist (Noisy Ghost).

Es benötigt eine 2D-Koordinate und einen Startwert und wird wie gewünscht monoton wiedergegeben. Es läuft in Echtzeit mit fps, unabhängig von der Bildschirmauflösung. Dafür sind GPUs da.

// 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)); 
}

Jede Auflösung, jede Textur, auf jedem Gerät (auch auf Mobilgeräten), das GL unterstützt (was mit einem Bildschirm so ziemlich alles ist).

Sieh es hier laufen, gerade jetzt!

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

Sie können diesen Shader einfach in Ihr Java-Programm mit Standard-OpenGL oder in jeden Browser mit Standard-WebGL einbinden.

Aus Spaß schmeiße ich den Spießrutenlauf, damit jeder Poltergeist in Qualität und Leistung auf allen Geräten schlagen kann. Noisy Ghost-Regeln! Unbesiegt!

Dominic Cerisano
quelle