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

Ответ 1

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

Ответ 2

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

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

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

Ответ 3

В настоящее время существует намного лучший выбор, чем 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];
   }

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

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

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

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

Ответ 7

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

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

Ответ 8

Я поклонник Isaac, в отличие от mersense twister, он кристально защищен (вы * не можете взломать период на наблюдение за рулонами)

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

* не может быть в течение разумных временных рамок (столетий?)

Ответ 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()
• легко понять

Ответ 10

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

Ответ 11

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

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

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

Ответ 12

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

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

Ответ 13

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

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

Ответ 14

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

А-ха!

Там ваше реальное требование!

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

Ответ 15

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

Ответ 16

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

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

Rob