- A* 알고리즘 (A Star Algorithm) 이란? A* 알고리즘은 그래프 혹은 지도(그리드) 상에서 최단 경로를 찾아내기 위한 휴리스틱(Heuristic) 기반 탐색 알고리즘입니다. 대표적으로 게임에서 NPC 캐릭터가 장애물을 피해 목표 지점까지 이동해야 할 때, 혹은 로보틱스에서 특정 지점까지 이동 경로를 계산할 때 자주 쓰입니다.
A* 알고리즘의 주요 개념 그래프(혹은 지도, 그리드)
일반적으로 노드(Node)와 간선(Edge, 노드간 이동 비용)으로 표현되는 구조에서의 경로 탐색을 가정합니다.
2D 격자(타일맵)에서도 가로, 세로, 대각선 이동처럼 이동 가능한 방향과 비용(Weight)을 설정할 수 있습니다.
오픈 리스트(Open List), 클로즈드 리스트(Closed List)
오픈 리스트: 아직 방문하지 않았지만, 탐색 후보가 되는 노드를 모아둔 리스트
클로즈드 리스트: 이미 방문한 노드(탐색을 마친 노드)
휴리스틱(Heuristic) 함수
현재 노드가 목표 지점까지 얼마나 가까운지 추정하기 위한 함수입니다.
예: 맨해튼 거리(Manhattan Distance: |x1 - x2| + |y1 - y2|), 유클리드 거리(Euclidean Distance), 등등
점수 함수 (f(n) = g(n) + h(n))
f(n): 노드 n을 평가할 때 사용하는 총 비용
g(n): 시작 지점에서 노드 n까지의 실제 이동 비용(지금까지의 경로 비용)
h(n): 노드 n에서 목표 지점까지의 휴리스틱(추정 비용)
A* 알고리즘의 순서 초기화
시작 노드(시작 지점)를 오픈 리스트에 넣고, g(시작 노드) = 0, h(시작 노드) = 시작 지점에서 목표까지의 휴리스틱 값으로 설정합니다.
f(시작 노드) = g(시작 노드) + h(시작 노드)
오픈 리스트에서 f(n)이 가장 작은 노드를 꺼냄
오픈 리스트에서 f 값이 최소인 노드를 선택하여 현재 노드로 설정합니다.
현재 노드가 목표 지점이면 탐색 종료
만약 현재 노드 == 목표 노드라면, 경로 복원을 통해 최단 경로를 얻고 알고리즘을 끝냅니다.
이웃 노드 탐색
현재 노드와 인접한 노드(이동 가능한 노드)들을 확인합니다.
각 이웃 노드 m에 대해,
임시 g 값(tempG) = g(현재 노드) + (현재 노드 -> m 이동 비용)
이전에 계산된 g(m)보다 tempG가 작으면 더 좋은 경로가 발견된 것이므로,
g(m) = tempG
h(m) = 목표까지의 휴리스틱(변함 없음)
f(m) = g(m) + h(m)
이웃 노드 m의 부모(경로 상 이전 노드)를 현재 노드로 갱신
만약 이웃 노드 m이 오픈 리스트에 없으면 새로 추가
현재 노드를 클로즈드 리스트로 이동
더 이상 현재 노드를 탐색할 필요가 없으므로 클로즈드 리스트에 넣어 관리합니다.
오픈 리스트가 빌 때까지 2~5 과정 반복
오픈 리스트가 완전히 빌 때까지 반복하고, 목표 노드를 찾지 못한 상태라면 경로가 없는 것으로 간주할 수 있습니다.
A* 알고리즘은 휴리스틱 함수를 적절히 사용함으로써, 탐색 범위를 줄이고 효율적인 최단 경로를 찾는 데 매우 유용합니다.