Случайный шум на основе семян

16

В настоящее время я работаю над программой, которая должна генерировать случайный шум на экране, основываясь на «координатах» пикселя. Координаты должны иметь одинаковый цвет при каждом перезапуске программы. Однако, используя утилиту Java.Random, результаты, которые я получаю, не так случайны, как хотелось бы:

Снимок экрана

Я думал, что если бы я использовал объединенные координаты (как в одном целом числе, сформированном из обеих координат рядом друг с другом), у каждой координаты был бы другой номер. Используя это число в качестве начального числа, я ожидал получить разные случайные числа для каждой координаты, чтобы использовать их для значения rgb этой координаты.

Это код, который я использовал:

public class Generate {

static Random Random;

    public static int TileColor(int x, int y){          
        Random = new Random(Integer.valueOf(Integer.toString(x)+Integer.toString(y)));
        int b = 1 + Random.nextInt(50);
        int g = 1 + Random.nextInt(50);
        int r = 1 + Random.nextInt(50);
        int color = -Color.rgb888(r, g, b);
        return color;
    }
}

Является ли шаблон, который создает программа, из-за того, как работает функция java Random, или я делаю что-то не так, и мне следует попробовать другой подход?

Обновление: теперь я попытался избавиться от проблем, связанных с конкатенацией, используя следующий код:

public static int TileColor(int x, int y){  
            Randomy = new Random(y);
            Randomx = new Random(x);
            Random = new Random(Integer.valueOf(Integer.toString(Randomx.nextInt(1234))+Integer.toString(Randomy.nextInt(1234))));
            int b = 1 + Random.nextInt(100);
            int g = 1 + Random.nextInt(100);
            int r = 1 + Random.nextInt(100);
            int color = -Color.rgb888(r, g, b);
            return color;
}

Каким-то образом это также дало (на мой взгляд) достаточно случайное изображение:

мяу изображение

Этот код, однако, повторяется три раза на пиксель. Несмотря на то, что сейчас это не проблема для меня, я думаю об изменении этого кода на тот случай, если позже мне понадобится улучшенная производительность.

стрекоза
источник
3
Не уверен насчет Java Random, но я уверен, что это не совсем случайно ... Читайте en.wikipedia.org/wiki/Pseudorandom_number_generator Вы поймете, почему вы видите эти шаблоны.
Salketer
23
Нечто важное, чего не хватает в других ответах: не перезаряжайте ГСЧ для каждого пикселя. Разберите его один раз и сгенерируйте последовательные значения для всех пикселей вашего изображения на основе этого.
Конрад Рудольф
4
Примечание: генерация псевдослучайных чисел может быть равномерно распределена в одном измерении , но потерпит неудачу при использовании более чем одного измерения ... вы эффективно генерируете точки в 3D (r, g и b и 3 разных координаты), поэтому вам нужен генератор случайных чисел, который гарантирует не только то, что генерируемые им значения равномерно распределены, но также и генерируемые им триплеты равномерно распределены в трехмерном пространстве.
Бакуриу
6
@Bakuriu Если X, Y и Z - независимые однородные случайные величины, то я уверен, что (X, Y, Z) однороден в трехмерном пространстве.
Джек М
2
Вы можете поэкспериментировать с использованием разных RNG, таких как Mersenne Twister .
Кевин

Ответы:

21

java.util.RandomКласс Java обычно дает вам последовательности псевдослучайных чисел, которые достаточно хороши для использования в играх 1 . Однако эта характеристика применяется только к последовательности из нескольких выборок на основе начального числа. Когда вы повторно инициализируете ГСЧ с увеличивающимися начальными значениями и просматриваете только первое значение каждой последовательности, характеристики случайности будут не такими хорошими.

Что вы могли бы сделать вместо этого:

  • Используйте одно и то же начальное число для генерации целых кусков пикселей за раз. Например, когда вам нужно значение цвета пикселя 425: 487, введите координаты 400: 400 в ГСЧ, сгенерируйте 10000 случайных цветов и используйте цвет с индексом 2587 (25 * 100 + 87). Куски, сгенерированные таким образом, должны быть кэшированы, чтобы избежать повторной генерации этих 10000 случайных цветов для каждого отдельного пикселя этого куска.
  • Вместо использования генератора случайных чисел используйте функцию дайджеста сообщения, чтобы превратить пару координат в значение цвета. Вывод большинства MDF достаточно непредсказуем, чтобы выполнить большинство тестов на случайность. Выходные данные обычно превышают 24 бита, необходимые для значения RGB, но их усечение обычно не составляет проблем.

    Для повышения производительности вы можете комбинировать генерацию дайджеста сообщений с кусками. Создайте небольшие куски пикселей, которые достаточно велики, чтобы использовать всю длину одного вывода вашей функции дайджеста.

1, когда абсолютно необходимо, чтобы никто не мог предсказать следующее число, используйте более медленное, но менее предсказуемоеjava.security.SecureRandom

Philipp
источник
13

Координаты должны иметь одинаковый цвет при каждом перезапуске программы

