Навигационная сетка , или navmesh , представляет собой абстрактную структуру данных , используемую в приложениях искусственного интеллекта для помощи агентам в поиске пути через сложные пространства. Этот подход известен по крайней мере с середины 1980-х годов в робототехнике , где он назывался meadow map , [1] и был популярен в видеоиграх AI в 2000 году.
Навигационная сетка — это набор двумерных выпуклых многоугольников ( полигональная сетка ), которые определяют, какие области среды доступны для прохождения агентами. Другими словами, персонаж в игре может свободно перемещаться по этим областям, не встречая препятствий в виде деревьев, лавы или других препятствий, являющихся частью среды. Соседние многоугольники соединены друг с другом в графе .
Поиск пути внутри одного из этих полигонов может быть выполнен тривиально по прямой линии, поскольку полигон выпуклый и проходимый. Поиск пути между полигонами в сетке может быть выполнен с помощью одного из большого количества алгоритмов поиска графа , таких как A* . [2] Таким образом, агенты в навигационной сетке могут избегать вычислительно затратных проверок обнаружения столкновений с препятствиями, которые являются частью среды.
Представление проходимых областей в форме, подобной 2D, упрощает вычисления, которые в противном случае пришлось бы выполнять в «истинной» 3D-среде, однако в отличие от 2D-сетки оно допускает проходимую область, которая перекрывается сверху и снизу на разной высоте. [3] Полигоны различных размеров и форм в навигационных сетках могут представлять произвольные среды с большей точностью, чем обычные сетки. [4]
Навигационные сетки могут быть созданы вручную, автоматически или с помощью некоторой комбинации этих двух методов. В видеоиграх дизайнер уровней может вручную определить полигоны навигационной сетки в редакторе уровней . Такой подход может быть довольно трудоемким. [5] В качестве альтернативы можно создать приложение, которое принимает геометрию уровня в качестве входных данных и автоматически выводит навигационную сетку.
Обычно предполагается, что среда, представленная навигационной сеткой, статична – она не меняется со временем – и, таким образом, навигационная сетка может быть создана в автономном режиме и быть неизменяемой. Однако были проведены некоторые исследования онлайн-обновления навигационных сеток для динамических сред. [6]
В робототехнике использование связанных выпуклых многоугольников таким образом получило название «картографирование лугов» [1], введенное в обращение в техническом отчете Рональда С. Аркина за 1986 год . [7]
Навигационные сетки в искусственном интеллекте видеоигр обычно приписываются статье Грега Снука 2000 года «Упрощенное 3D-движение и поиск пути с использованием навигационных сеток» в Game Programming Gems . [8] В 2001 году Дж. М. П. ван Вейверен описал похожую структуру с выпуклыми и связанными 3D-полигонами, названную «Системой осведомлённости об области», используемую для ботов в Quake III Arena . [9]
{{cite journal}}: Цитировать журнал требует |journal=( помощь )