1. A* 알고리즘 개요

• A* 알고리즘은 경로 탐색 알고리즘 중 하나로, 게임에서 NPC 또는 플레이어의 자동 이동, 추적, 회피 등에 널리 사용된다.
  • 목적지까지 “가장 빠르고 유망한 경로"를 계산하기 위해 점수 기반 탐색을 수행한다.
  • Dijkstra 알고리즘과 달리 휴리스틱을 활용하여 탐색 방향을 가늠한다.
  • 다익스트라 알고리즘의 경우, 목적지가 있음에도, 가까운 정점부터 순차적으로 탐색해야하므로, 비효율적임.
  • A*의 경우, 목적지가 정해져있으면, 그쪽으로 빠르게 탐색할 수 있도록 탐색한다.

적용 예:

• 2D 게임에서 몬스터 AI 경로 추적
• RTS 게임의 유닛 자동 이동

2. 목표

• A* 알고리즘의 기본 개념을 이해한다.
• A* 알고리즘과 Dijkstra 알고리즘의 차이를 비교한다.
• 휴리스틱(Heuristic)의 역할과 중요성을 이해한다.

3. 내용

1. A* vs Dijkstra 알고리즘

다익스트라 알고리즘이란?

그래프에서 하나의 시작 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘이다.
모든 간선의 가중치가 **0 이상(음수 없음)**일 때만 올바르게 작동한다.

핵심 개념

• 가중치 있는 그래프에서
• 시작 노드에서 다른 모든 노드까지의 최단 거리를 구함
• 탐욕적(Greedy) 방법으로 동작
• BFS와 유사하지만 가중치를 고려함

작동 원리 (단계별)

1. 시작 노드의 거리를 0으로 설정, 나머지는 모두 무한대(∞)로 초기화
2. 아직 방문하지 않은 노드 중에서 최단 거리 노드를 선택
3. 해당 노드의 이웃 노드들에 대해,
   • 현재 거리 + 간선 가중치 < 기존 거리이면 갱신
4. 모든 노드를 방문할 때까지 반복

특징

A* 알고리즘과의 비교

실생활 비유

다익스트라는 모든 길을 돌아보면서 어디가 제일 빠른지를 찾는 방식,
A*는 대충 방향을 잡고 빠르게 최적인 길을 찾는 방식.

2. A* 알고리즘 핵심 요소

F: 예상 최종거리

G: 지금까지 걸린 거리

H: 남은것으로 예상되는 거리(휴리스틱)

F(x) - 예상 최종거리 = G(x) - 지금까지 걸린 거리 + H(x) - 남은것으로 예상되는 거리(휴리스틱)

주의: H 값에 따라 성능이 크게 달라진다. → H는 “맨해튼 거리 = 격자의 가로나 세로만 연산” 또는 “유클리드 거리 = 직선거리"로 계산 가능.

A* 알고리즘 동작 방식

3. 휴리스틱 (Heuristic)

휴리스틱이란, 문제 해결 또는 의사결정 과정에서 정확한 해답을 구하는 대신, 빠르고 근사적인 해결책을 찾기 위해 사용하는 추정 기법 또는 경험 기반의 간단한 판단 기준이다.

컴퓨터 과학에서는 특히 탐색 알고리즘에서,

목적지까지의 “추정 비용” 또는 “거리"를 계산하는 데 사용되는 함수 또는 값

길 찾기에서의 휴리스틱

“이 길이 제일 가까울 것 같다"는 직관적인 추정값이 바로 휴리스틱.

• g(n): 실제로 걸어온 거리 (운전 시간, 휘어진 길 등)
• h(n): 남은 거리의 추정값 (직선 거리 등)
• f(n): 지금 이 길로 쭉 가면 대략 얼마나 걸릴지를 합산한 것

휴리스틱의 역할

• 탐색 알고리즘이 덜 의미 없는 경로를 시도하게 유도함
• 전체 탐색 공간을 효율적으로 줄여줌
• 계산 시간과 자원을 절약할 수 있음
• 그러나 잘못된 휴리스틱은 최적 경로를 놓치거나 탐색 효율이 나쁠 수 있음

3. 추가 사항

• 휴리스틱 함수 최적화가 알고리즘 효율성에 핵심
• 장애물 환경에서도 예상 H는 무조건 직선거리 기준
• 실제 게임 적용 시, 반복적으로 경로 재계산하거나 목적지 예측 시스템과 결합 가능
• 구현 시 우선순위 큐(Priority Queue) 또는 힙(Heap)을 활용하면 성능 개선 가능
• 시각적 확인 : 길찾기 알고리즘 링크