A* 알고리즘
A* 알고리즘은 출발 노드부터 목적 노드까지 최단거리를 계산하는 알고리즘이다.
다익스트라 알고리즘에 목적 노드까지의 예상치를 고려한 휴리스틱을 넣어 목적 노드까지의 거리만을 계산해주기 때문에 과정을 단축시킬 수 있다.
다익스트라 알고리즘의 확장판이라고 생각하면 되겠다.
A* 알고리즘의 핵심은 휴리스틱으로 휴리스틱을 기존 노드의 거리에 더해줘 최종 거리를 계산한다.
F = 최종거리
G = 간선거리
H = 휴리스틱
F(n) = G(n) + H(n)과 같이 표현할 수 있으며
나머지는 다익스트라 알고리즘과 동일하게 작동된다.
다익스트라 알고리즘
A* 알고리즘
A* 알고리즘 동작 과정
-
시작 노드, 목적 노드를 생성한다.
-
노드를 넣어줄 그래프를 하나 생성하고 시작 노드 0으로 초기화 하고 넣어준다.
-
시작 노드를 제외한 나머지 노드들을 무한에 가까운 수로 초기화한다.
-
경로를 저장할 경로 배열을 하나 만들어준다
-
가장 거리가 짧은 노드를 반환할 변수를 하나 생성하고 목적지에 도달할 경우 경로를 저장한다.
-
현재 노드에서 인접한 노드와의 거리와 예상 비용(휴리스틱)을 계산한 후 기존의 거리보다 짧다면 거리를 갱신하고 경로를 저장한다
-
4-6번을 반복한다
A* 알고리즘 특징
- 다익스트라 알고리즘과 큰 차이점은 휴리스틱이므로 휴리스틱이 0, 즉 F(n) = G(n) 이면 다익스트라 알고리즘과 동일하다.
- 시작 노드와 목적 노드만의 검색을 위한 알고리즘이기 때문에 다른 노드를 탐색하는데는 적절하지 않다.
- 휴리스틱 함수에 굉장히 의존적이기 때문에 휴리스틱 함수 작성에 주의를 요해야한다.
- 목표 지점이 변경되면 처음부터 다시 계산해야하기 때문에 정적인 목표와의 거리를 계산할 때 요긴하게 사용된다.
A* 알고리즘 코드
A* 알고리즘은 다익스트라 알고리즘에서 휴리스틱과 휴리스틱+간선 거리를 계산한 내용을 추가한 것에 가깝다.
즉슨 휴리스틱 함수에 따라 성능 차이가 심하기 때문에 휴리스틱 함수를 얼마나 잘 계산하느냐가 A* 알고리즘 성능에 큰 영향을 미칠것이다.
아래 코드는 List배열로 작성되었으며 우선순위 큐와 성능 차이가 심하기 때문에 우선순위 큐를 자주 사용하는것을 알아두면 좋을것이다.
public class AstarNode : IComparable<AstarNode>
{
public int index; //노드 인덱스, 구별값
public Vector2 pos; //노드 위치
public float G; //시작점에서 지금 위치까지의 실제 비용
public float H; //휴리스틱, 예측비용
public float F => G + H; //총 비용
public AstarNode parents; //부모 노드, 경로 복원 용도
public AstarNode(int index, Vector2 pos, float g, float h, AstarNode parents = null)
{
this.index = index;
this.pos = pos;
G = g;
H = h;
this.parents = parents;
}
//F값 기준 정렬을 위한 비교 함수
public int CompareTo(AstarNode other)
{ //F값으로 우선 비교해보기
int fCompare = F.CompareTo(other.F);
if (fCompare != 0)
{
return fCompare;
}
//F값이 같을 경우 인덱스 기준으로 비교하기
return index.CompareTo(other.index);
}
}
public class AstarExample : MonoBehaviour
{
//두 좌표 사이의 거리를 휴라스틱으로 사용
static float Heuristic(Vector2 a, Vector2 b) => Vector2.Distance(a, b);
private void Start()
{
int n = 4; //노드 4개 A,B,C,D
int startIndex = 0; //시작 위치는 0번 노드 A
int goalIndex = 3; //목표 위치는 3번 노드 D
//각각의 노드에 좌표 설정
Vector2[] position = new Vector2[4]
{
new(0,0), //A
new(1,0), //B
new(0,1), //C
new(1,1) //D
};
//그래프 구성
List<(int to, float cost)>[] graph = new List<(int to, float cost)>[n];
for (int i = 0; i < n; i++)
{
graph[i] = new List<(int to, float cost)>();
}
//비용 정보 추가
graph[0].Add((1, 1)); //A->B 코스트가 1
graph[0].Add((2, 4)); //A->C 코스트가 4
graph[1].Add((2, 2)); //B->C 코스트가 2
graph[1].Add((3, 6)); //B->D 코스트가 6
graph[2].Add((3, 3)); //C->D 코스트가 3
//각 노드까지의 최소 거리 저장 배열
float[] gScore = new float[n];
for (int i = 0; i < n; i++)
{
gScore[i] = float.MaxValue;
}
//시작 지점
gScore[startIndex] = 0;
//방문 여부
bool[] closed = new bool[n];
//오픈 리스트, 탐색 대상들
var openList = new List<AstarNode>();
//시작 지점 추가
openList.Add
(new AstarNode
(startIndex,
position[startIndex],
0,
Heuristic(position[startIndex], position[goalIndex])
)
);
//탐색 루프
while (openList.Count > 0)
{
openList.Sort((a, b) => a.CompareTo(b));
//F가 가장 낮은 노드 찾아오기
var current = openList[0];
//방문한 노드는 제거
openList.RemoveAt(0);
//이미 방문한 노드는 패스
if (closed[current.index])
{
continue;
}
//방문 처리
closed[current.index] = true;
//목표에 도달했으면 경로 복원
if (current.index == goalIndex)
{
//경로 저장용 배열
var path = new List<int>();
//경로 저장
var temp = current;
//부모 따라가면서 추적하기
while (temp != null)
{
path.Add(temp.index);
temp = temp.parents;
}
//역순이니까 뒤집기
path.Reverse();
Debug.Log($"A* 패스 {string.Join("->", path)}");
Debug.Log("최단 거리 " + current.G);
break;
}
//인접 노드 탐색하기
foreach (var neighbor in graph[current.index])
{
//이미 처리한 노드는 패스
if (closed[neighbor.to])
{
continue;
}
//현재의 G + 이동 비율 계산
float t = current.G + neighbor.cost;
//더 짧은 경로를 발견 시
if (t < gScore[neighbor.to])
{
gScore[neighbor.to] = t;
//H값 계산
float h = Heuristic(position[neighbor.to], position[goalIndex]);
//새로운 노드 추가
openList.Add(new AstarNode(neighbor.to, position[neighbor.to], t, h, current));
}
}
}
}
}
