내비게이션 메시

1. 개요[편집]

내비게이션 메시 Navigation Mesh (Navmesh)
분야	게임 AI × 계산기하
표현	보행 가능 영역의 볼록 다각형 분할
생성	복셀화 기반 자동 생성 (Recast 계열)
탐색	다각형 그래프 A* + 스트링 풀링
대안	웨이포인트 그래프

NPC가 벽에 얼굴을 문지르고 있다면, 십중팔구 내비메시가 거기서 끊겨 있다.

내비게이션 메시(navigation mesh, 줄여서 내비메시)는 게임 월드에서 캐릭터가 걸어 다닐 수 있는 표면을 볼록 다각형의 집합으로 분할해 놓은 자료구조다. 핵심 성질은 단 하나에서 나온다. 볼록 다각형 내부의 두 점은 언제나 직선으로 이을 수 있다는 것. 따라서 길찾기는 “어느 다각형들을 거칠 것인가”라는 이산 그래프 문제로 축소되고, 다각형 내부의 이동은 그냥 직진하면 된다.

이 단순한 통찰 덕분에 내비메시는 3D 게임 길찾기의 사실상 표준이 되었다. 상용 엔진은 물론 오픈소스 진영에서도 Recast/Detour(미코 모노넨 작)가 사실상의 레퍼런스 구현으로 통한다.¹

2. 웨이포인트 그래프와의 대비[편집]

내비메시 이전의 국룰은 웨이포인트 그래프였다. 레벨 디자이너가 통로마다 점을 찍고 선으로 이으면, AI는 그 점들을 따라 다닌다.

항목	웨이포인트 그래프	내비게이션 메시
표현하는 것	선(경로)	면(영역)
제작	대개 수작업	형상에서 자동 생성
이동 자유도	레일 위에만	다각형 어디든
지역 회피	어렵다	자연스럽다
폭 정보	없음	다각형 자체가 폭
메모리	작다	상대적으로 크다

웨이포인트의 결정적 약점은 점과 점 사이의 공간을 모른다는 것이다. 넓은 광장을 대각선으로 가로지르면 될 것을 굳이 점을 따라 ㄱ자로 돌아가고, 옆에서 다른 NPC가 오면 비켜설 여유 공간이 있는지조차 판단할 수 없다. 반면 내비메시는 면을 알기 때문에 “여기서 저기까지 직선으로 갈 수 있나?”라는 질의(navmesh raycast)에 즉답하고, 몸집이 다른 에이전트나 군중 시뮬레이션의 지역 회피와도 궁합이 맞는다.

3. 자동 생성 파이프라인[편집]

내비메시를 손으로 그리는 시대는 지났다. Recast 계열의 생성 과정은 대략 이렇다. 핵심 발상은 복잡한 삼각형 수프를 일단 복셀로 뭉갠 뒤 다시 다각형으로 복원하는 것.²

1. 복셀화 — 레벨의 충돌 형상을 격자에 래스터화해 높이장(heightfield)을 만든다. 여기서 원본 형상의 지저분한 위상(뒤집힌 법선, T-정션, 겹친 삼각형)이 통째로 세탁된다. 이 “일단 부수고 다시 만든다”는 태도는 마칭 큐브의 문제의식과 닮았다.
2. 보행 가능성 필터 — 복셀 스팬마다 판정한다. 경사가 한계각(예: 45°)보다 급하면 탈락. 위쪽으로 에이전트 키($h$)만큼 공간이 없으면 탈락. 인접 스팬과의 단차가 오를 수 있는 높이($c$)를 넘으면 탈락, 낭떠러지 가장자리도 제거.
3. 침식 — 에이전트 반지름 $r$만큼 벽에서 안쪽으로 깎는다. 이렇게 해두면 런타임에 에이전트를 점으로 취급해도 몸이 벽에 박히지 않는다. 고체역학이 아니라 계산기하의 민코프스키 축소를 격자로 흉내 낸 것.
4. 영역 분할 — 남은 보행 가능 셀을 거리장 기반 분수령(watershed) 등으로 덩어리로 나눈다.
5. 윤곽 추출과 단순화 — 각 영역의 테두리를 따라가며 계단 모양 픽셀 윤곽을 뽑고, 편차 허용치 안에서 정점을 솎아낸다.
6. 다각형화 — 단순화된 윤곽을 볼록 다각형으로 분할하고, 인접한 것들을 가능한 한 병합해 개수를 줄인다.
7. 디테일 메시 — 다각형은 평평하지만 실제 지형은 울퉁불퉁하므로, 높이 정확도 복원용 삼각형 층을 따로 붙인다.

