Как я могу создать псевдослучайный шаблон из координат X / Y детерминистически?

Question

Я пишу шейдер, который иногда заставляет точку искриться на 2D-карте.(«Искорка» - просто пиксель более яркого цвета.) Мне бы хотелось, чтобы сверкающие блоки отображались случайным и равномерным образом на (бесконечной) плоскости, но я хочу, чтобы искривление было детерминированным на основе координат X и Y.Я попытался создать начальное значение из координат и создать Java Random из этого начального значения, но мои попытки до сих пор приводили к распознаваемым шаблонам.Эта функция будет вызываться часто (много миллионов раз), поэтому производительность критична.

Сначала я попытался имитировать мою реализацию hashCode(), которая использует множитель простого числа, чтобы избежать коллизий.Это привело к видимому разрыву на карте, где ряд точек разделяли одно и то же начальное число.

Затем я попытался создать начальное число, объединив координаты следующим образом:

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

чтобы привести к шаблонным данным, хотя шаблон не так очевиден.Выбранные координаты отображаются в строках, которые распределены неравномерно.

Я избегал использования MD5 или других криптографических алгоритмов хеширования, потому что боюсь влияния на производительность.

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, но намного быстрее ....

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

Может быть удобно присвоить каждой точке Timer, период которой выбран из той же последовательности:

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 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 является хорошо понятным алгоритмом, и криптографическая безопасность не важна для этого приложения.Я определенно хотел бы что-то более быстрое (и менее грязное), однако.