Что это


CastlevaniaBot — это плагин для эмулятора NES Nintaco, который играет в Castlevania. Если запустить его на экране заставки, то плагин пройдёт всю игру от начала до конца. Или же можно запустить его в любом месте игры, чтобы он прошёл её часть.


В этой статье я расскажу, как создал бота, способного пройти Castlevania, и как вы можете создать нечто подобное для любой игры на NES.



Структура на основе знания


В этом проекте не использовалось машинное обучение. Скорее, разработку можно назвать «научением машины». Я знаю, как проходить Castlevania. Сложность заключалась в том, чтобы записать моё знание в компьютерную программу. Результатом стала система, симулирующая тот же процесс принятия решений, который выполняю я с контроллером в руках. Для её создания необходимо было чётко изложить подробные детали физики, управляющей битовым миром Саймона Бельмонта, и всех тактик, необходимых опытному охотнику на вампиров.

У CastlevaniaBot есть доступ к набору стратегий, позволяющих справляться с широким диапазоном ситуаций. Большинство из них предназначено для работы с конкретным типом игровых объектов. Например, существует стратегия борьбы со скелетами, ещё одна для людей-рыб, для разбивания свечей, для собирания сердец, и так далее.

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

Перед принятием решения о переключении CastlevaniaBot рассматривает текущую цель и стратегию. Если ему это не удастся, он может застрять в бесконечном цикле, переключаясь туда и обратно между двумя целями с равным или почти равным приоритетом. Чтобы избежать этого, при появлении новой основной цели, которая только слегка выше по приоритету текущей цели, CastlevaniaBot может решить продолжить текущую стратегию.

Некоторые стратегии автоматически запускаются при попадании в определённую область. Обычно они предназначены для одновременной обработки нескольких игровых объектов. Например, в коридоре с кучей летающих голов медуз лучше всего просто идти вперёд, а не целиться в каждую голову по отдельности.

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



Составление плана 8-битного мира


При работе над подобными проектами я в первую очередь стремлюсь упростить задачу. Я представил, на что была бы похожа Castlevania, если бы на уровнях не было врагов, свечей и собираемых предметов. Всё, что в таком случае было бы нужно — просто дойти от начала до конца уровня. Я задался вопросом — если мне удастся научить бота это делать, то насколько сложно будет уничтожить по пути несколько врагов?

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


Каждый уровень разделён на 3 или 4 этапа. Этапы обычно разделены деревянными дверями, которые со скрипом открываются и захлопываются за спиной игрока.


Двери являются контрольными точками (чекпоинтами). Если игрока убивают, то он возвращается к началу этапа, но только если у него не кончились жизни. Если продолжить игру после Game Over, то игрока отправляют в самое начало уровня.

Номер этапа обозначает общее количество чекпоинтов, пройденных с начала игры. Последний этап имеет номер 18. Но если убить Дракулу, то игра начинается с самого начала в сложном режиме (Difficult Mode), а номера этапов продолжают увеличиваться до 19 и дальше. Если пройти Difficult Mode, то третий цикл игры не становится сложнее, но номера этапов по-прежнему продолжают увеличиваться.


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


Для отслеживания номера игрового цикла, номера этапа и номера подэтапа игра использует 3 байта. Игровой цикл в обычном режиме (Normal Mode) имеет значение 0; значения 1 и выше обозначают Difficult Mode. Вне зависимости от игрового цикла этапы всегда имеют нумерацию от 0 до 18. А подэтапы всегда имеют значение 0 или 1, потому что этапы никогда не содержат больше, чем 2 горизонтальных полосы. CastlevaniaBot отслеживает эти байты, чтобы знать, где он находится.

Для своего удобства я записал полосу фона каждого подэтапа в отдельный графический файл. Если мне необходимо было узнать точные координаты какого-то объекта, то я мог быстро их выяснить с помощью графического редактора. Файлы я записал с помощью встроенного в Nintaco инструмента Map Maker. Я включил его, а затем прошёл всю игру. Некоторые из получившихся изображений содержали соединённые вместе несколько подэтапов, которые было легко разбить на части.

Nintaco's Map Maker

Изучив изображения фонов, я понял, что единственными важными тайлами являются платформы и лестницы. Всё остальное можно считать пустым пространством. Лестницы бывают двух типов: ведущие вперёд или назад (их можно представить как левое и правое ребро равнобедренного треугольника). Иногда лестницы заканчиваются платформой, по которой может ходить игрок.


