Обобщённый поиск путей для ИИ в платформерах

Предисловие

Если вы создаёте игру-платформер в стиле «беги и прыгай», то, возможно, уже задумывались о добавлении в неё ИИ. Он может управлять противниками, объектами, которые игрок должен преследовать, и так далее… И слишком часто ради простоты программист реализации отказывается от умного ИИ, что в результате приводит к тому, что ИИ не может справиться с хитрыми прыжками, особо умным игроком или движущимися объектами уровня.

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

Мы рассмотрим основную идею и создадим полную реализацию. Более сложные случаи, в том числе подвижные платформы/разрушаемые стены, мы рассмотрим в другой статье.

Эта техника использована в игре Nomera, см. на www.dotstarmoney.com или в Twitter.

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

Подготовка

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

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

Основная идея

Говоря простым языком: вы, как разработчик, передвигаетесь по уровню и прыгаете по платформам, а движок записывает ввод пользователя, используемый в точке, в которой вы прыгаете/падаете с платформы до времени, пока вы не окажетесь в следующей. Эти данные считаются «ребром», в которое сохраняется записанный ввод игрока. Когда ИИ хочет создать путь через уровень, он обрабатывает серию платформ (с этого момента мы будем называть их узлами) как вершины, а записанные между ними рёбра — как граф. Затем ИИ проходит путь, двигаясь по разным узлам и используя записанный ввод в рёбрах, чтобы достичь конечной точки. Нам нужно рассмотреть ещё много важных подробностей, но для начала сосредоточимся на более общих концепциях.

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

1. Загружаем статичные данных коллизий уровня и вычисляем из них набор узлов.
2. Загружаем все записанные для уровня рёбра (пути) и добавляем их в соответствующие им начальные узлы.
3. С помощью модели коллизий и параметров движения врагов записываем пути между узлами и добавляем их к графу.
4. При выходе из уровня экспортируем записанные для уровня рёбра.

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

А теперь общий вид обхода графа пути:

1. Получаем конечную точку в виде конечного узла, и расстояние в направлении этого узла; вычисляем схожие параметры для исходного (начального) узла.
2. Вычисляем путь с помощью любого алгоритма обхода графа от исходной к конечной точке, где путём является набор узлов и рёбер.
3. Проводим ИИ через узел к ребру ходьбой (или бегом, т.е. любым движением, которое известно ИИ) для достижения нужной начальной скорости следующего ребра на пути.
4. Когда ИИ достигает начальной точки следующего узла на пути с определённым допуском положения и скорости, отключаем автоматическое управлении ИИ и выполняем управление через покадрово записанные введённые данные рёбер.
5. Когда записанные введённые данные заканчиваются, возвращаем управление автоматическому движению для того узла, в котором стоит ИИ.
6. Повторяем последние три этапа, пока не будет достигнута конечная точка.

Уже начинаете понимать? Давайте подробно разберём каждый этап.

Реализуем поиск путей шаг за шагом

Создание графа путей

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

Узел/платформа имеет следующие свойства:

• Это подмножество отрезков прямых, формирующих геометрию уровня.
• При обычной гравитации все отрезки узла ориентированы таким образом, что их первая вершина имеет строго меньшую координату x, чем вторая (при инвертированной гравитация ситуация будет обратной).
• Каждый последующий отрезок узла начинается там, где закончился последний отрезок.
• Каждый отрезок узла может быть пройденным ИИ, идущим по его поверхности.

Что же это нам даёт? Следующую важную идею: узел может быть полностью пройден ИИ, идущим по его поверхности без прыжков или падений, и ИИ может пройти в любую точку по узлу из любой другой точки.

Вот изображение геометрии коллизий уровня:

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

Примечание: на этом изображении есть небольшая ошибка: 26 и 1 являются разными узлами, но, как видите, они должны быть одним.

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

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

