[Unity] A* 알고리즘 개념 정리

A* 알고리즘이란?

A*는 최단 경로를 찾기 위한 휴리스틱 기반 알고리즘으로,

실제 거리와 예상 거리를 모두 고려하여 빠르고 정확한 길찾기를 수행합니다.

---

어디에 사용될까?

• 게임에서 캐릭터 이동 경로 찾기
• 네비게이션 시스템 (지도)

---

기반이 되는 알고리즘

다익스트라(Dijkstra)

• 출발 지점에서 모든 노드까지의 최단 거리를 계산하는 알고리즘
• 큐를 사용해, 가장 적은 비용으로 도달할 수 있는 노드부터 탐색
• 모든 간선의 가중치가 0 이상일 때 정확한 최단 경로를 보장함
• 목표 지점이 정해져 있어도 전체를 탐색하기 때문에 비효율적일 수 있음

휴리스틱( Heuristic )

• 현재 노드에서 목표 노드까지의 "예상 거리"를 추정하는 함수
• 이 값은 실제 거리가 아니어도 되며, 대략적인 가늠치로 A*의 탐색 방향을 유도함

---

작동 방식 요약

A*는 각 노드에 대해 다음 수식을 계산합니다:

f(n) = g(n) + h(n)

• g(n) : 시작점에서 현재 노드 n까지의 실제 거리
• h(n) : 현재 노드 n에서 목표 지점까지의 추정 거리 (휴리스틱)
• f(n) : 현재 노드를 선택할 때 사용하는 우선순위 점수

---

탐색 흐름

1. 시작 노드를 오픈 리스트에 추가
2. 오픈 리스트에서 f(n)이 가장 작은 노드 선택
3. 인접 노드에 대해 g, h, f 계산
4. 더 좋은 경로가 있으면 갱신
5. 목표 노드에 도달하면 경로 추적

---

A*의 장점

• 경로가 있으면 최단 경로 보장
• 다익스트라보다 탐색 효율이 좋음 (목표 방향으로 유도됨)

---

A*의 단점

• 휴리스틱이 잘못 설정되면 성능 저하
• 노드 수가 많으면 메모리/연산 부담