Существует всего 5 важных типов тайлов, и на каждом уровне они имеют разный внешний вид. Я скопировал и вставил их в отдельные графические файлы размером 16?16. Затем я написал программу, сравнивающую каждый тайл в каждом подэтапе с соответствующим набором изображений. Так я получил матрицы типов тайлов для всех подэтапов.

Матрицы можно было бы извлечь непосредственно из ROM, но я не смог найти документацию о том, как и где хранятся данные. Так как пространство ROM ограничено, данные уровней обычно представлены в сжатом виде, напоминающем формат векторной графики. В каждой игре используется собственный формат, поэтому я не посчитал необходимым проводить исследования, ведь у меня был Map Maker. Кроме того, мне всё равно были нужны графические изображения подэтапов. Если бы я не выполнил захват полос фонов, то мне бы пришлось писать программу, генерирующую изображения из матриц.



Поиск путей


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

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


Аналогично, если Саймон находится на лестнице, то он может перемещаться на один тайл в одном из двух возможных направлений.


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

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


Добавив операцию «ничего не делать», я получил 15 операций. Все они достаточно просты для того, чтобы бот мог легко определить последовательность нажатия кнопок, необходимое для их выполнения во время выполнения игры.

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

Для создания этой симуляции потребовалось тщательное изучение Саймона Бельмонта. В отличие от других классических платформеров, где игрок может ускоряться от ходьбы к бегу, Саймон при движении по горизонтали всегда перемещается ровно на 1 пиксель за кадр. Это справедливо для ходьбы, прыжков, взбирания по лестницам и даже при отбрасывании назад при атаках врагов.

Ограничение горизонтальной скорости очень упрощает распознавание барьеров. Игра проверяет, есть ли стена в одном пикселе перед персонажем, и при необходимости останавливает движение. Проверка выполняется ниже уровня головы, что позволяет голове проходить под низкими потолками без помех горизонтальному движению.

С вертикальным движением всё немного сложнее. Если Саймон сходит с края платформы, он вместо постепенного ускорения мгновенно падает вниз со скоростью 8 пикселей на кадр. Так как каждый тайл имеет высоту 16 пикселей (что кратно 8), распознавание земли упрощается. Одновременно игрок сохраняет горизонтальную скорость в 1 пиксель на кадр в направлении, полученном непосредственно перед падением.

Ширина спрайта Саймона — 16 пикселей, и тем не менее, он может нависать над блоком максимум на ±4 пикселя от его средней точки. Если сдвинуться чуть больше, то он упадёт ниже.


Интересно, что если он сойдёт с платформы и упадёт ровно на 1 тайл со скоростью 1 горизонтальный и 8 вертикальных пикселей на кадр, то при приземлении не будет точно стоять на блоке. Одна из его ног будет оставаться внутри стены на глубину 2 пикселя.


После этого он сможет выйти из стены, но не зайти в неё.

Во время прыжка Саймон не может менять его направление. После нажатия на кнопку A он совершает фиксированный путь по параболе.


В верхней точке Саймон поднимается на 36 пикселей, что позволяет ему запрыгивать на платформы высотой 2 тайла. А вершина «параболы» на удивление плоская. Похоже, что он зависает в пространстве на 9 полных кадров, возможно для того, чтобы упростить удары хлыстом в воздухе. Если Саймону не на что приземлиться, то движение по параболе продолжается, пока он не вернётся на исходную высоту. После этого он начинает падать со скоростью 8 пикселей в кадр, то есть с той же постоянной скоростью падения с платформы.

Когда прямо над головой персонажа есть платформа, прыжки не допускаются.


В противном случае он частично «впрыгивает» в тайлы платформ.


Как говорилось раньше, если Саймон касается больше, чем верхушкой головы, он перестаёт двигаться по горизонтали. Это довольно раздражает в конце первого этапа уровня 4, когда игрок пытается выбраться из пещеры.


Лестницы позволяют свободно перемещаться по вертикали между платформами.


В одном из случаев Саймон поднимается по лестнице, проходя насквозь тайл платформы. Находясь на лестнице, он свободно может проходить через стену.


На подвижных платформах уровня 4 игрок обычно пригибается под низко висящими сталактитами. Однако можно подняться и упереться в них. В такой ситуации игра ограничивает горизонтальное движение, быстро утягивая Саймона в водную ловушку.


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

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

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


