Игра никогда не составляет головоломку вручную. Она выращивает её из одного-единственного числа, а затем разыгрывает эту головоломку сама против себя, чтобы убедиться, что та не тривиальна и не невозможна, — ещё до того, как вы её увидите.
Написано и отредактировано на английском языке. Эта русская версия создана машинным переводом; там, где важна точность, авторитетным остаётся английский оригинал. Читать оригинал на английском →
Уровень Contraption нигде не хранится. Нет файла, где было бы записано, где находится цель или как расположены уступы. Вместо этого весь уровень — стартовая позиция шарика, положение цели, число и расстановка неподвижных стенок, набор выдаваемых вам деталей — вычисляется из одного начального числа, называемого сидом (seed). Дайте генератору тот же сид — и получите байт в байт ту же головоломку. 1
Это возможно потому, что единственный источник «случайности» для генератора — маленький детерминированный генератор псевдослучайных чисел. Contraption использует mulberry32 — компактный 32-битный генератор, автор которого Томми Эттингер (Tommy Ettinger); его легко узнать по фирменной константе 0x6d2b79f5, прибавляемой к состоянию при каждом вызове. 2 Он быстр, умещается в несколько строк и, что принципиально, вовсе не случаен: это фиксированная математическая последовательность, которая лишь выглядит перемешанной. Задайте ему начало — и он будет выдавать один и тот же поток чисел вечно. Затем генератор уровня читает этот поток, решая, куда что поставить.
Режим Daily («Ежедневный») опирается на эту детерминированность, чтобы сделать нечто социальное. Его сид не случаен — он изготовлен из календаря. Игра берёт сегодняшнюю дату по всемирному времени, записывает её в короткую строку вроде "contraption:2026-7-28" и пропускает этот текст через хеш-функцию, сжимая его до одного 32-битного числа. 1
Хеш — это FNV-1a, известный некриптографический перемешиватель: он начинает с фиксированного смещения — десятичного 2 166 136 261, или 0x811c9dc5, — и для каждого символа вмешивает его операцией исключающего ИЛИ, а затем умножает на простое число FNV 16 777 619. 3 В итоге получается число, стабильное в пределах дня и совершенно иное на следующий день, так что изменение даты на один символ полностью разбрасывает сид. Поскольку календарь у всех один, одинаков и сид, а значит, и головоломка. Два незнакомца на противоположных концах света открывают Daily и видят одно и то же поле — именно это и делает сравнение результатов осмысленным.
Ежедневное испытание честно не потому, что сервер рассылает всем один и тот же уровень, а потому, что копия игры у каждого независимо вычисляет один и тот же уровень из одной и той же даты.
Случайную геометрию создать легко; хорошую случайную геометрию — нет. Генератор, который просто разбрасывает цель и несколько уступов, иногда выдаст уровень, где шарик, отпущенный сверху, сам падает прямо в цель. Это не головоломка, а заставка. Поэтому, прежде чем принять мир-кандидат, Contraption проводит тихую проверку, которую код называет preSolved: он моделирует уровень без единой поставленной детали и проверяет, не доходит ли голый шарик до цели под действием одной лишь гравитации. Если доходит, уровень выбрасывается, и генератор бросает кости заново. 1
Это тонкая инверсия привычного представления о физическом движке. Та же функция simulate(), которая разыгрывает вашу машину, во время генерации обращается внутрь — чтобы проверить сложность самого уровня. Движок — одновременно и судья вашего решения, и контролёр качества головоломки.
Отбраковать слишком лёгкий уровень — лишь половина дела. Другая опасность — невозможный уровень, где цель спрятана там, куда не довести шарик никакой расстановкой деталей. Contraption защищается от этого маленьким решателем полного перебора под названием plausiblySolvable. Он не мыслит хитро. Он просто пробует. 1
Точнее, он проводит один-единственный пандус по сетке позиций над полем и в каждой точке пробует четыре разных наклона. Для каждой такой пробной расстановки он запускает полную симуляцию и спрашивает: довёл ли этот один пандус шарик до цели? Как только какая-либо расстановка срабатывает, уровень объявляется решаемым и отправляется вам. Если после всего прохода ничего не сработало, генератор предпочитает отбросить уровень и попробовать новый сид.
| Параметр прохода | Диапазон | Смысл |
|---|---|---|
| Пандус X | 15 → 85, шаг 14 | столбцы поперёк поля |
| Пандус Y | 30 → 120, шаг 18 | ряды сверху вниз по полю |
| Пробуемые углы | 4 | ±0,45 и ±0,8 радиана |
| Проверка на расстановку | 1 полная симуляция | доходит ли шарик до цели? |
Стоит честно сказать, что именно это доказывает, — ведь и код об этом честен: комментарий называет проверку «cheap plausibility check … not exhaustive» («дешёвая проверка правдоподобия… не исчерпывающая»). Уровень, прошедший её, заведомо имеет хотя бы одно грубое решение с одним пандусом. Уровень, не прошедший её, всё ещё может решаться вентилятором, шестернёй или более хитрым пандусом, которого сетка не пробовала, поэтому генератор не считает неудачу доказательством невозможности. Первый найденный нетривиальный мир он сохраняет как запасной, и если сорок попыток проходят без чистого решения одной деталью, он выдаёт этот запасной вариант, а не зацикливается навечно. Итог — прагматичная гарантия: никогда не бесплатная победа, почти всегда настоящий путь к цели и никогда не бесконечное ожидание «идеального» уровня. 1
Если взглянуть шире, генератор уровней Contraption — чистый пример очень старого и очень общего способа решения задач: сгенерируй и проверь. Предложи кандидата наугад; проверь его на соответствие требованиям; оставь, если прошёл, отбрось и предложи нового, если нет. Этот цикл стоит за процедурным контентом в бесчисленных играх, за значительной частью эволюционных вычислений и, если прищуриться, за самим естественным отбором: мутация предлагает, среда проверяет, выжившие остаются. 4
Элегантность версии Contraption в том, что проверка здесь — не дешёвая замена играбельности, она и есть играбельность. Генератор не оценивает честность уровня, считая уступы или измеряя расстояния. Он буквально играет в уровень дважды: один раз пустым — убедиться, что это не подарок, и один раз с пробным пандусом — убедиться, что путь существует. Та же детерминированная физика, что будет судить ваше решение, проверяла и головоломку. Нет отдельного «валидатора уровней», который мог бы разойтись с настоящими правилами, потому что набор правил один и используется для всего.
А поскольку всё детерминировано, эта проверка свободна от везения в обе стороны. Ежедневный сид не может сговориться и подсунуть одному игроку поле легче, чем другому, и не может никому подсунуть нечестное поле — потому что, прежде чем стать испытанием, уровень уже пережил партию, которую игра сыграла в него сама против себя.