В этом случае вы захотите использовать детерминированную шумовую функцию, такую ​​как шум Перлина или симплексный шум .

( См. Этот вопрос для получения дополнительной информации о шуме Perlin с некоторыми красивыми картинками. )

В большинстве random()случаев использование встроенной или аналогичной функции будет давать вам разные значения при каждом запуске программы, поскольку они могут использовать часы в качестве входных данных или какое-либо другое псевдослучайное значение.

Другой вариант - создать «карту шума» один раз в автономном режиме, а затем использовать ее в качестве источника случайных чисел.

В вашей реализации вы объединяете строковые представления x и y. Это плохо, поскольку это не уникально для всего домена. Например,

x    y   concatenated
40   20  4020
402   0  4020
10   10  1010
101   0  1010
12   34  1234
123   4  1234
1   234  1234

Удачи!

3Dave
источник
1
Хороший момент о сцепленных числах. Программа, однако, всегда дает один и тот же результат, если я запускаю ее несколько раз. Я также рассмотрел перлин / симплексный шум, мог бы взглянуть на это и посмотреть, работает ли он лучше. Однако я еще не уверен, почему Java создает шаблоны, поскольку проблема конкатенации, кажется, не решает ее полностью
dragonfly
1
Разве недостаточно просто заполнить Random с постоянным начальным значением перед генерацией пикселей?
Джек М,
1
@JackM Это полностью зависит от алгоритма PRNG в игре.
3Dave
4
«Однажды я увидел реализацию rand (), которая использовала каждое значение как начальное значение для следующего значения». Разве не так работает большинство не криптографических генераторов псевдослучайных чисел? Они используют предыдущее случайное число (или состояние) в качестве входных данных для генерации следующего случайного числа / состояния.
JAB
2
@DavidLively Практически все PRNG делают это или что-то эквивалентное, если только их внутреннее состояние не превышает диапазон генерируемых ими чисел (например, твистеры Мерсенна), и даже тогда последовательность случайных чисел, конечно, полностью определяется начальным числом.
Конрад Рудольф
9

Давайте посмотрим, что вы делаете точно:

  • Вы перебираете все пиксели один за другим
  • Для каждого пикселя вы используете конкатенацию его координат в качестве начального числа
  • Затем вы начинаете новый случайный случай с данного семени и вынимаете 3 числа

Все это звучит хорошо, но вы получаете образец, потому что:

Пиксель в 1,11 и пиксель в 11,1 засевают номер 111, поэтому они наверняка имеют одинаковый цвет.

Кроме того, если вы всегда выполняете циклы одинаково, вы можете использовать только один генератор, не нужно использовать один для каждого пикселя. Один на весь образ подойдет! Из-за псевдослучайности все еще будут какие-то паттерны. @David_Lively прав в использовании некоторого алгоритма Шума, он сделает его более случайным.

Salketer
источник
Дело в том, что вид на изображение должен быть в состоянии смещаться (дальше к положительным координатам). Таким образом, этот подход не будет работать полностью
стрекоза
4
На самом деле «все это» звучит не очень хорошо - повторное заполнение детерминированного ГСЧ для каждого пикселя является ужасной стратегией, если только начальное число не принадлежит криптографическому ГСЧ (и даже в этом случае это бесполезная стратегия по причинам, не связанным с распределением).
Конрад Рудольф
Вы можете указать правильный способ объединения чисел в этом контексте. То есть. (x + y * ширина)
Темыр
1

Сделайте генератор цветов, а затем произведите ваши цвета для вашей плитки. Семя только один раз! Вам не нужно высевать больше, по крайней мере, за плитку.

public class RandomColorGenerator {
  private final int minValue;
  private final int range;
  private final Random random;
  public RandomColorGenerator(int minValue, int maxValue, Random random) {
    if (minValue > maxValue || (long)maxValue - (long)minValue > (long)Integer.MAX_VALUE) {
      throw new IllegalArgumentException();
    }
    this.minValue = minValue;
    this.range = maxValue - minValue + 1;
    this.random = Objects.requireNonNull(random);
  }

  public int nextColor() {
    int r = minValue + random.nextInt(range);
    int g = minValue + random.nextInt(range);
    int b = minValue + random.nextInt(range);
    return -Color.rgb888(r, g, b);
  }
}

public class Tile {
  private final int[][] colors;
  public Tile(int width, int height, RandomColorGenerator colorGenerator) {
    this.colors = new int[width][height];
    for (int x = 0; x < width; x++) {
      for (int y = 0; y < height; y++) {
        this.colors[x][y] = colorGenerator.nextColor();
      }
    }
  }

  public int getColor(int x, int y) {
    return colors[x][y];
  }
}

И использование будет как следовать:

RandomColorGenerator generator = new RandomColorGenerator(1, 100, new Random(0xcafebabe));
Tile tile = new Tile(300, 200, generator);
...
// getting the color for x, y:
tile.getColor(x, y);

С этим, если вы не довольны результатом, просто поменяйте Randomсемена. Кроме того, вам нужно только хранить / передавать семена и размеры, чтобы у всех клиентов было одинаковое изображение.

Оливье Грегуар
источник
1

