내비게이션 메시

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