Внутри некоторых разрушаемых блоков содержатся скрытые предметы. И уничтожение блоков изменяет этот граф. Чтобы обойти эту проблему, к подэтапам был применён алгоритм поиска путей с разбиваемыми блоками и без них. Во время выполнения CastlevaniaBot наблюдает за состояниями разбиваемых блоков и использует соответствующую таблицу поиска.




Состояние игры


CastlevaniaBot интегрируется в Nintaco через его API. Он регистрирует реализацию FrameListener, чтобы получать в каждом кадре возврат. Так как эмулятор выполняется с частотой примерно 60 кадров в секунду, этот listener необходимо возвращать вовремя; длительные вычисления или простои замедлят или блокируют эмулятор. За короткий промежуток времени CastlevaniaBot считывает состояние игры, определяет свою основную цель, переключает стратегии, если цель изменилась и выполняет текущую стратегию.

CastlevaniaBot считывает текущее состояние Саймона Бельмонта непосредственно из ОЗУ процессора. Но я не могу определить, как представлены в памяти другие игровые объекты. Поэтому CastlevaniaBot выполняет считывание непосредственно из памяти атрибутов объектов (Object Attribute Memory, OAM) — области, хранящей список отображаемых спрайтов.


Эта техника работает и в общем случае применима к другим играм, но имеет множество недостатков. Порядок спрайтов в OAM постоянно меняется. Если на экране одновременно есть несколько экземпляров одного типа врага, то единственный способ отслеживать их — определение их близости, сопоставление последних координат спрайта с координатами из предыдущего кадра.


Некоторые игровые объекты состоят из повторяющихся спрайтов, например, костяные башни.


Подвижные платформы состоят из одного спрайта, повторяющегося 4 раза.


Для сортировки обоих этих случаев требуется дополнительная логика, которую реализовать совсем несложно. Апгрейды вторичного оружия и некоторые виды самого вторичного оружия используют одни и те же спрайты. Хуже того — на уровне 5 рыцари заимствуют спрайты вторичного оружия Саймона.


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


Некоторые игровые объекты при создании мигают, например хрустальные шары в конце боёв с боссами, косы Смерти и тело Дракулы. Мигающие спрайты появляются и исчезают из OAM, поэтому для отслеживания этих объектов требуется дополнительная логика.


Также стоит заметить, что из-за аппаратных ограничений NES может отображать только 8 спрайтов на растровую строку. Так как приоритет спрайтов частично зависит от их индексов в OAM, порядок в каждом кадре произвольно перемешивается, чтобы избежать сдвига, делающего один спрайт невидимым постоянно. Несколько спрайтов мигает по очереди, постепенно изменяя свой приоритет. Это мигание не влияет на считывание спрайтов из OAM. Данные всё равно остаются там, но эмулируемое железо их не отображает. Это отличается от описанной выше ситуации с мигающими при создании спрайтами. Кроме того, в Nintaco есть опция, значительно снижающая аппаратное мигание.


И наконец, небольшая часть состояния игры считывается из таблиц имён PPU — области памяти, содержащей все данные фонов. К нему относится проверка разрушаемых блоков и слежение за позициями «давилок» на уровне 2.




Эвристические машины состояний


Стратегии — это машины состояний. CastlevaniaBot задаёт их как абстрактный класс с методами init и step. Метод init вызывается, когда CastlevaniaBot переключается на соответствующую стратегию, позволяя машине состояний выполнить сброс в исходное состояние. А метод step выполняет стратегию. Например метод step стратегии для людей-рыб проверяет, находится ли человек-рыба в пределах удара хлыстом, и если да, то бот ударяет хлыстом. В противном случае он проверяет, можно ли прыжком достичь расстояния удара, и если это так, то бот прыгает. И наконец, если бот стоит слишком близко к противнику, то отходит от него. Благодаря этим простым правилам CastlevaniaBot побеждает людей-рыб.

Чтобы максимально упростить написание стратегий, я создал библиотеку возможных выполняемых действий. Например вместо нажатия и отпускания кнопки A для прыжка бот просто вызывает из библиотеки метод прыжка. А перед этим он запрашивает библиотеку, находится ли Саймон на платформе и может ли прыгать.

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

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



Прохождение