Вместо использования Random, рассмотрите возможность использования хеш-дайджеста, такого как MD5. Это обеспечивает трудно прогнозируемое «случайное» значение на основе определенного ввода, но всегда одинаковое значение для одного и того же ввода.

Пример:

public static int TileColor(int x, int y){
        final MessageDigest md = MessageDigest.getInstance("MD5");
        final ByteBuffer b = ByteBuffer.allocate(8);
        b.putInt(x).putInt(y);
        final byte[] digest = md.digest(b.array());
        return -Color.rgb888(digest[0], digest[1], digest[2]);
}

ПРИМЕЧАНИЕ: я не знаю, откуда берется Color.rgb888 (..), поэтому я не знаю, каков допустимый диапазон. 0-255 нормально, хотя.

Улучшения для рассмотрения:

  • Сделайте переменные MessageDigest и ByteBuffer вне класса, чтобы повысить производительность. Для этого вам нужно будет сбросить ByteBuffer, и метод больше не будет потокобезопасным.
  • Дайджест-массив будет содержать байтовые значения 0-255, если вы хотите использовать другие диапазоны, вам придется поработать с ними.
  • Если вам нужны разные «случайные» результаты, вы можете добавить какое-то «начальное число». Например, измените на ByteBuffer.allocate (12) и добавьте .putInt (seed).
cranphin
источник
1

Другие отмечают, что один из способов получить желаемое поведение - использовать хеш-функцию, известную как «функция дайджеста сообщения». Проблема в том, что они часто основаны на таких алгоритмах, как MD5, которые криптографически безопасны (то есть действительно, действительно, действительно случайны), но очень медленны. Если вы используете криптографическую хэш-функцию каждый раз, когда вам нужен случайный пиксель, вы столкнетесь с довольно серьезными проблемами производительности.

Тем не менее, существуют некриптографические хеш-функции, которые могут выдавать значения, которые являются достаточно случайными для вашей цели, а также быстрыми. То, к чему я обычно обращаюсь, - это бормотание . Я не пользователь Java, но, кажется, есть хотя бы одна доступная реализация Java . Если вы обнаружите, что вам действительно нужно, чтобы каждый пиксель генерировался из его координат, а не генерировал их все сразу и сохранял их в текстуре, то это был бы хороший способ сделать это.

Натаниель
источник
1

Я бы использовал простое число более 2000 (максимальное типичное разрешение).
Это позволит минимизировать (или устранить дублирующиеся семена)

public class Generate {

    static Random Random;

    public static int TileColor(int x, int y){          
        Random = new Random(x + 2213 * y);
        int b = 1 + Random.nextInt(50);
        int g = 1 + Random.nextInt(50);
        int r = 1 + Random.nextInt(50);
        int color = -Color.rgb888(r, g, b);
        return color;
    }
}
папараццо
источник
0

Randomдостаточно случайно Вы используете это неправильно по двум основным причинам.

  • Он не был предназначен для повторного посева. Случайные свойства имеют место только для одной последовательности случайных чисел.
  • Существует огромная корреляция Integer.valueOf(Integer.toString(x)+Integer.toString(y))между пикселями, которые вы засеваете.

Я бы просто использовал несколько вариантов следующего кода, где вы можете выбрать хеш-функцию (не используйте Integer.getHashCode) из ответов на /programming/9624963/java-simplest-integer- гашиш

public static int TileColor(int x, int y) {
    return hash(x ^ hash(y));
}

где хэш-функция может быть

Джимми
источник
0

Вы можете попробовать использовать текущее время системы в качестве начального числа:

Random random = new Random(System.currentTimeMillis())

Надеюсь, это даст более случайное значение.

анонимный разработчик
источник
Однако это не создает значение dame для координаты dame каждый раз.
стрекоза
0

Вот одна строковая статическая функция, которую я придумал - poltergeist (Noisy Ghost).

Он принимает двухмерную координату и начальное число и отображает монотонно по запросу. Он работает в режиме реального времени, независимо от разрешения экрана. Это то, для чего нужны графические процессоры.

// poltergeist (noisy ghost) pseudo-random noise generator function
// dominic.cerisano@standard3d.com 03/24/2015

precision highp float;

float poltergeist(in vec2 coordinate, in float seed) 
{
    return fract(sin(dot(coordinate*seed, vec2(12.9898, 78.233)))*43758.5453); 
}

void mainImage(out vec4 fragColor, in vec2 fragCoord) 
{   
    fragColor = vec4(poltergeist(fragCoord, iGlobalTime)); 
}

Любое разрешение, любая текстура, на любом устройстве (в том числе и на мобильном), поддерживающем GL (что практически одинаково с экраном).

Посмотри, как это работает, прямо сейчас!

https://www.shadertoy.com/view/ltB3zD

Вы можете легко включить этот шейдер в свою Java-программу, используя стандартный opengl, или в любом браузере, использующем стандартный webgl.

Ради интереса я бросаю вызов любому, кто превзойдет Poltergeist по качеству и производительности на всех устройствах. Шумный призрак правил! Непобедимый!

Birkensocks
источник