Можно ли настроить рандом

Алгоритмы рандома

В этой статье вы увидите самые разнообразные велосипеды алгоритмы для генерации случайных чисел.

Про что статья

C++ rand

Первое что узнаёт начинающий программист С++ по теме получения рандома — функция rand, которая генерирует случайное число в пределах от 0 и RAND_MAX. Константа RAND_MAX описана в файле stdlib.h и равна 32’767, но этом может быть не так, например в Linux (см. коммент). Если же rand() в вашем компиляторе генерирует числа в пределах 32’767 (0x7FFF) и вы хотите получить случайное число большого размера, то код ниже можно рассматривать как вариант решения этой проблемы:

Реализация функции rand в старом C была проста и имела следующий вид:

Данная реализация имела не очень хорошее распределение чисел и ныне в C++ улучшена. Так же стандартная библиотека C++ предлагает дополнительные способы получения случайного числа, о которых ниже.

С++11 STL random

Данный сорт рандома появился в C++11 и представляет из себя следующий набор классов: minstd_rand, mt19937, ranlux, knuth_b и разные их вариации.

Чтобы последовательность случайных чисел не повторялась при каждом запуске программы, задают «зерно» псевдослучайного генератора в виде текущего времени или, в случае с некоторыми ретро (и не только) играми — интервалы между нажатиями клавиш с клавиатуры/джойстика. Библиотека random же предлагает использовать std::random_device для получения зерна лучше чем от time(NULL), однако в случае с компилятором MinGW в Windows функция практически не работает так как надо. До сих пор…

Некоторые из алгоритмов в STL random могут работать быстрее чем rand(), но давать менее качественную последовательность случайных чисел.

PRNG — Pseudo-random Numbers Generator

Можете считать это название — синонимом линейного конгруэнтного метода. PRNG алгоритмы похожи на реализацию rand в C и отличаются лишь константами.

PRNG алгоритмы быстро работают и легки в реализации на многих языках, но не обладают большим периодом.

XorShift

Алгоритм имеющий множество вариаций отличающихся друг от друга периодом и используемыми регистрами. Подробности и разновидности XorShift’а можете посмотреть на Википедии или Хабре. Приведу один из вариантов с последовательностью 2 в 128-й степени.

Данный генератор очень хорош тем, что в нём вообще нет операций деления и умножения — это может быть полезно на процессорах и микроконтроллерах в которых нету ассемблерных инструкций деления/умножения (PIC16, Z80, 6502).

8-bit рандом в эмуляторе z26

Z26 это эмулятор старенькой приставки Atari2600, в коде которого можно обнаружить рандом ориентированный на работу с 1-байтовыми регистрами.

Однажды мне пришлось сделать реализацию этого алгоритма для z80:

Компактный рандом для Z80 от Joe Wingbermuehle

Если вам интересно написание программ под машины с зилогом, то представляю вашему вниманию алгоритм от Joe Wingbermuehle (работает только на зилоге):

Генератор рандома в DOOM

В исходниках игры Дум есть такой интересный файл под названием m_random.c (см. код), в котором описана функция «табличного» рандома, то есть там вообще нет никаких формул и магии с битовыми сдвигами.

Приведу более компактный код наглядно показывающий работу этой функции.

Конечно же это ни какой не рандом и последовательность случайных чисел легко предугадать даже на уровне интуиции в процессе игры, но работает всё это крайне быстро. Если вам не особо важна криптографическая стойкость и вы хотите что-то быстро генерирующее «типа-рандом», то эта функция для вас. Кстати в Quake3 рандом выглядит просто — rand()&0x7FFF.

RDRAND

Некоторые современные процессоры способны генерировать случайные числа с помощью одной ассемблерной команды — RDRAND. Для использования этой функции в C++ вы можете вручную прописать нужные инструкции ассемблерными вставками или же в GCC подключить файл immintrin.h и выбрать любую из вариаций функции _rdrandXX_step, где XX означает число бит в регистре и может быть равно 16, 32 или 64.

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

Концовка

Класс std::minstd_rand из библиотеки STL random работает быстрее обыкновенного rand() и может стать его альтернативной заменой, если вас не особо волнует длинна периода в minstd. Возможны различия в работе этих функций в Windows и Unix’ах.

Источник

«Случайности не случайны, всё это большой обман.» или как работают элементы рандома в играх.

ПРЕДИСЛОВИЕ

Доброго времени суток StopGame! Сегодня я расскажу вам, как работают элементы рандома (случайных событий) и как на самом деле разработчики создают те или иные ситуации, где эти элементы требуются. Сразу уточню для большего понимания: случайность — рандом. Постараюсь рассказать как можно более сжато и понятно для восприятия. Ну что же, поехали!

