항법 메쉬

Navigation mesh

네비게이션 메쉬(Navigation mesh, navmesh)는 인공지능 어플리케이션에 사용되는 추상적인 데이터 구조로 복잡한 공간을 통한 경로 탐색에 요원들을 돕는다.이런 접근법은 적어도 1980년대 중반부터 초원지도라고 불렸던 로봇공학 분야에서 알려졌으며 2000년 비디오 게임 AI에서 대중화됐다.

설명

항법 메쉬는 2차원 볼록 폴리곤(폴리곤 메쉬)의 모음으로, 어떤 환경의 영역이 작용제에 의해 통과될 수 있는지를 정의한다.즉, 게임 속 캐릭터는 나무, 용암 또는 환경의 일부인 다른 장벽에 의해 방해받지 않고 자유롭게 돌아다닐 수 있다.인접한 다각형은 그래프로 서로 연결되어 있다.

이 다각형들 중 하나에서 길을 찾는 것은 폴리곤이 볼록하고 횡단이 가능하기 때문에 사소한 일직선으로 행해질 수 있다.메쉬 내 폴리곤 간 경로 탐색은 A*[1]와 같이 많은 수의 그래프 검색 알고리즘 중 하나로 수행할 수 있다.따라서 항법조치의 에이전트는 환경의 일부인 장애물과의 계산상 비용이 많이 드는 충돌 감지 검사를 피할 수 있다.

2D와 유사한 형태로 횡단 가능한 영역을 표현하면 "진정한" 3D 환경에서 수행되어야 할 계산을 단순화하지만, 2D 그리드와는 달리 다른 높이에서 위아래가 겹치는 횡단 가능한 영역을 허용한다.[2]항법 메쉬의 다양한 크기와 모양의 다각형은 일반 그리드보다 더 높은 정확도로 임의 환경을 나타낼 수 있다.[3]

창조

항법 메시는 수동으로, 자동으로 또는 두 개의 조합으로 만들 수 있다.비디오 게임에서 레벨 디자이너는 레벨 편집기에서 수동으로 Navmesh의 다각형을 정의할 수 있다.이 접근법은 상당히 노동 집약적일 수 있다.[4]또는 레벨 지오메스를 입력으로 사용하고 자동으로 Navmesh를 출력하는 애플리케이션을 만들 수 있다.

일반적으로 navmesh로 대표되는 환경은 정적(시간이 지남에 따라 변하지 않음)이므로 navmesh는 오프라인에서 생성되어 불변할 수 있다고 가정한다.그러나, 동적 환경을 위한 해군의 온라인 업데이트에 대한 조사가 있었다.[5]

역사

로봇공학에서, 이러한 방식으로 연결된 볼록 폴리곤을 사용하는 것은 1986년 로널드 C의 기술 보고서에서 만들어진 "midow mapping"[6]이라고 불려왔다. 아킨.[7]

비디오 게임 인공지능의 내비게이션 메시는 보통 게임프로그래밍 젬스에 실린 그렉 스누크의 2000년 기사인 "네비게이션 메스를 이용한 3D 이동과 경로 찾기"에서 기인한다.[8]2001년 J.M.P 밴 웨이브렌은 퀘이크 3 아레나에서 봇에 사용되는 "영역 인식 시스템"이라고 불리는 볼록하고 연결된 3D 다각형으로 유사한 구조를 묘사했다.[9]

메모들

  1. ^ 스누크 2000, 페이지 294–295.
  2. ^ 스누크 2000, 페이지 289.
  3. ^ 브랜드 2009, 페이지 4.
  4. ^ 브랜드 2009, 페이지 10.
  5. ^ 반 톨, 쿡 4세 & 제라츠 2012.
  6. ^ 토주르 2002, 페이지 171.
  7. ^ 아킨 1986.
  8. ^ 골로데츠 2013.
  9. ^ 반 웨이브렌 2001, 페이지 24-46.

참조

  • Arkin, Ronald C. (1986). "Path Planning for a Vision-Based Autonomous Robot" (PDF) (Technical Report). University of Massachusetts. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  • Brand, Sandy (2009). Efficient obstacle avoidance using autonomously generated navigation meshes (PDF) (Master thesis). Delft University of Technology. Retrieved 2015-06-09.
  • Golodetz, Stuart (October 2013). "Automatic Navigation Mesh Generation in Configuration Space". Overload. ACCU. 117.
  • Snook, Greg (2000). "Simplified 3D Movement and Pathfinding Using Navigation Meshes". In DeLoura, Mark (ed.). Game Programming Gems. Charles River Media. pp. 288–304. ISBN 1-58450-049-2.
  • Tozour, Paul (2002). "Building a Near-Optimal Navigation Mesh". In Rabin, Steve (ed.). AI Game Programming Wisdom. Charles River Media. pp. 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. S2CID 2996937. Retrieved 2015-06-09.
  • van Waveren, J.M.P. (2001-01-28). The Quake III Arena Bot (PDF) (M.Sc. thesis). Delft University of Technology.

외부 링크