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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

* не может в разумные сроки (столетия?)

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

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

Однако следует отметить один момент: правильно установить MT в состояние, которое проходит тесты на случайность.

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

// 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 () реализации
• легко понять

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

А-ха!

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

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

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

Итак, в SQL (моя область) это ABS (CHECKSUM (NEWID ()))% 1000

Роб

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

Вот статья, в которой рассматривается ГПСЧ, в которой я нашел реализацию 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];
   }

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

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

Я просто не мог беспокоиться о том, чтобы набирать столько ТОЛЬКО для того, чтобы получить случайное число! : P