길 찾기

게임 인공지능에서 가장 기본적이며 광범위함

일상에서의 길 찾기

게임에서의 길찾기

• 캐릭터 : 캐릭터 직접 조작 및 이동
• 유닛 : 자동 게임 진행

길 찾기와 비슷한 기술을 활용하여 게임에 어떻게 적용하는가

문제

캐릭터/유닛이 A지점에서 B지점으로 이동하기 위한 경로를 찾음

• 일직선 이동 불가
• 다양한 요소를 고려하여 길을 생성해야 함
• 게임에서 가장 흔한 인공지능 요소
• 실시간 전략 게임은 많은 수의 유닛이 있기 때문에, 특별히 중요함

예시

1. 언덕을 내려감
2. 앞마당에서 다리까지 감
3. 다리를 건넘
4. 평지를 지남
5. 다리를 건넘
6. 평지를 지남
7. 앞마당을 지남
8. 언덕을 오름
9. 적 본진까지 감

길 찾기 방법

• 최단 경로
  • 짧은 길이 최선인지 고려해야함
  • 상대방의 매복 가능성, 위험 요소, 비용 등
• 자연스러운 경로
  • 사람이 보기에 경로가 자연스러운지 고려해야함
  • 상용 게임에서는 부드럽게 만드는 과정을 별도로 진행함
• 주변 환경을 고려한 경로
  • 주변 캐릭터, 문, 창문, 벽, 강, 바다, 용암, 좁은 길 등
• 캐릭터를 고려한 경로
  • 점프 가능성, 비행 가능성, 도구 활용도, 교통 수단 등

단순한 경우의 길 찾기

• 단일 캐릭터
• 실시간 아닌 턴 기반 게임
• 격자 공간
• 정적 세계

A* 알고리즘이 가장 적절함

복잡한 경우의 길 찾기

• 다수의 캐릭터가 경로가 겹칠 때
• 실시간 게임
• 연속적인 맵
• 동적 세계

다른 형태의 A* 알고리즘을 사용

길 찾기 예제

• 어떻게 게임 맵을 컴퓨터에 표현할 것인가
• 표현된 게임맵에서 어떻게 최단 경로를 찾을 것인가

그래프를 이용한 맵의 표현

격자 형태의 맵의 표현

---

참고 자료

• Red Blob Games

트리 탐색을 이용한 길 찾기

시각화되어 탐구할 수 있는 사이트

너비 우선 탐색

• 장점
  • 경로 탐색을 위한 최단 거리를 찾아냄
  • 비용이 높음
  • 시간이 오래 걸릴 수 있음
• 단점
  • 맵 사이즈에 따라 변동이 크기 때문에 실제 게임에 적용하기에 비효율적임

A* 알고리즘

• 대표적인 탐색 알고리즘
• 휴리스틱 탐색 알고리즘
• 목적지 탐색이 빠르고 효율적임
  • 휴리스틱으로 가이드하여 빠른 탐색
  • 적은 수의 셀을 탐색
• 만약 경로가 존재한다면 반드시 찾아냄
  • 특정 조건을 만족할 경우, 반드시 해를 찾아냄을 보장함
• 단점
  • 새로운 동적 환경에 취약
  • 실시간

휴리스틱

일정 문제를 해결할 때 쓰이는 특수한 솔루션

• 탐색할 때 휴리스틱을 사용함
• 휴리스틱 함수 h(n)은 n으로부터 목적지까지의 거리를 예측함

휴리스틱 함수의 예 - 맨하탄 거리

맨하탄 거리

격자 구조의 거리를 측정

• 장애물은 생각하지 않아도됨
• 거리만 측정하면 됨
• 휴리스틱 값이 실제 두 지점의 경로와 큰 차이가 나지 않으면 됨
• 실제 거리보다 작게만 예측하면 됨

A* 알고리즘

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

$f(n)$, 예측 비용

$g(n)$, 시작에서 n까지의 실제 비용

$h(n)$, 휴리스틱

• Start

  

  시작에서 목표까지 맨하탄 거리가 3이기 때문에, h = 3으로 설정됨
  

• Step 1

  

  • A
    • 시작 지점에서부터 A 지점까지 실제 거리가 1이기 때문에 g = 1
    • A 지점에서부터 목표 지점까지 맨하탄 거리가 2이기 때문에 h = 2
    • g + h = 1 + 2 = 3 이기 때문에, f = 3

• Step 2

  

  • A의 f가 가장 작은 값이기 때문에 A에서 확장
    • A에서 D 밖에 가지 못하기 때문에 D의 값을 계산
    • 이후 B, C, D의 값이 다 동일하기 때문에 가장 먼저 들어온 B를 확장

• Step 3

  

  • B에서는 E만 가능하기 때문에 E의 값을 계산
  • C, D, E 중에서 f의 값이 작은 C, D가 가장 작고, C가 가장 먼저 들어왔기 때문에 C를 확장

• Step 4

  

  • C에서는 F, G를 갈 수 있기 때문에 둘 다 계산
    • D, E, F, G 중 D, E의 값이 가장 작고 D를 먼저 확장

• Step 5

  • D에서는 갈 곳이 없음
  • 나머지 안 간 세 곳 중 가장 작은 값을 가진 F를 확장

• Step 6

  

  • F에서는 왼쪽(J)과 아래(I)를 갈 수 있기 때문에 이 둘을 계산함
  • 계산을 해보니 기존에 있는 값들보다 f(n) 값이 작은 값이 생김 = J
    • 이는 그래프 탐색 중 BFS와는 다른 특징

• Step 7

  

  • L이 가장 작기 때문에 이를 확장

• Final

  

BFS과 A* 알고리즘 비교

공통점

• 결과적으로 경로가 동일함

차이점

• 탐색한 노드의 수
  • BFS : 전체
  • A* : 14
• 확장한 노드의 수
  • BFS : 전체
  • A* : 9