정말 부정확한 메모 경로 찾기 - A*

2차원 맵구조에서 지점에서 지점으로의 경로를 추출하는 방법에는 일단 초보적인 너비우선탐색법 이라는 것이 있다. 이 방식은 시작점에서 떨어진 수준 순서로 처리가 된다. 여기서 처리라 함은 간단히 자기 주변 노드들을 처리 대상 모음 힙에 넣는 일이다. 넣을때 중요한 일이 하나 있는데, 넣어지는 녀석의 데이터 구조에 자신을 넣은 노드를 지목하는 란에 현재 처리 대상 노드를 넣어서 힙에 넣는다.
 
이 방법은 너무 제약과 단점이 많기 때문에 게임 에서는 주로 다른 방식을 사용하는데 거리우선탐색법 이라는 구조다. 너비우선탐색법에서는 대각선에 놓인 노드와 수평으로 옆에 놓인 노드가 같은 실행 순서를 할당받을 수 있었다면, 거리우선탐색 구조에서는 대각선은 수평,수직 부분 처리가 모두 이루어진 후에 이루어지게 된다.

거리우선탐색법을 응용한 여러 방식이 있는데 그 중에서 가장 유명한 것이 A*(에이스타)라고 하는 방식이다. 이 방식에서는 힙에서 정렬 값으로 삼는(그래서 처리 순서에 영향을 주는 값)휴리스틱 변수에 현재까지 계산된 진행된거리 + 목표셀까지의 직선거리를 합산한 방식을 사용한다.

이책을 읽으며 -