Navigationsnät
Ett navigationsnät , eller navmesh , är en abstrakt datastruktur som används i tillämpningar för artificiell intelligens för att hjälpa agenter att hitta vägar genom komplicerade utrymmen. Detta tillvägagångssätt har varit känt sedan åtminstone mitten av 1980-talet inom robotik , där det har kallats en ängskarta , och populariserades i videospel AI år 2000.
Beskrivning
Ett navigationsnät är en samling tvådimensionella konvexa polygoner (ett polygonnät ) som definierar vilka områden i en miljö som kan passeras av agenter. Med andra ord kan en karaktär i ett spel fritt gå runt inom dessa områden utan hinder av träd, lava eller andra barriärer som är en del av miljön. Intilliggande polygoner är kopplade till varandra i en graf .
Sökväg inom en av dessa polygoner kan göras trivialt i en rät linje eftersom polygonen är konvex och går igenom. Sökväg mellan polygoner i nätet kan göras med en av det stora antalet grafsökningsalgoritmer , såsom A* . Agenter på ett navmesh kan därmed undvika beräkningsdyra kollisionsdetekteringskontroller med hinder som är en del av miljön.
Att representera genomkörbara områden i en 2D-liknande form förenklar beräkningar som annars skulle behöva göras i den "äkta" 3D-miljön, men till skillnad från ett 2D-rutnät tillåter det genomkörbara områden som överlappar över och under på olika höjder. Polygonerna av olika storlekar och former i navigeringsnät kan representera godtyckliga miljöer med större noggrannhet än vanliga rutnät kan.
Skapande
Navigationsnät kan skapas manuellt, automatiskt eller genom någon kombination av de två. I videospel kan en nivådesigner manuellt definiera polygonerna för navmesh i en nivåredigerare . Detta tillvägagångssätt kan vara ganska arbetsintensivt. Alternativt kan en applikation skapas som tar nivågeometrin som indata och automatiskt matar ut ett navmesh.
Det antas vanligtvis att miljön som representeras av en navmesh är statisk – den förändras inte över tiden – och därför kan navmesh skapas offline och vara oföränderlig. Det har dock gjorts en del undersökningar av online uppdatering av navmeshes för dynamiska miljöer.
Historia
Inom robotteknik har användning av länkade konvexa polygoner på detta sätt kallats "ängsmapping", myntat i en teknisk rapport från 1986 av Ronald C. Arkin .
Navigationsnät i artificiell intelligens för videospel krediteras vanligtvis till Greg Snooks artikel från 2000 "Simplified 3D Movement and Pathfinding Using Navigation Meshes" i Game Programming Gems . År 2001 beskrev JMP van Waveren en liknande struktur med konvexa och sammankopplade 3D-polygoner, kallat "Area Awareness System", som används för bots i Quake III Arena .
Anteckningar
-
Arkin, Ronald C. (1986). "Vägplanering för en visionsbaserad autonom robot" (PDF) (Teknisk rapport). University of Massachusetts.
{{ citera journal }}: Citera journal kräver|journal=( hjälp ) - Brand, Sandy (2009). Effektivt undvikande av hinder med hjälp av autonomt genererade navigeringsnät (PDF) (Masteruppsats). Delfts tekniska universitet . Hämtad 2015-06-09 .
- Golodetz, Stuart (oktober 2013). "Automatisk generering av navigeringsnät i konfigurationsutrymmet" . Överbelastning . ACCU. 117 .
- Snook, Greg (2000). "Förenklad 3D-rörelse och vägsökning med hjälp av navigeringsnät". I DeLoura, Mark (red.). Spelprogrammeringsädelstenar . Charles River Media. s. 288–304. ISBN 1-58450-049-2 .
- Tozour, Paul (2002). "Bygga ett nästan optimalt navigeringsnät". I 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). "Ett navigationsnät för dynamiska miljöer" (PDF) . Datoranimation och virtuella världar . John Wiley & Sons. 23 (6): 535–546. doi : 10.1002/cav.1468 . S2CID 2996937 . Hämtad 2015-06-09 .
- van Waveren, JMP (2001-01-28). The Quake III Arena Bot (PDF) (M.Sc.-uppsats). Delfts tekniska universitet.