Поиск пути, или как враги в играх находят дорогу

Зачем нужен pathfinder и как его внедрить в игру так, чтобы игроки не считали врагов идиотами?

Поиск пути, или как враги в играх находят дорогу

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

Почему возникает проблема поиска пути?

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

Есть такой вид игр-головоломок — лабиринт Минотавра. Игрока помещают на сетчатое поле со стенками. Одна из клеток поля является выходом, а на другой стоит монстр. Задача игрока — добраться до выхода раньше, чем монстр доберётся до него. Игрок и монстр ходят по очереди на сколько-то клеток, но монстр всегда перемещается быстрее игрока.

Пример игры вида «лабиринт Минотавра»
Пример игры вида «лабиринт Минотавра»

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

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

Как найти путь?

Задача поиска пути состоит из двух этапов: адаптирование игрового мира в математическую модель и поиск в этой модели пути между двумя точками.

Адаптирование игрового мира

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

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

Пример построения графа (игра «Депония»)
Пример построения графа (игра «Депония»)

Одна из простых вариаций графа — игровая сетка, где кружочками являются клетки, а рёбра проводятся между любыми соседними клетками, свободными от препятствий. Проще всего разобраться в этом на примере пошаговых игр, у которых сетку видно невооружённым глазом, вроде Sneaky-Sneaky или Return of the Necrodancer.

Примерная сетка в игре Sneaky-Sneaky
Примерная сетка в игре Sneaky-Sneaky

Клетки, на которых стоят непреодолимые препятствия, обозначаются крестиком, а проходимые места — пустотой. Или, если говорить на языке программирования, клетки обозначаются 0 или 1, где 0 означает, что пройти нельзя, а 1 — что пройти можно. Более сложные игры вроде Heroes of Might and Magic III отличаются только тем, что их сетка рисуется более произвольно, а клетки, которые расположены на разных типах земли, отнимают разное количество шагов.

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

В Death Stranding упрощённую карту для поиска пути можно увидеть при сканировании местности. Крестиками показываются непроходимые места, жёлтым — проходимые с трудом, голубым — легко проходимые.

Поиск пути, или как враги в играх находят дорогу

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

Алгоритмы поиска пути

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

Поиск в ширину

Визуализация поиска в ширину

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

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

Если же описывать работу в виде алгоритма, то получатся такие шаги:

  1. Помещаем стартовую точку в список «на проверку».

  2. Все точки из списка «на проверку» добавляем в список «исследованное».
  3. Для всех точек из списка «на проверку» находим все соседние точки, на которые можно перейти (для обычной сетки это будут все соседние клетки без препятствий). Помещаем их в список «текущие».

  4. Выкидываем из списка «текущие» те точки, которые уже были исследованы и хранятся в списке «исследованное».

  5. Список «на проверку» очищаем и помещаем туда все точки из списка «текущее». Текущий список тоже очищаем.

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

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

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

Алгоритм Дейкстры

Алгоритм Дейкстры работает с моделями, в которых расстояния между точками могут быть разными. Например, в Heroes of Might and Magic III проход по снегу тратит на 50% больше очков перемещения, так что условно можно посчитать, что проход по снегу занимает 1.5 шага вместо 1 по обычной земле. В этом случае обход снега может быть быстрее, чем проход напрямую по нему, хоть визуально и будет пройдено большее расстояние.

По этой причине прокладчик пути в игре выбирает сначала путь по тропинке, и только в конце сворачивает в снег.
По этой причине прокладчик пути в игре выбирает сначала путь по тропинке, и только в конце сворачивает в снег.

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

Алгоритм:

  1. Помещаем стартовую точку и расстояние до неё в виде «0» в список «на проверку» и в список «исследованное».

  2. Выбираем из списка «на проверку» точку с самым маленьким расстоянием до неё, удаляем её из списка.

  3. Находим все соседние доступные точки и суммируем расстояние от выбранной точки до них с расстоянием до выбранной точки. Добавляем эту информацию в список «текущий».

  4. Выкидываем из списка «текущие» точки из списка «исследованное», расстояние до которых больше, чем значение расстояния в списке «исследованное».

  5. Список «на проверку» очищаем и помещаем туда все точки из списка «текущее». Эти же точки помещаем в список «исследованное». Текущий список тоже очищаем.

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

Эвристический алгоритм

Работа эвристического поиска по сравнению с поиском в ширину

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

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

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

Алгоритм A*

Визуализация алгоритма A* в игре Factorio

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

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

Несколько интересных примеров можно прочитать в статьях про новый алгоритм поиска пути в Factorio и про устройство поведения полчищ крыс в A Plague Tale: Innocence.

Дополнительные материалы

Бонус: на этом сайте можно наглядно визуализировать работу разных алгоритмов, самостоятельно выстроив для них преграды.

Текст написала Алёна Киселёва, автор в Smirnov School. Мы готовим концепт-художников, левел-артистов и 3D-моделеров для игр и анимации. Если придёте к нам на курс, не забудьте спросить о скидке для читателей с DTF.

116116
19 комментариев

Эта гифка ждала нужного момента

10
Ответить

Делал A* для оценки эффективности пути игрока в обучающей игре... было весело.

4
Ответить

Изучал давно вопрос поиска путей, и как я понял  А* самый адекватный (из универсальных).

2
Ответить

Комментарий недоступен

2
Ответить

Тут надо обратиться  к специалистам из CDPR, они лучшие в этом деле

3
Ответить

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

Ответить

Сразу вспоминаю особенности поиска пути в Baldur's Gate

3
Ответить