В этом разделе я подробно опишу используемые CastlevaniaBot стратегии, прокомментировав всё прохождение.

Игра начинается во дворе перед замком. Объекты в кадре проранжированы для выбора основной цели, которой в данном случае является колонна с пламенем. Стратегия работы с колоннами приказывает боту приблизиться к колонне и использовать хлыст, когда он будет в пределах досягаемости.


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

При ранжировании объектов CastlevaniaBot всегда учитывает долговременную цель — прохождение уровня до того, пока кончится время. При создании списка потенциальных целей в него всегда добавляется дверь на следующий уровень. Двери назначается низкий приоритет, но после уничтожения всех колонн и сбора всех предметов она становится приоритетной. Только за одним исключением: CastlevaniaBot знает, как раскрывать все скрытые сокровища, и перепрыгивает через вход в замок, чтобы создать мигающий мешок с деньгами.


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


Часто кажется, что хлыст уничтожает врагов, не касаясь их. Я нашёл в ROM игры таблицу прямоугольников коллизий, поэтому CastlevaniaBot точно знает, когда что-то находится в пределах действия хлыста. А поскольку прямоугольники коллизий часто слегка выдаются за границы спрайтов, хлыст может ударять «невидимой частью».

В большинстве случаев при уничтожении свечей CastlevaniaBot прыгает вертикально, а не вперёд. Это тактика избегания риска. Так как находясь в воздухе, изменить направление движения невозможно, толпа приближающихся врагов может усложнить безопасное приземление или сделать его невозможным. Кроме того, при вертикальном прыжке CastlevaniaBot остаётся на том же блоке; ему не нужно проверять, приведёт ли прыжок к падению на нижнюю платформу или дно ямы.

Когда не остаётся ни уничтожаемых свечей, ни собираемых предметов, CastlevaniaBot начинает преследовать призраков. Но «стратегия пантеры» приказывает ему стоять на месте, ожидая пока враг не попадёт в пределы удара хлыста.


Кроме того, что свечи служат источниками сердец и других предметов, они направляют игрока по пути через этап. Например на показанным ниже изображении свечи в верхнем правом углу «приглашают» игрока подняться по лестнице. Однако чтобы подняться вверх по ступеням, игроку изначально нужно пройти влево, из-за чего свечи пропадают с экрана. Так как решения CastlevaniaBot основаны на расстановке приоритетов видимых на экране предметов, эта ситуация может привести к бесконечному циклу, где бот попеременно выбирает кратчайший путь к свечам (влево) или кратчайший путь к двери выхода (вправо).


Подобные проблемы можно решить несколькими способами. Например, CastlevaniaBot можно оснастить запоминанием объектов, пониманием того, что объекты продолжают существовать, даже если их не видно. Но для этого всё равно изначально их нужно увидеть. Если бы свечи были ещё правее, то после их обнаружения нужно было бы возвращаться назад ещё дальше.

С учётом этого я добавил стимулы, подталкивающие CastlevaniaBot к исследованию областей этапа, которые он обычно бы игнорировал. Эти стимулы работают аналогично выходным дверям, привлекая CastlevaniaBot туда, куда ему нужно идти. Кроме того, я добавил правила, заставляющие его игнорировать свечи и предметы, находящиеся слишком далеко (по проходимому расстоянию, а не по прямой линии).

После поднятия по лестнице и уничтожения свечей создаётся святая вода — самое ценное из всего вторичного оружия. CastlevaniaBot выбирает его, обменивая на него кинжал.


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


При дальнейшем движении CastlevaniaBot вы заметите, что он начинает использовать для уничтожения призраков и свечей святую воду. Это может показаться излишним, но служит важной цели. Castlevania вознаграждает игроков за использование вторичного оружия с двойным и тройным воздействием. Другими словами, CastlevaniaBot гриндит апгрейды вторичного оружия.


После нажатия кнопки B существует задержка в 16 кадров до удара хлыста. Хлыст остаётся длинным в течение дополнительных 10 кадров, но действует только в первом из этих десяти. CastlevaniaBot использует этот факт для улучшения прицеливания. В частности, он отслеживает скорости всех объектов в кадре, предполагая, что основная цель будет продолжать двигаться по линейной траектории. Затем он нажимает кнопку B за 16 кадров до того, как цель должна встретиться с ударом хлыста. Враг всегда может изменить направление в течение этих 16 кадров, но обычно эта простая эвристика работает.

