A*란? - 상태 공간 안의 특정한 상태에 이웃한, 즉 인접한 상태들을 조사해 나가면서 시작

                 상태로부터 목표 상태로 이르는 가장 싼 비용의 경로를 찾는 알고리즘

             - 아직 조사하지 않은 상태들 중 가장 유망한 상태를 조사하는 과정을 반복하는 것

            - 현재 상태에 인접한 상태들중 TotalCost(x)가 가장 낮은 상태를 찾음

2. A*가 관리하는 상태 목록 - 열린목록(openlist) : 아직 조사하지 않은 상태를 담음

                                        - 닫힌목록(closelist) : 이미 조사한 상태들을 담음

      CostFromStart(X) : 현재에서 목표에 이르는 가장 싼 비용

      CostFromGoal(X) : 현재에서 목표에 이르는 가장 싼 추정비용

      TotalCost(x) = 총경로비용 . (CostFromStart(X) +CostFromGoal(X))

                x:"유망함“을 평가하기 위한 정보를 가짐

3. A*의 특징 - ① A*는 시작으로부터 목표에 이르는 하나의 경로를 찾음

                        ② A*는 최적의 경로를 찾음(CostToGoal()이 항상 과소평가)

                        ③ A*는 휴리스틱을 가장 효율적으로 사용

4. 상태표현 - 위치 또는 장소 (위치를 어떻게 표현할 것인가?)

                  - 추가고려사항 : 유닛의 방향이나 속도의 영향 -> 직선적인 경로 선택

                                         : 길의 상태 및 맵의 상태

     * 공간을 나누는 방법 - 정사각형 격자 : (단) 내가 고려해야 할 부분이 많음.

                            [2D]                맵의 크기가 ↑ -> 검색시간 ↑

                          - 쿼드트리 : 모두 같은 성분(동일한 지형)이 될 때까지 계속 4등분

                            [3D]      (장) 내가 고려해야 할 부분이 줄어듦

                                           사각형 ↑(개수↓) -> 검색시간 ↓, 표현저장용이

                                         (단) 연산이 ↑보다 복잡.

                                            영역자체가 커지면 뒤에 해줘야하는 작업이 복잡

                          - 블록다각형 : 다각형의 크기가 다름-> Vertex수가 ↑->구조적으로복잡

                            [3D]

                          - 가시점 : 면과 선의 충돌체크

                            [2D]     (장) 빠르고 복잡한 구조에서 구현하기 쉽다.

                                         (단) 장애물 벽에 딱 달라붙어 가게 됨

                          - 원통형태

5. 두 위치들 사이의 경로 비용 - 그 경로가 최적인지 아닌지를 비교하기 위한 값

                                           (이동한거리, 이동에 걸린 시간, 소비한 이동력, 소비한 연료)

                                           - 유닛의 종류에 따라, 양끝에 해당하는 위치의 차이에 따라

                                            비용이 달라지기도 함

6. 이웃한 상태들 - 맵의 표현이나 분할방식에 따라

                         - 지형 or 유닛의 종류에 따라 이웃결정

7. 추정 - 최적의 경로 찾기 : 주어진 위치부터 목표까지의 실제 맵상의 최단거리 * 단위 거리당

                                          최소 지형 비용

         - 검색속도

8. 휴리스틱 함수(추정치) -> 두점사이의 거리

       - 과소평가 : (연산) 시간이 많이 걸림

       - 과대평가 : 길을 못찾을 수도 있다

    => 최적의 경로를 찾는 것보다 빠른 검색 속도가 더 중요하다면 목표까지의 비용을 “과대평가”할수도 있다.

    => 가중치가 ↑ -> 직선적으로 찾아감

9. A*의 단점 - 현명하게 사용하지 않으면 시간 낭비가 될 수도 있음

                   - 상당히 많은 CPU 시간을 잡아 먹음

                   - 메모리를 전부 잡아 먹을 수도 있음

                  - 시작 위치에서 목표까지의 경로가 존재하지 않는 상황에서 A*는 상당히 비효율적이다. 그런 경우 A*는 시작위치로부터 도달할 수 있는 모든 위치들을 조사한 후에야 목표에 도달할 수 없다는 것을 깨닫게 됨

10. 검색 속도냐? 최적의 경로냐?

