Come posso produrre un pattern pseudocasuale dalle coordinate X/Y deterministicamente?

Question

Sto scrivendo uno shader che occasionalmente fa scintillare un punto su una mappa 2D. (Lo "scintillio" è semplicemente un pixel più luminoso). Vorrei che i blocchi scintillanti appaiano distribuiti in modo casuale e uniforme sul piano (infinito), ma voglio che lo scintillio sia deterministico sulla base delle coordinate X e Y. Ho provato a creare seed dalle coordinate e a creare un Java Random da quel seme, ma i miei tentativi finora hanno portato a modelli riconoscibili. Questa funzione verrà chiamata frequentemente (molte milioni di volte), quindi le prestazioni sono fondamentali.

Ho prima tentato di simulare l'implementazione hashCode(), che utilizza un moltiplicatore di numeri primi per evitare collisioni. Ciò ha provocato uno squarcio visibile attraverso la mappa in cui una serie di punti ha condiviso lo stesso seme.

Ho quindi cercato di creare un seme concatenando le coordinate in questo modo:

long seed = ((long) x << 32) | (long) y; 
Random rand = new Random(seed); 

Questo sembra causare dati fantasia pure, se il modello non è così evidente. Le coordinate selezionate appaiono in linee, non distribuite uniformemente.

Ho evitato di utilizzare MD5 o altri algoritmi di hashing crittografico perché temo l'impatto sulle prestazioni.

Answer 1

Il linear congruential generator implementato in java.util.Random ha il vantaggio di essere ripetibile per qualsiasi SEED scelto. Alla luce di queste dichiarazioni,

private static final int SEED = 42; 
private static final int N = 128; 
private static final int MAX_X = 1024; 
private static final int MAX_Y = 1024; 
private final Random rnd = new Random(SEED); 
private final List<SparklePoint> list = new ArrayList<SparklePoint>(N); 

È possibile inizializzare una (ripetibile) elenco delle N punti scelti a caso nel rettangolo (0, 0, MAX_X, MAX_Y) come segue:

public void init(int seed) { 
    for (int i = 0; i < N; i++) { 
     int x = rnd.nextInt(MAX_X); 
     int y = rnd.nextInt(MAX_Y); 
     list.add(new SparklePoint(x, y)); 
    } 
} 

Può essere conveniente per dare ad ogni punto un periodo Timer cui viene scelto dalla stessa sequenza:

private class SparklePoint implements ActionListener { 

    private static final int MAX_DELAY = 1000; 
    private final Point p; 
    private final Timer t; 
    private boolean bright; 

    public SparklePoint(int x, int y) { 
     p = new Point(x, y); 
     t = new Timer(rnd.nextInt(MAX_DELAY), this); 
     t.setRepeats(false); 
     t.start(); 
    } 

    @Override 
    public void actionPerformed(ActionEvent e) { 
     t.stop(); 
     if (bright) { 
      // darken p 
     } else { 
      // brighten p 
     } 
     bright = !bright; 
     t.setDelay(rnd.nextInt(MAX_DELAY)); 
     t.start(); 
    } 
} 

Answer 2

Quanto segue è una funzione molto efficiente per la miscelazione di bit in una ps Eudo-casuale, ma modo deterministico:

public static final long xorShift64(long a) { 
    a ^= (a << 21); 
    a ^= (a >>> 35); 
    a ^= (a << 4); 
    return a; 
} 

Quindi, se si vuole un risultato a lungo pseudo-casuale da xey coordinate si potrebbe fare qualcosa di simile:

long mix = xorShift64(x) + Long.rotateLeft(xorShift64(y),32) + 0xCAFEBABE; 
    long result = xorShift64(mix); 

Ho usato questo approccio con successo in grafica prima, dà risultati abbastanza buoni! La qualità dei numeri casuali è buona quanto java.util.Random ma è molto più veloce ....

Answer 3

Questo è qualcosa che ho fatto che funziona (produce l'effetto desiderato) ma sicuramente non è perfetto.

MessageDigest md5; 
try { 
    md5 = MessageDigest.getInstance("MD5"); 
} catch (NoSuchAlgorithmException e) { 
    e.printStackTrace(); 
    return null; 
} 
md5.update(new byte[] { 
    (byte)(x >>> 24), 
    (byte)(x >>> 16), 
    (byte)(x >>> 8), 
    (byte)x, 
    (byte)(z >>> 24), 
    (byte)(z >>> 16), 
    (byte)(z >>> 8), 
    (byte)z 
}, 0, 8); 
byte[] digest = md5.digest(); 
long seed = digest[0] + (digest[1] << 8) + (digest[2] << 16) + (digest[3] << 24) + (digest[4] << 32) + (digest[5] << 40) + (digest[6] << 48) + (digest[7] << 56); 
Random random = new Random(seed); 

Oltre ad essere particolarmente prolisso, l'uso del Random è probabilmente eccessivo da quando ho solo tirare chiamare nextInt() due volte. È utile per generare valori in un intervallo specifico, ma dovrei essere in grado di farlo con l'aritmetica modulo comunque.

Mi piace che MD5 sia un algoritmo ben compreso e la sicurezza crittografica non è importante per questa applicazione. Mi piacerebbe sicuramente qualcosa di più veloce (e meno disordinato), però.