A* 알고리즘

내일배움캠프 65일차 TIL

✨ 오늘 내가 배운 것

 

오늘은 경로 탐색 알고리즘 중에서 *A(A-Star) 알고리즘에 대해 공부했다. 시작점에서 목표 지점까지 가장 효율적으로 최단 경로를 찾아주는 이 알고리즘이 어떻게 작동하는지, 그리고 우리 게임에 어떻게 적용할 수 있을지 고민해 보는 시간이었다.

 

A* 알고리즘이란?

A*는 그래프 기반 탐색 알고리즘으로, 시작점에서 목표 지점까지 가장 비용이 적은 경로를 찾아준다. 단순히 주변을 탐색하는 것을 넘어, 휴리스틱 함수(Heuristic)라는 예상 비용을 활용해서 탐색 효율성을 엄청나게 높인다는 점이 가장 큰 특징이었다.
나는 A*가 마치 BFS의 정확성과 DFS의 속도를 절충한, 정말 스마트한 길 찾기 알고리즘이라고 생각했다.

 

작동 원리

A*는 f(n) = g(n) + h(n)이라는 간단하면서도 강력한 공식으로 작동한다.

• f(n): 시작점에서 목표까지의 총 예상 비용이다. 이 값이 가장 낮은 노드부터 우선적으로 탐색하게 된다.
• g(n): 시작점에서 현재 노드까지의 실제 비용이다. 이미 지나온 길의 실제 거리라고 생각하면 이해가 쉬웠다.
• h(n): 현재 노드에서 목표까지의 휴리스틱(예상) 비용이다. 아직 가지 않은 길이지만, 목표까지 대략 얼마나 걸릴지 예측하는 값이다.

사용 자료구조: A*를 구현할 때 필요한 핵심 자료구조는 다음과 같다는 것을 알았다.

• Open List: 아직 방문하지는 않았지만, 앞으로 탐색할 후보 노드들을 담는 곳이다. 보통 f(n) 값이 낮은 순서대로 꺼내야 하므로 우선순위 큐로 구현하는 것이 효율적이라고 배웠다.
• Closed List: 이미 방문을 완료한 노드들을 담는 곳이다. 다시 방문하지 않도록 표시하는 역할을 한다.
• Parent Map: 각 노드가 어떤 노드를 통해서 왔는지 기록하는 지도다. 나중에 최단 경로를 역추적할 때 사용한다.

 

간단한 흐름:

1. 시작 노드를 Open 리스트에 넣고 탐색을 시작한다.
2. Open 리스트에서 f(n) 값이 가장 낮은 노드를 꺼낸다.
3. 만약 꺼낸 노드가 목표 지점이라면 탐색을 끝낸다.
4. 목표가 아니라면, 해당 노드와 인접한 노드들을 살펴본다. 각 인접 노드에 대해 g, h, f 값을 계산하고 Open 리스트에 추가한다.
5. 만약 이미 방문했던 노드이거나, 새로 계산한 비용이 더 비싸다면 무시한다.
6. 이 과정을 Open 리스트가 빌 때까지 계속 반복한다.

휴리스틱 함수란?

휴리스틱 함수는 A* 알고리즘에서 경로를 더 빠르게 찾기 위한 예상 비용 계산 함수다. 정확성보다는 속도에 중점을 둔 근삿값을 제공하는 것이 특징이다.

대표 휴리스틱 종류: 내가 공부한 대표적인 휴리스틱 함수들은 다음과 같다.

• 맨해튼 거리 (Manhattan Distance): |dx| + |dy|로 계산한다. 주로 상하좌우로만 이동 가능한 격자 맵(예: 체스판)에서 사용한다.
• 유클리드 거리 (Euclidean Distance): √(dx² + dy²)로 계산한다. 대각선 이동이 가능한 경우에 사용하면 좋다. 실제 직선 거리와 가장 유사하다.
• 체비쇼프 거리 (Chebyshev Distance): max(|dx|, |dy|)로 계산한다. 대각선 이동 비용과 상하좌우 이동 비용이 같은 경우(예: 킹의 이동)에 사용한다.

장점과 단점

A* 알고리즘의 장점과 단점을 정리해보았다.

장점

• 최단 경로 보장: 조건만 잘 맞으면 항상 최단 경로를 찾아준다는 점이 큰 매력이었다.
• 유연성: 다양한 휴리스틱 함수를 적용해서 상황에 맞게 커스터마이징할 수 있다.
• 최적성과 효율성의 균형: 최단 경로를 보장하면서도 탐색 효율성을 높여준다는 것이 A*의 가장 큰 강점이라고 생각했다.
• 격자 기반 맵에 최적화: 우리 게임처럼 격자 기반 맵이라면 A*가 정말 잘 어울린다고 느꼈다.

