전략 게임의 유닛이 장애물을 돌아 목적지로 가고, RPG 몬스터가 플레이어를 쫓아오는 데에는 길찾기 알고리즘이 쓰입니다. 그중 A*(에이스타)는 게임에서 가장 널리 알려진 길찾기 알고리즘입니다. 이 글은 A*가 어떤 생각으로 길을 찾는지, 실제 게임에 넣을 때 무엇을 고려하는지 설명합니다.

길찾기 문제를 그래프로 바꾸기

길찾기를 하려면 먼저 맵을 컴퓨터가 다룰 수 있는 형태로 바꿔야 합니다. 가장 쉬운 방법은 맵을 격자로 나누고 각 칸을 지나갈 수 있는지 표시하는 것입니다. 각 칸이 점(노드)이 되고, 이웃 칸으로 가는 길이 선(간선)이 됩니다.

이렇게 만든 그래프에서 출발 칸부터 목표 칸까지 비용이 가장 적은 경로를 찾는 것이 길찾기 문제입니다. 늪이나 언덕처럼 지나가기 힘든 칸에는 비용을 더 높게 줄 수 있습니다.

격자 크기는 정확도와 속도 사이의 선택입니다. 칸을 잘게 나누면 좁은 틈까지 정확히 다룰 수 있지만 칸 수가 늘어 계산이 무거워지고, 크게 나누면 빠르지만 지나갈 수 있는 틈을 놓칠 수 있습니다.

A*의 핵심: g, h, f 세 가지 값

A*는 f 값이 가장 작은 칸부터 살펴봅니다. 다익스트라 알고리즘이 출발점에서 사방으로 고르게 퍼지며 찾는 것과 달리, A*는 h 값 덕분에 목표 쪽으로 기울어 탐색합니다. 그래서 같은 결과를 더 적은 칸만 보고 찾을 수 있습니다.

동작 순서

1. 출발 칸을 열린 목록(앞으로 살펴볼 후보)에 넣습니다.
2. 열린 목록에서 f 값이 가장 작은 칸을 꺼내 닫힌 목록(이미 본 칸)으로 옮깁니다.
3. 꺼낸 칸이 목표라면 탐색을 끝냅니다.
4. 이웃 칸마다 g, h, f를 계산하고, 더 좋은 경로라면 값과 부모 칸을 갱신해 열린 목록에 넣습니다.
5. 열린 목록이 빌 때까지 2번부터 반복합니다. 비면 길이 없는 것입니다.
6. 목표 칸에서 부모 칸을 거꾸로 따라가면 최종 경로가 나옵니다.

열린 목록에서 가장 작은 값을 빨리 꺼내야 하므로 우선순위 큐(힙)를 쓰는 것이 일반적입니다. 자료구조 선택이 길찾기 속도에 직접 영향을 주는 대표적인 사례입니다.

휴리스틱 고르기

• 맨해튼 거리: 가로·세로로만 움직이는 격자에 적합
• 대각 거리(옥타일): 8방향 이동 격자에 적합
• 유클리드 거리: 자유로운 방향 이동에 적합

휴리스틱이 실제 남은 비용보다 크게 어림하지 않으면 A*는 최단 경로를 찾습니다. 일부러 휴리스틱에 가중치를 주면 최단 경로는 아닐 수 있지만 탐색이 훨씬 빨라집니다. 게임에서는 '조금 덜 정확해도 빠른 쪽'을 택하는 경우도 많습니다.

실제 게임에 넣을 때

3D 게임은 격자 대신 내비게이션 메시(내비메시)를 많이 씁니다. 걸어갈 수 있는 바닥을 다각형으로 나누고, 그 다각형들을 노드 삼아 A*를 돌립니다. 유니티와 언리얼 모두 내비메시 기능을 제공합니다.

• 경로 다듬기: 격자 경로는 지그재그가 생기므로 직선으로 갈 수 있는 구간을 합쳐 자연스럽게 만듭니다.
• 계산 나누기: 유닛이 많으면 한 프레임에 모두 계산하지 않고 여러 프레임에 나눠 처리합니다.
• 결과 재사용: 같은 목표로 가는 유닛 무리는 흐름장(Flow Field) 같은 방식으로 한 번에 계산하기도 합니다.
• 회피: 경로를 따라가면서 다른 유닛과 부딪히지 않도록 국지적 회피를 따로 처리합니다.

연습과 학습 경로

먼저 격자 맵에서 BFS로 길을 찾아 보고, 다익스트라, A* 순서로 바꿔 가며 탐색한 칸 수를 화면에 색으로 표시해 보세요. 세 알고리즘의 차이가 눈으로 보입니다. 이후 엔진의 내비메시를 써 보면 내부에서 어떤 일이 일어나는지 이해하기 쉽습니다.

SBS아카데미게임학원 게임프로그래밍 과정은 AI 알고리즘을 포함한 개발 기술을 실습 중심으로 다뤄, 길찾기를 몬스터 AI와 함께 구현해 볼 수 있습니다.

자주 묻는 질문