Однако после прохождения через дверь CastlevaniaBot встречает красных летучих мышей. Как и головы медуз, красные летучие мыши летают по экрану, пролетая по синусоиде сквозь платформы и лестницы. Чтобы предсказать, где будет красная летучая мышь спустя 16 кадров, я записал движение одной из них в таблицу. Во время выполнения игры CastlevaniaBot отслеживает летучих мышей и ждёт пиков или минимумов траектории, где вертикальная скорость меняет свой знак. Тогда он способен сопоставить координаты со значениями в заранее созданной таблице. Это позволяет соответствующей стратегии ударить красную летучую мышь хлыстом, наклониться или подпрыгнуть над ней.

При скоростном прохождении (спидранах) Castlevania игроки выполняют маневры, делающие игру как можно более детерминированной. Например, они обнаружили, что если в конце уровня 1 разрушить блок и подобрать апгрейд оружия в определённой временной последовательности, то босс будет вести себя в соответствии с желательным паттерном, позволяющим быстро его победить.

Какими бы опытными ни были люди, они не могут полностью приручить генератор случайных чисел. Тем не менее, поскольку CastlevaniaBot может контролировать нажатия кнопок с покадровой точностью, он может довести концепцию скоростного прохождения до её предела, каждый раз проходя игру абсолютно идентичным образом. Если бы он так делал, это бы ничуть не лучше прохождения TAS. Поэтому CastlevaniaBot произвольно добавляет с помощью внешнего генератора случайных чисел в свои действия ошибки и задержки, чтобы избежать детерминированного геймплея. Например, когда он ударяет хлыстом находящуюся высоко свечу, то намеренно добавляет в прыжок и удар задержку на случайное количество кадров. Подобные крошечные изменения значительно влияют на прохождение игры.

Хотя CastlevaniaBot и стремится избежать детерминированности, он всё же позаимствовал у спидраннинга одну концепцию: damage boosts. В 50% случаев CastlevaniaBot полностью избегает прохождение подземелья людей-рыб, прыгая назад на красную летучую мышь, которая отбрасывает его на недостижимую иным способом платформу.


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


Из-за непредсказуемости создания врагов и их огненных шаров большинство игроков обычно пробегает часть с людьми-рыбами. Но CastlevaniaBot тратит на них время, собирает все сердца и даже скрытое сокровище в самом правом краю. Бот точно знает, какие предметы содержатся в каждой свече, и поскольку он предпочитает пользоваться святой водой, то пропускает свечи, в которых скрыты хронометры. Однако если остаться в этой части и сражаться с людьми-рыбами, то иногда можно неизбежно подобрать хронометр.

Этапы часто завершаются крестами, уничтожающими всех врагов на экране. На случай, если вам любопытно, скажу — кресты не могут убивать боссов в конце уровня. На самом деле кресты иногда создаются даже во время боёв с боссами. Например, в битве с Медузой при уничтожении змей иногда появляются кресты. Но эти кресты могут убивать только других змей.


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


Это правило «проверяй наличие врагов перед прыжком» иллюстрирует один из принципов структуры CastlevaniaBot: он должен управляться простыми, как можно более обобщёнными правилами. В некоторых частях игры необходимо использовать одноразовые стратегии, решающие очень конкретные задачи. Но в бОльшей части игры действия бота управляются многоразовыми эвристиками. Я не писал команду, заставляющую его остановиться в этой конкретной точке и ждать, пока призраки уйдут с пути. Это поведение возникло как результат эвристик.

CastlevaniaBot завершает уровень, убив Phantom Bat тройной святой водой. Но его стратегия атаки определяется его вторичным оружием. На самом деле, если бы у него не было вторичного оружия, он был готов к убийству босса с помощью одного кнута. Особо интересным случаем является убийство Phantom Bat с помощью топора. Аналогично случаю с красной летучей мышью, я записал в таблицу движение топора по параболе. Во время выполнения игры CastlevaniaBot выполняет смещение таблицы, сопоставляя её с каждым из тайлов пола. Это позволяет вычислить оптимальную точку для убийства босса топором.


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


