Традиционно считается, что достаточно реализовать алгоритм поиска пути и дальше всё будет работать само собой.
На практике же мы имеем совсем другую ситуацию.
Алгоритмы поиска пути разобраны досконально.
Нужен поиск пути с весами? A*. Нужен поиск для большого количества юнитов? Flow Field или кластеризация.
По большому счету по поиску пути не осталось не разобранных вопросов.
И вот, поиск пути реализован и довольный игродел запускает свою игру… И видит, что болванчики полностью оправдывают своё название. Они конечно находят путь и едут туда, куда им сказали. Но при этом спотыкаются о препятствия… Толкаются друг с другом или проезжают насквозь… Упираются друг в друга при встречном движении…
Эти проблемы и будем сегодня решать.
Данная статья не претендует на исчерпывающее решение обозначенной проблемы.
Я лишь рассказываю о том, как конкретно мне видится решение, над которым я работал. Это решение в оттюнингованном виде попало в один из зарелизенных в этом году РТС проектов, но осталось ли там на данный момент я не знаю. Комментарии и дополнения приветствуются.
Постановка задачи
Юниту приказано двигаться к следующему вейпоинту. На уровень выше вейпоинты задаются алгоритмом поиска пути, но юнит об этом ничего не знает. Он лишь знает следующую точку назначения.
Юнит должен корректно обрабатывать следующие ситуации.
Движение группой в одну точку: самая типичная ситуация, когда игрок выбирает несколько юнитов и отправляет их в одну точку. Юниты не должны въезжать друг в друга или застревать, ожидая когда соседний юнит проедет дальше.
Движение сквозь группу других юнитов, стоящих на месте или движущихся в другом направлении — также весьма популярная ситуация. Часть юнитов выставлена для обороны участка. Другая группа юнитов едет из тыла в атаку, проезжая через обороняющихся. Движущиеся юниты должны корректно объезжать стоящих.
Общее описание алгоритма
Если по направлению движения юнита есть препятствие — юнит должен принять решение с какой стороны его объехать. Маневрирование возможно только в ограниченном диапазоне. Ближайшая аналогия — объезд машин на шоссе: водитель не может развернуться, не может уехать на обочину или встречку, маневры возможны только в пределах полос попутного направления.
Ограничение на маневрирование связано с тем, что маневрирование выполняется локально. Юнит не знает о мире достаточно, чтобы, например, развернуться и объехать препятствие по другому пути. Решение об объезде может принять только алгоритм на уровень выше (поиск пути). Уровень маневрирования такие решения не принимает. Таким образом, алгоритм сводится к простой идее: смотрим вперед на небольшое расстояние и если впереди препятствие, то проверяем, что слева или справа есть возможность его объехать. Если возможности объехать нет, сообщаем, что препятствие маневрированием объехать нельзя. И тут у нас три варианта:
- Остановиться и ждать
- Остановиться и запросить новый маршрут
- Продолжить движение сквозь препятствие
Отступление
Третий вариант кажется неприемлемым. Ведь проезд сквозь другие юниты игроками однозначно воспринимается как баг!
«Но не всё так однозначно» (с)
Давайте рассмотрим ситуацию с точки зрения игрока, который играет в нашу игру.
Итак, игрок отдает приказ юниту двигаться в точку. Для игрока важно, чтобы юнит добрался до точки назначения и выполнил свою задачу.
В первом случае:
Юнит застрял в середине пути. Например, уперся в другой юнит, стоящий в обороне. Игрок рассчитывает на то, что юнит уже добрался до точки. Но его там нет. Он ищет его на карте и находит тупящим посередине маршрута. Задумка игрока провалена. Игрок матерится на тупоголового болванчика и разработчиков, не способных в нормальный ИИ.
Во втором случае:
Юнит застрял в середине пути. Например, подъехал к мосту, а на мосту пробка. Он запросил новый путь и новый путь отправил его на другой мост. Находящийся под контролем противника или просто очень далеко. Игрок рассчитывает на то, что юнит уже добрался до точки. Но его там нет. Он ищет его на карте и находит. Он как раз набрел на мост, захваченный противником и вот-вот будет уничтожен. Задумка игрока провалена. Игрок матерится на тупоголового болванчика и разработчиков, не способных в нормальный ИИ.
Стоит отметить, что так делают достаточно часто в РТС. Думаю многие олдфаги, читающие этот текст, помнят негодование от харвестора из C&C, решившего доехать до ресурсов через вражескую базу просто потому, что мост как раз в этот момент пересекал другой харвестер и заблокировал проезд.
Третий случай:
Юнит доехал до моста. На нём пробка. Юнит сделал запрос на новый маршрут. Но новый маршрут оказался значительно длиннее текущего, в итоге изменение маршрута было заблокировано. Юнит запустил таймер ожидания, в надежде что пробка рассосется. Пробка не рассосалась за отведенное время. Юнит начинает двигаться сквозь пробку, игнорируя препятствия, в нарушение законов логики и физики. С точки зрения критики игры это баг. С точки зрения игрового процесса — это условность. Но в итоге игрок получил то, что должен был получить — юнит на указанной позиции. Мы по максимуму стараемся сделать вид, что всё работает по законам физики. Но если уж не получилось — пусть лучше будут условности, нарушающие законы физики, чем тупость ИИ, нарушающая погружение в игру.
Детальное описание алгоритма объезда:
Нормальное физически честное зрение — очень дорогая штука. Это множество лучей, которые нужно рассчитать и обработать. В нашем же случае это не нужно. Мы представим всё что может видеть юнит в виде двумерной сетки. Каждая клетка содержит значение проходимости. Чем выше значение, тем нежелательнее туда ехать. Для реализации объезда было бы достаточно и простого бинарного значения 0 — препятствие, 1 — пусто. Но есть нюансы, для которых двух значений недостаточно, о них поговорим позже.
Каждый раз когда юнит хочет осмотреться — необходимо построить сетку. Делается это следующим образом.
Каждое динамическое препятствие (юнит) записывает в сетку в своём положении окружность с меняющимся значением от 1 до 0. Если в клетку сетки уже установлено значение, то выбирается большее из двух.
Каждое статичное препятствие записывает максимальное значение в сетку. Это означает, что проезд насквозь запрещен категорически. Нельзя-Нельзя.
То есть через юниты у нас проезд разрешен в крайнем случае. Через препятствия не разрешен никогда.
Зачем это нужно? Например, чтобы в случае пробки на мосту юнит ехал насквозь через пробку, а не насквозь через реку.
После того как все ближайшие динамические и статические препятствия оставили свой отпечаток на сетке — юнит делает запрос «что находится у меня на пути»? Запрос выполняется в виде построения линии (далее я буду называть это трейсом на вейпоинт) от позиции юнита в сторону вейпоинта.
Расстояние трейса на вейпоинт ограничено параметром «максимальная дальность видимости».
Если трейс на вейпоинт дошел до максимальной дальности видимости, значит путь свободен — просто едем к вейпоинту.
Если трейс на вейпоинт уперся в препятствие — запускается еще два трейса: налево и направо, перпендикулярно трейсу на вейпоинт. Задача этих трейсов — выбрать точку с минимальным значением.
Если оба трейса вернули точки с одинаковыми значениями, то выбирается значение ближе к центру.
После того как точка с минимальным значением получена, юнит принимает решение что делать дальше:
- значение меньше порогового — просто поворачиваемся и едем в направлении этой точки;
- значение больше порогового, но меньше максимального — сообщаем «наверх», что нужно принять решение как быть. Если принято решение двигаться напролом — продолжаем движение, как будто то значение меньше порогового. Тут как раз важно вспомнить о том, почему юниты создают вокруг себя поле градиентное, а не простое поле проходимости. Простое поле проходимости не дает информации о том, как через него ехать. А градиент даже при движении сквозь препятствия позволяют создать ощущение, что юнит проезжает не насквозь, а проталкивается между, пусть и с пересечением геометрии;
- значение больше максимума (статичное препятствие) — сообщаем наверх, что ехать никакой возможности нет и ждём новый путь.
Дополнительный алгоритм для отталкивания:
Алгоритм, описанный выше, позволяет юнитам достаточно уверенно объезжать препятствия. Но в ряде случаев этого бывает недостаточно и юниты все равно при движении геометрически пересекаются.
В голову приходит очевидный вариант — включить им физику на уровне движка и забыть про эту проблему. Ведь они будут физически отталкиваться. Но делать так нельзя. В этом случае ИИ не сможет проехать сквозь препятствие в ситуации, когда юнит полностью застрял.
Но выход есть: мы будем отталкивать юниты друг от друга нашим собственным алгоритмом, который будет отталкивать, но при этом позволит при необходимости юнитам проезжать друг сквозь друга.
Реализация следующая:
Если юнит видит, что рядом есть кто-то ближе радиуса отталкивания — он получает вектор в котором нужно оттолкнуться, чтобы прекратить пересечение. Для жестких тел длина этого вектора была бы равна разнице радиуса отталкивания и текущего расстояния. Но мы будем считать длину по-другому. А именно: возьмем скорость юнита, умножим её на коэффициент отталкивания (меньше 1) и умножим на время. То есть выталкивание будет происходить со скоростью, пропорциональной скорости юнита, но при этом строго меньшей.
Даже если юнит лбом уткнется в препятствие, то поскольку его скорость выше скорости выталкивания, то он въедет в препятствие, а потом препятствие его вытолкнет. При боковом же соприкосновении это будет выглядеть как обычное соприкосновение жестких тел.
Еще одним плюсом такого алгоритма является то, что стоящие на месте объекты не будут расталкиваться едущими юнитами, так как алгоритм односторонний. При этом, если едут два юнита и они пересеклись — они оба в рамках своего расчета взаимно оттолкнутся.
Заключение
В итоге мы имеем алгоритм, который до последнего пытается изобразить, что юниты ездят как честные физические объекты, но даже в тех редких случаях, когда этого достичь не удается — геймплей не страдает, а в жертву геймплею приносится условность реалистичности.