A* 알고리즘

그래프/트리의 탐색 알고리즘으로 길찾기 알고리즘이다. 게임에서 많이 사용되며 다익스트라의 확장판, BFS의 가지치기 알고리즘이라 생각하면 된다. 따라서 휴리스틱 알고리즘이기도 하다.

1. 휴리스틱 추정값

• f(x) = h(x) + g(x)
  • f(x): 출발 노드에서 목적지 노드까지 경로의 총 가중치 합
  • h(x): 현재 노드에서 목적지 노드까지의 추정 경로 가중치(휴리스틱)
  • g(x): 현재 노드에서 출발 지점까지의 경로 가중치
  • f(x)가 가장 최소가 되는 노드를 다음 탐색 노드로 선정
    - 이를 위해 우선순위 큐를 사용

    h(x)가 휴리스틱 함수이기 때문에 해당 함수를 어떻게 설계하냐에 따라 알고리즘의 성능이 달라진다. 대표적으로 맨해튼 거리 함수와 유클리디안 거리 함수가 있다.

2. 실행 과정

• A에서 B로 이동
  

• A주변 노드의 f(n)을 계산 후 가장 작은 노드를 다음 탐색 노드로 선정
  

• B에 도달할 때까지 반복

• B에 도달했다면, 최소 비용 경로를 역추적하여 결과를 얻음

3. 구현

1. 시작 노드에서 검색된 인접사각형들을 열린 목록에 넣음
   1-1. 만약 인접한 사각형이 갈 수 없는 곳이거나 닫힌 목록 상에 있다면 무시
   1-2. 만약 인접한 사각형이 열린 목록에 없다면, 열린 목록에 추가하고, 이 사각형의 부모를 현재 사각형으로 지정및 해당 사각형의 F,G,H 비용을 기록
   1-3. 이미 열린 목록에 있다면, G비용을 이용해 해당 사각형이 더 나은지 확인 후 부모 사각형을 바꿈, G, F비용을 다시 계산
2. 아래 과정을 반복
   1) 열린 목록에서 가장 낮은 F비용을 찾아 현재 사각형으로 선택
   2) 이것을 열린 목록에서 꺼내 닫힌 목록으로 넣음
3. 중단 조건
   3-1. 목표지점을 열린 목록에 추가한 경우
   3-2. 열린 목록이 비어있을 경우(실패 경우)

• 소스코드(해당 코드는 UE상에서 구현되는 코드이며 알고리즘이 동작하는 코드 부분입니다.)

while (OpenNodes.Num() != 0) {
		OpenNodes.StableSort([](const AGridNode& node1, const AGridNode& node2) {return node2 > node1;});	//기존 순서를 유지하며 정렬
		
		CurrentNode = OpenNodes.Pop();
		if (CurrentNode == GoalNode) break; //목적지를 찾아 종료
		
		TArray<AGridNode*> ChildNodes = Grid->GetValidNeighbors(CurrentNode); //주변 노드들을 자식노드로 들고옴
		for (auto& ChildNode : ChildNodes) {
			int currentcost = CurrentNode->cost + CostNodes(CurrentNode, ChildNode); //비용 계산
			if (OpenNodes.Contains(ChildNode)) { //해당 노드가 열린 목록에 있다면
				if (ChildNode->cost <= currentcost) continue; //이전에 계산한 비용이 방금 계산한 비용보다 작다면 아래 내용을 수행할 필요가 없음
			}
			else if (ClosedNodes.Contains(ChildNode)) { //해당 노드가 닫힌 목록에 있다면 무시
				continue;
			}
			else {
				OpenNodes.Add(ChildNode);
				SetOpenNode(ChildNode);
				TotalOpenNodes++;
				ChildNode->heuristic = Heuristic(ChildNode); //휴리스틱값을 계산
			}
			ChildNode->cost = currentcost;
			ChildNode->parent = CurrentNode;
		}
		ClosedNodes.Add(CurrentNode);//현재노드는 탐색이 종료된 노드로 간주
		ExploredNodes++;
		SetClosedNode(CurrentNode);
	}

4. 다른 길찾기 알고리즘과 다른점

A*알고리즘은 대표적으로 다익스트라와 많이 비교되곤 한다. 다익스트라와 A*의 차이점은 휴리스틱 함수의 사용 유무이다.

• 휴리스틱 함수 사용: 휴리스틱 함수를 사용함으로서 현재 노드부터 목적지까지의 거리를 추정한다.
• 성능: 휴리스틱 함수를 사용하여 불필요한 경로의 탐색을 피할 수 있어 더 빠른 솔루션을 찾게 한다.
  결론적으로 A*에서 휴리스틱의 가중치를 0으로 설정한다면 다익스트라가 되는것이다.

5. 결과