InnerWorkingsOfNavigationSystem
Внутренняя работа Навигационной системы
Если вы хотите чтобы ваши персонажи (в среде Искусственного Интеллекта (AI) они называются агентами) , разумно перемещались по сцене, вы должны решить две проблемы: как проанализировать игровой уровень, чтобы найти точку назначения, и как туда двигаться. Две эти проблемы хотя и тесно связаны, но по сути своей совершенно разные. Проблема анализа игрового уровня более глобальна и статична, поскольку она учитывает весь уровень. Движение к точке назначения более локальная и динамичная задача, она учитывает только направление движения и способы предотвращения столкновений с другими движущимися агентами.
Проходимые области (Walkable Area)
Навигационная система нуждается в собственных данных, чтобы представлять доступные области в игровой сцене. Проходимые области определяют места в сцене, где агент может стоять и двигаться. В Unity агенты описываются как цилиндры. Проходимая область автоматически создается из геометрии сцены, определяя точки, где может находится агент. Затем эти точки соединяются в поверхность, лежащую поверх геометрии сцены. Эта поверхность называется навигационной сеткой (для краткости NavMesh).
NavMesh сохраняет эту поверхность как совокупност выпуклых полигонов. Выпуклые полигоны являются полезным представлением, поскольку мы знаем, что между любыми двумя точками внутри выпуклого полигона нет препятствий. Вдобавок к этому мы сохраняем информацию о том, какие полигоны являются соседями. Это позволяет нам иметь представление о всей проходимой области.
Поиск пути
Чтобы найти путь между двумя точками в сцене, нам сначала нужно сопоставить места начала и места назначения с их ближайшими полигонами. Затем мы начинаем поиск в исходном местоположении, посещая всех соседей, пока не достигнем целевого полигона. Отслеживание посещенных полигонов позволяет нам найти последовательность полигонов, которая будет проходить от начала до места назначения. Распространенным алгоритмом поиска пути является A * (произносится как «эй стар»), его и использует Unity.
Следование по маршруту
Последовательность полигонов, которые описывают путь от начала до целевого полигона, называется коридором. Агент достигнет пункта назначения, всегда направляясь к следующему видимому углу коридора. Если у вас есть простая игра, в которой только один агент перемещается в сцене, хорошо бы найти все углы коридора одним махом и анимировать персонажа для перемещения вдоль сегментов линии, соединяющей углы.
Когда вы работаете с несколькими агентами, которые одновременно двигаются, им нужно будет отклоняться от исходного пути, чтобы избежать столкновения друг с другом. Попытка исправить такие отклонения с использованием пути, состоящего из сегментов линии, вскоре приведёт к сильному усложнению задачи и возникновению ошибок.
Так как перемещение агента в каждом кадре довольно мало, мы можем использовать связанность полигонов, чтобы зафиксировать коридор, если нам нужно немного пройти. Затем мы быстро найдем следующий видимый угол, и направимся к нему.
Обход Препятствий
Логика управления берёт позицию следующего угла и на основании этого определяет желаемое направление и скорость, необходимые для достижения цели. Использование желаемой скорости для перемещения агента может привести к столкновению с другими агентами.
Логика уклонения от препятствий выбирает новую скорость, которая балансирует между движением в нужном направлении и предотвращением будущих столкновений с другими агентами и краями навигационной сетки. Unity использует Совместную Скорость Препятствий (Reciprocal Velocity Obstacles, RVO) для прогнозирования и предотвращения столкновений.
Передвижение Агента
Наконец, после определения направления и предотвращения столкновений с препятствиями вычисляется конечная скорость. В Unity агенты моделируются с использованием простой динамической модели, которая также учитывает ускорение, чтобы обеспечить более естественное и плавное движение.
На этом этапе вы можете передавать скорость от симулируемого агента в анимационную систему, чтобы переместить персонаж с помощью корневого движения или позволить навигационной системе самой позаботиться об этом.
Когда агент перемещен с использованием любого из методов, положение имитируемого агента перемещается и привязывается к NavMesh. Этот последний маленький шаг важен для надежной навигации.
Глобальная и Локальная Навигация
Одна из самых важных вещей, которые нужно понимать в навигации, - это разница между глобальной и локальной навигацией.
Глобальная навигация используется для поиска коридора по всему миру. Поиск пути по всему миру - дорогостоящая операция, требующая довольно большой вычислительной мощности и много памяти.
Линейный список полигонов, описывающих путь, представляет собой гибкую структуру данных для управления движением, и ее можно локально корректировать по мере перемещения позиции агента. Локальная навигация пытается выяснить, как эффективно перейти к следующему углу, не сталкиваясь с другими агентами или движущимися объектами.
Два варианта обхождения препятствий
Многим приложениям требуются не только агенты, но и другие типы препятствий. Это могут быть обычные ящики и бочки в шутерской игре или транспортное средство. Препятствия можно обойти с помощью локального избегания препятствий или глобального поиска пути.
Когда препятствие движется, его лучше всего обойти, используя локальное избегание препятствия. Таким образом, агент может прогностически избегать препятствия. Когда препятствие становится неподвижным и может блокировать путь для всех агентов, оно должно влиять на глобальную навигацию, то есть на навигационную сетку.
Изменение NavMesh называется вырезка. Процесс определяет, какие части препятствия касаются NavMesh и вырезает в NavMesh дырки. Это дорогостоящая операция, которая является еще одной убедительной причиной, почему нужно преодолевать препятствия с помощью предотвращения столкновений.
Локальное избегание столкновений часто можно использовать также для того, чтобы обойти рассеянное скопление препятствий. Поскольку алгоритм является локальным, он будет учитывать только несколько ближайших столкновений и не может обходить ловушки или обрабатывать случаи, когда препятствие блокирует путь. Эти задачи могут быть решены с помощью вырезки.
Описание Несеточных Переходов (Off-Mesh Link)
Связи между полигонами NavMesh описаны с помощью ссылок внутри системы поиска пути. Иногда необходимо, чтобы агент мог пересечь места, которые являются непроходимыми, например, перепрыгнуть через забор или пройти через закрытую дверь. Этим функциям требуется знать место специального действия.
Эти специальные действия могут быть реализованы с использованием Off-Mesh Link, которые сообщают алгоритму поиска пути, что через указанное место существует проход. Этот пререход может быть позже доступен при движении по пути, и тогда может быть выполнено специальное действие.