Быстрый генератор псевдослучайных чисел для процедурного контента
Вопрос
Я ищу генератор псевдослучайных чисел, который был бы специализирован для быстрой работы, когда перед генерацией каждого числа ему дается начальное число.Большинство генераторов, которые я видел до сих пор, предполагают, что вы устанавливаете начальное число один раз, а затем генерируете длинную последовательность чисел.Единственное, что чем-то похоже на то, что я видел до сих пор, — это шум Перлина, но он генерирует слишком «гладкие» данные — для аналогичных входных данных он имеет тенденцию давать аналогичные результаты.
Объявление генератора должно выглядеть примерно так:
int RandomNumber1(int seed);
Или:
int RandomNumber3(int seedX, int seedY, int seedZ);
Я думаю, что хорошего RandomNumber1 должно быть достаточно, поскольку можно реализовать RandomNumber3, хешируя его входные данные и передавая результат в RandomNumber1, но я написал второй прототип на случай, если какая-то реализация сможет использовать независимые входные данные.
Предполагаемое использование этого генератора — использовать его для генератора процедурного контента, например, для создания леса путем размещения деревьев в сетке и определения случайного вида деревьев и случайных пространственных смещений для каждого местоположения.
Генератор должен быть очень эффективным (менее 500 циклов ЦП), поскольку процедурный контент создается в огромных количествах в реальном времени во время рендеринга.
Решение
Похоже, вы запрашиваете хэш-функцию, а не PRNG.Поиск в Google «быстрой хэш-функции» дает несколько многообещающих результатов.
uint32_t hash( uint32_t a)
a = (a ^ 61) ^ (a >> 16);
a = a + (a << 3);
a = a ^ (a >> 4);
a = a * 0x27d4eb2d;
a = a ^ (a >> 15);
return a;
}
Редактировать: Да, некоторые хеш-функции определенно выглядят более подходящими, чем другие.
Для ваших целей должно быть достаточно взглянуть на функцию и убедиться, что однобитовое изменение входных данных распространится на множество выходных битов.
Другие советы
Да, вы ищете быстрый алгоритм целочисленного хеширования, а не PRNG.
Этот страница имеет несколько алгоритмов, я уверен, что теперь, когда вы знаете правильные условия поиска, вы найдете гораздо больше.
Редактировать:Исходная страница удалена, можно использовать живую версию. найдено на GitHub.
Вот небольшой генератор случайных чисел, разработанный Джорджем Марсальей.Он эксперт в этой области, поэтому вы можете быть уверены, что генератор обладает хорошими статистическими свойствами.
v = 36969*(v & 65535) + (v >> 16);
u = 18000*(u & 65535) + (u >> 16);
return (v << 16) + u;
Здесь u и v — беззнаковые целые числа.Инициализируйте их любыми ненулевыми значениями.Каждый раз, когда вы генерируете случайное число, сохраните где-нибудь u и v.Вы можете обернуть это в функцию, соответствующую вашей подписи выше (за исключением того, что целые числа не подписаны).
видеть std::tr1::ranlux3
, или другие генераторы случайных чисел, являющиеся частью дополнений TR1 к стандартной библиотеке C++.Я изначально предлагал mt19937, но потом увидел ваше замечание, что он должен быть очень быстрым.TR1 должен быть доступен на Microsoft ВК++ и GCC, а также его можно найти в библиотеках boost, которые поддерживают еще больше компиляторов.
пример адаптирован из повысить документацию:
#include <random>
#include <iostream>
#include <iterator>
#include <functional>
#include <algorithm>
#include <ctime>
using namespace std;
using namespace std::tr1;
int main(){
random_device trueRand;
ranlux3 rng(trueRand); // produces randomness out of thin air
// see pseudo-random number generators
uniform_int<> six(1,6); // distribution that maps to 1..6
// see random number distributions
variate_generator<ranlux3&, uniform_int<> >
die(rng, six); // glues randomness with mapping
// simulate rolling a die
generate_n( ostream_iterator<int>(cout, " "), 10, ref(die));
}
пример вывода:
2 4 4 2 4 5 4 3 6 2
Любой генератор случайных чисел TR1 может засеять любое другой генератор случайных чисел.Если вам нужны результаты более высокого качества, рассмотрите возможность подачи выходных данных mt19937 (который медленнее, но более высокого качества) в minstd_rand или randlux3, которые являются более быстрыми генераторами.
Если память на самом деле не является проблемой и скорость имеет первостепенное значение, вы можете заранее создать большой массив случайных чисел и просто перебирать его во время выполнения.Например, отдельная программа сгенерирует 100 000 случайных чисел и сохранит их как отдельный файл, например
unsigned int randarray []={1,2,3,....}
затем включите этот файл в свою компиляцию, и во время выполнения вашей функции случайных чисел нужно будет только извлекать числа из этого массива и возвращаться к началу, когда она достигнет конца.
Я использую следующий код в своей библиотеке случайных чисел Java — у меня это сработало очень хорошо.Я также использую это для создания процедурного контента.
/**
* State for random number generation
*/
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);
/**
* Gets a long random value
* @return Random long value based on static state
*/
public static long nextLong() {
long a=state;
state = xorShift64(a);
return a;
}
/**
* XORShift algorithm - credit to George Marsaglia!
* @param a initial state
* @return new state
*/
public static final long xorShift64(long a) {
a ^= (a << 21);
a ^= (a >>> 35);
a ^= (a << 4);
return a;
}