1. 내비게이션 그래프 구축
    1. 타일 기반
      1. 각 셀에 특정 지형 타입을 지정하므로, 그에 맞게 그래프의 에지에 가중치 부여
      2. 단점
        1. 탐색 공간이 아주 커짐
    2. 가시점(Point Of Visibillity, POV)
      1. 각각의 노드가 적어도 하나의 노드와 연결되도록 수작업으로 위치시킴
      2. 장점
        1. 연결 데이터 위로 정보를 제공하는 노드들을 포함하도록 쉽게 확장할 수 있다
      3. 단점
        1. 맵이 크고 복잡할수록 시간이 오래 걸림
        2. 모든 타입의 맵 생성 특징을 포함하는 계획에는 부적합
    3. 확장 지형
      1. POV 그래프를 자동으로 생성시키기 위해 모양에 담긴 정보 사용
      2. 순서
        1. 다각형 확장
          1. 확장 지형의 꼭지점이 노드로 추가됨
          2. 노드간의 연결을 위한 알고리즘 실행
          3. 에지가 적절하게 추가됨
    4. NavMesh
      1. 다각형의 모든 점에서 다른 점까지 방해받지 않고 진행
      2. 각각의 노드가 볼록 공간을 표현하는 그래프를 사용해서 하나의 환경 표현
      3. 장점
        1. 자료구조가 컴팩트, 빠른 탐색
        2. 환경은 다각형으로 구축됨
        3. 지역을 자동으로 나눌 수 있음
  2. Raven 내비게이션 그래프
    1. 성기게 과립화된 그래프
      1. 에이전트가 목표에 도달할 때까지 두 번이나 물러서야 함
      2. 그래프의 어떤 노드에서도 시선이 닿지 않는 위치가 존재
      3. 유연화 알고리즘(path smoothing algorithm) 사용
    2. 정교하게 과립화된 그래프
      1. 과립화를 증가시킴으로써 잘못된 경로와 접근할 수 없는 위치 문제 해결
      2. 밀물 채우기 알고리즘(flood fill algorithm)을 사용해 자동화
    3. Raven 내비게이션 그래프에 아이템 추가하기
      1. 아이템은 내비게이션 그래프에 노드로 추가됨
      2. AI가 아이템을 찾아서 경로를 계획할 수도 있다
      3. 동일 아이템에 대해 여러 인스턴스가 있으면 navgraph 최소 비용 검사 후 결정
      4. NavGraphZNode : GraphNode
        1. extra_info m_ExtraInfo
          1. 아이템 타입 등 추가 정보
          2. 짝지워진 아이템에 대한 포인터
    4. 접근 질의의 속도를 향상시키기 위해서 공간 분할 사용하기
      1. 공간 분할 기법 사용시
        1. O(n^2) -> O(d)
  3. 경로 계획자 클래스 만들기
    1. Raven_PathPlanner
      1. 경로 게획 객체가 제공해야만 하는 최소한의 기능
        1. 현재 위치로부터 모든 다른 곳까지의 경로 계획
        2. 현재 위치와 특정 아이템 타입 간의 최소 비용 경로 계획
    2. 특정 위치까지의 경로 계획하기
      1. CreatePathToPosition(Vector2D TargetPos, std::list<Vector2D>& path)
        1. 1. bot의 현재 위치에서 가장 가까우면서 장애물에 방해받지 않는 가시의 그래프 노드를 찾는다.
        2. 2. 목표 위치까지의 가장 가까우면서 장애물에 방해받지 않는 가시의 그래프 노드를 찾는다.
        3. 3. 둘 사이의 최소 비용 경로를 찾아내는 탐색 알고리즘을 사용한다.
    3. 어떤 아이템 타입까지의 경로 계획하기
      1. 특정 타입의 인스턴스가 많은 아이템 타입에 요구되는 최소 비용 경로를 찾는 경우
        1. A*
          1. 해당 아이템 인스턴스가 선택되기 전에 각각의 인스턴스에 대한 탐색이 모두 끝난 상태여야 한다.
        2. difkstra
          1. 목표 아이템을 찾을 때까지 최단경로트리(SPT)를 성장시킨다.
          2. 찾고자 하는 아이템이 발견되자마자, 알고리즘은 종료됨
          3. SPT는 루트로부터 원하는 타입의 가장 가까운 아이템까지의 경로를 포함
          4. 결론 : 단 한 번만 실행하면 된다.