Лекция
, англ. navmesh или navigation mesh , это абстрактная структура данных, которая используется в программах искусственного интеллекта для помощи агентам в поиске путей через сложные пространства. Этот подход был известен по крайней мере с середины 1980-х годов в робототехнике , где его называли " картой лугов" (meadow map) , и был популяризирован в игровом ИИ в 2000 году.
Навигационная сетка – это совокупность двухмерных выпуклых многоугольников ( полигональная сетка ), определяющих, какие участки среды проходят агенты. Другими словами, персонаж в игре может свободно ходить по этим участкам без помех дерева, скамьи или других преград, являющихся частью окружающей среды. Смежные многоугольники соединены между собой в графе .
Определение контуров в пределах одного из этих многоугольников можно выполнять тривиально по прямой , т.к. многоугольник выпуклый и проходной . окружающей среды.
Представление проходных областей в 2D-образной форме упрощает вычисления, которые в противном случае нужно было бы делать в "настоящей" 3D-среде, однако, в отличие от 2D-сетки, оно позволяет проходимым участкам, которые накладываются сверху и снизу на разной высоте. Полигоны разных размеров и форм в навигационных сетях могут представлять произвольные среды с большей точностью, чем обычные сетки.
Навигационная сетка в игре (часто называемая navigation mesh или navmesh) — это упрощенная геометрическая структура, которая указывает, где персонажи могут перемещаться. Она выглядит как сеть многоугольников (обычно треугольников или четырехугольников), натянутых по поверхности уровней. Вот как ее можно представить:
Плоские или рельефные полигоны, покрывающие проходимые области;
Яркие границы, отделяющие зоны, где движение возможно, от препятствий;
Иногда — стрелки или направления движения, если навмеш использует потоковые данные;
Разрывы или «дыры» в местах, где ходить нельзя (например, вода, стены, обрывы).
Визуально это похоже на упрощенную карту уровня, разлинованную на кусочки, где каждый кусочек — потенциальная точка для перемещения NPC. В редакторах или дебаг-режимах она обычно отображается полупрозрачной сеткой поверх сцены.
По сравнению с навигационными точками навигационные сетки имеют следующие преимущества:
Навигационные сетки можно создавать вручную, автоматически или с помощью определенной комбинации. В видеоиграх дизайнер уровней может вручную определить полигоны navmesh в редакторе уровней .
Обычно принято считать, что среда, представленная в navmesh, является статичной - она не меняется со временем - и, следовательно, navmesh может быть создана в офлайн-режиме и оставлена без изменений. Однако было проведено некоторое исследование онлайн-обновления навигационных сеток для динамических сред.
Создается навигационная карта на основе геометрии уровня (вручную или автоматически).
Навигационные агенты (NPC, враги, союзники) используют NavMesh для поиска пути.
В связке с алгоритмом (чаще всего A*), агент рассчитывает кратчайший маршрут до цели.
В робототехнике использование связанных выпуклых многоугольников таким образом было названо «маппингом щелочей» придуманным в техническом отчете Рональда К. Аркина в 1986 году.
Навигационные сетки в искусственном интеллекте видеоигр, как правило, причисляются к статье Грега Снука от 2000 года "Упрощенное движение и поиск путей с помощью навигационных сетей" в " Game Programming Gems" . «Система осведомленности о местности» (Area Awareness System ) , используемая для ботов на Quake III Arena .
Реализация навигационной сетки на самом деле представляет собой три алгоритма:
Для поиска оптимального пути чаще всего используется A*
| Игровой жанр | Применение NavMesh |
|---|---|
| 3D Action/RPG | Враги ищут путь к игроку |
| 2D платформеры | Прыжки по платформам и избегание обрывов |
| Стратегии | Группы юнитов обходят здания и объекты |
| Симуляторы толпы | Люди избегают столкновений друг с другом |
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов