Замки в Gothic 1 Remake довели меня, и я написал сайт, который вскрывает любой из них

В ремейке Готики две сложности: выжить в Колонии и открыть сундук. С первой справляется прокачка. Со второй у меня дошло до того, что я сел разбираться - листочек, математика, код - и в итоге получился unlock my loot. Ниже про то, как я до этого докатился и что вышло.

Бесплатно, без регистрации: unlockmyloot.com, код открыт на GitHub. Проводил ресерч и разбирался в алгоритмах и поисках решениях сам; в удобную оболочку это уже упаковывал с нейронкой.

Правила выглядят безобидно. У каждой пластины семь отверстий, штифт надо привести в центральное. Жмёшь влево-вправо - он ездит.

Но пластины связаны: двигаешь третью - едет пятая. Двигаешь пятую - едет вторая, в обратную сторону. Связи односторонние: первая тянет третью, а третья первую нет. На шести пластинах эта паутина уже не помещается в голове.

За ошибку наказывают. Упёрся любой пластиной в край, даже той, которую не трогал, и отмычка получает урон. Пара таких промахов - и она ломается, прогресс сбрасывается.

Да, можно прокачать взлом у Фингерса. Но отдавать 10 очков обучения за то, чтобы реже ломать железки, жаба не позволяет. Эти очки нужны на мастерство лука (да, играю трусом).

Сначала казалось, что я умный. Четырёхпластинные замки решаются головой: подвигал, запомнил связи, развёл штифты. Даже приятно.

Потом попался сундук, где две пластины ходили строго в противофазе, а третья цепляла обе. Я сидел с листочком и рисовал стрелочки. Сломал шесть отмычек, загрузил сейв двенадцать раз. Бумага не спасла: мало вычислить, куда сколько двигать - нужен ещё правильный порядок ходов. А его на листочке уже не просчитаешь.

Я полез разбираться и выяснил, что это вариация Lights Out. Была такая игрушка в 90-х: поле из лампочек, нажимаешь на одну - переключается она и соседние, цель погасить всё. Математики её давно разобрали, у Wolfram MathWorld есть подробный разбор: считаешь методом Гаусса, сколько раз нажать на каждую клетку, порядок нажатий не важен.

В Готике почти то же самое, только ход двигает пластину и всех, кто к ней привязан.

Я программист, так что сел кодить именно это: систему уравнений, которая выдаёт «первую двинуть на минус два, третью на плюс пять». Ответ получался математически верный и практически бесполезный.

В Lights Out нет краёв, а здесь есть - и потому порядок ходов важен. Как с мебелью в узком коридоре: куда в итоге - понятно, но если тащить в неправильной последовательности, застрянешь на полпути. Выполняешь правильный план не в той последовательности - и где-нибудь на третьем шаге штифт выезжает за границу. Итог был бы верным, но отмычка до него не доживает. Нужен не ответ «сколько», а маршрут, безопасный на каждом промежуточном шаге.

Была дверь, на которую ушло два часа, куча отмычек и 19 откатанных сейвов - после неё я перестал верить в листочек.

Тогда я представил замок как граф. Вершина - расстановка всех штифтов, ребро - один ход. Ходы, после которых хоть один штифт выходит за границы, в граф просто не добавляются: для алгоритма их не существует, поэтому он не может предложить ничего опасного в принципе.

По такому графу ищет путь BFS, поиск в ширину. Алгоритм из учебника, ему лет семьдесят. Идёт волнами: сначала все состояния в одном ходе от стартового, потом в двух, и так до цели. Первое найденное решение автоматически кратчайшее. Тем же способом решают пятнашки, а навигатор по родственному принципу ищет маршрут.

Вся логика - три маленькие функции. Первая делает один ход: двигает пластину, тащит за ней связанные и проверяет границы. Если хоть один штифт вылез, функция возвращает null - и такого хода для алгоритма просто нет.

Вторая упаковывает расстановку штифтов в одно число. Позиций семь, так что конфигурация - это буквально число в семеричной системе.

Это главный трюк. Для восьми пластин всех расстановок 7^8, около 5,7 миллиона, и благодаря числовой кодировке вместо словарей и строк хватает одного Uint8Array на 5,7 МБ: по индексу-числу лежит «были мы тут или нет». Очередь BFS - такой же плоский массив. Третья часть - сам поиск.

Когда волна докатывается до цели, массив parent раскручивается назад до старта - и получается пошаговый план для игрока. На моём ноутбуке худший случай считается за секунды, обычный замок за миллисекунды. Всё в браузере, серверов нет.

Полный код с комментариями лежит в репозитории, он не минифицирован.

Поверх поиска я добавил симулятор, который прогоняет каждый найденный маршрут и проверяет: штифты в центре, границы не нарушены ни на одном шаге. Прогнал несколько тысяч случайных конфигураций. И сверился с реальными: дверь башни в Старом Лагере вскрывается ровно за 45 ходов - короче безопасного пути там нет.

Работает на любой конфигурации до восьми пластин - больше в игре и не встречается, а браузеру и так приходится переваривать миллионы состояний.

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

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

UPD: В комментариях предложили идею с анализом фотографии, я постараюсь придумать как это можно реализовать.

Ну и еще разок: unlockmyloot.com

PS: Это лучшая мини игра по вскрытию замков, которую когда либо придумывали. Самая интересная, сложная и правильная, на мой взгляд.