파이프라인 입력에서 에이전트 반지름·키·오를 수 있는 높이·최대 경사 네 개가 사실상 모든 것을 결정한다. 덩치가 다른 몬스터를 여럿 쓰려면 원칙적으로 내비메시를 그만큼 따로 굽는다.

계산기하 쪽에서는 들로네 삼각분할이나 보로노이 다이어그램의 중심축(medial axis)으로 내비메시를 정확히 구성하는 접근도 오래 연구되었다. 이론적으로는 더 깔끔하지만, 실제 게임 레벨의 형상이 워낙 더러워서 강건성 면에서 복셀화 방식이 이겼다.

4. 경로 탐색과 스트링 풀링[편집]

내비메시가 준비되면 런타임은 두 단계다.

1단계: 그래프 A* 탐색. 다각형을 노드로, 공유 변(portal)을 간선으로 삼아 A*를 돌린다. 비용은 보통 다각형 중심 간 거리, 휴리스틱은 목표까지의 유클리드 거리다. 유클리드 거리는 실제 경로 길이를 절대 넘지 않으므로 허용 가능(admissible)하며, A*의 최적성이 보장된다. 결과는 하나의 경로가 아니라 다각형의 띠, 즉 코리도(corridor)다. 지역 비용(물은 4배, 진창은 3배)이나 플래그(문 열기 능력 필요)를 다각형에 붙여 필터링하는 것도 이 단계다.

2단계: 스트링 풀링(퍼널 알고리즘). 코리도 안에서 최단 경로를 뽑는다. 이름 그대로 다각형의 띠 속에 실을 꿴 뒤 양쪽을 팽팽히 당기는 것이다. 이걸 안 하고 다각형 중심을 이으면 NPC가 격자무늬로 지그재그를 그리게 된다.

퍼널 알고리즘은 정점(apex)과 좌·우 두 개의 포탈 점으로 이루어진 삼각형을 유지하며 포탈을 하나씩 훑는다. 판정은 2D 외적 부호 하나로 끝난다.

$$\text{tri}(\mathbf{a}, \mathbf{b}, \mathbf{c}) = (\mathbf{b}-\mathbf{a}) \times (\mathbf{c}-\mathbf{a})$$

새 포탈 점이 퍼널을 좁히면 갱신하고, 반대편 변을 넘어서면 그 반대편 점이 진짜 코너라는 뜻이므로 경로에 추가하고 정점을 그 코너로 옮긴 뒤 다시 시작한다. 각 포탈을 상수 번만 보므로 복잡도는 코리도 길이에 선형이다.³ 코드가 40줄 남짓인데 이름이 “Simple Stupid Funnel Algorithm”인 데는 이유가 있다.

5. 오프메시 링크와 동적 갱신[편집]

오프메시 링크(off-mesh link)는 걸어서 갈 수 없는 두 지점을 명시적으로 잇는 간선이다. 절벽에서 뛰어내리기, 난간 넘기, 사다리, 순간이동 포탈이 전부 여기에 해당한다. 그래프 탐색은 이 간선을 그냥 비용 있는 연결로 취급하고, 실제 이동은 링크에 붙은 애니메이션·물리 엔진 동작이 대신 처리한다. 즉 길찾기는 “갈 수 있다”만 알고, “어떻게 가는지”는 행동 트리와 애니메이션의 소관이라는 역할 분담이다.

