[Unity] Navigation mesh

1. Navigation and Pathfinding

• 내비게이션 시스템은 Scene geometry에서 자동으로 생성되는 내비게이션 메시를 사용하여 게임 월드에서 지능을 갖고 움직일 수 있는 캐릭터를 생성하는 데 도움을 줍니다. 역동적인 장애물은 런타임 시점에 캐릭터의 내비게이션을 바꾸도록 하며 off-mesh 링크는 문을 열거나 절벽 같은 지형에서 뛰어내릴 수 있도록 특정한 액션을 빌드한다.

2. 내비게이션 영역 및 비용

• Navigation Areas는 특정 영역을 걸어서 지나가는데 드는 비용(cost)을 뜻하며, 경로를 탐색할 때에는 낮은 비용 영역순으로 선택됨. 또한 각각의 navmesh agent에는 Area Mask가 있어 에이전트가 이동할 수 있는 영역을 지정할 수 있다.

• Water : 높은 비용이 할당되어 있어 걸어가는데 더 많은 비용이 소요됨. 이를 통해 물이 얕은 곳을 느리게 걸어가는 시나리오를 처리할 수 있다.
• Door : 특정 캐릭터만 접근할 수 있다. 이를 통해 사람은 통과할 수 있지만 좀비는 통과할 수 없는 시나리오를 처리할 수 있다.

3. 경로 탐색 비용

• 비용을 조절하여 경로 탐색자가 경로를 탐색할 때 선호하는 영역을 제어할 수 있다.
  • ex) 영역의 비용을 3.0으로 설정하면 해당 영역을 지나가기 위해서는 다른 경로로 지나갈 때보다 3배의 시간이 걸린다.

• Unity는 A* 를 사용하여 nav mesh에서 최단 경로를 계산한다.

• A* 는 연결된 노드 그래프에서 작동한다.

• Unity 내비게이션은 폴리곤 메시로 나타내기 때문에 경로 탐색자는 우선 각 폴리곤에 노드의 위치가 되는 포인트를 배치해야한다. 최단 경로는 이 노드들 사이에서 계산된다.

• 어떤 레벨에서 경로 탐색자는 항상 최단 경로를 선택하지 않는다는 점도 알아두어야 한다. 이는 노드 배치 때문이다. 작은 장애물 옆에 큰 열린 영역이 있을 때, 즉 내비게이션 메시에 아주 큰 폴리곤과 아주 작은 폴리곤이 포함될 때 이런 현상을 쉽게 볼 수 있다. 큰 폴리곤의 노드는 해당 폴리곤의 아무 곳에나 배치될 수 있는데, 경로 탐색자의 관점에서 볼 때 이것이 우회 경로로 보일 수 있다.

4. 내비게이션 시스템

• NavMesh
  : 내비게이션 메시의 줄임말로, 게임 월드에서 걸을 수 있는 표면을 뜻하며, 내비 메시를 사용하여 게임 월드 안에 움직일 수 있는 한 위치에서 다른 위치로 이동할 수 있는 경로를 찾을 수 있다. 데이터 구조는 level geometry에서 자동으로 빌드 또는 베이크 된다.

• NavMesh Agent
  : 컴포넌트를 사용하여 각자의 목적지를 이동하는 동안 서로를 피할 수 있는 캐릭터를 생성할 수 있다. 에이전트는 내비메시를 사용하여 게임 월드를 추론하며, 움직이는 장애물 뿐만 아니라 서로를 피하는 방법을 알게 된다.

• Off-Mesh Link
  : 컴포넌트를 사용하여 걸을 수 있는 표면만으로는 정의할 수 없는 내비게이션 단축키를 통합할 수 있다. 예를 들어 배수로나 울타리를 뛰어넘거나 문을 지나가기 전에 여는 행동 등은 모두 오프 메시 링크로 정의할 수 있다.

  • 
  • 

• NavMesh Obstacle
  : 컴포넌트를 사용하여 에이전트가 월드를 탐색하는 동안 회피해야 하는 움직이는 장애물을 정의할 수 있다. 이에 대한 예로는 물리 시스템이 제어하는 통이나 상자를 들 수 있다. 움직이는 장애물이라면 에이전트가 이를 피하도록 하고, 장애물이 정지한 경우 내비메시에 구멍을 carving하여 에이전트가 장애물을 돌아가도록 경로를 변경하거나, 정지한 장애물이 경로를 완전히 차단할 경우 에이전트가 다른 경로를 찾게 할 수 있다.

5. 내비게이션 시스템의 내부 작업

• 게임에서 캐릭터(agent)를 지능적으로 움직이려면 목적지를 찾기 위해 필요한 레벨 추론과 목적지까지 이동하는 방법이라는 두가지 문제를 해결해야함.