В начале уровне 2 CastlevaniaBot избегает первых свечей, в которых спрятан бумеранг. Стратегия работы с рыцарем-копейщиком похода на стратегии призраков или людей-рыб, однако это первый враг, для убийства которого нужны два удара. Чёрная летучая мышь дремлет, пока к ней не приблизишься, после чего она взлетает и движется достаточно линейно, чтобы её можно было убить хлыстом с помощью упомянутой выше простой эвристики.


Разрушив кирпичи стены, в 50% случаев CastlevaniaBot, похоже, уходит из комнаты, не подняв корону. Но так ли это? На самом деле в таких случаях он подбирает корону, воспользовавшись багом игры. Так как конец верхней лестницы совпадает по горизонтали с расположением короны, игрок при прохождении вверх и за экран на мгновение оказывается внизу. Если прислушаться к звуку или посмотреть на очки, то можно увидеть, что бот на самом деле берёт корону.


На уровне 2 враги не атакуют игрока, когда он находится на подвижной платформе. CastlevaniaBot просто должен подождать, пока платформа подъедет, зайти на платформу, дождаться, пока она доедет до другой стороны, а затем сойти с неё. Существует небольшая вариация для платформ, которые не касаются тайлов с другой стороны. В таких случаях CastlevaniaBot не сходит, а спрыгивает с платформы.


Дверь ведёт в коридор, заполненный летающими головами, и CastlevaniaBot реагирует на это, двигаясь вперёд. Как и в случае с подвижными платформами, CastlevaniaBot знает, что эту стратегию нужно применять на основе своего положения, а не расстановки приоритетов находящихся на экране игровых объектов. Однако как только все головы медуз пролетят, он снова переключается к этой технике, чтобы выбрать стратегию, которая будет использоваться дальше.


Ещё одна стратегия, зависящая от позиции, срабатывает после поднятия по следующей лестнице, ведущей в заполненную головами медуз область. В 50% случаев CastlevaniaBot намеренно прыгает на голову медузы, чтобы получить damage boost, подталкивающий его на верхнюю платформу рядом с дверью, ведущей к следующему этапу. Это единственные два damage boost, о которых знает CastlevaniaBot. В отличие от спидраннеров, он выполняет его не для экономии времени, это всего лишь ещё один вклад в недетерминированность прохождения.


Прохождение через «давилки» — это интересная стратегия на основе положения, повторяемая три раза. CastlevaniaBot ждёт, пока ближайшая «давилка» слева от него достигнет нужной позиции, после чего пробегает через неё. После её прохождения он останавливается, поворачивается, ударяет свечи хлыстом, подбирает созданный предмет и повторяет операцию с последующими «давилками». Одним из предметов потенциально может быть святая вода, поэтому он всегда уничтожает эти свечи.


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


Уровень 2 обычно заканчивается тем, что CastlevaniaBot мгновенно убивает Медузу бесконечным потоком святой воды. Однако он готов работать и с любым другим типом вторичного оружия.


На уровне 3 появляются прыгуны. CastlevaniaBot реагирует на них тем, что ждёт, пока они впрыгнут в пределы действия кнута. Если прыгуны перепрыгивают игрока, то CastlevaniaBot перемещается в противоположном направлении и ударяет их хлыстом прежде, чем они коснутся земли.


Дальше появляются белые скелеты. Они имеют очень случайный паттерн. Кроме того, они кидаются костями. На уровне 3 CastlevaniaBot пытается избежать их попадания. Но я обнаружил, что на последующих уровнях кости только отвлекают, и эффективнее будет просто их игнорировать. Стратегия CastlevaniaBot для белых скелетов — просто бить их.


CastlevaniaBot ждёт, пока подлетят вороны. Затем на основании высоты ворона относительно игрока он точно вычисляет, когда ударить хлыстом после прыжка.


После перехода на следующий этап CastlevaniaBot самостоятельно ударяет свечи, из которых появляется хронометр, а потом ждёт, пока он не исчезнет. Немного впереди и за экраном находится ворон. Бот уничтожает свечи перед схваткой с вороном, чтобы снизить риск случайного удара по ним и получения нежелательного вторичного оружия.


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


Далее CastlevaniaBot намеренно ударяет по свечам, из которых вываливается кинжал. Как и в случае с хронометром, он делает это, чтобы не подобрать его случайно во время последующих действий.


И наконец, мумии оказываются повержены дождём из святой воды.


