A*(AStar) 알고리즘 [길찾기 알고리즘]

A* (AStar*) 의 개요
A* 는 상태 공간 안의 턱정 상태에 이웃한, 즉 인접한 상태들을 조사해 나가면서 시작 상태로부터 목표 상태로 이르는 가장 싼 비
용의 경로를 찾는 알고리즘이다.(간단하게 말하면 그냥 주의 상태보고 가고 픈 곳에서 가장 가까운 값을 찾는다~)
열린 목록(Open List) 란 아직 조사하지 않은 상태를 말하고
닫힌 목록(Close List) 란 이미 조사한 상태를 말합니다.
TotalCost(X) = CostFromStart(X) + CostToGoal(X)
CostFromStart(X) : 하나의 시작 지점으로부터 이 상태에 이르는 가장 싼 비용
CostToGoal(X) : 현재 상태로부터 목표에 이르는 가장 싼 추정 비용
열린 목록 안의 '가장 유망한' 상태 - TotalCost(X)가 가장 낮은 상태.
A* 사용
1. 시작으로부터 목표에 이르는 하나의 경로를 찾는다(존재하는 경우)
2. 최적의 경로를 찾는다 (CostToGoal(X)이 적절한 평가치를 돌려주는 경우)
3. A* 는 휴리스틱을 가장 효율적으로 사용한다.
격자의 경우 이웃한 상태들의 경우 (x, y)의 이웃은 (x+1, y), (x+1, y+1), (x, y+1) 등이 있다.
비용(Cost) 이라는 것은 그 경로가 최적인지 아닌지를 비교 하기 위한 값이다.
- 이동한 거리, 이동에 걸린 시간, 소비한 이동력, 소비한 연료 등을 비용으로 사용한다.
- 특정 영역을 지나면 비용을 더욱 크게 하거나 좀 더 저렴하게 할 수 있다.
- 유닛의 종류에 따라 달라지기도 한다.
(검색 속도를 위해서 비용 정보를 이웃 정보와 함께 자료구조에 저장해 두는 것이 이상적이다)
약점.
1. 맵의 크기가 클 경우(찾는 속도가 Gg 된다더라)
2. 시작 위치에서 목표까지의 경로가 존재하지 않는 상황

그림 예)
처음 시작위치에서 이웃노들들로 확장하며 각 노드마다 f값을 계산한다. 사각형 가운데의 그림은 이 상태에서 이전 상태를 가르키는 것으로 직선방향의 상태가 바로 이전의 지나왔던 상태이다. 각 상태마다 이전 상태의 위치정보도 저장하고 있어야 한다.

결과적으론 아래같이 된다.


근데..... 이거 어떻게 소스로 바꾸지? (......)