Что такое хороший генератор случайных чисел для игры?

Question

Что такое хороший генератор случайных чисел для игры на C++?

Мои соображения: нужны

1. Много случайных чисел, так что скорость хорошая.
2. Игроки всегда будут жаловаться на случайные числа, но я хотел бы указать их на ссылку, объясняющую, что я действительно выполнял свою работу.
3. Поскольку это коммерческий проект, на который у меня мало времени, было бы неплохо, если бы алгоритм либо a) был относительно прост в реализации, либо b) имел хорошую реализацию, отличную от GPL.
4. Я уже использую rand() в довольно многих местах, поэтому любой другой генератор должен быть лучше, чтобы оправдать все изменения, которые потребуются.

Я мало знаю об этом предмете, поэтому единственной альтернативой, которую я мог бы придумать, является Mersenne Twister; удовлетворяет ли это всем этим требованиям? Что-нибудь еще лучше?

Редактировать: Mersenne Twister, по-видимому, является консенсусным выбором. Но как насчет точки №4? Действительно ли это намного лучше, чем rand()?

Редактировать 2: Позвольте мне быть немного понятнее в пункте 2: игрокам не нужно обманывать, зная случайные числа. Период. Я хочу, чтобы это было достаточно случайным, чтобы люди (по крайней мере те, кто понимает случайность) не могут жаловаться на это, но меня не беспокоят прогнозы. Вот почему я ставлю скорость в качестве главного внимания.

Редактировать 3: Теперь я склоняюсь к RNG Marsaglia, но мне все равно нравится больше ввода. Поэтому я создаю щедрость.

Редактировать 4: Просто примечание. Я намерен принять ответ как раз перед полуночью UTC сегодня (чтобы не возиться с чьей-то защитой). Поэтому, если вы хотите ответить, не ждите до последней минуты!
Также мне нравятся генераторы XORshift от Marsaglia. Кто-нибудь знает о них?

Answer 1

George Marsaglia разработал некоторые из самых лучших и самых быстрых ГСЧЕЙ в настоящее время Multiply-with-carry будучи заметной один для равномерного распределения.

Answer 2

Sometimes Разработчикам игр не нужна истинная случайность, и более подходит shuffle bag.

Если вам нужна случайность, то Twister Mersenne удовлетворяет вашим требованиям. Он быстрый, статистически случайный, имеет длительный период и существует множество реализаций.

Редактировать: rand() обычно реализуется как linear congruential generator. Вероятно, лучше всего, если вы сделаете осознанный выбор того, достаточно ли это для ваших целей.

Answer 3

Mersenne Twister является типичным в отрасли, тем более, что он хорошо поддается SIMD и может быть сделан очень быстро. Knuth популярен также (спасибо, Дэвид).

В большинстве игровых приложений скорость действительно является критическим фактором, так как игроки собираются жаловаться на низкую частоту кадров намного больше, чем будут жаловаться на то, что есть небольшое смещение в сторону генерации 3, когда ему предшествует 7, 2 и 9 в указанном порядке.

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

Answer 4

Mersenne Twister очень хорош, и это быстро. Я использовал его в игре, и это не сложно реализовать или использовать.

WELL random algorithm был разработан как улучшение по сравнению с Mersenne Twister. Game Gems 7 имеет дополнительную информацию. на нем, если вы можете одолжить это или иметь его.

На этой странице WELL, с которой я связал вас, число является периодом алгоритма. То есть вы можете получить 2^N - 1 номера, прежде чем понадобится пересадка, где N равно: 512, 1024, 19937 или 44497. У Mersenne Twister есть период N = 19937 или 2^19937 - 1. Вы будете см это очень большое количество :)

Единственная вещь, которую я могу отметить, что boost имеет random library, который вы должны найти полезным.

В ответ на ваши изменения да, Twister или WELL намного лучше, чем rand(). Кроме того, старый трюк модуля вредит распределению чисел. Еще больше оснований использовать boost :)

Answer 5

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

Если вам нужна куча неподдельных случайных чисел (и вы онлайн-игра), вы можете получить их на Random.org. Используйте их для пошаговых игр или как семена для игр в реальном времени.

Answer 6

Я фанат Isaac, в отличие от mersense твистер, это crypographically безопасный (вы * не может треснуть период, наблюдая рулоны)

IBAA (rc4?) Также является тот, который used by blizzard для предотвращения люди от предсказания случайного числа, используемого для рутлов добычи. Я предполагаю, что что-то подобное делается w/diablo II, когда вы играете с сервера battle.net.

* не может в течение любого разумного периода времени (века?)

Answer 7

Купить дешевые вебкамеру, детектор ионизирующего излучения дыма. Разберите оба из них, детектор дыма содержит мало радиоактивного материала - источника гамма-волн, что приведет к обстрелу фотонов в вашей веб-камера. Это ваш источник истинной случайности :)

Answer 8

на основе генератора случайных чисел Яна С. Буллард:

// utils.hpp 
namespace utils { 
    void srand(unsigned int seed); 
    void srand(); 
    unsigned int rand(); 
} 

// utils.cpp 
#include "utils.hpp" 
#include <time.h> 