Для борьбы со всеми боссами CastlevaniaBot готов использовать любое вторичное оружие. На самом деле, стратегии применения вторичного оружия совершенно меняются, если по какой-то причине оказывается разрушенным блок, содержащий кусок свинины. Без этого блока невозможно подняться на верхнюю платформу, из-за чего сражаться приходится на нижнем уровне.

На уровне 4 возвращаются подвижные платформы. И на этот раз есть вероятность, что на пути появятся красные летучие мыши. Чтобы снизить вероятность их нападения, он ждёт, чтобы прибытие платформы совпало по времени с уничтожением красной летучей мыши. Так как красные мыши появляются через фиксированные промежутки, это даёт CastlevaniaBot достаточно времени, чтобы пересечь водную яму без летучих мышей. Он готов иметь дело с летучими мышами и случайно появляющимися людьми-рыбами, пока находится на платформе, но это делает очень опасными прыжки на платформу и с неё. Применяемая CastlevaniaBot стратегия повышает вероятность его успеха.


Та же стратегия повторяется посередине этапа. На этот раз прыжок к подвижной платформе намного длиннее, поэтому критически важно перед прыжком уничтожить красную летучую мышь.


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

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

CastlevaniaBot обычно полностью избегает этих свечей, потому что он достаточно успешно сохраняет святую воду. Но если она ему понадобится, то он встаёт очень близко к этим свечам, чтобы гарантированно подобрать выпавшую из них святую воду.

Далее CastlevaniaBot встречается с кучей прыгунов. В этой области после убийства прыгунов часто появляются топоры. CastlevaniaBot избегает их, потому что особо полезной при борьбе с боссом оказывается святая вода.


При переходе к последнему этапу уровня CastlevaniaBot полностью игнорирует костяного дракона.


Но от следующих двух он избавляется быстрыми ударами хлыста.


Чудовище Франкенштейна и Игорь уничтожаются постоянным потоком ударов хлыстом и святой воды. Как и в случае с другими боссами, CastlevaniaBot может справляться и другим вторичным оружием, или вовсе без него. Однако шансы на выживание без святой воды уменьшаются.


На уровне 5 CastlevaniaBot снова имеет дело с белыми скелетами. Но на этот раз он использует вариации стратегий, редко встречаемые на уровне 3. В зависимости от того, где они появляются, CastlevaniaBot бросает святую воду, а затем отходит назад, чтобы привлечь скелетов в пламя. Рядом с лестницами он проходит под скелетами, чтобы направить их туда, где они должны быть.


На уровне 5 впервые появляются возрождающиеся красные скелеты. CastlevaniaBot отслеживает время последнего удара по ним, чтобы знать, когда можно безопасно пройти по красным костям.


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


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


Двигаясь по лестницам уровня 5, CastlevaniaBot часто должен ждать, пока красный скелет отойдёт или от верхней, или от нижней части лестницы. Ближе к концу уровня костяная башня делает эту задачу ещё сложнее. В зависимости от того, как решат перемещаться скелеты, CastlevaniaBot ходит вниз и вверх по лестнице, пока не сможет пройти.


Для обработки групп красных скелетов требуется дополнительная логика, чтобы бот не попал в бесконечный цикл. Если CastlevaniaBot будет бить их хлыстом по отдельности, с таким интервалом, чтобы первый ударенный успевал возродиться, то он попадёт в цикл, где будет продолжать уничтожать бесконечно возрождающихся скелетов. Чтобы избежать этого, CastlevaniaBot не будет ударять хлыстом красного скелета, стоящего рядом с грудой красных костей. Это правило позволяет красным костям возродиться рядом с ещё живым красным скелетом, давая возможность ударить их двоих одновременно. Без интервала между их разрушением цикл создаваться не будет.


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


Если святой воды нет, то прямо перед коридором CastlevaniaBot может взять бумеранг. При удачном стечении обстоятельств он использует его для уничтожения рыцарей, а также получения апгрейдов оружия.


CastlevaniaBot оглушает Смерть святой водой, прежде чем она начнёт бросать косы, быстро её убивая. Также он может победить Смерть тройным бумерангом, но для этого обычно требуется несколько попыток.


Принципиальная стратегия CastlevaniaBot прохождения моста в начале уровня 6 — продолжать двигаться. Он ударяет хлыстом огромных летучих мышей сверху, чтобы оглушить их, а затем подпрыгивает над огромными летучими мышами, появляющимися снизу. Кроме того, ему время от времени нужно уклоняться от кидаемых летучими мышами огненных шаров, или бить их хлыстом.


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

