Siatka nawigacji
Siatka nawigacyjna lub navmesh to abstrakcyjna struktura danych używana w aplikacjach sztucznej inteligencji , aby pomóc agentom w wyszukiwaniu ścieżek w skomplikowanych przestrzeniach. Podejście to było znane co najmniej od połowy lat 80. w robotyce , gdzie zostało nazwane mapą łąki i zostało spopularyzowane w sztucznej inteligencji gier wideo w 2000 roku.
Opis
Siatka nawigacyjna to zbiór dwuwymiarowych wypukłych wielokątów ( siatka wielokątów ), które określają, które obszary środowiska są dostępne dla agentów. Innymi słowy, postać w grze może swobodnie poruszać się po tych obszarach bez przeszkód przez drzewa, lawę lub inne bariery będące częścią otoczenia. Sąsiednie wielokąty są połączone ze sobą w grafie .
Znalezienie ścieżki w jednym z tych wielokątów można wykonać w prosty sposób w linii prostej, ponieważ wielokąt jest wypukły i można go przebyć. Znajdowanie ścieżek między wielokątami w siatce można wykonać za pomocą jednego z wielu wyszukiwania grafów , takich jak A* . Agenci w navmesh mogą w ten sposób uniknąć kosztownych obliczeniowo wykrywania kolizji z przeszkodami, które są częścią środowiska.
Przedstawienie obszarów, po których można się poruszać, w formie podobnej do 2D, upraszcza obliczenia, które w przeciwnym razie musiałyby być wykonane w „prawdziwym” środowisku 3D, jednak w przeciwieństwie do siatki 2D pozwala na obszary, po których można się poruszać, które nakładają się powyżej i poniżej na różnych wysokościach. Wielokąty o różnych rozmiarach i kształtach w siatkach nawigacyjnych mogą reprezentować dowolne środowiska z większą dokładnością niż zwykłe siatki.
kreacja
Siatki nawigacyjne można tworzyć ręcznie, automatycznie lub za pomocą kombinacji tych dwóch metod. W grach wideo projektant poziomów może ręcznie zdefiniować wielokąty navmesh w edytorze poziomów . Takie podejście może być dość pracochłonne. Alternatywnie można utworzyć aplikację, która pobiera geometrię poziomu jako dane wejściowe i automatycznie generuje navmesh.
Powszechnie przyjmuje się, że środowisko reprezentowane przez navmesh jest statyczne – nie zmienia się w czasie – dlatego navmesh może być tworzony offline i niezmienny. Jednak przeprowadzono badania dotyczące aktualizacji sieci navmesh w trybie online dla środowisk dynamicznych.
Historia
W robotyce używanie połączonych wypukłych wielokątów w ten sposób zostało nazwane „ mapowaniem łąki ”, ukutym w raporcie technicznym Ronalda C. Arkina z 1986 roku .
Siatki nawigacyjne w sztucznej inteligencji gier wideo są zwykle przypisywane artykułowi Grega Snooka z 2000 r. „Uproszczony ruch 3D i wyszukiwanie ścieżek za pomocą siatek nawigacyjnych” w Game Programming Gems . W 2001 roku JMP van Waveren opisał podobną strukturę z wypukłymi i połączonymi wielokątami 3D, nazwaną „Area Awareness System”, używaną przez boty w Quake III Arena .
Notatki
-
Arkin, Ronald C. (1986). „Planowanie ścieżki autonomicznego robota wizyjnego” (PDF) (raport techniczny). Uniwersytet Massachusetts.
{{ cite journal }}: Cite journal wymaga|journal=( pomoc ) - Marka, Sandy (2009). Skuteczne omijanie przeszkód z wykorzystaniem autonomicznie generowanych siatek nawigacyjnych (PDF) (praca magisterska). Uniwersytet Technologiczny w Delft . Źródło 2015-06-09 .
- Golodec, Stuart (październik 2013). „Automatyczne generowanie siatki nawigacji w przestrzeni konfiguracyjnej” . Przeciążenie . ACCU. 117 .
- Snook, Greg (2000). „Uproszczony ruch 3D i odnajdywanie ścieżek przy użyciu siatek nawigacyjnych” . W DeLoura, Mark (red.). Klejnoty programowania gier . Media Charlesa Rivera. s. 288–304. ISBN 1-58450-049-2 .
- Tozour, Paweł (2002). „Budowanie niemal optymalnej siatki nawigacyjnej” . W Rabin, Steve (red.). Mądrość programowania gier AI . Media Charlesa Rivera. s. 171 –185. ISBN 1-58450-077-8 .
- Van Toll, Wouter G.; Kucharz IV, Atlas F.; Geraerts, Roland (2012). „Siatka nawigacyjna dla środowisk dynamicznych” (PDF) . Animacja komputerowa i światy wirtualne . John Wiley & Synowie. 23 (6): 535–546. doi : 10.1002/cav.1468 . S2CID 2996937 . Źródło 2015-06-09 .
- van Waveren, JMP (2001-01-28). Bot Quake III Arena (PDF) (praca magisterska). Politechnika w Delft.