Navigation AI & Pathfinding

1. Overview

내비게이션 AI 및 경로 탐색(Navigation AI & Pathfinding, NAP)은 정적인 물리 지형을 에이전트가 이동 가능한 수리적 그래프로 해석하고, 시작점에서 목표점까지의 최단 물리 경로를 실시간으로 추출하는 '공간 지능 거버넌스'입니다.

학습자는 공간을 기하학적 폴리곤 묶음으로 단순화한 **내비게이션 메시(NavMesh)와, 비용 수치에 기반해 탐색 효율을 극대화하는 *A (A-star) 알고리즘을 배옵니다. 특히, 여러 에이전트가 물리적으로 충돌하지 않고 자연스럽게 이동하는 스티어링(Steering) 기술과 군집의 물리적 흐름을 제어하는 수리적 수순을 익힙니다. 이를 통해 단순히 명령을 따르는 이동을 넘어, 동적인 물리 환경 변화에 수리적으로 적응하며 목표를 완수하는 하이엔드 자율 이동 성향을 구현합니다.

2. Scope & Boundaries

In-Scope

• Spatial Representation Mechanics: Grid-based vs Mesh-based(NavMesh) 수리적 분할 대조
• Pathfinding Algorithm Calculus: A*, Dijkstra, HPA* 등 비용 함수($f = g + h$) 기반 탐색
• Steering Behavior Dynamics: 목표 추격(Seek), 회피(Flee), 무리 짓기(Flocking)의 물리 벡터 합산
• Dynamic Obstacle Avoidance: 실시간으로 나타나는 물리 장애물을 우회하는 수치 보정 기술
• Navigation Mesh Baking Logic: 3D 기하체로부터 수리적 보행 가능 영역을 추출하는 물리 수순

Out-of-Scope

• 일반적인 지도의 GPS 경로 탐색 및 서버사이드 위치 정보 시스템 (08-01-XX 영역에서 분담)
• 에이전트의 성격이나 감정을 다루는 심리적 AI 설계 (12-01-XX 혹은 인공지능 영역에서 분담)

Boundaries

• NAP vs. Classical AI: 일반 인공지능(11-01-XX)이 '추론과 학습'에 집중한다면, NAP는 '3D 시각 정보와 기하학적 제약 조건 하에서의 즉각적인 물리적 변위 산출'이라는 공간 실천성에 집중하여 구분합니다.

3. Counterexample

• 단순히 "길 찾게 만들기"라 설명하는 것은 NAP 학습이 아닙니다. 왜 경로 수치가 최단거리임에도 에이전트가 물리적 회전 반경 물리 한계를 고려하지 않아 벽에 부딪히는지 증명할 수 있어야 하며, NavMesh 수치 데이터가 너무 정밀할 때 발생하는 탐색 비용 폭증($CPU$ $Spike$)과 너무 단순할 때 발생하는 물리적 '공중 부양' 현상을 수리적으로 방어하지 못한다면 내비게이션 공학의 본질을 이해하지 못한 것입니다.

4. Prerequisites

• Data Structures & Algorithms (Basic): 04-XX-XX의 그래프 탐색(BFS/DFS) 및 우선순위 큐 이해가 필수입니다.
• Vector Mathematics (Recommended): 04-XX-XX의 벡터 합성과 물리적 방향 벡터 제어 이해가 권합됩니다.

5. Learning Map

1. Graphing the World: 무생물인 물리 도면을 이동 가능한 수리적 노드와 엣지로 변환하는 법을 배웁니다.
2. Strategic Search: 방대한 노드 중 물리적 목적지에 도달하는 가장 '저렴한' 수리 경로를 골라냅니다.
3. Physical Steering: 딱딱한 직선 경로를 부드러운 물리적 움직임(Curve)으로 수리 전이합니다.
4. Crowd Intelligence: 수천 개의 에이전트가 하나의 물리 질서를 공유하며 이동하는 하이엔드 군집 시스템을 완성합니다.

6. Learning Topics

Basic

Core: 경로 탐색과 A* 알고리즘 (Search Physics)

• Why to Learn: 목적지까지의 수리적 최단 거리를 하드웨어 부하 없이 빠르게 계산하기 위해서입니다.
• What to Learn:
  • Heuristic Math: 목적지까지의 남은 물리 거리를 추산하는 수리적 기법
  • Open/Closed Lists: 탐색 완료 및 미완료 노드의 수리적 필터링 수순
  • Path Smoothing Logic: 지그재그 경로를 물리적으로 자연스럽게 펴는 법
• How to Learn:
  • 격자형 맵($Grid$)에서 장애물을 배치하고, *A 알고리즘**이 노드를 수리적으로 확장해가는 과정을 시각화 실습
  • Manhattan vs Euclidean 휴리스틱 수치 조절에 따른 탐색 경로의 물리적 정확도 차이 대조
• Implement: 특정 그리드 정보와 목표 좌표를 받아 최단 수리 노드 리스트를 반환하는 기초 A_Star_Searcher

Recommended

Core: 내비게이션 메시와 구워내기 (NavMesh Dynamics)