Получив узлы, вы закончите первый этап создания графа путей. Нам также нужно определиться с тем, как количественно выражать положение. Положение, которое мы используем при определении начальных и конечных точек при поиске путей — это узел (в нашем случае по числу) и горизонтальное смещение вдоль этого узла относительно самой левой его точки. Почему горизонтальное смещение вместо длины дуги вдоль узла? Допустим, коллайдер ИИ — это квадрат или круг, идущий вдоль плоской поверхности по направлению к поднимающемуся склону. Может ли его поверхность коснуться внутренней угловой точки склона? Нет, поэтому положение измеряется как горизонтальное смещение, чтобы мы могли рассматривать горизонтальное смещение как «изогнутую горизонтальную линию».

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

Ребро обладает следующими свойствами:

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

Здесь нужно заметить следующее: совершенно необходимо, чтобы сгенерированный набор записанного покадрово ввода имел ТЕ ЖЕ свойства коллизий и движения, что и ИИ, для которого создаётся путь. Большой вопрос здесь в том, откуда же берутся записываемые покадрово вводимые данные. Правильный ответ — от разработчика!

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

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

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

Второй этап в создании графа путей — загрузка всех ранее созданных рёбер, а третий — сам процесс записи. Способ записи полностью зависит от вас. Вот скриншот из Nomera с нарисованными на экране рёбрами. Линии соединяют только начальное и конечное положение, и не отслеживают путь, но чётко объясняют технику:

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

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

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

Обход графа путей

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

class Player{
public:
// ...
void setInputs(int left, int right, int jump);
// ...
private:
// ...
}

Где «left, right, jump» вводятся с клавиатуры. Во-первых, это будут значения, которые вы будете записывать во время записи рёбер. Во-вторых, поскольку ИИ тоже нужен интерфейс управления «setInputs», почему бы не написать НАСТОЯЩИЙ интерфейс? Тогда код становится более модульным:

enum PC_ControlMode{
MANUAL,
RECORDED
}
class PlatformController{
public:
// ...
void setManualInput(int left, int right, int jump);
void bindRecordedInput(RecordedFrames newRecord);
int getLeft();
int getRight();
int getJump();
void step(timestep as double);
// ...
protected:
PC_ControlMode controlMode;
RecordedFrames curRecord;
void setInputs(int left, int right, int jump);
// ...
}
class Player : public PlatformController{
// ...
}
class AI : public PlatformController{
// ...
}

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

Ну ладно, теперь в контроллере ИИ нам нужны методы в стиле «чёрного ящика»:

createPath(positionType destination);
step(double timestep);

Первая строка задаёт путь между текущим положением и конечным положением, а вторая строка передаёт вводимые данные в setInputs(), чтобы привести ИИ в конечное положение. В нашем поэтапном изложении алгоритма createPath выполняет первые два этапа, а step — последние три. Давайте рассмотрим создание пути.

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

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

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

edgeFrameLength = количество кадров в записи ребра
walkToEdgeDist = abs(edgeStartX - edgeStartNodeCurrentPositionX)
edgeWeight = edgeFrameLength * TIMESTEP + walkToEdgeDist / (HORIZONTAL_WALKING_SPEED)
if(edgeDestinationNode == destinationPositionNode){
edgeWeight += abs(edgeEndX - destinationPositionX) / (HORIZONTAL_WALKING_SPEED)
}

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

Если мы можем вычислить веса наших рёбер, то можем применить алгоритм Дейкстры! (Или любой другой алгоритм обхода графа, здесь хорошо подойдёт A*, если вы используете эвристику типа «эвклидово расстояние до конечного положения»).

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

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

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

Теперь мы готовы передать управление записи ребра.

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

Дополнения

Для настройки этой техники в игре можно внести в неё некоторые изменения.

Крайне рекомендуется добавить внутриигровой интерфейс записи и стирания путей, который поможет удобно создавать пути перемещения по уровню: в Nomera создание путей уровня занимает около 10 минут, и это довольно забавно.

Также удобно обеспечить автоматическое извлечение узлов. Хотя технически вы можете делать это самостоятельно, добавление автоматического извлечения делает рабочий процесс НАМНОГО проще.

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

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

Подводим итог

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

Но работает ли это? Ещё как работает? Вот gif:

Эти ребята находятся в «режиме обнимашек». Они пытаются сблизиться со мной, куда бы я не отправился.

Если у вас есть вопросы или предложения, пишите мне по адресу chris@dotstarmoney.com. Благодарю за чтение!

Автор: PatientZero

Источник