• 레벨을 추론하는 문제는 Scene 전체를 고려해야 한다는 점에서 훨씬 전역적이고 정적이다. 목적지까지의 이동은 지역적이고 동적이며, 이동하는 방향과 이동중인 다른 에이전트와의 충돌을 방지하는 방법에 대해서만 고려하면 된다.

걸을 수 있는 영역

• 게임 Scene에서 걸을 수 있는 영역을 나타내기 위해 내비게이션 시스템은 자체적인 데이터가 필요하다. 걸을 수 있는 영역은 씬에서 에이전트가 서거나 움직일 수 있는 장소를 정의한다.

• 걸을 수 있는 영역은 Scene의 geometry에서 에이전트가 설 수 있는 위치를 테스트하여 자동으로 빌드된다. 그런 다음 이러한 위치가 Scene geometry의 맨 위에 위치한 표면에 연결된다.

• nav mesh는 이 표면을 Convex 폴리곤으로 저장한다. Convex 폴리곤은 폴리곤 안의 두 지점 사이에 아무런 장애물이 없기 때문에 이러한 목적으로 유용하게 사용된다. 폴리곤의 경계를 비롯하여 서로 이웃한 폴리곤에 대한 정보도 저장한다. 이렇게 하면 걸을 수 있는 모든 영역을 추론할 수 있다.

경로 찾기

• Scene에서 두 위치 사이의 경로를 찾기 위해서는 먼저 시작 위치와 목적지 위치를 가장 가까운 폴리곤에 매핑해야 한다.

• 시작 위치에서 탐색을 시작하여 모든 이웃 폴리곤을 거쳐 목적지 폴리곤에 도달한다. 이동 중에 방문한 모든 폴리곤의 경로를 추적하여 시작에서 목적지까지 연결해주는 폴리곤의 시퀀스를 찾을 수 있다. -> A* 알고리즘 사용

장애물 회피

• Steering logic은 통로 선상에 있는 다음 코너의 포지션을 파악하고, 이에 기반하여 목적지에 도달하기 위한 원하는 방향과 속도를 계산한다. 원하는 속도를 사용하여 에이전트를 움직일 때 다른 에이전트와의 충돌이 발생할 수 있다.

  • Steering logic은 제어 신호의 설정에 따라 데이터 입력을 출력으로 라우팅하는 회로

• 장애물 회피는 원하는 방향으로 나아가되 다른 에이전트 및 내비게이션 메시의 가장자리와 충돌하지 않게 적절한 균형점을 찾아 새로운 속도를 선택한다. Unity는 상호간 속도 장애물(RVO)을 사용하여 충돌을 예견하고 방지한다.

글로벌 및 로컬

• 글로벌 내비게이션은 월드에서 통로를 찾는데 사용된다. 월드에서 경로를 탐색하려면 상당한 프로세싱 능력과 메모리가 필요하다.

• 경로를 정의하는 폴리곤의 linear list는 스티어링을 위한 유연한 데이터 구조이며, 에이전트의 포지션이 움직임에 따라 로컬하게 조정될 수 있다.

• 로컬 내비게이션은 다른 에이전트나 움직이는 오브젝트와 충돌없이 어떻게 효율적으로 다음 코너를 향해 나아갈 수 있는지를 결정한다.

장애물의 두가지 사례

• 내비게이션에는 다른 에이전트보다 다른 타입의 장애물이 많이 응용된다.

• 움직이는 장애물이라면 로컬 장애물 회피를 사용하는 것이 좋다. 이 경우 에이전트가 장애물을 예측하며 회피한다.

• 정지해 있을 수 있고 모든 에이전트의 경로를 차단하는 장애물이라면 글로벌 내비게이션인 내비게이션 메시에 영향을 주어야한다.

• 내비메시를 변경하는 것을 carving 이라고 한다. 이 프로세스는 장애물의 어떤 부분이 내비메시에 닿는지를 감지한 다음, 내비메시에서 해당 부분을 깎아내어 구멍을 만든다. 이를 계산할 때 매우 많은 비용이 소모되기 때문에 움직이는 장애물은 충돌 회피를 통해 처리하는 이유이기도 하다.

• 로컬 충돌 회피는 종종 흩어진 장애물을 피하는데 사용되기도 한다. 알고리즘이 로컬이므로 바로 직면한 충돌만 회피할 수 있으며 함정을 피하거나 장애물이 경로를 차단하는 경우를 처리할 수 없다. 이러한 경우는 카빙을 통해 처리할 수 있다.

출처 : https://docs.unity3d.com/kr/2021.3/Manual/nav-InnerWorkings.html

https://docs.unity3d.com/kr/current/Manual/nav-NavigationSystem.html

https://docs.unity3d.com/kr/530/Manual/class-OffMeshLink.html