레벨이 바뀌면(문이 닫히고, 다리가 무너지고, 플레이어가 건물을 짓고) 내비메시도 따라 바뀌어야 한다. 통짜로 다시 굽는 것은 수 초가 걸리므로 프레임 예산에 들어갈 리가 없다. 그래서 실무는 타일 단위로 간다.

• 타일 내비메시 — 월드를 격자 타일로 나눠 각각 독립적으로 굽고, 타일 경계에서 이어 붙인다. 형상이 바뀐 타일만 다시 구우면 되므로 비용이 국소화된다. 공간 분할 자료구조의 사고방식이 그대로 적용된 것.
• 임시 장애물(temporary obstacle) — 원기둥·상자 하나 놓자고 타일을 다시 굽는 것도 아까울 때, 압축된 타일 중간 데이터를 캐시해 두고 장애물만 래스터화해 덧씌운 뒤 다각형화만 다시 한다. Detour의 타일 캐시가 이 방식.
• 비동기 리빌드 — 굽는 작업은 워커 스레드로 빼고, 완성된 타일만 메인 스레드에서 원자적으로 교체한다.

주의할 것은 다른 에이전트는 내비메시에 반영하지 않는다는 원칙이다. NPC 하나 움직일 때마다 내비메시를 다시 구울 수는 없으므로, 에이전트 간 회피는 RVO/ORCA 같은 지역 회피 층이 충돌 감지 수준에서 따로 담당한다. 정적 세계는 내비메시, 동적 이웃은 스티어링 — 이 계층 분리가 현대 게임 AI의 기본 골격이다.

6. 현업에서의 현실[편집]

• 아티스트가 난간 하나를 5 cm 옮기면 내비메시가 끊긴다. 그리고 그건 QA가 발견한다.
• 에이전트 반지름을 너무 작게 잡으면 좁은 틈으로 경로가 생기고, NPC는 그 틈에 어깨를 끼운 채 열심히 앞으로 걷는다.
• 계단은 영원한 숙적이다. 경사로 처리하자니 단차가 크고, 단차로 처리하자니 오를 수 있는 높이 설정과 싸운다.
• 내비메시 위에 있는지(isOnNavmesh) 확인 없이 좌표를 던지면, 가장 가까운 다각형을 찾다가 엉뚱한 층의 바닥에 붙는다. 멀티플로어 레벨의 단골 버그.
• 그럼에도 웨이포인트 시절로 돌아가자는 사람은 없다. 디자이너에게 점 찍기를 시키는 것보다 파라미터 네 개를 튜닝하는 편이 싸다.⁴

7. 관련 문서[편집]

• 공간 분할 자료구조 · 경계 볼륨 계층
• 들로네 삼각분할 · 보로노이 다이어그램
• 충돌 감지 · 물리 엔진
• 마칭 큐브 · 메시 생성
• 역운동학 · 파티클 시스템

8. Footnotes[편집]

1. Recast가 굽고(builder), Detour가 런타임 질의(A*, 스트링 풀링, 크라우드)를 담당하는 2인조 구성이다. zlib 라이선스라 상업 게임에 그냥 넣을 수 있어서, 이 바닥에서 “내비메시를 처음부터 짠다”는 말은 보통 취미이거나 면접 과제다. ↩

2. 이 발상의 미덕은 강건성이다. 레벨 형상이 위상적으로 아무리 엉망이어도 복셀 격자는 불평하지 않는다. 대신 격자 해상도(cell size)보다 얇은 것은 통째로 사라지므로, 난간이 증발했다면 셀 크기를 의심하라. ↩

3. 코리도 밖으로 나가지 않는다는 제약 하의 최단 경로라는 점에 주의. 코리도 자체가 최단 다각형 열이 아니었다면 최종 경로도 전역 최단은 아니다. 다각형 중심 거리로 A*를 돌린 이상 이건 근사다. ↩

4. 물론 그 파라미터 네 개를 튜닝하다가 하루가 사라지는 것은 별개의 문제다. 셀 크기를 절반으로 줄이면 품질이 좋아지지만 굽는 시간은 대략 네 배가 되고, 메모리도 같이 따라온다. ↩