기술 요약: 동적 게임 환경에서의 확장 가능한 내비게이션을 위한 멀티스레드 Recast 기반 A* 경로 탐색

문제 정의

A* 알고리즘은 휴리스틱 기반 경로 탐색의 업계 표준으로 남아 있으나, 고충실도(high-fidelity)의 동적 3D 게임 환경에 직접 적용할 경우 두 가지 주요 한계에 직면한다:

1. 계산적 확장성: 노드 수가 증가함에 따라 경로 재계산에 필요한 메모리 오버헤드와 CPU 사이클이 증가하여, 소비자용 하드웨어에서 프레임 레이트 저하를 유발하는 병목 현상이 발생한다.
2. 움직임의 충실도: 표준 A*는 각진 전환을 포함하는 조각별 선형 궤적(piecewise linear trajectories)을 출력하므로 인간과 같은 유연한 움직임이 부족하다. 또한, 매 프레임마다 발생하는 값비싼 충돌 감지 비용 없이 고밀도 에이전트 클러스터를 조정하는 것은 실시간 시스템에서 여전히 큰 과제로 남아 있다.

방법론

저자들은 견고한 탐색 공간 추상화와 비동기 처리를 합성하기 위해 설계된 다각적인 프레임워크를 제안한다. 시스템 아키텍처는 네 가지 핵심 구성 요소로 통합된다:

1. 탐색 공간 추상화 (Recast Graphs)

단순한 그리드나 수동으로 배치된 웨이포인트 대신, 본 프레임워크는 절차적 NavMesh 생성을 위해 Recast Graphs를 활용한다.

• 생성: 원시 3D 기하 구조를 복셀화(voxelized)하고 분할하여 내비게이션 표면 생성을 자동화한다.
• 노멀 재계산: 표면 노멀(normal)을 재계산하여 일관된 상향 방향성을 보장함으로써 벽, 천장, 구형 표면과 같은 복잡한 지형 구조 전반의 연결성을 확보한다.
• 동적 업데이트: 헬퍼 클래스가 엣지(edge) 수정을 추적하여, 응답성과 계산 오버헤드 사이의 균형을 맞출 수 있도록 구성 가능한 업데이트 빈도를 제공한다.

2. 멀티스레드 A* 연산

메인 렌더링 루프로부터 경로 탐색을 분리하기 위해, 시스템은 **스레드 풀 아키텍처(Thread Pool Architecture)**를 채택한다.

• 실행 모델: 경로 탐색 계산은 동적 스레드 풀로 오프로드된다. 시스템은 가용 코어 및 메모리에 따라 스레드 수를 자동으로 조정하며, 저사양 하드웨어(싱글 코어 또는 RAM 512MB 미만)에서는 동기식 실행으로 복귀한다.
• 작업 큐 관리: 세 가지 메커니즘이 동기화를 조정한다:
  • 그래프 업데이트 플러시(Flush Graph Updates): 그래프 변경 사항을 적용하기 전에 스레드를 일시 중지하여 계산을 완료한다.
  • 작업 항목 플러시(Flush Work Items): 대기 중인 작업 항목을 즉시 적용한다.
  • 그래프 업데이트 큐 삽에(Queue Graph Updates): 중복 콜백을 방지하면서 안전한 실행을 위해 업데이트를 예약한다.

3. 궤적 최적화 파이프라인

원시 A* 출력값은 자연스러운 움직임을 구현하기 위해 다음과 같은 후처리 파이프라인을 거친다:

• 퍼널 알고리즘(Funnel Algorithm): 폴리곤 코리더(polygon corridors)를 통과하는 최단 경로를 계산하여 불필요한 웨이포인트를 제거하고 장애물 경계를 준수함으로써 경로를 단순화한다.
• 베지에 곡선 보간(Bezier Curve Interpolation): 이산적인 웨이포인트를 2차 베지에 보간을 사용하여 $C^1$ 연속 곡선으로 변환한다. 이를 통해 코너를 깎지 않고도 부드러운 전환을 보장하며, 시각적 부드러움과 계산 비용 사이의 균형을 맞추기 위해 구성 가능한 품질 설정을 제공한다.
• 레이캐스트 검증(Raycast Validation): 물리 레이캐스트를 통해 노드 제거 시 단순화된 경로가 충돌체와 교차하지 않는지 검증한다.

