Софтлок ищут тестами, хотя тупик выводится из структуры: монотонный мир, где ни один поступок не сокращает набор доступных игроку действий, проверяется одним проходом за линейное время. Один расходуемый ключ ломает свойство: пять дверей с пятью ключами дают 120 порядков, и перебирать приходится каждый. Цена задачи растёт до аккермановской – границу доказали Войцех Червинский и Лукаш Орликовский на FOCS в 2021 году.
Рис. 1. Граф мира: новый предмет открывает рёбра и не закрывает ни одного
Монотонный мир и неподвижная точка
Мир описывает ориентированный граф G(V, E) с пометками на рёбрах. Вершины – локации, рёбра – переходы, пометка – условие доступа: «крюк-кошка» или «бомбы или молот». Инвентарь игрока – множество предметов, и переход открыт, когда условие выполнено на текущем наборе.
Свойство монотонности записывается одной строкой. Обозначим через Reach(S) всё достижимое с набором возможностей S; мир монотонен, если из S ⊆ S′ следует Reach(S) ⊆ Reach(S′). Обладать бо́льшим никогда не значит мочь меньше.
Монотонность даёт бесплатную проверку. Берётся стартовый инвентарь, собирается всё достижимое, условия оцениваются заново, шаг повторяется до остановки. Инвентарь растёт на каждом проходе и ограничен сверху, поэтому цикл сходится к единственной наименьшей неподвижной точке независимо от порядка обхода.
Подземелье из десяти комнат раскрывается за три прохода. Пустой инвентарь открывает три комнаты, где лежат бомбы и крюк-кошка; второй проход добавляет пять помещений, доступных с этой парой; третий – оставшиеся два. Разработчики рандомайзеров зовут проходы сферами и печатают их списком в спойлер-логе.
Задачу проходимости решали четырежды в разных областях. Уильям Даулинг и Жан Галье в 1984 году показали, что выполнимость хорновских формул – а условия без отрицания и есть хорновские – проверяется за линейное время. Том Байландер в 1994 году разметил сложность планирования: общая задача PSPACE-полна, а частный случай с положительными предусловиями и положительными эффектами полиномиален.
Рис. 2. Сферы раскрываются слоями: следующий открыт предметами предыдущего
Первая оговорка касается границ модели. Простой орграф описывает только условия «один предмет – один проход»; требование «крюк-кошка и лук» образует гиперребро с двумя началами. Для гиперрёбер нужен аппарат ориентированных гиперграфов: его собрал Джорджо Галло с соавторами в 1993 году, а обзор Джузеппе Аузиелло и Луиджи Лауры обновил в 2017-м.
Вторая оговорка – о цене. Проверка проходимости линейна, а поиск кратчайшего маршрута через тот же мир NP-полон. Алгоритм не решает нерешаемое: отвечает «пройти можно» и не берётся сказать, как быстро.
Геймдизайн: знание, которое нельзя потратить
Крайний случай монотонности показывает Outer Wilds. Солнце вспыхивает сверхновой каждые 22 минуты, система сбрасывается, корабль восстанавливается, физический прогресс отменяется целиком – разрушительнее к состоянию не придумать.
Мир Outer Wilds при этом монотонен идеально, потому что единственная форма прогресса здесь – знание. Знание не расходуется, не выбрасывается и не пропускается: оно хранится в игроке, а не в файле сохранения. Софтлок недостижим по построению, и открытая с первой минуты карта следует из свойства, а не из смелости авторов.
Return of the Obra Dinn устроен так же: подтверждённый факт не становится неподтверждённым. Метроидвании попадают в тот же класс почти случайно – способности в жанре постоянны, двойной прыжок не расходуется при использовании.
Перекос индустрии заметен по инструментам. Рандомайзеры предметов делают преимущественно для метроидваний, а платформа Randovania поддерживает Metroid Prime первой, второй и третьей частей, Dread, Samus Returns, AM2R, Cave Story и Super Metroid. Жанровая монотонность и есть причина такого выбора.
Рис. 3. Сверхновая обнуляет корабль, но не память игрока
Рис. 4. Outer Wilds: вспышка Солнца задаёт ритм игрового цикла
Ключи: цена одного расходуемого предмета
Потраченный ресурс превращает инвентарь из множества в вектор счётчиков. Три ключа отличаются от двух, расход двигает состояние назад по оси, монотонность исчезает. Конструкция известна как система сложения векторов, она же сеть Петри.
Подземелье с пятью запертыми дверями и пятью ключами допускает 120 порядков расходования, восемь дверей дают 40’320, и проверять приходится каждый: достижимость перестала зависеть только от состава инвентаря. Монотонная версия отвечает на вопрос за один проход.
Теория подтверждает оценку сверху. Достижимость в системах сложения векторов разрешима, но аккермановски полна, а двумя годами раньше та же группа во главе с Червинским доказала неэлементарность задачи в Journal of the ACM.
Разрыв виден в живом коде. Рандомайзер Ocarina of Time гарантирует проходимость сида при любом порядке расходования ключей подземелья, и гарантия держится на отдельной логике, написанной поверх алгоритма размещения предметов. Такой код есть в каждом рандомайзере Zelda и не нужен ни одному рандомайзеру Metroid.
Контраст двух серий одного издателя решает всё. Ракетные двери Metroid тратят ракеты, но боезапас восполняется с врагов и станций, поэтому невозвратного нуля не бывает. Малые ключи Zelda не возвращаются никогда, зато не покидают своё подземелье – взрыв состояний огорожен дверями одной локации.
Рандомайзеры: проходимость по построению
Сообщество рандомайзеров решило задачу раньше академии. Калеб Джонсон с соавторами описал три алгоритма размещения в IEEE Access в 2021 году и отметил, что прежде знание лежало в комментариях к коду и чатах разработчиков.
Рис. 5. Расходуемый ключ включает режим паники с тремя выходами
Подходов три. Случайное размещение перемешивает предметы и проверяет результат, прямое заполнение наращивает сферы наружу, обратное – раскладывает с конца, считая недоставленные предметы уже полученными.
Обратное заполнение выигрывает за счёт инварианта. На каждом шаге частичная раскладка продлевается до проходимой, поэтому возвраты не нужны вовсе. Корректность держится ровно на монотонности: как только появляется расходуемый ключ, к алгоритму пристраивают отдельную логику, как в рандомайзерах Zelda.
Платформа Archipelago показывает цену немонотонности в интерфейсе. Функция fill_restrictive принимает режим паники со значениями swap, raise и start_inventory – три способа выйти из тупика, которых в чисто монотонном мире не потребовалось бы.
Отмена хода: топология вместо удобства
Отмена хода меняет саму топологию пространства состояний. Симметричное отношение переходов превращает ориентированный граф в неориентированный, а достижимость в неориентированном графе решается на логарифмической памяти – доказал Омер Рейнгольд в 2008 году в Journal of the ACM.
Рис. 6. Sokoban 97: ящик можно толкать, но нельзя тянуть
Без отмены толкаемый ящик создаёт невозвратные тупики. PSPACE-полноту Sokoban доказал Джозеф Кулберсон в 1997 году, и головоломка до сих пор служит эталонным тестом для планировщиков. Baba Is You позволяет себе механику, где уровень ломается двумя ходами, ровно потому, что отмена встроена в основу.
Второй приём – избыточность вместо сохранности. Deus Ex и Prey разрешают испортить почти всё и остаются проходимыми, потому что к каждой цели ведёт запасной маршрут. Гарантию даёт не монотонность, а связность: ни одна отдельная потеря не фатальна.
Третий приём – монотонный хребет с немонотонной поверхностью. Majora’s Mask проносит через трёхдневный цикл маски и песни, а рупии и расходники отбрасывает; рогалики строят мета-прогрессию по той же схеме. Проверять достаточно хребет, поверхность разрешено делать сколь угодно жестокой.
Частые ошибки
Первая – искать софтлок прохождением. Тестировщик находит тупик, только если случайно выбрал нужный порядок ходов, а монотонный мир проверяется сферами за один прогон и без удачи. Тест доказывает наличие тупика, но не его отсутствие.
Вторая – путать проходимость со скоростью. Проверка отвечает «пройти можно» за линейное время, а кратчайший маршрут через тот же мир ищется NP-полной задачей: для спидрана и темпа нужен другой инструмент.
Третья – разносить немонотонность по всей карте. Малые ключи Zelda живут внутри своего подземелья, и перебор порядков заперт в нём же; ключ, который путешествует между локациями, выпускает перебор на всю игру.
Что запомнить?
- Мир монотонен, если больший инвентарь никогда не сужает достижимое.
- Проходимость монотонного мира проверяется сферами за линейное время.
- Один расходуемый ключ превращает проверку в перебор порядков: пять дверей дают уже 120 вариантов проверки.
- Отмена хода, запасной маршрут и монотонный хребет возвращают проверяемость.
- Немонотонность огораживают одной локацией, монотонный хребет прогоняют на каждой сборке, а поверхность отдают плейтесту.
Заключение
Нижняя граница для систем сложения векторов сдвигалась дважды за три года. В 2021 году Червинский и Орликовский закрыли вопрос аккермановской полнотой, независимо Жером Леру доказал непримитивную рекурсивность, а в 2023-м расширенная группа опубликовала новые нижние оценки для фиксированных размерностей.
Для геймдизайна вывод неутешительный и полезный сразу. Ждать инструмента, который проверит мир со свободно перемещаемыми расходуемыми ключами, бессмысленно: препятствие лежит в самой задаче, а не в качестве реализации. Ограничивать приходится постановку.
Практический порядок работы:
- выписать все расходуемые ресурсы и все переходы, ведущие в одну сторону
- проверить каждый на возобновляемость, отмену, запасной маршрут или магазин
- огородить оставшуюся немонотонность одной локацией, чтобы перебор порядков не разошёлся по игре
- прогонять монотонный хребет на каждой сборке, а поверхность отдать плейтесту.
Поставьте проверку в регулярный контур: правка одного условия открывает тупик в другом конце карты. Софтлок – редкий случай, когда дефект дешевле вывести на бумаге, чем поймать прохождением. Сферы подскажут, что игрок сможет увидеть. Расходуемый ключ подскажет, сколько будет стоить это выяснить.