Ключевые слова: NavMesh, Unity, агент, навигационная система.
Когда разработчику необходимо умно перемещать игровых персонажей (также их называют агентами) в игре, он должны решить две проблемы: как «понять» игровой уровень, чтобы найти цель, и как переместиться туда. Проблема «понимания» уровня берет в расчет целую сцену. Движение рассматривает только направление движения и как предотвратить сталкивание с другими агентами.
Система навигации нуждается в данных для отображения проходимых областях в сцене. Проходимые области определяются как места в сцене, где агент может стоять и двигаться. Проходимые области строятся автоматически, тестируя места, где агент может стоять. Затем эти места связываются к поверхности сцены. Это поверхность называется навигационной сеткой (Часто ее называют NavMesh) [1], которая изображена на рисунке 1.
Рис. 1. Навигационная сетка и агент
NavMesh хранит эту поверхность как выпуклые полигоны. Выпуклые полигоны полезны тем, что сообщают, что там нет препятствий между любыми двумя точками внутри полигона. Также к границам полигонов добавляется информация, какие полигоны являются соседними, по отношению друг к другу.
Чтобы найти путь между двумя локациями в сцене, сперва необходимо отметить стартовую и конечную локации их ближайших полигонов. Затем необходимо начать поиск с начальной локации, посещая всех соседей, до тех пор, пока не будет найден нужный полигон. Отслеживание всех посещенных полигонов позволяет найти последовательность полигонов, которая ведет от старта к конечной цели. Распространённый алгоритм для нахождения пути, который использует Unity - это A*[2] (произносится как А звезда или А стар).
Последовательность полигонов, которая описывает путь от старта, до конечной цели называется коридором. Агент достигнет конечной цели, направляясь к следующему, видимому угла коридора. Если разработчик имеет простую игру, где перемещается только один агент по сцене, то есть возможность найти все углы коридора одним махом.
Когда же разработчик имеет дело с множественными агентами, которые двигаются в одно и тоже время, тогда им нужно отклоняться с оригинального пути, чтобы избегать друг друга. Поскольку движение агента в каждом кадре довольно маленькое, то можно использовать связь полигонов, чтобы поправить коридор для взятия крюка.
Направляющая логика берет позицию следующего угла, желаемое направление и скорость, нужные для достижения цели.
Obstacle avoidance (Алгоритм избегания препятствий) выбирает новую скорость, которая балансирует между движением в желаемом направлении, предотвращением будущих столкновений с другими агентами и краями NavMesh-а. Unity использует reciprocal velocity obstacles (взаимная скорость объектов) чтобы предсказать и предотвратить столкновения.
Наконец, после выбора направления и использования obstacle avoidance, финальная скорость подсчитана. В Unity агенты симулированы, используя простую динамическую модель, которая также берет в расчет ускорение, чтобы обеспечить более естественное и плавное перемещение.
На этой стадии возможно отправить скорость симулированного агента Mecanim animation system, чтобы переместить персонажа, или же позволить навигационной системе самой позаботиться об этом. Как только персонаж был перемещен, расположение персонажа перемещено и ограничено по NavMesh. Этот шаг важен для надежной навигации.
Одна из самых главных вещей для понимания навигации – это разница между глобальной и локальной навигациями. Глобальная навигация используется чтобы найти коридор через весь мир. Нахождение пути через мир – трудоемкая операция, требующая довольно много энергии процессора и памяти.
Линейный лист полигонов описывающий путь – это гибкая структура данных для выбора направления, и может быть локально корректирована во время движения персонажа. Локальная навигация пытается понять, как эффективно двигать к следующему углу без столкновения с другими агентами или движущимися объектами.
Многие приложения навигационной системы требуют другой тип препятствий, чем просто другие агенты. К примеру, это могли бы быть обычные ящики или бочки в шутере. Препятствия могут быть рассмотрены, используя локальное obstacle avoidance или глобальное нахождение пути. Когда препятствие движется, оно лучше рассматривается, используя локальное obstacle avoidance. Когда препятствие становиться неподвижным оно должно повлиять на глобальную навигацию, то есть на NavMesh.
Изменение NavMesh называется carving (резьба или вырезание) [3]. Этот процесс обнаруживает какие части препятствий касаются NavMesh, и вырезает дыры в NavMesh. Это сложная вычислительная операция, которая является еще одной убедительной причиной, почему перемещение препятствий должно рассматриваться, используя collision avoidance (Алгоритм избегания столкновений).
Локальное collision avoidance также может быть часто использовано, чтобы выбираться направление возле скудно разбросанных препятствий. Поскольку алгоритм локальный, он будет учитывать только следующее непосредственное столкновение, и не может быть направлено возле ловушек или рассматривать случаи, где препятствие блокирует путь. Эти случаи могут быть решены, используя carving.
Связь между полигонами NavMesh описана, используя ссылки внутри системы нахождения пути. Иногда необходимо позволить агенту ориентироваться через места, где нельзя пройти, к примеру прыжок через забор или прохождение через закрытую дверь. Этим случаям нужно знать расположения этого действия.
Эти действия могут быть описаны с использованием Off-mesh Links, которая расскажет системе нахождения пути, что существует маршрут через указанную ссылку. Эта ссылка может быть позже доступна, при следовании определенного пути и выполнении специального действия. Пример изображен на рисунке 2.
Рис. 2. Применение Off-Mesh Link
Литература:
- Хокинг Джозеф. Unity в действии. Мультиплатформенная разработка на C# - 2016.
- Гибсон Бонд, Гибсон Бонд Джереми. Unity и C#. Геймдев от идеи до реализации – 2019
- Мэннинг Джон, Батфилд-Эддисон Пэрис. Unity для разработчика. Мобильные мультиплатформенные игры – 2018 – C. 274-292