namespace { 
    static unsigned int s_rand_high = 1; 
    static unsigned int s_rand_low = 1^0x49616E42; 
} 

void utils::srand(unsigned int seed) 
{ 
    s_rand_high = seed; 
    s_rand_low = seed^0x49616E42; 
} 

void utils::srand() 
{ 
    utils::srand(static_cast<unsigned int>(time(0))); 
} 

unsigned int utils::rand() 
{ 
    static const int shift = sizeof(int)/2; 
    s_rand_high = (s_rand_high >> shift) + (s_rand_high << shift); 
    s_rand_high += s_rand_low; 
    s_rand_low += s_rand_high; 
    return s_rand_high; 
} 

Почему?

• очень, очень быстро
• выше энтропия, чем большинство стандартных rand() реализаций
• легко понять

Answer 9

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

A-ha!

Это ваше настоящее требование!

Никто не может вас погубить, если вы используете Mersenne Twister в этом приложении.

Answer 10

Я бы проголосовал за Mersenne Twister. Реализации широко доступны, он имеет очень большой период 2^19937 -1, является достаточно быстрым и проходит большинство тестов случайности, включая тесты Дихарда, разработанные Марсалья. rand() и Co., являющиеся LCG, производят более низкие отклонения качества, и их последовательные значения могут быть легко выведены.

Следует обратить внимание на то, что необходимо надлежащим образом перевести MT в состояние, которое проходит тесты случайности. Обычно для этой цели используется LCG, например drand48().

Я бы сказал, что MT удовлетворяет всем требованиям, которые вы установили (доказуемо), и было бы излишним для чего-то вроде MWCG imo.

Answer 11

В зависимости от целевой ОС вы могли бы использовать/dev/random. Это действительно не требует какой-либо реализации, и в Linux (и, возможно, в некоторых других операционных системах) это действительно случайное. Чтение блоков до тех пор, пока не будет доступна достаточная энтропия, поэтому вы можете прочитать файл и сохранить его в буфере или чем-то другим. Если вы не можете использовать блокирующий вызов чтения, вы можете использовать/dev/urandom. Он генерирует случайные данные почти так же, как/dev/random, но он повторно использует некоторые случайные данные для немедленного вывода. Это не так безопасно, но может работать нормально, в зависимости от того, что вы планируете с ним делать.

Answer 12

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

Таким образом, в SQL (моя область), это ABS (СУММА (NEWID()))% 1000

Роб

Answer 13

Есть гораздо лучший выбор, чем Вихрь Мерсенна в настоящее время. Вот RNG под названием WELL512, разработанный дизайнерами Mersenne, разработанный 10 лет спустя, и все вокруг лучший выбор для игр. Этот код внесен в общественное достояние доктором Крисом Ломонтом. Он утверждает, что эта реализация на 40% быстрее, чем Mersenne, не страдает от плохой диффузии и ловушки, когда состояние содержит много 0 бит и, очевидно, намного проще. Он имеет период 2^512; ПК занимает 10^100 лет, чтобы перебирать состояния, поэтому он достаточно велик.

Вот документ, в котором рассматриваются PRNG, где я нашел реализацию WELL512.

Так что, быстрее, проще, созданных теми же дизайнерами 10 лет спустя, и производит лучшие цифры, чем Мерсенне. Как вы ошибаетесь?:)

ОБНОВЛЕНИЕ (11-18-14): Исправлена ​​ошибка (изменен 0xDA442D20UL на 0xDA442D24UL, как описано в документе, приведенном выше).

/* initialize state to random bits */ 
static unsigned long state[16]; 
/* init should also reset this to 0 */ 
static unsigned int index = 0; 
/* return 32 bit random number */ 
unsigned long WELLRNG512(void) 
    { 
    unsigned long a, b, c, d; 
    a = state[index]; 
    c = state[(index+13)&15]; 
    b = a^c^(a<<16)^(c<<15); 
    c = state[(index+9)&15]; 
    c ^= (c>>11); 
    a = state[index] = b^c; 
    d = a^((a<<5)&0xDA442D24UL); 
    index = (index + 15)&15; 
    a = state[index]; 
    state[index] = a^b^d^(a<<2)^(b<<18)^(c<<28); 
    return state[index]; 
    } 

Answer 14

Дополнительные критерии, которые следует учитывать, это безопасность потоков. (И вы должны использовать потоки в сегодняшних многоядерных средах.) Просто вызов rand из более чем одного потока может испортить его детерминированное поведение (если ваша игра зависит от этого). По крайней мере, я рекомендую вам переключиться на rand_r.

Answer 15

Знаете что? Простите меня, если вы думаете, что этот ответ полностью сосет ... Но я был (потому что бог знает только, по какой причине ...) используя DateTime.Now.Milliseconds как способ получить случайное число. Я знаю, что это не совсем случайный, но, похоже, он ...

Мне просто нечего было печатать так много, просто чтобы получить случайное число! : P

Answer 16

GameRand реализовать алгоритм размещен здесь http://www.flipcode.com/archives/07-15-2002.shtml

Это то, что я первоначально разработана в конце 80-х годов. Он легко избивает rand() в терминах численного качества, и, поскольку побочным преимуществом является самый быстрый случайный алгоритм.