Навігаційна сітка, англ. navmesh чи navigation mesh, - це абстрактна структура даних, яка використовується в програмах штучного інтелекту для допомоги агентам у пошуку шляхів через складні простори. Цей підхід був відомий принаймні з середини 1980-х років у робототехніці, де його називали "мапою лугів" (meadow map), і був популяризований в ігровому ШІ у 2000 році.
Опис Навігаційна сітка - це сукупність двовимірних опуклих багатокутників (полігональна сітка), що визначають, які ділянки середовища проходять агенти. Іншими словами, персонаж у грі може вільно ходити по цих ділянках без перешкод дерева, лави чи інших перепон, які є частиною навколишнього середовища. Суміжні багатокутники з’єднані між собою у графі.
Визначення контурів у межах одного з цих багатокутників можна виконувати тривіально по прямій, тому що багатокутник опуклий та прохідний. Виділення шляху між полігонами в сітці може бути здійснено за допомогою одного з великої кількості алгоритмів пошуку графіків, таких як A * агенти в navmesh можуть уникнути обчислювально дорогих перевірок виявлення зіткнень із перешкодами, які є частиною навколишнього середовища.
Подання прохідних областей у 2D-подібній формі спрощує обчислення, які в іншому випадку потрібно було б робити в "справжньому" 3D-середовищі, проте, на відміну від 2D-сітки, воно дозволяє проходжувані ділянки, які накладаються зверху та знизу на різній висоті . Полігони різних розмірів і форм у навігаційних сітках можуть представляти довільні середовища з більшою точністю, ніж звичайні сітки .
Створення Навігаційні сітки можна створювати вручну, автоматично або за допомогою певної комбінації. У відеоіграх дизайнер рівнів може вручну визначити полігони navmesh у редакторі рівнів. Цей підхід може бути досить трудомістким . Як варіант, можна створити програму, яка приймає геометрію рівня як вхідну й автоматично виводить навігаційну мережу.
Зазвичай заведено вважати, що середовище, подане у navmesh, є статичним - воно не змінюється з часом - і, отже, navmesh може бути створено в офлайн-режимі та залишено без змін. Однак було проведено деяке дослідження онлайн-оновлення навігаційних сіток для динамічних середовищ .
Історія У робототехніці використання зв’язаних опуклих багатокутників у такий спосіб було названо «мапінгом лугів» придуманим у технічному звіті Рональда К. Аркіна 1986 року .
Навігаційні сітки у штучному інтелекті відеоігор, як правило, зараховуються до статті Грега Снука від 2000 року "Спрощений рух і пошук шляхів за допомогою навігаційних сіток" у "Game Programming Gems". У 2001 році JMP ван Ваверен описав подібну структуру з опуклими та з’єднаними трикутниками у 3D, що отримала назву «Система обізнаності про місцевість» (Area Awareness System), що використовується для ботів на Quake III Arena .
Примітки
Джерела
Зовнішні посилання
UDK: Navigation Mesh Reference Unity: Navigation Meshes Source Engine: Navigation Meshes Urho3D: Navigation Godot Engine Navigation Cry Engine Navigation And AI