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

Question

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

Мои соображения таковы:

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

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

Редактировать: Мерсенн Твистер, кажется, консенсусный выбор. Но как насчет пункта № 4? Это действительно намного лучше, чем rand()?

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

Редактировать 3: Сейчас я склоняюсь к ГСМ Marsaglia, но мне все еще хотелось бы большего. Поэтому я назначаю щедрость.

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

Answer 1

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

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

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

Answer 2

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

Вот статья с обзором PRNG, в которой я нашел реализацию WELL512. http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

Итак - быстрее, проще, созданный теми же дизайнерами спустя 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 3

Джордж Марсалья разработал один из лучших и быстрых ГСЧ, доступных в настоящее время Multiply-with-carry является заметным для равномерного распределения.

=== Обновление 2018-09-12 ===

Для моей собственной работы я сейчас использую Xoshiro256 **, который является своего рода эволюцией / обновлением XorShift Марсальи.

Answer 4

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

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

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

Answer 5

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

Answer 6

Мерсенн Твистер очень хорош, и он также быстр. Я использовал его в игре, и его совсем нетрудно реализовать или использовать.

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

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

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

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

Answer 7

Я фанат Исаака , в отличие от мерсенсовского твистера, он крипографически безопасен (вы не можете взломать период, наблюдая за бросками)

IBAA (rc4?) - также тот, который используется Blizzard , чтобы препятствовать людям предсказывать случайное число, используемое для бросков добычи. Diablo II, когда вы играете с сервера Battle.net.

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

Answer 8

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

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

Answer 9

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

// 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 10

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