A* 알고리즘이란?

A* 알고리즘은 그래프 탐색 알고리즘 중 하나로,
주어진 출발점에서 목표 지점까지의 최단 경로를 찾는 데 사용됩니다.
이 알고리즘은 다익스트라 알고리즘과 휴리스틱을 결합하여, 경로를 탐색할 때 실제 비용(GCost)과 추정 비용(HCost)을 모두 고려는 방식입니다.

A스타 알고리즘은 각 노드마다 세 개의 비용을 관리하면서 길을 찾습니다.

• GCost (Movement Cost): 시작 지점에서 현재 노드까지의 실제 경로 비용입니다.
• HCost (Heuristic Cost): 현재 노드에서 목표 지점까지의 추정 비용입니다. 이는 일반적으로 맨해튼 거리, 유클리드 거리 또는 체비셰프 거리와 같은 휴리스틱 함수를 사용하여 계산됩니다.
• FCost (Total Cost): FCost = GCost + HCost로, 총 예상 비용입니다.

프로젝트에서 사용

과정

C#에는 기본적으로 우선순위큐를 제공하지 않습니다.
그렇기 때문에, List를 이용하여, 우선순위 큐를 구현했습니다.

이는, 에이스타 알고리즘의 효율성을 올리기 위한 작업입니다.

에이스타 알고리즘을 구현함에 앞서,
사각형 셀과 육각형 셀의 차이에 대해서 알아야 합니다.

사각형 셀은 자기 자신을 기준으로 9방향을 탐지하며 이때, 대각선의 거리와 우회하는 거리 비용이 달라지게 됩니다.
통상 기본 비용의 1.4배에 해당하는 거리 비용을 책정합니다.

하지만, 육각형 셀은 여섯 방위를 탐지하며, 모든 비용이 동일하게 책정됩니다.

예를들면,

과 같이, (x,y)값에 1을 감산하거나 증산하는 방식으로 다음 셀을 구합니다.

적용 결과

코드

A스타 알고리즘을 구현한 코드입니다.

FindPath는 주어진 시작 타일과 목적지 타일 간의 최단 경로를 찾습니다. 이를 위해 우선순위 큐와 폐쇄된 타일 집합을 사용하여 탐색하며, 각 타일의 G 값(출발 지점부터의 이동 비용), H 값(목적지까지의 예상 이동 비용), 그리고 F 값(G 값과 H 값의 합)을 계산합니다.

RetracePath 메서드는 목적지 타일부터 시작하여 부모 타일을 따라가며 최종 경로를 역으로 추적합니다.

GetDistance는 두 타일 간의 유클리디안 거리를 계산하여 휴리스틱 함수로 사용됩니다. 이 거리는 직선 거리를 구하기 위해 두 점의 좌표 차이를 계산한 후, 피타고라스의 정리를 통해 구해집니다.

GetNeighbors 메서드는 주어진 타일의 이웃 타일을 찾아 반환합니다. 여기서는 헥스 그리드의 특성에 따라 헥스 타일 주변에 있는 이웃 타일을 찾습니다.

헥사 셀, 타일맵을 저장하는 코드입니다.
월드 상의 주소를 저장하는 originPos와 A* 알고리즘을 이용하여 최단거리를 구하기 위한 X,Y 변수를 저장합니다.