Вікіпедія

Навігаційна сітка

Навігаційна сітка, англ. navmesh чи navigation mesh, - це абстрактна структура даних, яка використовується в програмах штучного інтелекту для допомоги агентам у пошуку шляхів через складні простори. Цей підхід був відомий принаймні з середини 1980-х років у робототехніці, де його називали "мапою лугів" (meadow map), і був популяризований в ігровому ШІ у 2000 році.

Опис ред.

Навігаційна сітка - це сукупність двовимірних опуклих багатокутників (полігональна сітка), що визначають, які ділянки середовища проходять агенти. Іншими словами, персонаж у грі може вільно ходити по цих ділянках без перешкод дерева, лави чи інших перепон, які є частиною навколишнього середовища. Суміжні багатокутники з’єднані між собою у графі.

Визначення контурів у межах одного з цих багатокутників можна виконувати тривіально по прямій, тому що багатокутник опуклий та прохідний. Виділення шляху між полігонами в сітці може бути здійснено за допомогою одного з великої кількості алгоритмів пошуку графіків, таких як A * . [1] агенти в navmesh можуть уникнути обчислювально дорогих перевірок виявлення зіткнень із перешкодами, які є частиною навколишнього середовища.

Подання прохідних областей у 2D-подібній формі спрощує обчислення, які в іншому випадку потрібно було б робити в "справжньому" 3D-середовищі, проте, на відміну від 2D-сітки, воно дозволяє проходжувані ділянки, які накладаються зверху та знизу на різній висоті. [2] Полігони різних розмірів і форм у навігаційних сітках можуть представляти довільні середовища з більшою точністю, ніж звичайні сітки. [3]

Створення ред.

Навігаційні сітки можна створювати вручну, автоматично або за допомогою певної комбінації. У відеоіграх дизайнер рівнів може вручну визначити полігони navmesh у редакторі рівнів. Цей підхід може бути досить трудомістким. [4] Як варіант, можна створити програму, яка приймає геометрію рівня як вхідну й автоматично виводить навігаційну мережу.

Зазвичай заведено вважати, що середовище, подане у navmesh, є статичним - воно не змінюється з часом - і, отже, navmesh може бути створено в офлайн-режимі та залишено без змін. Однак було проведено деяке дослідження онлайн-оновлення навігаційних сіток для динамічних середовищ. [5]

Історія ред.

У робототехніці використання зв’язаних опуклих багатокутників у такий спосіб було названо «мапінгом лугів»[6] придуманим у технічному звіті Рональда К. Аркіна 1986 року. [7]

Навігаційні сітки у штучному інтелекті відеоігор, як правило, зараховуються до статті Грега Снука від 2000 року "Спрощений рух і пошук шляхів за допомогою навігаційних сіток" у "Game Programming Gems". [8] У 2001 році JMP ван Ваверен описав подібну структуру з опуклими та з’єднаними трикутниками у 3D, що отримала назву «Система обізнаності про місцевість» (Area Awareness System), що використовується для ботів на Quake III Arena. [9]

Примітки ред.

  1. ↑ Snook, 2000, с. 294–295.
  2. ↑ Snook, 2000, с. 289.
  3. ↑ Brand, 2009, с. 4.
  4. ↑ Brand, 2009, с. 10.
  5. ↑ van Toll, Cook IV та Geraerts, 2012.
  6. ↑ Tozour, 2002, с. 171.
  7. ↑ Arkin, 1986.
  8. ↑ Golodetz, 2013.
  9. ↑ van Waveren, 2001, с. 24–46.

Джерела ред.

 

  • Arkin, Ronald C. (1986). Path Planning for a Vision-Based Autonomous Robot (PDF) (Technical Report). University of Massachusetts. Архів оригіналу (PDF) за 15 серпня 2018. Процитовано 24 лютого 2021.
  • Brand, Sandy (2009). Efficient obstacle avoidance using autonomously generated navigation meshes (PDF) (Master thesis). Delft University of Technology. Архів оригіналу (PDF) за 10 червня 2015. Процитовано 9 червня 2015.
  • Golodetz, Stuart (October 2013). Automatic Navigation Mesh Generation in Configuration Space. Overload. ACCU. 117. Архів оригіналу за 10 червня 2015. Процитовано 24 лютого 2021.
  • Snook, Greg (2000). Simplified 3D Movement and Pathfinding Using Navigation Meshes. У DeLoura, Mark (ред.). Game Programming Gems. Charles River Media. с. 288–304. ISBN 1-58450-049-2.
  • Tozour, Paul (2002). Building a Near-Optimal Navigation Mesh. У Rabin, Steve (ред.). AI Game Programming Wisdom. Charles River Media. с. 171–185. ISBN 1-58450-077-8.
  • van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland (2012). A navigation mesh for dynamic environments (PDF). Computer Animation and Virtual Worlds. John Wiley & Sons. 23 (6): 535—546. doi:10.1002/cav.1468. Архів оригіналу (PDF) за 24 вересня 2015. Процитовано 9 червня 2015.
  • van Waveren, J.M.P. (28 січня 2001). The Quake III Arena Bot (PDF) (M.Sc. thesis). Delft University of Technology. Архів оригіналу (PDF) за 5 березня 2005. Процитовано 24 лютого 2021.

Зовнішні посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Навігаційна_сітка&oldid=35030516