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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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