• Why to Learn: 그리드 방식의 물리적 해상도 한계를 극복하고 3D 공간 전체를 수리 유기적으로 관리하기 위함입니다.
• What to Learn:
  • Walkable Area Analysis: 기하체의 경사 수치에 따른 물리적 보행 가능성 판별
  • Polygon Triangulation: 보행 구역을 최적의 수리적 폴리곤들로 분할하는 법
  • Off-mesh Links: 점프, 사다리 등 단절된 물리 구간을 수리적으로 연결하는 유닛
• How to Learn:
  • 3D 맵 하드웨어 위에서 NavMesh Baking을 수행하며, 장애물 주변의 물리적 '완충 수치($Agent$ $Radius$)'가 어떻게 수리 생성되는지 분석
  • Area Masking 수치를 적용하여 특정 구역(물속, 늪지 등)에 대한 물리적 이동 가중치를 차별화하는 훈련
• Implement: 3D 삼각형 리스트를 입력받아 보행 가능 수리 영역을 추출하는 NavMesh_Baker_Simulator

Practical

Core: 스티어링과 군집 행동 (Steering Mechanics)

• Why to Learn: 에이전트가 경로를 기계적으로 따라가는 것이 아니라, 물리적 관성과 주변 감지에 따라 유연하게 움직이게 하기 위해서입니다.
• What to Learn:
  • Steering Vectors: 원하는 방향으로의 가속도 수치와 현재 속도의 물리적 합산
  • Reynolds' Boids Physics: Separation, Alignment, Cohesion 3대 무리 물리 법칙
  • Velocity Obstacle (VO): 충돌 가능한 물리 궤적을 수리적으로 예측하여 사전에 회피
• How to Learn:
  • 100개의 파티클에 Boids 물리 법칙을 주입하고, 새 떼처럼 수리적으로 뭉치고 흩어지는 현상 관찰 실습
  • Arrival (도착 속도 감쇄) 수치를 조절하며 목표 지점에 물리적으로 부드럽게 정지하는 기법 분석 훈련
• Implement: 주변 이웃들의 물리 좌표를 기반으로 충돌 회피용 수리 벡터를 산출하는 Autonomous_Steering_Agent

Advanced

Core: 대규모 경로 가속과 군중 거버넌스 (Advanced Governance)

• Why to Learn: 수만 명의 에이전트가 있는 하이엔드 전략 게임 등에서 경로 탐색 비용을 수리적으로 압축하기 위함입니다.
• What to Learn:
  • Hierarchical Pathfinding (HPA*): 맵을 구역별로 묶어 거시적/미시적 수리 탐색 병행
  • Jump Point Search (JPS): 그리드 탐색의 물리적 불필요 노드를 수리적으로 건너뛰는 기술
  • RVO (Reciprocal Velocity Obstacles): 에이전트 간의 상호 회피를 수리적으로 보장하는 기제
• How to Learn:
  • HPA* 구조를 구축하여, 거대한 물리 맵에서의 탐색 속도가 수리적으로 얼마나 비약($N$배)하는지 입증 실습
  • Job System Analysis를 통해 수천 명의 단위($Unit$) 경로 연산을 하드웨어 코어에 물리 분산시키는 전략 프로젝트
• Implement: 다단계 수리 맵 구도를 통해 대규모 경로를 하이엔드 속도로 연산하는 Cloud_Crowd_Navigator

7. Terminology

8. References

Primary

• [P1] CS2023 - Artificial Intelligence - Search — Search foundations.
• [AI for Games, 3rd Ed] Ian Millington — The definitive guide to NAP physics.

Secondary

• [Programming Game AI by Example] Mat Buckland - Practical steering math.
• [Geometric Tools for Computer Graphics] — Foundational math for NavMesh.

Industry

• [Unity: Navigation (NavMesh) System Guide] — Practical industrial standards.
• [Unreal Engine: Recast & Detour Navigation] — High-end industrial navigation governance.

9. Final Checklist

Primary

• 'A*' 알고리즘의 수리적 비용 함수($f=g+h$)가 탐색 효율에 미치는 물리적 영향(P1)을 설명 가능한가?
• '그리드' 방식 대비 '내비게이션 메시'가 갖는 수리적 메모리 이점과 물리적 가독성을 논증할 수 있는 가? (P1)

Secondary

• '스티어링' 수순에서 '회전 물리량' 제한이 에이전트의 이동 궤적에 미치는 수리적 변화를 소통 가능한가?
• Heuristic 수치 오차가 경로 탐색 알고리즘을 어떻게 '탐욕적($Greedy$)' 혹은 '비효율적'으로 만드는지 진단할 수 있는 가?

Industry

• 실무 서비스의 성능 검수 시, 에이전트 개수 수치에 따른 Pathfinding Load 물리 병목을 수리적으로 분산 제안할 수 있는 가? (SFIA)
• Dynamic NavMesh Update 수순을 활용하여, 파괴 가능한 물리 지형에 대응하는 수리 경로 재산출 전략을 제안할 수 있는 가?