4. 밀도 분석을 통한 군집 조정

본 프레임워크는 로컬 충돌 회피(고밀도에서 불안정할 수 있음)에만 의존하지 않고, 글로벌 밀도 분석을 구현하여 다중 에이전트 내비게이션을 관리한다.

• 밀도 감지: 에이전트는 설정된 반경 내의 밀도를 감지한다. 예측 위치(예: 10개 노드 앞)의 밀도가 임계값을 초과하면, 대체 경로를 찾기 위한 경로 재계산이 트리거된다.
• 피벗 포인트 교정: 다층 환경에서 정확한 바닥 선택을 보장하기 위해 캐릭터 중심이 아닌 모델의 발 또는 바퀴 위치를 기준으로 경로 요청을 계산한다.
• 경로 선택: 새로운 경로는 현재 비용과 비교되며, 더 낮은 비용의 경로가 즉시 현재 내비게이션을 대체한다.

주요 기여

본 논문은 세 가지 주요 기여를 명시한다:

1. 지형적 추상화: Recast 그래프를 사용하여 3D 공간에서의 보행 가능한 경사도와 등반 높이를 정확하게 모델링하면서 탐색 공간 복잡도를 줄인다.
2. 궤적 최적화: 퍼널 알고리즘과 베지에 곡선 보간을 결합하여 이산적인 웨이포인트를 유연하고 연속적인 궤적으로 변환하는 파이프라인을 제공한다.
3. 비동기 멀티스레드 아키텍처: 밀도 분석과 결មាន된 동적 스레드 풀을 활용하여, 군집 관리를 위해 확장 가능한 디커플링된 실행 모델을 제공한다.

실험 결과

본 프레임워크는 기초적인 2D 미로부터 복잡한 다층 동적 세계에 이르기까지 10단계의 실험 연구를 통해 검증되었다.

• 성능 지표:
  • 단일 에이전트: 1.2ms의 CPU 메인 스레드 시간과 함께 835.2 FPS 달성.
  • 다중 에이전트 (25 NPC): 2.5ms의 CPU 시간과 함께 407.2 FPS 유지.
  • 고밀도 확장성: 1,000개의 동시 에이전트 상황에서도 350+ FPS를 유지.
  • 비교: 싱글 스레드 베이스라인은 200명의 에이전트에서 20 FPS 미만으로 저하된 반면, 제안된 멀티스레드 아키텍처는 과부하 상황에서도 90 FPS 이상을 유지하여 약 4.5배의 성능 향상을 나타냈다.
• 경로 계산:
  • 단순 2D 시나리오에서 서브 밀리초(0.00ms) 계산 달성.
  • 수천 개의 노드(5,328개)가 있는 복잡한 3D 환경에서 9ms 미만으로 완료.
  • 대규모 오픈 월드(6,484개 노드)는 12.96ms 내에 완료되어, 60 FPS 게임플레이를 위한 16.67ms 프레임 예산 범위 내에 머물렀다.
• 군집 시나리오: 최대 100명의 에이전트가 참여하는 세 가지 특정 밀도 시나리오(수렴, 대치 그룹, 클러스터 횡단)에서 매 프레임 충돌 해결 오버헤드 없이 충돌 없는 내비게이션을 입증했다.

의의 및 한계

본 논문은 제안된 프레임워크가 동적 게임 환경에서 계산 성능과 시각적 사실주의 사이의 트레이드오프를 성공적으로 해결했음을 주장한다. 경로 탐색을 메인 스레드에서 분리하고 Recast 기반 추상화를 활용함으로써, 시스템은 높은 에이전트 수에서도 플레이 가능한 프레임 레이트를 유지한다. 연구는 간헐적인 경로 재계산이 프레임 단위 업데이트보다 우수하며, 베지에 보간이 최소한의 오버헤드로 움직임의 자연스러움을 크게 개선함을 확인한다.

한계:
저자들은 에이전트 속도와 충돌 회피 정확도 사이에 역관계가 있음을 솔직하게 언급했다. 또한 향-후 연구 방향으로 동적 캐릭터 AI를 위한 행동 트리(Behavioral Trees)의 통합, 대규모 교통 시뮬레이션을 위한 최적화, 그리고 항공 이동체를 위한 볼륨릭(volumetric) 3D 경로 탐색 개발을 제시하였다.