如何基于X/Y坐标确定性地生成伪随机模式？

Question

我正在编写一个着色器，偶尔会使2D地图上的某个点闪烁。（“闪光”只是更亮色的像素。）我希望这些闪烁的块在（无限的）平面上随机且均匀分布，但基于X和Y坐标，我希望闪烁是确定性的。我尝试从坐标中创建种子，并从该种子创建Java Random，但我的尝试迄今为止导致了可识别的模式。由于这个函数将经常调用（数百万次），因此性能至关重要。

我首先尝试模仿我的hashCode()实现，它使用质数乘法器来避免冲突。这导致地图上出现明显的裂口，其中一系列点共享相同的种子。

然后我尝试通过连接坐标来创建种子，如下所示：

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

这似乎也会导致数据呈现出模式，尽管这种模式不太明显。所选坐标出现在行中，而不是均匀分布。

我避免使用MD5或其他加密哈希算法，因为我担心会影响性能。

- Henry Merriam

---

如果您从一个lcm中生成数百万个伪随机数并在2D平面上绘制，那么您可能会看到可识别的“模式”，除非您使用加密强度的生成器。搜索k-planes。您可能希望使用非线性同余伪随机数发生器。 - Mitch Wheat

Answer 1

以下是一种非常高效的函数，用于以伪随机但确定性的方式混合位：

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

如果您想从x和y坐标生成伪随机长结果，可以执行以下操作：

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

我之前在图形方面成功地使用过这种方法，效果非常好！随机数的质量与java.util.Random相当，但速度要快得多....

- mikera

---

看起来很有趣。你知道有没有评估这种结构的抗碰撞性的文章吗？（对于小地图而言，这不是很重要，但我很好奇。） - Henry Merriam

Answer 2

线性同余生成器在java.util.Random中的实现具有一个优点，即对于任何选择的SEED都可以重复。 鉴于这些声明，

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

您可以按照以下方式初始化一个（可重复）包含N个在矩形（0，0，MAX_X，MAX_Y）中随机选择的点列表：

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

可能会方便一些，给每个点都分配一个计时器，其周期从同一序列中选择：

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

- trashgod

---

挑战在于首先生成那个种子。我不能使用一个固定的种子，因为在任何给定的时间，我只会绘制地图的一小部分。如果我离原点很远，我不希望Random旋转直到它达到我正在绘制的坐标。 - Henry Merriam

啊，我以为选择的点集保持不变；我可以看到优化视图以忽略当前可见区域外的点。 - trashgod

Answer 3

这是我做的一些东西，它可以工作（产生所需的效果），但绝对不完美。

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

除了特别冗长之外，使用Random可能过度了，因为我只调用nextInt()两次。它对于生成特定范围内的值很有用，但是我应该能够通过模算术来实现。

我喜欢MD5是一个众所周知的算法，并且在这个应用程序中加密安全性并不重要。虽然我肯定希望有更快（而且不那么混乱）的东西。

- Henry Merriam