О ВИДАХ СЛУЧАЙНЫХ ЭЛЕМЕНТОВ

Немногие знают, но компьютер не может создать полностью случайное число, какие алгоритмы бы не применялись. Всегда созданное число будет от чего-нибудь зависеть и не будет полностью случайным. Компьютер — это машина и она подчиняется математическим алгоритмам и формулам, а случайность в принципе прямая противоположность каким-либо математическим правилам. Разработчики всегда идут на ухищрения, чтобы максимально правдоподобно создать иллюзию случайности, но это всё равно нельзя назвать полным рандомом.

На самом деле существует несколько ситуаций, где требуется применение элементов рандома:

1.Процедурная генерация (создание ландшафта и миров).

2.«Честная» генерация предметов (Выпадение предметов из противников, сундуков и тд.).

3.«Не честная» генерация предметов (Кейсы в играх, покупаемые за реальные деньги).

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

5.Различные ситуации, которые должны возникать в рандомное время (Например смена погоды с солнечной на дождливую).

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

Процедурная генерация

Конечно под этим словом подразумевается не только создание ландшафта и окружения, сюда входит местонахождение предметов на локации, персонажей и много чего ещё, но всё же самым популярным методом использования всё равно остаётся генерация случайных миров. Ярким примером может являться создание мира в «Minecraft», где работает именно процедурная генерация, она создаёт абсолютно всё окружение вокруг игрока (все блоки, сундуки, враги, объекты, персонажи и др.) и давайте разберём, как же он создаётся. На самом деле алгоритм не раз менялся, но на сегодняшний день он работает так:

Знаете ли вы, что мир в «Minecraft» не бесконечен? Он составляет 30 на 30 миллионов блоков. При генерации (не только в «Minecraft», во многих играх также) используется так называемый «seed» — начальное значение.

Чтобы создать уникальный мир, это начальное значение создать из случайных цифр и символов. Без него не работает практически никакой метод ГПСЧ (Генератор псевдослучайных чисел). Но так как, компьютер не может создать ничего случайного, игра берёт за случайные цифры дату и время на компьютере. Если вы попытаетесь создать два мира в игре с одной и той же датой и временем (например 20.10.2020, 18:34), то получите два абсолютно одинаковых мира. Но созданием «seed» всё не кончается, далее это начальное значение преобразуется в 32-х битное число путём нескольких формул. После получается число, которое применяется ещё к одному методу — Шуму Перлина.

Шум Перлина на самом деле к звуку никакого отношения не имеет, это по сути картинка (пример на изображении ниже) с множеством оттенков серых, белых и чёрных цветов. Если говорить совсем простым языком, чем темнее пиксель на изображении шума Перлина, тем выше (либо ниже) создаётся ландшафт.

Допустим такой пример (очень упрощённо, на деле всё сложнее, есть куча «фильтров» последующей «полировки» мира). На картинке шума есть пиксели только трёх цветов (без оттенков): белый, серый и чёрный, тогда мир «Minecraft» может сгенерироваться с ландшафтом высотой максимум в 3 блока. Белым будет блок воздуха (по сути отсутствие блока), серым толщина ландшафта в 1 блок, а чёрным толщина в 2 блока. Но такой шум Перлина принято называть двумерным.

В игре используется в основном трёхмерный шум(3D) (но и двумерный тоже работает для «полировки»), так как при использовании только двумерного (2D) невозможно было бы создать например пещеры и различные постройки. Ниже вы можете увидеть 2D шум. На первой картинке вы видите слева сам шум, а справа результат создания (неудачный я нашёл пример, справа создаётся какая-то 2D игра). На второй картинке вы сразу видите результат работы шума Перлина уже в игровом движке. На третей и четвёртой картинке показано всё более понятно.

Вот примерно так и создаются все процедурно-генерируемые миры, шум Перлина совместно с алгоритмами псевдослучаных чисел остаются пожалуй самыми популярными и простыми. Я старался описать как можно более понятно, но допускаю, что всё равно слишком сложно для восприятия. Напишите в комментариях, если не понятно, буду дорабатывать блог. Ну а мы перейдём к следующему элементу случайности. Более подробно и в разы более интересно про процедурную генерацию можно узнать из видео ниже:

«Честная» и «нечестная» генерация предметов.

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

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

Упрощённо эта система работает так: пусть вероятность выпадения предметов такая — обычный (70%), редкий (20%), эпический (9%), легендарный (1%). Всё это суммарно даёт 100% вероятность, и тогда алгоритм будет выглядеть так условно так: если случайно введённое число находится в промежутке от 0 до 70, выпадет обычный предмет, если от 71 до 90, выпадет редкий предмет, если от 91 до 99 то выпадет эпический предмет, а если введённое число 100 выпадет легендарный. Элементом рандома здесь и является это самое ввёденное число. Где же взять это рандомное число? Способов на самом деле масса: от ранее упомянутого seeda (просто брать последние два его числа), до прослушивания атмосферного шума и шума микрофона для его последующего преобразования в цифровой вид (так работает популярный сайт: Random.org).

