게임 인공지능 | 게임 인공지능의 길찾기 - 2주차 강의 정리

이 글은 게임 인공지능 강의 2주차 내용을 정리한 것입니다.

게시 2025/06/14

By Shin Min Geun

8 분읽는 시간

게임에서 길찾기가 중요한 이유

길찾기는 게임 인공지능에서 가장 기본적이면서도 광범위하게 사용되는 기술이다. 우리가 일상에서 지도 앱으로 쉽게 길을 찾듯이, 게임 속 캐릭터들도 목적지까지 최적의 경로를 찾아야 한다.

게임에서의 길찾기 특징

플레이어 캐릭터 조작: 직접 이동시키거나 자동으로 경로를 찾아 이동한다
실시간 처리: 게임에서는 즉시 경로를 계산해야 하므로 속도가 핵심이다
복잡한 지형: 언덕, 다리, 장애물 등을 고려한 경로 생성이 필요하다
다양한 제약사항: 일직선 이동이 불가능한 복잡한 환경을 다룬다

길찾기에서 고려해야 할 요소들

경로의 종류

최단 경로: 단순히 짧은 길이 항상 최선은 아니다
- 적의 매복 가능성
- 위험 요소와 비용 고려
자연스러운 경로: 사람이 보기에 자연스러운 움직임
- 상용 게임에서는 경로를 부드럽게 만드는 후처리 과정이 필수다
환경을 고려한 경로: 주변 상황 분석
- 다른 캐릭터, 문, 벽, 강, 좁은 길 등
캐릭터 특성 반영: 개별 능력 고려
- 점프 가능 여부, 비행 능력, 도구 활용, 교통수단 등

💡 현실의 한계: 여전히 많은 게임에서 경로 탐색 실패나 부자연스러운 움직임 버그가 존재한다.

길찾기 문제의 복잡도

단순한 경우 (A* 알고리즘으로 해결 가능)

✅ 단일 캐릭터
✅ 턴제 게임 (실시간이 아님)
✅ 격자 공간 (타일 기반)
✅ 정적인 환경

복잡한 경우 (고급 A* 변형 필요)

❌ 다수 캐릭터 (경로 겹침 발생)
❌ 실시간 게임
❌ 연속적인 공간
❌ 동적인 환경

맵을 컴퓨터에 표현하는 방법

1. 그래프 표현

각 방을 노드(Node)로 표현한다
연결된 경로를 엣지(Edge)로 연결한다
간단하지만 정밀도가 떨어질 수 있다

2. 격자 표현

맵을 정밀한 격자로 분할한다
더 자연스러운 경로 생성이 가능하다
계산 복잡도가 증가한다

너비 우선 탐색 (BFS)의 한계

작동 방식

시작점을 루트 노드로 설정한다
가장 가까운 지점들을 순서대로 탐색한다 (상하좌우)
목표 지점을 찾을 때까지 반복한다

장단점

장점:

✅ 최단 경로를 보장한다

단점:

❌ 높은 계산 비용
❌ 불필요한 영역까지 모두 탐색한다
❌ 긴 탐색 시간

A* 알고리즘: 게임 AI의 핵심

A* 알고리즘은 게임 인공지능에서 가장 널리 사용되는 휴리스틱 탐색 알고리즘이다.

핵심 개념: 휴리스틱 함수

휴리스틱(Heuristic): 완벽하지는 않지만 문제 해결에 도움이 되는 추정 방법

A* 알고리즘의 공식

f(n) = g(n) + h(n)

g(n): 시작점에서 현재 노드까지의 실제 비용
h(n): 현재 노드에서 목표까지의 예상 비용 (휴리스틱)
f(n): 총 예측 비용

맨하탄 거리: 대표적인 휴리스틱 함수

격자 구조에서 두 점 사이의 거리를 계산하는 방법:

맨하탄 거리 = |x1 - x2| + |y1 - y2|

특징:

장애물을 무시하고 계산한다
실제 거리보다 작거나 같아야 최적 경로를 보장한다
간단하고 빠른 계산이 가능하다

A* 알고리즘 작동 과정

단계별 실행

초기화: 시작점에 f, g, h 값을 설정한다
노드 확장: 이동 가능한 인접 노드들의 값을 계산한다
우선순위 선택: f값이 가장 작은 노드부터 확장한다
반복: 목표 지점을 찾을 때까지 계속한다
경로 추적: 목표 지점에서 시작점까지 역추적한다

탐색 패턴의 차이

너비 우선 탐색: 시작점 중심의 원형 확장
A* 알고리즘: 목표 지향적 타원형 확장

A* 알고리즘의 장점과 한계

장점

✅ 최적 경로를 보장한다 (조건 만족 시)
✅ 효율적 탐색: 불필요한 노드를 배제한다
✅ 널리 검증됨: 게임 업계 표준 알고리즘

발전 방향

동적 환경 대응: 실시간으로 변하는 맵을 처리한다
실시간 처리: 더 빠른 계산을 위한 최적화
다중 캐릭터: 여러 유닛의 동시 이동을 처리한다

실습해볼 수 있는 도구들

길찾기 알고리즘을 직접 체험해보고 싶다면:

PathFinding.js: 다양한 탐색 알고리즘 시각화 도구
Red Blob Games: 게임 개발 관련 상호작용 튜토리얼
Mapbox: 실제 지도 데이터를 활용한 길찾기 서비스

마무리

A* 알고리즘은 40년이 넘는 세월 동안 게임 개발의 핵심 기술로 자리잡았다. 단순한 격자 게임부터 복잡한 3D 오픈월드까지, 거의 모든 게임에서 캐릭터들이 똑똑하게 움직일 수 있는 것은 바로 이 알고리즘 덕분이다.

물론 완벽한 알고리즘은 아니다. 실시간 처리, 동적 환경, 다중 캐릭터 등 해결해야 할 과제들이 여전히 남아있다. 하지만 기본 원리를 이해하고 있다면, 게임 속 AI가 어떻게 동작하는지 한층 더 깊이 이해할 수 있을 것이다.

A* 알고리즘에 대해 정말 쉽게 알아갈 수 있었다. 시간이 되는되로 A* 알고리즘을 실제로 구현해보고, 게임에서 어떻게 활용되는지 등 자세히 살펴봐야겠다는 생각이 들었다.

Study, Study\GameAi

AI Game AI 강의정리 STAR-MOOC