a* search

a* search는 최단경로 검색 알고리즘이라 생각하면 된다.

다만, 기존의 kruskal과 같은 탐색 알고리즘과는 달리 경로에 장애물이 있을 경우를 고려하는게 차이점이다.

초기조건은 탐색 영역을 사각형으로 나눈다.

초록색이 시작위치,

파란색이 장애물,

빨간색이 도착위치일 경우 아래와 같은 흐름으로 탐색이 진행된다.

A. 현재 위치와 이동 위치와의 간선차 = G

B. 이동 위치와 도착 위치와의 간선차(직선일 경우 멘하탄방법임) = H

C. 갱신 거리값은 G + H로 계산된다.

1) 자신의 위치에서 주변(9방향)의 사각형 위치로 이동한다는 가정하에 총 간선값을 계산한다.

2) 이동이 가능할 경우 스택에 쌓는다.

3) 스택에서 가장 짧은 간선을 가진 사각형으로 이동 후 다시 주변(9방향)으로 간선값을 갱신한다.

4) 현재 간선값과 새로히 계산된 간선값과 비교하여 작은경우를 이동한다.

5) 단, 이동 시에는 자신의 부모 사각형의 위치를 인덱스값으로 기억하며 간선 값이 갱신될 경우 부모도 갱신한다.

도착 위치에 도달할 경우, 부모 사각형을 따라가는 경로가 최단 경로이다.