Однако же StopGame — это игровой портал, поэтому давайте узнаем, как генерируются такие числа в двух, самых популярных игровых движках: Unity и Unreal Engine.

-В этих движках одним из методов используется «XorShift», который берёт за seed дату и время на ПК, потом преобразует полученное число в двоичную систему счисления, потом суммирует это число несколько раз со сдвигом вправо и влево, после полученное число обрезается по длине исходного и получается псевдослучайное число. Более понятно и подробно об этом способе рассказано в видео ниже.

Давайте теперь поговорим о «нечестной» генерации предметов.

Самое широкое распространение такой способ имеет в онлайн играх по типу: «Warface», «Overwatch» и «CS:GO». В них тоже используется принцип, основанный на вероятностях, как и в «честном» способе, только в отличие от него нечестный способ изменяет свою вероятность в зависимости от ранее полученных данных. Теперь языком попроще: если вам выпала «легендарная» вещь с шансом в 1%, то следующая «легендарная» вещь уже будет иметь шанс выпадения например 0.5% или менее, а вещи «обычной» с шансом в 70% наоборот поднимут свой шанс выпадения например до 80%, так после нескольких попыток открытия условных «кейсов в CS:GO» шанс будет повышаться, пока опять не достигнет своего максимума в 1%, а вероятность на выпадение «обычной» вещи не опустится до 70%.

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

Ситуации, где на элементах рандома завязана вся игра:

Я говорю про те игры, где ваша победа напрямую зависит от изначально (или в процессе) полученной случайной комбинации элементов. Самый яркий пример тому в реальной жизни — это игральные карты. Человек перемешивает карты руками, после раздаёт их на всех игроков. Но как карты может перемешать компьютер? На самом деле можно воспользоваться весьма странным, но рабочим методом: отслеживания перемещений стрелки мыши. (Не знаю, используется ли конкретно в конкретно карточных играх такой способ, но во многих проектах он присутствует). Компьютер отслеживает координаты X и Y, на которых сейчас находится мышь и берёт только по последней цифре от каждой координаты. Допустим стрелка мыши находится на координатах X=54 и Y=27. Алгоритм возьмёт для создания случайного числа только 4 (из числа 54) и 7 (из числа 27), далее функций может быть много, числа можно сложить, вычесть, умножить, разделить и получить любое другое новое псевдослучайное число. Далее карты нумеруются допустим от 0 до 36, сложим ранее полученные 4 и 7, получим 11, значит игроку достанется карта под номером 11 из колоды и так, пока игроки не получат нужное количество карт. Естественно отслеживаются все перемещения мыши допустим за минуту времени, так как если каждый раз смотреть на текущую координату мыши, псевдослучайное число всегда будет одним и тем же если мышь не двигается.

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

Давайте перейдём к последнему элементу рандома, который я смог сформулировать.

Различные ситуации, которые должны возникать в рандомное время.

В пример можно привести дождь и грозу из того же «Minecraft». На самом деле там нет никакой случайности, периодичность дождей зависит от всё того же «злополучного» seedа, который создан при генерации мира. При определённых seedах период дождей изменяется, благодаря вычислениям по определённым формулам (которые «Mojang» не показывает). Грубо говоря в одном мире, с одним seed дожди происходят раз в игровых 5 дней, в другом же мире, с другим seed периодичность уже будет например раз в игровых 7 дней. Тут вообще нет никаких элементов рандома, всё происходит закономерно и по формулам.

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

Возьмём в пример странствующих торговцев в «Dying Light». Не могу точно уверять, что всё рабоатет именно так, как я говорю, поскольку доступа к исходному коду «движка» у простых пользователей нет, но всё намекает именно на такой метод.Торговцы появляются в случайное время (которое определяется через ГСПЧ) со случайным товаром в случайном месте. Но и тут к сожалению никакого по настоящему случайного элемента нет. Торговцы появляются в специально заготовленных местах, которые выбрали для них разработчики, и продают товар, который тоже не случайно генерируется (товар создают из специально заготовленных наборов предметов, который разработчики тоже успели ранее сделать). Также и цены на товар могут меняться в большую или меньшую сторону всего одной формулой (убавления процентов к изначальной цене товара), тем самым привлекая игрока «временной скидкой и ограниченным предложением», но всё это лишь иллюзия обмана.

Источник