A* 알고리즘

거의 한 2주 동안 A* 알고리즘을 공부하고 프로그래밍 해보았는데, 진짜 많은 걸 배웠다.

---

💡 A* 알고리즘

A* 알고리즘은 일반적으로 2D 타일맵에서 자주 사용되는 길찾기 알고리즘이다. 그러나 2D 타일맵에만 국한되는 것은 아니다. 본질적으로 생성된 노드들을 기반으로 시작 노드부터 목표 노드까지 가장 효율적이고 빠른 경로를 찾아주는 알고리즘이다.

간단히 말해, 최단 경로를 찾기 위한 알고리즘이라고 말할 수 있다.

---

🔥 G / H / F Cost

A* 알고리즘을 이해하려면 세 가지 중요한 값을 알아야 한다. 바로 G, H, F 값이다.

1. G Cost (Cost from Start Node)

   G 값은 시작 노드부터 현재 노드까지의 실제 이동 비용을 나타낸다. 이는 지금까지 걸어온 실제 누적 거리나 비용을 의미한다.

2. H Cost (Heuristic: Estimated Cost to End Node)

   H 값은 현재 노드부터 목표 노드까지의 '예상' 이동 비용을 나타내는 값이다.

   이를 휴리스틱(Heuristic)이라고 부르며, A* 알고리즘의 성능에 가장 큰 영향을 미치는 요소 중 하나이다. 어떤 휴리스틱 함수를 사용하느냐에 따라 알고리즘의 효율성이 크게 달라질 수 있다.

   대표적인 H 값 계산 방법은 두 가지가 있다:

   • 맨해튼 거리 (Manhattan Distance)

     $|x_1 - x_2| + |y_1 - y_2|$

     블록처럼 직각으로만 이동할 수 있는 경우에 주로 사용된다. 택시가 건물 사이를 이동하는 것과 비슷하다고 생각하면 된다.
     

   • 유클리드 거리 (Euclidean Distance)

     $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

     대각선 이동이 가능한 경우에 사용하기 좋다. 두 점 사이의 직선 거리라고 생각하면 된다.

3. F 값 (Total Estimated Cost)

   F 값은 G 값과 H 값을 더한 값이다.

   이 값은 시작 노드부터 목표 노드까지의 '총 예상' 비용을 나타낸다. A* 알고리즘은 이 F 값이 가장 낮은 노드를 우선적으로 탐색한다.

---

🔥 Open List / Closed List

A* 알고리즘이 경로를 탐색할 때 사용하는 두 가지 중요한 리스트가 있다. 바로 Open List와 Closed List이다.

1. Open List (탐색할 노드들)

   Open List는 아직 방문하지 않았지만, 앞으로 방문할 가능성이 있는 노드들을 모아두는 곳이다. A* 알고리즘은 이 Open List에서 F 값이 가장 낮은 노드를 선택하여 탐색을 진행한다.

2. Closed List (탐색 완료 노드들)

   Closed List는 이미 방문했고, 더 이상 탐색할 필요가 없는 노드들을 모아두는 곳이다. 한 번 Closed List에 들어간 노드는 다시 탐색하지 않는다. 보통 노드 검색을 빨리 할 수 있는 해시 셋을 통해 구현한다.

---

🔍 A* 알고리즘 작동 원리

1. 시작 노드를 Open List에 추가한다.

2. Open List가 비어있지 않다면, F 값이 가장 낮은 노드를 Open List에서 꺼내 Closed List에 추가한다. (이 노드를 현재 노드 - Current Node라고 한다.)

3. 만약 현재 노드가 목표 노드라면, 경로를 찾은 것이므로 알고리즘을 종료한다.

4. 현재 노드의 주변 노드들(이웃 노드들)을 확인한다.

   • 만약 주변 노드가 벽이거나 이미 Closed List에 있다면 무시한다.

   • 그렇지 않다면, 현재 노드를 통해 주변 노드까지 가는 새로운 G 값을 계산한다.

5. 계산된 G 값이 기존에 그 주변 노드에 저장되어 있던 G 값보다 작다면 (더 좋은 경로라면):

   • 주변 노드의 G 값을 업데이트하고, H 값을 계산하여 새로운 F 값을 구한다.

   • 이 주변 노드가 Open List에 없다면 Open List에 추가하고, 있다면 정보만 업데이트한다.

6. Open List가 빌 때까지 2단계부터 5단계까지 반복한다. (만약 Open List가 비었는데도 목표 노드를 찾지 못했다면, 경로가 없는 것이다.)

이 과정을 반복하다 보면, A* 알고리즘은 가장 효율적인 길을 찾아내게 된다.

---

✨ 마무리

오늘 포스팅은 간단하게 A* 알고리즘에 대해서만 알아보았다. 다음 포스팅에서는 이를 어떻게 커스터마이징했고 어떤 문제가 발생했고 어떻게 해결했는지 써 볼 것이다.