На следующем подэтапе CastlevaniaBot два или более раз использует полученный на мосту хронограф, чтобы пройти сквозь орлов и прыгунов. Без хронографа он пытается проделать путь с помощью хлыста.


Когда CastlevaniaBot добирается до башни Дракулы, он может подниматься и опустаться по лестнице несколько раз, чтобы снова создавать свечи, что позволяет собрать как минимум 20 сердец.


Самые правые свечи в покоях Дракулы дают святую воду, которая необходима для борьбы со второй формой Дракулы.

Для победы над первой формой Дракулы требуется 16 ударов по голове. CastlevaniaBot несколько раз подходит к Дракуле, ждёт, пока тот выстрелит огненными шарами, а затем перепрыгивает шары и ударяет по голове Дракулы хлыстом.


Вторую форму Дракулы, которую прозвали Cookie Monster, бот оглушает святой водой и несколько раз ударяет хлыстом по голове. Время от времени Cookie Monster прыгает к игроку, при этом CastlevaniaBot уворачивается. Также Cookie Monster бросает огненные шары, которые обычно можно уничтожить святой водой и хлыстом. Иногда при этом можно получить апгрейд оружия. А двойная святая вода ловит Cookie Monster в постоянный цикл оглушения, ведущий к быстрой победе.


CastlevaniaBot не умеет проходить Difficult Mode, который начинается после финальных титров. Однако после повторного начала игры во дворе замка он сбрасывает байт цикла игры на ноль, переключая её в Normal Mode. Это позволяет CastlevaniaBot играть бесконечно.




Файлы


CastlevaniaBot_2018-12-09.zip

В файле .zip содержатся:

  • src — дерево исходников.
  • CastlevaniaBot.jar — скомпилированный двоичный файл.
  • lgpl-2.1.txt — лицензия свободного программного обеспечения.



Запуск


Обязательные требования


  • Nintaco — эмулятор NES.
  • Castlevania (U) (PRG1) [!].nes — ROM игры.

Запуск плагина


  1. Запустите Nintaco и откройте Castlevania (U) (PRG1) [!].nes.
  2. Извлеките CastlevaniaBot.jar из скачанного .zip.
  3. Откройте окно Run Program, выбрав Tools | Run Program...
  4. Введите путь к файлу в поле JAR или выберите его, нажав на кнопку Find JAR....
  5. Нажмите Load JAR, чтобы загрузить его.
  6. Нажмите Run.

Copyright © 2018 meatfighter.com

Данный проект является свободным программным обеспечением. Вы можете распространять его и/или модифицировать его на условиях лицензии LGPLv2.1.

Комментарии (6)


  1. KongEnGe
    13.12.2018 13:59

    Молодость моя — Castlevania :)


  1. dekeyro
    13.12.2018 14:34

    Сколько заняла разработка этого бота по времени?


  1. Sirion
    13.12.2018 17:23
    +1

    Человек, который программирует лучше меня, пишет бота, который играет лучше меня. Двойное унижение)


  1. gorodnev
    13.12.2018 22:05
    +1

    На всякий случай поискал видео процесса прохождения игры ботом — это круто!


  1. Quickie
    14.12.2018 06:27

    В большинстве случаев при уничтожении свечей CastlevaniaBot прыгает вертикально, а не вперёд. Это тактика избегания риска.

    Пожалуй, это единственное, что сильно бросается в глаза при просмотре игры бота (да, я просмотрел все видео, причем с большим удовольствием).

    Уважения автор заслуживает огромного! ~25-27 лет назад мне удалось быть единственным в школе, кто проходил эту игру за полчаса руками (уроки были по 40 минут). Только называлась она Vampire Killer, емнип, и играли мы в нее на Yamaha MSX (на Z80) на монохромных дисплеях.

    Аутентичная музыка при просмотре ласкала слух, а остатки памяти в некоторых местах прохождения бота заставляли пальцы непроизвольно тянуться к клавиатуре.

    Работой восхищен! Спасибо большое за все.


    1. igenkin
      14.12.2018 08:31

      О да! Я помню как я в нее играл первый раз — MSX2 и цветной дисплей. Первое прохождение заняло почти весь день.

      А музыка из 13-го (или 5-го) этапа у меня до сих пор как рингтон.