A* 길찾기 알고리즘

📌 A* 알고리즘이란?

• A*(A Star) 알고리즘은 다익스트라 알고리즘에 휴리스틱(Heuristic) 개념을 더해 목표 지점을 더 빠르고 정확하게 찾도록 최적화된 알고리즘입니다.
• 경로의 총 비용(F)을 F = G + H로 계산합니다:
  • G: 시작점에서 현재 노드까지의 실제 이동 비용
  • H: 현재 노드에서 목표 지점까지의 예상 거리 (휴리스틱)
  • F: 노드의 총 우선순위 값 (작을수록 더 먼저 탐색)

---

📦 핵심 자료구조

priority_queue<PQNode, vector<PQNode>, greater<PQNode>> pq;
vector<vector<bool>> closed;
vector<vector<int32>> best;
map<Pos, Pos> parent;

• pq: 오픈 리스트(발견된 노드들), greater를 통해 F값이 가장 낮은 노드 우선 탐색.
• closed: 클로즈드 리스트(이미 방문한 노드)
• best: 각 노드까지 도달하는 데 드는 현재 최적 비용 저장
• parent: 경로 추적을 위한 부모 노드 정보 저장

---

🔁 알고리즘 실행 흐름 요약

1. 시작 노드 초기화
2. pq에서 최적 후보 추출
3. 방문 처리 및 종료 조건 확인
4. 8방향 이웃 노드 탐색
5. 더 나은 경로 발견 시 정보 갱신
6. 도착점에 도달하면 경로 역추적

---

🧠 방향 정의 및 이동 비용

const int DIR_COUNT = 8;
Pos front[DIR_COUNT] = { ... }; // 상, 하, 좌, 우, 대각선 4방향
int cost[DIR_COUNT] = {10, 10, 10, 10, 14, 14, 14, 14}; // 대각선 비용은 √2 ≈ 1.4 → 14

• 8방향 탐색으로 더 현실적인 경로 탐색 가능
• 상하좌우는 1칸 = 10, 대각선은 루트2 ≈ 14로 설정

---

🔍 코드 분석

1. 시작 및 도착 지점

Pos start = _pos;
Pos dest = _board->GetExitPos();

2. 우선순위 큐에 초기 노드 삽입

int32 g = 0;
int32 h = 10 * (abs(dest.y - start.y) + abs(dest.x - start.x));
pq.push(PQNode{g + h, g, start});
best[start.y][start.x] = g + h;
parent[start] = start;

• h: 맨해튼 거리 사용
• F = G + H를 우선순위로 설정

3. 후보 노드 추출 및 방문 체크

PQNode node = pq.top(); pq.pop();
if (closed[node.pos.y][node.pos.x]) continue;
if (best[node.pos.y][node.pos.x] < node.f) continue;
closed[node.pos.y][node.pos.x] = true;

• 중복 처리 방지
• 더 우수한 후보 경로가 이미 존재한다면 스킵

4. 목적지 도달 검사

if (node.pos == dest) break;

• 도착 지점에 도달하면 탐색 종료

5. 주변 노드 탐색 및 비용 계산

for (int dir = 0; dir < DIR_COUNT; dir++) {
    Pos next = node.pos + front[dir];
    if (!CanGo(next) || closed[next.y][next.x]) continue;

    int32 g = node.g + cost[dir];
    int32 h = 10 * (abs(dest.y - next.y) + abs(dest.x - next.x));

    if (best[next.y][next.x] <= g + h) continue;

    best[next.y][next.x] = g + h;
    pq.push(PQNode{g + h, g, next});
    parent[next] = node.pos;
}

• 이웃 노드를 검사하여 비용을 계산하고, 최적의 경로일 경우 업데이트 및 큐에 삽입

6. 경로 추적 (역방향)

Pos pos = dest;
_path.clear(); _pathIndex = 0;

while (true) {
    _path.push_back(pos);
    if (pos == parent[pos]) break;
    pos = parent[pos];
}
reverse(_path.begin(), _path.end());

• 목적지에서 시작지까지 부모 노드를 따라가며 경로 구성
• 완성된 경로를 반대로 정렬하여 시작 → 도착 순서로 만듦

---

🧪 PQNode 구조

struct PQNode {
    bool operator>(const PQNode& other) const { return f > other.f; }
    int32 f, g;
    Pos pos;
};

• f: 우선순위 결정용 점수 (G + H)
• g: 현재까지의 이동 비용
• pos: 해당 노드 좌표

---

⚙️ 전체 흐름

단계	설명
1️⃣ 초기화	시작 노드의 F, G, H 계산
2️⃣ 큐에서 꺼냄	가장 낮은 F값 노드를 추출
3️⃣ 종료 조건	목적지 도달 시 종료
4️⃣ 탐색	이웃 노드들 검사 및 비용 계산
5️⃣ 최적 경로 기록	더 나은 경로일 경우 업데이트
6️⃣ 경로 추적	부모 노드를 따라 경로 재구성

---

✅ A*, 다익스트라, BFS 차이점

알고리즘	특징
BFS	가중치 없는 그래프 최단 거리
다익스트라	가중치 그래프의 전체 최단 거리
A*	목적지까지의 최적 경로 + 휴리스틱 사용

---