Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Навігаційна сітка англ navmesh чи navigation mesh це абстрактна структура даних яка використовується в програмах штучног

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

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

Навігаційна сітка, англ. 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.

Примітки

  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). (PDF) (Technical Report). University of Massachusetts. Архів оригіналу (PDF) за 15 серпня 2018. Процитовано 24 лютого 2021.
  • Brand, Sandy (2009). (PDF) (Master thesis). Delft University of Technology. Архів оригіналу (PDF) за 10 червня 2015. Процитовано 9 червня 2015.
  • Golodetz, Stuart (October 2013). . 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 .
  • Tozour, Paul (2002). Building a Near-Optimal Navigation Mesh. У Rabin, Steve (ред.). AI Game Programming Wisdom. Charles River Media. с. 171–185. ISBN .
  • van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland (2012). (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). (PDF) (M.Sc. thesis). Delft University of Technology. Архів оригіналу (PDF) за 5 березня 2005. Процитовано 24 лютого 2021.

Зовнішні посилання

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Navigacijna sitka angl navmesh chi navigation mesh ce abstraktna struktura danih yaka vikoristovuyetsya v programah shtuchnogo intelektu dlya dopomogi agentam u poshuku shlyahiv cherez skladni prostori Cej pidhid buv vidomij prinajmni z seredini 1980 h rokiv u robototehnici de jogo nazivali mapoyu lugiv meadow map i buv populyarizovanij v igrovomu ShI u 2000 roci OpisNavigacijna sitka ce sukupnist dvovimirnih opuklih bagatokutnikiv poligonalna sitka sho viznachayut yaki dilyanki seredovisha prohodyat agenti Inshimi slovami personazh u gri mozhe vilno hoditi po cih dilyankah bez pereshkod dereva lavi chi inshih perepon yaki ye chastinoyu navkolishnogo seredovisha Sumizhni bagatokutniki z yednani mizh soboyu u grafi Viznachennya konturiv u mezhah odnogo z cih bagatokutnikiv mozhna vikonuvati trivialno po pryamij tomu sho bagatokutnik opuklij ta prohidnij Vidilennya shlyahu mizh poligonami v sitci mozhe buti zdijsneno za dopomogoyu odnogo z velikoyi kilkosti algoritmiv poshuku grafikiv takih yak A agenti v navmesh mozhut uniknuti obchislyuvalno dorogih perevirok viyavlennya zitknen iz pereshkodami yaki ye chastinoyu navkolishnogo seredovisha Podannya prohidnih oblastej u 2D podibnij formi sproshuye obchislennya yaki v inshomu vipadku potribno bulo b robiti v spravzhnomu 3D seredovishi prote na vidminu vid 2D sitki vono dozvolyaye prohodzhuvani dilyanki yaki nakladayutsya zverhu ta znizu na riznij visoti Poligoni riznih rozmiriv i form u navigacijnih sitkah mozhut predstavlyati dovilni seredovisha z bilshoyu tochnistyu nizh zvichajni sitki StvorennyaNavigacijni sitki mozhna stvoryuvati vruchnu avtomatichno abo za dopomogoyu pevnoyi kombinaciyi U videoigrah dizajner rivniv mozhe vruchnu viznachiti poligoni navmesh u redaktori rivniv Cej pidhid mozhe buti dosit trudomistkim Yak variant mozhna stvoriti programu yaka prijmaye geometriyu rivnya yak vhidnu j avtomatichno vivodit navigacijnu merezhu Zazvichaj zavedeno vvazhati sho seredovishe podane u navmesh ye statichnim vono ne zminyuyetsya z chasom i otzhe navmesh mozhe buti stvoreno v oflajn rezhimi ta zalisheno bez zmin Odnak bulo provedeno deyake doslidzhennya onlajn onovlennya navigacijnih sitok dlya dinamichnih seredovish IstoriyaU robototehnici vikoristannya zv yazanih opuklih bagatokutnikiv u takij sposib bulo nazvano mapingom lugiv pridumanim u 1986 roku Navigacijni sitki u shtuchnomu intelekti videoigor yak pravilo zarahovuyutsya do statti Grega Snuka vid 2000 roku Sproshenij ruh i poshuk shlyahiv za dopomogoyu navigacijnih sitok u Game Programming Gems U 2001 roci JMP van Vaveren opisav podibnu strukturu z opuklimi ta z yednanimi trikutnikami u 3D sho otrimala nazvu Sistema obiznanosti pro miscevist Area Awareness System sho vikoristovuyetsya dlya botiv na Quake III Arena PrimitkiSnook 2000 s 294 295 Snook 2000 s 289 Brand 2009 s 4 Brand 2009 s 10 van Toll Cook IV ta Geraerts 2012 Tozour 2002 s 171 Arkin 1986 Golodetz 2013 van Waveren 2001 s 24 46 Dzherela Arkin Ronald C 1986 PDF Technical Report University of Massachusetts Arhiv originalu PDF za 15 serpnya 2018 Procitovano 24 lyutogo 2021 Brand Sandy 2009 PDF Master thesis Delft University of Technology Arhiv originalu PDF za 10 chervnya 2015 Procitovano 9 chervnya 2015 Golodetz Stuart October 2013 Overload ACCU 117 Arhiv originalu za 10 chervnya 2015 Procitovano 24 lyutogo 2021 Snook Greg 2000 Simplified 3D Movement and Pathfinding Using Navigation Meshes U DeLoura Mark red Game Programming Gems Charles River Media s 288 304 ISBN 1 58450 049 2 Tozour Paul 2002 Building a Near Optimal Navigation Mesh U Rabin Steve red AI Game Programming Wisdom Charles River Media s 171 185 ISBN 1 58450 077 8 van Toll Wouter G Cook IV Atlas F Geraerts Roland 2012 PDF Computer Animation and Virtual Worlds John Wiley amp Sons 23 6 535 546 doi 10 1002 cav 1468 Arhiv originalu PDF za 24 veresnya 2015 Procitovano 9 chervnya 2015 van Waveren J M P 28 sichnya 2001 PDF M Sc thesis Delft University of Technology Arhiv originalu PDF za 5 bereznya 2005 Procitovano 24 lyutogo 2021 Zovnishni posilannyaUDK Navigation Mesh Reference 13 listopada 2016 u Wayback Machine Unity Navigation Meshes 5 travnya 2021 u Wayback Machine Source Engine Navigation Meshes 24 sichnya 2021 u Wayback Machine Urho3D Navigation 14 veresnya 2020 u Wayback Machine Godot Engine Navigation 26 lyutogo 2021 u Wayback Machine Cry Engine Navigation And AI 12 travnya 2021 u Wayback Machine

Дата публікації:
Топ