A* 알고리즘
기본 정보
- 명칭: A* 알고리즘
- 영문명: A* Search Algorithm
- 분류: 경로 탐색(Pathfinding) 알고리즘
- 최초 발표: 1968년
- 개발자: Peter Hart, Nils Nilsson, Bertram Raphael
- 주요 용도: 최단 경로 탐색
- 관련 주제: #AStar #Pathfinding #AI #게임개발 #그래프
개요
A*(A-Star) 알고리즘은 현재까지 알려진 경로 탐색 알고리즘 중 가장 널리 사용되는 최단 경로 탐색 알고리즘 중 하나이다.
출발지(Start)에서 목적지(Goal)까지 이동할 때 단순히 가까운 곳만 찾는 것이 아니라, 앞으로 얼마나 더 가야 하는지까지 계산하여 가장 효율적인 경로를 찾는다.
게임 개발, 로봇 공학, 내비게이션, 물류 시스템, AI 분야에서 널리 사용된다.
핵심 아이디어
A*는 다음 공식을 사용한다.
f(n) = g(n) + h(n)| 항목 | 의미 |
|---|---|
| g(n) | 시작점부터 현재 노드까지 실제 비용 |
| h(n) | 목표까지 예상 비용(휴리스틱) |
| f(n) | 총 예상 비용 |
구조
시작점
↓
현재 위치
↓
목표 위치 예상
↓
가장 유망한 노드 선택
↓
목적지 도착A*는 장애물을 피해 가장 짧은 경로를 찾는다.
동작 과정
Open List 생성
↓
시작점 추가
↓
가장 작은 f값 선택
↓
이웃 노드 탐색
↓
g,h,f 계산
↓
Open List 추가
↓
목적지 도착 시 종료Open List
탐색 후보 노드 목록
Open List
↓
방문 예정우선순위 큐(Priority Queue)를 사용한다.
Closed List
이미 방문한 노드 목록
Closed List
↓
방문 완료중복 탐색을 방지한다.
휴리스틱(Heuristic)
목표까지 얼마나 남았는지 추정하는 값
대표 방식
Manhattan Distance
|x1-x2| + |y1-y2|격자(Grid) 게임에서 많이 사용된다.
Euclidean Distance
√((x1-x2)² + (y1-y2)²)실제 거리 계산
Diagonal Distance
대각선 이동 가능전략 게임에서 자주 사용된다.
예제 계산
현재 위치
(1,1)목표
(5,5)Manhattan
|1-5| + |1-5|
=
8의사 코드
while(OpenList){
현재노드 선택
목표인가?
종료
이웃 탐색
비용 계산
OpenList 추가
}간단 구현 예시 (Python)
import heapq
open_list = []
heapq.heappush(
open_list,
(0, start)
)
while open_list:
current = heapq.heappop(
open_list
)
if current == goal:
break실제 구현에서는 g, h, f 값을 함께 관리한다.
시간 복잡도
최악의 경우
O(b^d)| 기호 | 의미 |
| -- | ----- |
| b | 분기 수 |
| d | 탐색 깊이 |
실제 성능은 휴리스틱 품질에 크게 영향을 받는다.
A* vs 다익스트라
| A* | 다익스트라 |
|---|---|
| 휴리스틱 사용 | 휴리스틱 없음 |
| 목적지 방향 탐색 | 전체 탐색 |
| 보통 더 빠름 | 상대적으로 느림 |
| 게임 개발 활용 | 네트워크 최단경로 |
A* vs BFS
| A* | BFS |
|---|---|
| 비용 계산 | 비용 계산 없음 |
| 휴리스틱 사용 | 사용 안 함 |
| 최적 경로 탐색 | 최단 칸 수 탐색 |
| 대규모 맵에 유리 | 작은 맵에 적합 |
A* vs DFS
| A* | DFS |
|---|---|
| 최단 경로 가능 | 보장 안 됨 |
| 비용 계산 | 없음 |
| 경로 품질 높음 | 탐색 위주 |
게임 개발 활용
대표 사례
- RTS 게임
- RPG 게임
- MMORPG
- 전략 시뮬레이션
- 타워 디펜스
RTS 예시
유닛
↓
A*
↓
최단 경로 계산
↓
이동Unity 활용
Unity에서도 A*는 매우 많이 사용된다.
대표 패키지
- A* Pathfinding Project
- NavMesh
AI 활용
NPC
↓
A*
↓
플레이어 추적로봇 공학 활용
로봇
↓
A*
↓
목적지 이동장점
- 최적 경로 탐색 가능
- 매우 빠름
- 휴리스틱 활용
- 게임 개발에 적합
- 장애물 회피 가능
단점
- 메모리 사용량 높음
- 휴리스틱 품질에 의존
- 매우 큰 맵에서는 비용 증가
- 동적 환경에서는 재계산 필요
실무 메모
실무에서는 다음과 같은 방식이 권장된다.
- Grid 기반 게임에 적합
- Open List는 Heap 사용
- Manhattan 휴리스틱 활용
- Closed List 사용 필수
- 대형 맵은 영역 분할 고려
- 실시간 게임은 경로 캐싱 적용
- 이동 비용 가중치 설계
- 장애물 업데이트 최적화
- Unity는 NavMesh 우선 검토
- AI 이동 시스템과 연계
A*와 함께 사용하는 기술
대표 활용 사례
- 스타크래프트 유닛 이동
- RPG NPC 이동
- 로봇 경로 탐색
- 물류 최적화
- 지도 서비스
- 드론 자동 이동
- 자율주행 일부 경로 계산
- 게임 AI
관련 문서
출처
- A* Search Algorithm 논문
- Red Blob Games Pathfinding Guide
- AI Pathfinding 관련 연구 자료