Gamedev Дмитрий Мучкин
6 711

Как генерируются случайные числа в старых играх

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

В закладки

Игры — это программы, работающие по чётко заданным алгоритмам. Но иногда им необходимы случайные значения — например, чтобы рассчитать, встретятся персонажу RPG враги или нет, сколько их будет, какая у них будет экипировка и так далее.

В таких случаях программисты используют генераторы псевдослучайных чисел (ГПСЧ). Чаще всего это помогает решить задачу, но не всегда: если способ генерации чисел недостаточно продуманный, игроки могут начать эксплуатировать его, получая преимущество, не предусмотренное разработчиками.

Портал Gamasutra изучил методы генерации случайных чисел, используемые в Final Fantasy, Super Mario 64 и Pokemon Emerald, и выявил их сильные и слабые стороны.

Final Fantasy

В первой части Final Fantasy два генератора случайных чисел. Первый используется для расчёта случайных встреч с противниками во время изучения игрового мира. Он происходит с помощью перебора чисел в массиве из 256 заранее заданных значений. Каждый шаг игрока счётчик двигается по массиву вверх и вниз согласно сложному алгоритму, а игра сравнивает выбранное значение с пороговой величиной. Если оно ниже порога, игроку попадаются враги.

Второй ГПСЧ в игре определяет, какие противники игроку попадутся и будут ли они атаковать первыми. Этот генератор тоже использует массив из 256 значений, но считывает значения по порядку. Это значит, что сразу после загрузки сохранения есть вероятность наткнуться на ту же самую группу врагов.

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

Несмотря на это, игроки находят способы использовать ГПСЧ Final Fantasy для получения преимущества. К примеру, в одной из игровых локаций можно встретить промежуточного босса под названием Warmech. Шанс встретить врагов в этой комнате очень высок, но именно Warmech попадается в ней в трёх случаях из 256. Зная положение счётчика в момент начала боя, можно «заставить» игру сгенерировать встречу с этим противником.

Этими возможностями активно пользуются спидраннеры — так, во время быстрого прохождения Final Fantasy в рамках спидран-марафона Awesome Games Done Quick 2017 раннеры Gyre и Feasel успешно избегали опасных столкновений и быстро набирали уровни благодаря знанию механизмов работы ГПСЧ в игре.

Super Mario 64

В первой трёхмерной игре про Марио используется линейный конгруэнтный метод генерации чисел (ЛКГПСЧ) для определения положения монеток и поведения врагов. Главное отличие этого метода от многих других в том, что он считает значения не по порядку.

Всё начинается с исходного значения. За один шаг счётчика генератор выполняет арифметические операции над исходным значением и получает результат, который используется в качестве исходного значения в следующем шаге. Главная опасность здесь — создание такого алгоритма, что исходное значение в какой-то момент повторяется, и ГПСЧ зацикливается.

Как определили энтузиасты, в Super Mario 64 это происходит после 65 тысяч шагов. В теории, эта информация может использоваться для получения преимущества в игре.

Pokemon Emerald

В Pokemon ГПСЧ управляют генерацией покемонов: их вид, уровень и характеристики. Эти алгоритмы должны быть устойчивы к «взлому», потому что покемоны — это самая важная часть геймплея игры, и получение мощных существ в начале прохождения может открыть игроку возможности, которые не предусмотрены разработчиками.

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

Но при создании Pokemon Emerald разработчики допустили необычную ошибку: когда игра запускается, счётчик генератора всегда стоит на нуле. Таким образом, в ней можно точно определить кадр, на котором появится светящийся покемон.

Это не значит, что игроки могут всегда со стопроцентной вероятностью получить существо с нужным качеством, но знание этой информации сильно упрощает работу по его поимке. Без неё им приходилось бы довольствоваться вероятностью в один шанс из 8192.

Ещё один способ использования этого недостатка игры — получение покемонов с высокими индивидуальными характеристиками. Так, на AGDQ 2017 спидраннер манипулировал ГПСЧ, чтобы в самом начале прохождения получить мощного покемона, которого игрок использовал на протяжении почти всей игры.

#геймдизайн

{ "author_name": "Дмитрий Мучкин", "author_type": "self", "tags": ["\u0433\u0435\u0439\u043c\u0434\u0438\u0437\u0430\u0439\u043d"], "comments": 16, "likes": 77, "favorites": 43, "is_advertisement": false, "subsite_label": "gamedev", "id": 21969, "is_wide": false, "is_ugc": true, "date": "Mon, 25 Jun 2018 17:23:03 +0300" }
{ "id": 21969, "author_id": 6322, "diff_limit": 1000, "urls": {"diff":"\/comments\/21969\/get","add":"\/comments\/21969\/add","edit":"\/comments\/edit","remove":"\/admin\/comments\/remove","pin":"\/admin\/comments\/pin","get4edit":"\/comments\/get4edit","complain":"\/comments\/complain","load_more":"\/comments\/loading\/21969"}, "attach_limit": 2, "max_comment_text_length": 5000, "subsite_id": 64954 }

16 комментариев 16 комм.

Популярные

По порядку

Написать комментарий...
25

