¿Cómo puedo producir un patrón pseudoaleatorio desde las coordenadas X/Y de manera determinista?

Question

Escribo un sombreador que ocasionalmente hace brillar un punto en un mapa 2D. (El "brillo" es simplemente un píxel de color más brillante.) Me gustaría que los bloques destellados aparezcan aleatoria y uniformemente distribuidos en el plano (infinito), pero quiero que el destello sea determinista en función de las coordenadas X e Y. Intenté crear una semilla a partir de las coordenadas y crear una Java Random de esa semilla, pero mis intentos hasta ahora han resultado en patrones reconocibles. Esta función se llamará con frecuencia (muchos millones de veces) por lo que el rendimiento es crítico.

Intenté por primera vez imitar mi implementación hashCode(), que utiliza un multiplicador de número primo para evitar colisiones. Esto resultó en un corte visible en el mapa donde una serie de puntos compartía la misma semilla.

Luego trató de crear una semilla mediante la concatenación de las coordenadas, así:

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

Este parece ser el resultado de los datos modelados y, aunque el patrón no es tan obvio. Las coordenadas seleccionadas aparecen en líneas, no distribuidas uniformemente.

He evitado usar MD5 u otros algoritmos hash criptográficos porque tengo miedo del impacto en el rendimiento.

Answer 1

El linear congruential generator implementado en java.util.Random tiene la ventaja de ser repetible para cualquier SEED elegido. Teniendo en cuenta estas declaraciones,

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

Puede inicializar una lista (repetible) de N puntos elegidos al azar en el rectángulo (0, 0, MAX_X, MAX_Y) como sigue:

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

Puede ser conveniente para dar a cada punto de un período Timer cuya se elige de la misma secuencia:

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

La siguiente es una función muy eficiente para mezclar bits en un ps eudo-azar, sino de manera determinista:

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

Así que si quieres un resultado a largo pseudo-aleatoria de x e y las coordenadas que podría hacer algo como:

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

que he usado este enfoque ¡con éxito en gráficos antes, da resultados bastante buenos! La calidad de los números aleatorios es casi tan buena como java.util.Random pero es mucho más rápida ...

Answer 3

Esto es algo que hice que funciona (produce el efecto deseado) pero definitivamente no es perfecto.

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

Aparte de ser particularmente detallado, el uso de la Random es probablemente excesiva ya que sólo tire llamar nextInt() dos veces. Es útil para generar valores en un rango específico, pero de todos modos debería poder hacer eso con la aritmética de módulo.

Me gusta que MD5 sea un algoritmo bien entendido, y la seguridad criptográfica no es importante para esta aplicación. Sin embargo, definitivamente me gustaría algo más rápido (y menos desordenado).