A* 알고리즘 개요

A* 알고리즘은 초기노드(시작지점)에서 목표 노드(목표지점)까지의 경로를 찾는 그래프 탐색 알고리즘이다.
다른 그래프 탐색 알고리즘과 다른 점은 목표에 얼마나 근접한 것인지를 평가하는데 휴리스틱 함수를 사용한다는 것이다.

필요한 자료구조 및 객체

struct node {
int x, y;//해당 노드의 좌표
int dS, dG, dF;//해당 노드의 거리 정보
node *backpath;//자신 이전의 노드(자신과 시작 좌표 노드를 이어주는 전단계의 노드를 의미)
};

PriorityQueue OpenNodeList, CloseNodeList;
//우선순위 큐(dS값이 작은 노드를 우선적으로 뺄 수 있는 큐)로
//만들어진 열린 노드 목록, 닫힌 열린 목록이 필요하다.

자료구조, 객체 세부 설명

1. node 구조체 설명
dS = 이전 노드의 dS + 자신과 이전 노드간의 거리(일반적으로 수직,수평은 1, 대각선은 1.4로 계산)
dG = 자신과 목표지점까지의 특정 조건 없는 추측 거리(휴리스틱요소)
dF = dS + dG (의미 : 자신의 노드를 통해 거쳐가는 경로의 실제+휴리스틱 거리)
backpath = 일반적으로 자신을 Open Node List에 추가한 노드를 처음으로 가리키게 되며, 근접한 노드들이 자신을 점검할 때마다 dS를 비교하여 인접해있는 노드 중 dS가 가장 작은 노드를 가리키게끔 갱신된다.


2. 열린 노드 목록, 닫힌 열린 목록(OpenNodeList, CloseNodeList) 설명

노드들은 OpenNodeList 또는 CloseNodeList에 추가되어 관리된다.
OpenNodeList가 의미하는 것은, 다음 검색을 위해 이동할 수 있는 좌표의 노드들의 집합이며,
CloseNodeList가 의미하는 것은, 이미 검색을 마친 좌표 노드들의 집합이다.

알고리즘 순서

1. 시작점에 대한 노드를 추가하여 Open Node List에 추가한다.

2. Open Node List에서 dF가 가장 작은 노드(또는 dF가 같은 경우 dG가 가장 작은 노드)를 Pop한다.(Pop된 노드 : PopNode)

3. PopNode가 Goal 좌표에 해당하는 노드인지 비교하여 해당 좌표가 아니면 4번, 해당 좌표이면 6번으로 간다.

4. PopNode의 주변 좌표를 탐색하여,

• 이동할 수 있는 좌표의 경우
  1. Open Node List 또는 Close Node List에 없는 경우
      - 노드를 생성하여 추가한다.
  2. Open Node List 또는 Close Node List에 있는 경우
      - 해당 좌표에 대한 노드의 dS와 PopNode의 dS+추가되는 dS 를 비교하여 PopNode의 dS+추가되는 
       dS 가 더 작은 경우 PopNode를 통해 가는 경로가 더 빠르다는 의미이므로 backpath와 dS, dF를 
       갱신하고, Close Node List에 있었던 경우는 다시 Open Node List로 옮겨준다.
     
• 이동할 수 없는 좌표의 경우
   - 무시한다.

5. PopNode를 Open Node List에서 Close Node List로 옮긴다음 다시 2번으로 간다.

6. PopNode의 Backpath를 따라가면서 경로를 저장한다.