Меня больше удивило использование "рандомайзера" в фф12. Там в самом начале игры нужно возле первого кристала для сохранения лечиться, пока цифры лечение не выпадут в нужной комбинации. После этого загружаем нужную локацию и "на ощупь" находим невидимый сундук. Потом внимательно следим за определённым npc и в определённый момент открываем. Так получаем невидимый лук, который подходит любому герою и это одно из самых сильных оружий в игре.
Когда я это увидел, был только один вопрос: " как до такого дошли?"
https://youtu.be/vEcD5EjCG_8

Ответить
0

Фигасе.

Ответить
0

Допустим, вначале они выяснили, что именно эти два момента влияют на дроп, а дальше уже перебором. Возможно есть лут круче.

Ответить
3

Никогда не знал чтобы я делал еслиб Math.random()*256 не было. Нужно больше таких минералов как эта статья.

Ответить
0

Вполне годный псевдослучайный генератор делается в несколько строк.
struct random {
private:
union {
uint64 u64;
struct { uint32 u32_1, u32_2; };
} _seed;
public:
uint operator ()() {
_seed.u64 = _seed.u64 * 6364136223846793005ll + 1ll;
return _seed.u32_2;
}
};

Ответить
0

Я прогру на языке который и языком не называют. Там такое к сожалению не возможно. =)

Ответить
1

Но при создании Pokemon Emerald разработчики допустили необычную ошибку

А откуда еще им брать начальное значение на старте? Глобальных часов у GBA не было.

И, да, кстати о рандоме: вчера попал, если все правильно помню, в 1%

Ответить
0

Стартовое значение можно брать например из положения курсора на экране или замерять время в милисекндах между нажатями различных кнопок на пульте управления. Те случаи описанные в статье это просто жесть.

Ответить
0

Курсора на экране

Это ж GameBoy Advance, какой курсор?
А для "время в миллисекундах" как бы тоже можно при желании обмануть PRNG. На самом деле наверное единственное место, откуда можно взять энтропию — это самое начало игры, где игрок вводит имя, затем передвигается и ставит время. Но это сложно, очень сложно, по крайней мере на момент выхода игры — тогда подразумевалось, что ром просто так не вытащить. Комментарий был о том, что называть подобное поведение ошибкой без каких-то подробностей, которые явно указывают на то, что инициализация должна была проходить как-то по-другому (да-да, PlayStation 3, я на тебя смотрю) достаточно странно.

Сейчас вспомнил, что у GBA был датчик освещенности. Но это, как по мне, весьма сомнительный источник, который так же легко обмануть через эмулятор.

А вообще PRNG даже с инициализацией через, к примеру, текущее время, прекрасно обманываются, правда не всегда людьми. Вот, к примеру, прекрасная демонстрация TASBot'ом: https://youtu.be/mSFHKAvTGNk

Ответить
0

В оригинале сказано, что игра, по идее, должна обращаться к часам, чтобы выставить счётчик. Остальные игры этого же поколения (Ruby, Sapphire) обнуляют счётчики, только если батарейки часов помирают)

Ответить
0

А, тогда понятно

Ответить
1

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

Ответить
0

Было полезно, спасибо за статью.

Ответить
0

За такие статьи и люблю дтф

Ответить
0

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

И каких? Где ещё половина статьи? Х)

Ответить
0

Время попадания пули разное, т.к. пущена в разное время:

Ответить
0

Прямой эфир

[ { "id": 1, "label": "100%×150_Branding_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox_method": "createAdaptive", "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfl" } } }, { "id": 2, "label": "1200х400", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfn" } } }, { "id": 3, "label": "240х200 _ТГБ_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fizc" } } }, { "id": 4, "label": "240х200_mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "flbq" } } }, { "id": 5, "label": "300x500_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfk" } } }, { "id": 6, "label": "1180х250_Interpool_баннер над комментариями_Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "clmf", "p2": "ffyh" } } }, { "id": 7, "label": "Article Footer 100%_desktop_mobile", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjxb" } } }, { "id": 8, "label": "Fullscreen Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjoh" } } }, { "id": 9, "label": "Fullscreen Mobile", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjog" } } }, { "id": 10, "label": "Native Partner Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyb" } } }, { "id": 11, "label": "Native Partner Mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyc" } } }, { "id": 12, "label": "Кнопка в шапке", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fdhx" } } }, { "id": 13, "label": "DM InPage Video PartnerCode", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox_method": "createAdaptive", "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "clmf", "p2": "flvn" } } }, { "id": 14, "label": "Yandex context video banner", "provider": "yandex", "yandex": { "block_id": "VI-250597-0", "render_to": "inpage_VI-250597-0-1134314964", "adfox_url": "//ads.adfox.ru/228129/getCode?pp=h&ps=clmf&p2=fpjw&puid1=&puid2=&puid3=&puid4=&puid8=&puid9=&puid10=&puid21=&puid22=&puid31=&puid32=&puid33=&fmt=1&dl={REFERER}&pr=" } }, { "id": 15, "label": "Плашка на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byudo", "p2": "ftjf" } } }, { "id": 17, "label": "Stratum Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fzvb" } } }, { "id": 18, "label": "Stratum Mobile", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fzvc" } } } ]
Невероятно! Skyrim портировали на...
Подписаться на push-уведомления