11. A*의 미학적 최적화 - ① 직선적 경로 : A*알고리즘 안에서 직선화된 경로 만듦

                                        (비용가중치(휴리스틱가중치)를 신중하게 선택하는 것에 관련

                                         - 매 단계에서 인접한 위치를 평가하는 방식을 약간 수정

                                         : A*로 경로 결정한 다음에 그것을 직선화

                                         (격자형 검색 공간 안에서의 직선화된 경로)

                                 ~ 알고리즘 수행시

                          ② 매끄러운 경로 : Catmull-Rom 스플라인이 적합(보간)

                                 ~ 알고리즘 수행후

                          ③ 계통적 길찾기에서 미학적 최적화(좀더 직접적인 경로를 만듦)

                                          : (장) 사람이 실제로 길을 가는 방식과 흡사

                                                검색 성능이 보통의 A*보다 우월

                                          : (단) 전반적인 경로의 모습이 부자연스러움

        * Catmull-Rom 스플라인

                        : 주어진 네 개의 입력점들로부터 두 번째와 세 번째 점을 지나는 매끄러운

                         곡선을 돌려줌, 제어점을 지나감

                        : 첫 번째A와 두 번째B 제어점들 사이의 점 - AABC

                        : 두 번째B와 세 번째C 제어점들 사이의 점 - ABCD

                        : 세 번째C와 네 번째D 제어점들 사이의 점 - BCDD

                          (최초 시작시에는 첫 번째 제어점을 두 번 사용하고 목표에 도달할

                          때에는 마지막 제어점(목표)을 두 번 사용해야 한다)

                        : u의 간격을 좁힌다면 좀더 매끄러운 곡선을 얻을 수 있음

        * 격자의 크기 ↓ -> A*검색노드가 ↑ -> 검색시간 ↑

          격자의 크기 ↑ -> 보기에 이상(자연스럽지 X)

        * 실제 적용 - 행렬 / 보간 - 쿼터니언  (행렬↔쿼터니언 변화할 줄 알아야함)

12. 게임에서의 길찾기의 목표 : 유닛이 ‘좀 더 지능적이고 자연스럽게’ 행동하도록 만드는 것

13. 게이머가 체감하는 반응 시간을 단축시키기 - 소리이용, 곧 움직일 것이라는 느낌을 주는 눈속임 애니메이션 이용

14. 속도 최적화 - ① 검색 공간의 최적화

                         : 검색공간의 단순화 - 사각or육각형격자/ 실제다각형바닥

                                                       /특수화된 다각형  바닥 / 가시점방식

                  ② A*알고리즘 최적화

                         : 휴리스틱 함수

                         : 메모리 관리 - 길찾기 데이터를 분리

                                       - 메모리(길찾기에 사용되는 메모리)를 미리 할당, 노드뱅크

                                       - 마스트노드 목록

                                       - 오픈 리스트의 열린 목록의 최적화 => 우선순위 큐

                  ③ 자원의 최적화 (openlist와 closelist를 어떻게 관리, 정렬?-> 메모리관련)

                  ④ A*의 사용유무

        * A*의 속도는 검색 공간의 크기에 크게 영향을 받음

              => 검색공간 자체를 최적화 => A*구현 자체를 최적화

        * 검색공간의 단순화

        - 사각 또는 육각형 격자 : (장) 장애물이나 캐릭터들을 격자안에서 표현하기 쉬움.

                                            [2D] 연산용이

                                             (단) 검색 공간의 크기가 가장 큼.(메모리 많이 차지)

                                              3D X, 칸단위 이동으로 이동경로가 부자연스러움

        - 실제 다각형 바닥 : (장) 데이터 구조가 이미 3D맵에 들어있음. 빠른 검색 가능

                                      (단) 맵이 복잡 -> 다각형의 개수가 매우 많아짐..

                                        공간 안의 캐릭터나 장애물들을 표현 X

                                        다각형 안의 제어점들을 선택하기 위한 알고리즘 필요

        - 특수화된 다각형 바닥 : 레벨 디자이너가 길 찾기에 적합한 형태의 다각형 바닥 데이터를 직접 만드는 방식

                                (장) 검색 공간 작음. 빠른 검색. 장애물 표현가능

                                (단) 레벨 디자이너의 수작업 필요. 공간안의 캐릭터 표현 X

                                     다각형 안의 제어점들을 선택하기 위한 알고리즘 필요

        - 가시점 방식 : (장) 가장 작은 검색공간 , 장애물 표현가능

                                결과로 얻는 경로가 완전히 직접적

                              (단) 알고리즘 또는 수작업을 통해서 사전에 그래프를 만들어야 함

                             장애물이 파괴되어도 그래프 상에는 여전히 장애물이 있는 상태로 남음

                             공간안의 캐릭터 표현 X

                             넓게 늘어선 캐릭터들처럼 너비가 큰 캐체들을 제대로 다루지 못함

                             곡선으로 된 벽이 존재하면 그래프가 필요이상으로 복잡해짐