- 해당 글은 UNSEEN 2기 코딩 테스트를 대비하여 정리 목적으로 적은 글입니다. 잘못된 부분이 있다면 지적해 주시면 감사하겠습니다.
게임에서 많이 사용되는 알고리즘을 간단하게 개념 위주로 정리해 보자. 자세한 구현은 한 글에서 다룰 내용은 아닌 것 같아서 개요만 정리했다. 이번 글에서는 A*와 쿼드트리를 다룰 예정이다.
1. A*
A* 알고리즘?
최단 경로를 구하는 알고리즘을 꼽으라면 가장 대표적인 것이 다익스트라(Dijkstra) 알고리즘이다. 하지만 그래프 탐색의 특성상 시간 복잡도가 크기 때문에, 실생활이나 게임에서는 이를 확장시킨 A* 알고리즘을 많이 사용한다.
A* 알고리즘은 주어진 출발 지점에서 목표 지점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다.
하나의 시작 노드에서 다른 모든 노드에 대한 최단 경로를 구하는 다익스트라 알고리즘과 달리 A* 알고리즘은 시작 노드와 목표 노드를 분명하게 정하고 시작한다.
A* 알고리즘이 다익스트라 알고리즘과 다른 점은 바로 휴리스틱 추정값을 사용한다는 점이다.
휴리스틱(Heuristics)이란 최선의 판단하기 어려운 상황에서 어림짐작한 값을 통해 가능한 가장 좋은 해답을 구하는 방법이다. 현실적으로 목표까지 도달하는 모든 경로를 구하기 어려우니, A* 알고리즘에서는 목표 노드까지 거리의 휴리스틱 추정값을 사용해서 어느 경로가 더 나은지를 빠르게 판단한다.
A* 알고리즘은 휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 얼마나 빨리 최단 경로를 파악할 수 있느냐가 결정된다.
알고리즘 방식
A* 알고리즘은 그래프 탐색 알고리즘이다. 그래프는 노드와 간선으로 구성되는데, 각 간선에는 지나갈 때마다 일정한 비용이 필요하다. 우리가 사는 세상으로 비유하면 거리가 되겠다.
A* 알고리즘은 다익스트라 알고리즘에서 확장되었다.
다익스트라 알고리즘은 시작 노드에서 각 노드로 향하는 데에 필요한 최소 비용을 구한다. 시작 노드와 가까운 곳부터 시작해서 점점 더 범위를 넓혀가는 식이다.
A* 알고리즘도 다익스트라와 비슷하지만 목표 노드가 딱 하나로 정해져 있다. 생각해 보면, 경유지를 거쳐서 목적지까지 가는 거리는 (경유지까지의 거리 + 경유지에서 목적지까지의 거리)로 정의할 수 있다.
A* 알고리즘에서도 비슷한 논리로, 시작 노드에서 중간 노드까지 가는 실제 소요 경비 G와 중간 노드에서 목표 노드까지 가는 예상 경비 H의 합을 최소화한다.
- F = G + H
- G = 시작 노드에서 중간 노드까지의 실제 소요 경비
- H = 중간 노드에서 목표 노드까지의 추정 경비
- 부모 노드 = 해당 노드에 도달하기 직전에 거치는 노드 번호
여기서 중간 노드에서 목표 노드까지의 경비 H는 직접 가본 것이 아니므로 휴리스틱 추정값을 사용한다.
이 추정값은 상황에 따라 맞는 것을 사용하는데,
다음 글에서 A* 알고리즘의 예시를 그림을 통해 직관적으로 정리하고 있으니, 읽어보는 것을 추천한다.
최단 경로 탐색 – A* 알고리즘 – GIS Developer
A*에서는 저장소로 O 목록(Open list)과 C 목록(Close list)을 사용한다.
열린 목록인 O 저장소에는 최단 경로를 분석하기 위한 상태값이 계속해서 갱신되고, 닫힌 목록인 C 저장소는 처리가 완료된 노드를 담아두기 위한 목적으로 사용된다.
O는 아직 비용을 계산 중인 노드가 들어있으니 계속해서 갱신되고, C의 노드들은 이미 최단 비용이 계산되어 더 변경되지 않는다.
구체적인 알고리즘 동작 방식은 다음과 같다.
(1) 처음에는 시작 노드에서 인접한 노드를 열린 목록 O에 넣는다. 시작 노드는 닫힌 목록 C에 넣는다.
(2) 목표에 도달하거나 경로가 존재하지 않을 때까지 다음 과정을 반복한다.
- 열린 목록에서 가장 비용 F가 낮은 노드를 현재 노드로 고른다.
- 현재 노드를 열린 목록 O에서 닫힌 목록 C로 옮긴다.
- 현재 노드와 인접한 노드가 닫힌 목록 C에 없다면 열린 목록 O에 넣는다. 이때, 이미 열린 목록에 넣어놨을 수도 있는데, 그러면 더 비용이 낮은 쪽으로 비용과 부모 노드를 갱신한다.
목표 노드에 도달했다면, 그 경로는 부모 노드를 역으로 따라가서 구할 수 있다. 1, 2, 3, 6번을 따라갔다면, 부모 노드를 따라 구한다면 6번, 3번, 2번, 1번 순으로 나오게 된다.
2. 쿼드트리(Quadtree)
쿼드트리는 각 내부 노드에 정확히 4개의 자식이 있는 트리 데이터 구조이다.
2차원 공간을 재귀적으로 4개의 영역으로 분할하는 데 사용된다.
쿼드트리는 자식이 4개인 트리이다.
쿼드트리는 게임에서 2차원 공간의 지형을 저장할 때 사용된다.
쿼드트리를 이용하면 지형 탐색을 위해 컬링을 할 때 연산의 횟수가 줄어 효율적이다.
추가로, 쿼드트리를 사용하면 LOD(Level of details)를 구현하기 쉽다는 장점이 있다.
3차원 공간에서는 하나의 축이 더해져서 자식의 개수가 8개인 팔진트리(octree, 옥트리)를 사용한다.
참고
- A* 알고리즘
A* 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)
휴리스틱 이론 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)
[UNSEEN] 테스트 대비 7. 게임 알고리즘 (velog.io)
- Quadtree
'UNSEEN' 카테고리의 다른 글
| UNSEEN 5. 게임 알고리즘 (2): FSM, BT (1) | 2024.01.30 |
|---|---|
| UNSEEN 대비 4. C++ 주요 컨테이너 (2) (map, unordered_map) (1) | 2024.01.28 |
| UNSEEN 대비 4. C++ 주요 컨테이너 (1) (array, vector, list) (1) | 2024.01.28 |
| UNSEEN 대비 3. 메모리 영역 (1) | 2024.01.25 |
| UNSEEN 대비 2. C++ 언어의 특징 (0) | 2024.01.25 |
댓글