How can I produce a pseudorandom pattern from X/Y coordinates deterministically?

Question

I'm writing a shader which occasionally makes a point sparkle on a 2D map. (The "sparkle" is simply a brighter-colored pixel.) I'd like the sparkled blocks to appear randomly and uniformly distributed on the (infinite) plane, but I want the sparkling to be deterministic based on X and Y coordinates. I tried creating seed from the coordinates and creating a Java Random from that seed, but my attempts have so far resulted in recognizable patterns. This function will be called frequently (many millions of times) so performance is critical.

I first tried to mimic my hashCode() implementation, which uses a prime number multiplier to avoid collisions. This resulted in a visible gash across the map where a series of points shared the same seed.

I then tried to create a seed by concatenating the coordinates like so:

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

This seems to result in patterned data as well, though the pattern isn't as obvious. The selected coordinates appear in lines, not evenly distributed at all.

I've avoided using MD5 or other cryptographic hashing algorithms because I'm afraid of the performance impact.

Answer 1

The linear congruential generator implemented in java.util.Random has the advantage of being repeatable for any chosen SEED. Given these declarations,

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

You can initialize a (repeatable) list of N randomly chosen points in the rectangle (0, 0, MAX_X, MAX_Y) as follows:

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

It may be convenient to give each point a Timer whose period is chosen from the same sequence:

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

The following is a very efficient function for mixing bits in a pseudo-random but deterministic fashion:

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

So if you want a pseudo-random long result from x and y co-ordinates you could do something like:

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

I've used this approach successfully in graphics before, gives pretty good results! The quality of random numbers is about as good as java.util.Random but it is much faster....

Answer 3

This is something I did which works (produces the desired effect) but definitely isn't perfect.

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

Aside from being particularly verbose, the use of the Random is probably excessive since I only pull call nextInt() twice. It's useful for generating values in a specific range, but I should be able to do that with modulo arithmetic anyway.

I like that MD5 is a well-understood algorithm, and cryptographic security is not important for this application. I would definitely like something faster (and less messy), though.