[NDC 2016] 구형맵에서는 어떻게 길을 찾아야 하나요?

---

Recast: 언리얼 엔진에서 내비게이션 메시로 사용하고 있는 오픈 소스 라이브러리

장점

- 메시 빌드 속도

- 길찾기 속도

- 유연한 셋팅

단점

- 근시로 인한 오차

- 에이전트 검색 속도

- 난해한 셋팅

 

라이브러리 디렉토리 구성

Detour: Recast로 생성된 메시에서 길을 찾아주는 라이브러리

DetourCrowd: 에이전트들간의 충돌 회피를 하는 알고리즘

DetourTileCache: 동적 메시 생성을 위한 라이브러리

Recast: 내비게이션 메시를 생성하는 부분

RecastDemo: 비주얼라이제이션을 포함한 툴

 

 

 

Recast 내비게이션 메시는 여러 개의 폴리곤들과 그 폴리곤들 사이의 연결 정보로 구성되어 있음

 

1. 길을 찾을 때 폴리곤의 각 변의 중점을 따라 길을 찾음

2. 찾은 길의 폴리곤을 따라서 길을 똑바르게 편다

 

 

Recast에서 내비게이션 메시를 생성하는 방법

1. Rasterization: 주어진 맵의 폴리곤 정보를 분석해서 복셀로 만듦

2. Find Walkable: 복셀상에서 걸어다닐 수 있는 셀들을 찾음

3. Erode: 가장자리여서 갈 수 없는 셀들을 캐릭터의 반지름만큼 깎아냄

4. Build Region: 하나의 폐곡선으로 둘러쌀 수 있게 영역을 구분

5. Make Contour: 각각의 영역을 둘러싸는 폐곡선을 만듦

6. Make Polygon: 폐곡선을 적절하게 잘라서 볼록다각형으로 만듦

 

 

타일링을 통한 메시

그렇다면 실시간을 바뀌는 내비게이션 메시는 어떻게 처리해야 할까?

=> 재빌드를 하되, 내비게이션 메시를 타일 단위로 잘라서 한 번에 리빌드 하는 양을 줄이고, 다시 빌드하지 않아도 되는 부분을 미리 계산해서 저장해 둠(DetourTileCache)

 

타일링을 쓸 경우 본래 없어도 될 정점이 생기게 되면서 오탐색의 가능성이 높아짐

=> 이 문제는 경로 탐색 후 레이캐스팅을 통해 한번 더 검증해서 해결

 

 

구면 기하학

구면에서의 좌표는 일반적인 3차원 공간과 마찬가지로 (x,y,z) 벡터를 (크기는 무시하고 방향만) 사용.

구면상에서 직선은 두 점 사이의 최단 거리 (= 두 점을 포함한 대원의 일부)

 

원점을 지나는 평면이기 때문에 노멀 벡터로도 나타낼 수 있다

 

구면 상에서 두 점간의 거리는 두 지점 사이의 각으로 정의 된다.

단 이렇게 되면 높이에 따라 유닛의 이동 속도가 달라지는 문제가 생긴다.

 

 

 

구면에서 Recast를 적용하려면 구면을 격자로 쪼개야 한다

=> 정육면체를 구면으로 사영하는 쿼드 스피어 방식을 사용

 

---

출처: http://ndcreplay.nexon.com/NDC2016/sessions/NDC2016_0073.html