Предыдущая часть:
В предыдущих частях я освещал вопрос хранения данных в большой карте 4096 * 4096 клеток.
Строго говоря, нужно хранить данные, чтобы добиться наибольшей гибкости игры. В тех частях карты, которые мы не посещаем, может кипеть жизнь и без нашего участия.
В старых играх такие возможности были ограничены, и поэтому можно было вообще не хранить предыдущие данные, как только мы ушли в следующую комнату.
Но тогда возникает проблема: как вернуться назад в уже посещённую комнату?
Если мы попробуем ещё раз её сгенерировать, то получим совершенно другую комнату, так как всё строится только на случайных числах.
Seed
Числа, полученные из программного генератора случайных чисел (ГСЧ), на самом деле псевдо-случайны. Это всего лишь некая математическая формула, простая или сложная, которая вычисляет следующее число, базируясь на предыдущем шаге. Поэтому генератор точнее называть ГПСЧ.
У формулы есть начальное число, которое называется seed (семя). Оно задаёт старт последовательности случайных чисел, которая будет всегда одна и та же, если семя одно и то же.
Если мы хотим в будущем воссоздать комнату в оригинальном виде, мы должны при создании назначить ей семя и засеять им ГПСЧ. Когда эту комнату надо повторить, мы просто засеваем ГПСЧ тем же семенем.
Значит, вместо целого куска карты достаточно хранить всего лишь одно число – семя для него.
Да
Как обойтись вообще без хранения чего-либо?
У каждой клетки карты есть собственные координаты (x, y). Они не хранятся специально, потому что легко вычисляются.
Две координаты, два числа, можно преобразовать в одно число, например так:
seed = y * 4096 + x
И это число будет семенем для клетки с координатами (x, y).
Но
Проблема номер 1:
Координаты (x, y) в каждом новом прохождении игры одни и те же, значит игра будет получаться всегда одна и та же. Эту проблему можно решить, задавая дополнительное уникальное семя на старте новой игры и смешивая его с семенем, получаемым из координат (x, y).
Проблема номер 2:
Мы используем ГПСЧ для самых разных целей: для генерации карты, создания врагов, расчёта атак в битвах, выпадения предметов.
Засевая ГПСЧ повторно, мы просто сбрасываем его текущее состояние в начальное. Казалось бы, тут нет ничего страшного. Мы построим нужный кусок карты, а затем ГПСЧ просто продолжит работать, выдавая случайные числа.
Но это значит, что допустим следующая битва тоже повторится в точности, ведь последовательность случайных чисел будет та же самая.
Не вопрос, скажем мы. Надо после генерации комнаты засеять генератор новым семенем.
Действительно, это сработает. Но нужно проявлять осторожность.
Конкретно в Питоне есть лайфхак: состояние генератора можно сохранить, сделать с ним что угодно, а потом восстановить и продолжить с того же места. Это по идее лучшая стратегия.
Проблемы ГПСЧ
Очень многие ГПСЧ имеют недостатки, связанные с их псевдо-природой. В частности, числа могут обладать характеристиками случайных внутри последовательности, но не между последовательностями.
То есть даже если вы выберете другое семя, числа из этой последовательности всё равно будут определённым (неслучайным) образом коррелировать с числами из любой другой последовательности. И это может внести в игру какие-то неявные закономерности, которые приведут к ухудшению качества геймплея.
Различных алгоритмов ГПСЧ много, поэтому можно выбрать такой, который лишён недостатков. Но тут возникнет другая проблема: производительность. В играх, как правило, стремятся использовать очень быстрые ГПСЧ, которые неминуемо имеют компромиссы.
Целевой платформой для игры PyRogue является Питон, поэтому я проверил, как работает ГПСЧ из модуля random. Я прошёл в цикле по каждому пикселу экрана и задал ему случайный цвет из диапазона (0,1):
Как видим, распределение чёрных и белых пикселов вполне себе случайное.
Далее я повторил то же самое, но для каждой точки засевал генератор её собственными координатами (x, y) с помощью метода random.seed():
Здесь распределение тоже выглядит случайным. Если бы в генераторе были какие-то недостатки, то точки начали бы складываться в видимый узор.
При повторном запуске программы я буду всегда получать одни и те же точки. Тут есть один нюанс: вариант с засеванием работает в несколько раз медленнее, чем вариант без засевания. Правда, конкретно здесь я могу это игнорировать, так как по факту делается 480 000 засеваний подряд, а это очень много.
Тем не менее, далее мы рассмотрим методы, направленные на преодоление недостатков медленных либо плохо работающих ГПСЧ. В частности, в JavaScript вообще нет возможности засеять генератор (о чём они там думали?)
Хэш-функция
Суть хэш-функции в том, чтобы из любых значений на входе получить значение на выходе, которое собственно и есть хэш. Если давать ей одни и те же значения, то и на выходе будет одно и то же значение.
Фактически это то же самое, что
- засеять ГПСЧ входными значениями
- получить случайное число из генератора
Здесь есть два ключевых для нас момента. Первый это воспроизводимость результата. Второй это отсутствие состояния у функции – мы просто даём ей какие-то числа на вход, а она даёт число на выходе. Таким образом, не требуется ничего перезасевать.
Как выглядит простейшая хэш-функция? Например, так:
- вход: 1 → выход: 1
- вход: 2 → выход: 2
- вход: 3 → выход: 3
То есть на выходе – то же самое, что на входе. В чём смысл? Это просто демонстрация: функция работает так, как должна работать хэш-функция. Правда, не приносит никакой пользы.
Чтобы она была нам полезной в качестве источника случайных чисел, нужна соответствующая математика, которая превращала бы числа 1, 2, 3... на входе в какие-то совершенно несвязанные числа на выходе.
Одной из таких функций является криптографическая функция md5. Её использовали для хранения в базе паролей. На входе она получает пароль, а на выходе – случайное число, которое является хэшем этого пароля. Правда, её в конце концов взломали и сейчас она не рекомендуется для криптографических задач. Мы могли бы использовать её для игры, но нам она также не подходит из-за вычислительной сложности.
Поиски быстрого и качественного варианта привели к функции xxHash:
Она портирована с языка C на язык C#, и я выбрал именно этот вариант, потому что он гораздо чище. Планировал портировать его на Питон, но после проверки работы модуля random мне уже кажется, что это не требуется.
Совмещение хэш-функции и ГПСЧ
Для каждой клетки карты можно получать хэш с помощью хэш-функции от её координат. Чтобы построить лабиринт внутри клетки, можно этим хэшем засеять ГПСЧ и далее брать случайные числа из него.
С учётом вышепроделанных экспериментов это вроде и не нужно, так как ГПСЧ в Питоне справляется сам. Но может иметь свои плюсы. Скажем, засевать ГПСЧ хешем может быть лучше, чем координатами, так как это независимый от ГПСЧ источник.
Или это может быть быстрее... В общем, пока непонятно, Питон обнулил мне все возможные причины, зачем могла понадобиться хэш-функция :)
