Решаем мини-игру про взлом протокола в Cyberpunk 2077 за 50 строк на Python

Решаем мини-игру про взлом протокола в Cyberpunk 2077 за 50 строк на Python
Решаем мини-игру про взлом протокола в Cyberpunk 2077 за 50 строк на Python

Если вы хотя бы отдалённо интересуетесь играми и не прожили последнюю пару лет в тайге, то, вероятно, слышали что-нибудь о Cyberpunk 2077. После долгого ожидания она наконец вышла! И в ней есть мини-игра про взлом! И чем больше получишь в ней очков, тем ценнее приз! Может ли магия Python дать нам преимущество в этом жестоком Нете? Разумеется.

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

Учитываются все допустимые пути, а окончательное количество очков каждого пути вычисляется в зависимости от того, сколько последовательностей было завершено при его прохождении. Путь с наибольшим количеством очков затем выводится на экран. К сожалению, мой алгоритм не особо интересен и эффективен. Однако он должен быть достаточно быстр, чтобы решить любую из мини-игр Cyberpunk за несколько секунд, и этого вполне хватает! Уверен, что есть какие-то простые способы ускорения выполнения скрипта, но я решил поделиться уже имеющимися результатами, и обновлять пост по мере поступления новых идей и предложений.

Начнём с компонентов игры:

  • Матрица кода: многомерный массив, содержащий шестнадцатеричные значения (узлы) — «игровое поле»
  • Буфер: число, обозначающее максимальное количество выбираемых координат
  • Координата: точка в матрице кода
  • Путь: упорядоченный набор уникальных координат, по которым проходил пользователь
  • Последовательность: пути, дающие при завершении награды различного качества
  • Очки: вычисления, которые можно настраивать, чтобы отдавать приоритет разным наградам

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

Давайте запустим код и убедимся, что всё работает правильно. Хотя большинство мини-игр со взломом протокола имеют рандомизированные значения, в квесте «Spellbound» используется фиксированное состояние, и наилучшее решение уже известно. Оно создано GamerJournalist:

Решаем мини-игру про взлом протокола в Cyberpunk 2077 за 50 строк на Python

Успех! Из любопытства я решил увеличивать размер буфера, пока не смогу найти путь, выполняющий все последовательности. Учтите, что для вычисления результата может понадобиться какое-то время, поскольку алгоритм проходит по всем возможным путям длиной 11.

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

Давайте попробуем получить исходный результат заново с буфером длиной 7:

Сработало! Новое решение заметно быстрее, но буфер длиной 7 уже и так вычислен довольно быстро, поэтому трудно ощутить ускорение. Посмотрим, как проявляет себя оптимизация при вычислении пути с наибольшей наградой.

Ускорение почти в три раза благодаря добавлению двух строк кода. Совсем неплохо. Вероятно, существуют и другие простые возможности оптимизации, поэтому я, может быть, через неделю дополню пост. Ну а на этом всё. Присылайте свои предложения по улучшению качества/производительности кода!

источник