Навигационная сетка
Навигационная сетка , или navmesh , — это абстрактная структура данных , используемая в приложениях искусственного интеллекта , чтобы помочь агентам в поиске пути в сложных пространствах. Этот подход известен как минимум с середины 1980-х годов в робототехнике , где его называли картой лугов . [1] и был популяризирован в области искусственного интеллекта в видеоиграх в 2000 году.
Описание
[ редактировать ]Навигационная сетка — это набор двумерных выпуклых многоугольников ( многоугольная сетка ), которые определяют, какие области среды могут пересекать агенты. Другими словами, персонаж в игре может свободно передвигаться по этим областям, не загораживаясь деревьями, лавой или другими барьерами, являющимися частью окружающей среды. Соседние многоугольники соединяются друг с другом в графе .
Поиск пути внутри одного из этих многоугольников можно тривиально выполнить по прямой линии, поскольку многоугольник выпуклый и проходимый. Поиск пути между полигонами в сетке можно выполнить с помощью одного из большого количества алгоритмов поиска по графу , например A* . [2] Таким образом, агенты в навигационной сетке могут избежать дорогостоящих в вычислительном отношении проверок обнаружения столкновений с препятствиями, которые являются частью окружающей среды.
Представление проходимых областей в 2D-подобной форме упрощает вычисления, которые в противном случае пришлось бы выполнять в «настоящей» 3D-среде, однако, в отличие от 2D-сетки, оно позволяет пересекать области, которые перекрываются сверху и снизу на разной высоте. [3] Многоугольники различных размеров и форм в навигационных сетках могут представлять произвольную среду с большей точностью, чем обычные сетки. [4]
Создание
[ редактировать ]Навигационные сетки могут создаваться вручную, автоматически или путем их комбинации. В видеоиграх дизайнер уровней может вручную определять полигоны навигационной сетки в редакторе уровней . Этот подход может оказаться весьма трудоемким. [5] В качестве альтернативы можно создать приложение, которое принимает геометрию уровня в качестве входных данных и автоматически выводит навигационную сетку.
Обычно предполагается, что среда, представленная навигационной сеткой, является статической – она не меняется со временем – и, следовательно, навигационная сетка может быть создана в автономном режиме и быть неизменяемой. Тем не менее, было проведено исследование онлайн-обновления навигационных сеток для динамических сред. [6]
История
[ редактировать ]В робототехнике такое использование связанных выпуклых многоугольников называется «отображением лугов». [1] придуман в техническом отчете Рональда К. Аркина в 1986 году . [7]
Навигационные сетки в искусственном интеллекте видеоигр обычно приписывают статье Грега Снука 2000 года «Упрощенное 3D-движение и поиск пути с использованием навигационных сеток» в Game Programming Gems . [8] В 2001 году JMP ван Ваверен описал аналогичную структуру с выпуклыми и связанными 3D-полигонами, получившую название «Система осведомленности об области», используемую для ботов в Quake III Arena . [9]
Примечания
[ редактировать ]- ^ Перейти обратно: а б Тозур 2002 , с. 171.
- ^ Снук 2000 , с. 294–295.
- ^ Снук 2000 , с. 289.
- ^ Бренд 2009 , с. 4.
- ^ Бренд 2009 , с. 10.
- ^ ван Толль, Кук IV и Герертс 2012 .
- ^ Аркин 1986 .
- ^ Golodetz 2013 .
- ^ ван Ваверен 2001 , с. 24–46.
Ссылки
[ редактировать ]- Аркин, Рональд К. (1986). «Планирование пути для автономного робота на основе машинного зрения» (PDF) (технический отчет). Университет Массачусетса.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - Брэнд, Сэнди (2009). Эффективное объезд препятствий с использованием автономно генерируемых навигационных сеток (PDF) (магистерская диссертация). Делфтский технологический университет . Проверено 9 июня 2015 г.
- Голодец, Стюарт (октябрь 2013 г.). «Автоматическое создание навигационной сетки в пространстве конфигурации» . Перегрузка . 117 . АККУ.
- Снук, Грег (2000). «Упрощенное 3D-движение и поиск пути с использованием навигационных сеток». В ДеЛура, Марк (ред.). Жемчужины игрового программирования . Чарльз Ривер Медиа. стр. 288–304. ISBN 1-58450-049-2 .
- Тозур, Пол (2002). «Построение почти оптимальной навигационной сетки». У Рабина, Стив (ред.). Мудрость программирования игр с искусственным интеллектом . Чарльз Ривер Медиа. стр. 171–185 . ISBN 1-58450-077-8 .
- ван Толл, Воутер Г.; Кук IV, Атлас Ф.; Герертс, Роланд (2012). «Навигационная сетка для динамических сред» (PDF) . Компьютерная анимация и виртуальные миры . 23 (6). Джон Уайли и сыновья: 535–546. дои : 10.1002/cav.1468 . S2CID 2996937 . Проверено 9 июня 2015 г.
- ван Ваверен, JMP (28 января 2001 г.). Quake III Arena Bot (PDF) (магистерская диссертация). Делфтский технологический университет.