단점

• 연산량 급증: 장애물이 많거나 맵이 복잡해질수록 계산량이 급격히 늘어날 수 있다.
• 실시간 환경에서의 부담: 매우 빠르게 변하는 실시간 환경에서는 성능 부담이 될 수도 있다.
• 부자연스러운 Path: 비정형 지형에서는 찾아낸 경로가 다소 부자연스러워 보일 수도 있다.
• 구현 복잡도: 다른 간단한 탐색 알고리즘에 비해 구현이 조금 더 복잡한 편이다.

Unity의 NavMesh와 비교

Unity에서 길 찾기를 할 때 A*와 함께 많이 사용하는 NavMesh와 비교해 보았다.

항목	A*	NavMesh
구조	노드 기반 (그리드, 그래프 등)	삼각형으로 이루어진 네비게이션 메시
탐색 대상	격자, 그래프 기반 오브젝트	미리 Bake된 Unity Terrain 또는 Mesh
장점	커스터마이징 용이, 코드 제어 가능	성능 좋고 자동화 편리, 벽 타기 방지
단점	성능 이슈 가능성, 직접 구현 필요	지형 수정 시 다시 Bake해야 함
실시간 수정	직접 구현해야 함	NavMesh Modifier, Surface로 일부 지원
사용 예	턴제 게임, 타일 기반 게임	3D 오픈월드, AI NPC 탐색

 

실제 현장에서의 사용 경향

A*와 NavMesh는 각각 장단점이 명확해서, 게임의 종류에 따라 선호되는 방식이 다르다는 것을 알았다.

2D 격자 기반 게임 (예: 타워디펜스, 로그라이크):

A*를 선호한다. 격자 시스템과 잘 어울리고, 휴리스틱 튜닝이 용이하기 때문이다. 우리 게임처럼 2D 탑다운 서바이벌 게임에 딱이라고 생각했다.
3D 오픈월드 (예: RPG, 시뮬레이션):
NavMesh를 선호한다. 한 번 Bake 해두면 자연스러운 경로를 쉽게 찾을 수 있기 때문이다.
장애물 동적 생성, 실시간 환경:
혼합 방식을 사용한다. Unity의 NavMesh는 실시간 장애물 처리(Obstacle, Modifier)를 지원하기 때문에, 이를 활용하면서 필요에 따라 A*를 보조적으로 사용하는 경우가 많다.
다수 유닛의 독립 경로 탐색:
이 경우 A는 성능에 주의해야 한다. 많은 유닛이 동시에 A를 돌리면 퍼포먼스 문제가 발생할 수 있다.

A*를 사용할 때 고려할 것들

A*를 실제로 구현할 때 신경 써야 할 점들을 정리해보았다.

• 격자 크기 조절: 맵의 격자 크기를 너무 작게 하면 연산이 많아지고, 너무 크게 하면 경로가 부자연스러울 수 있다. 적절한 크기를 찾는 것이 중요하다고 느꼈다.
• 캐싱: 이미 탐색했던 동일한 경로는 다시 계산하지 않고 캐싱해서 재탐색을 최소화해야 한다.
• 우선순위 큐: f(n) 값이 낮은 노드를 효율적으로 꺼내기 위해 MinHeap 같은 자료구조를 사용하는 것이 좋다고 배웠다.
• 시각화: 디버깅을 위해 Open/Closed 리스트의 노드들을 Gizmo 등으로 시각적으로 표현하면 문제점을 찾기 훨씬 수월할 것이라고 생각했다.

 

느낀 점

A*는 경로 탐색 알고리즘 중에서 가장 직관적이면서도 강력한 도구였다. 단순히 공식만 외우는 것이 아니라, 직접 구현하며 다양한 휴리스틱과 우선순위 큐 최적화 등을 테스트해보니, 단순한 알고리즘이라고 가볍게 볼 수 없다는 것을 깨달았다.

Unity 프로젝트에서는 A와 NavMesh를 상황에 따라 적절히 혼용하는 전략이 필요하다고 느꼈다.

 

🧠 기억 포인트

• f(n) = g(n) + h(n): A* 알고리즘의 핵심 비용 계산 공식이다.
• 정확성 + 효율성: 최단 경로를 보장하면서도 효율적인 탐색을 가능하게 하는 이상적인 알고리즘이다.
• Unity 2D 게임 = A / Unity 3D 게임 = NavMesh 선호*: 각 환경에 맞는 최적의 선택이 있다.
• 복잡도 주의: 노드 수가 많아질수록 연산량이 급증할 수 있으니 주의해야 한다.
• 휴리스틱 함수: 예상 비용을 계산하며, 상황에 따라 유연하게 설정할 수 있다.