[실용적 예제로 본 게임 인공지능 프로그램하기] 5. 그래프의 비밀(최단거리탐색)
목표지점 까지의 최단거리를 탐색하는 방법을 공부하는 챕터 입니다. 이 장에서는 DFS, BFS, Dijkstra, A* 알고리즘에 대해 배우고 이 알고리즘들이 게임에서 어떻게 사용되는지 배웁니다.
게임에서 그래프는 다양한 곳에 쓰입니다. 그저 이동 뿐만 아니라 RTS 장르의 게임처럼 어떤 건물을 짓기 위해서 테크트리를 표현하는 데에 사용하던가, 퍼즐풀기 같은 곳 더 나아가 네트워크나 인공신경망에 이르기까지 여러 분야에서 이용이 됩니다.
그래프는 노드와 엣지로 이루어 집니다.(정점과 간선) 많은 그래프는 가중치를 갖는 간선을 가지며, 이들은 한 노드에서 다른 노드까지 움직이는 비용에 대한 정보를 표시합니다. 스타크래프트 같은 RTS 장르의 게임에서는 간선은 각 유닛을 향상시키기 위해 필요한 자원을 나타낼 것입니다.
게임 AI 에서의 그래프
다음은 게임 인공지능 개발에서 그래프를 사용할 수 있는 몇가지 경우 입니다.
- 항해 그래프
- 종속 그래프
- 상태 그래프
항해그래프는 게임 에이전트가 방문할 수 있는 게임환경의 모든 장소와 그 지점들 사이의 모든 연결을 나타냅니다. 즉 지점 A에서 지점 B로 가는 빠른 방법을 결정할 수 있는 그래프 입니다.
간선 형태의 항해그래프
위 그림은 노드에 간선을 연결하는 그래프로 이루어 졌습니다. 보시면 A에서 B로 가기위해 거쳐야 하는 정점과 간선이 그대로 path가 되는 것이죠. 늪지대, 강가 등 거리는 가까우나 늪지대 등을 지나려면 속도가 늦어집니다. 따라서 최단경로가 아닐 수 있습니다. 이를 표현하기 위해 늪지대 부분은 간선의 가중치를 낮게 줍니다.
이런 방식이 있는 반면, 모든 맵이 격자(셀) 형태로 이루어진 항해그래프도 있습니다.
셀 기반 형태의 항해그래프
셀 기반 항해그래프에서 늪지대 등을 표현하기 위해서는 늪지대 타일로 가는 것은 가중치를 더 낮게 주게 되면(즉, 비용을 더 높게 준다면) 그 타일은 피해 갈 것입니다.
종속그래프는 여러 빌딩, 물자. 유닛과 선수에 적용될수 있는 기술들 사이의 종속성을 표현하기 사용됩니다. 종속그래프는 AI가 전략을 결정하기 위해, 적의 미래 상태를 예측하기 위해, 그리고 자원을 효율적으로 할당하기 위해 사용할 수 있기 때문에 이러한 장르를 위한 AI를 디자인 할 때 유용합니다.
출처 : 블리자드
상대 팀의 공성전차가 우리 진영으로 들어왔다면, 이를 기반으로 공성전차의 종속성을 찾습니다. 공선전차가 있다면, 군수공장이 있단 뜻이고 이를 파괴하기 위해 군수공장의 부모 노드인 병영을 파괴하기 위해 암살자를 생성하는데에 자원을 쏟을 수도 있습니다.
또한, 어떤 유닛을 생성하게 되면 승리가 거의 확실시 되는 상황이라면 그 유닛을 뽑기 위한 최단거리를 나타낼 수도 있습니다. 이때는 각 자원을 만드는 비용이 간선에 할당되어야 합니다.
상태그래프는, 그래프가 분기 했을 때 어떤 상태를 가질 수 있는지 전부 보여주는 것 입니다. 예를 들면 하노이 탑에서 각 재귀마다 각 기둥이 어떤 모습을 갖는지 알려주는 것 입니다. 하지만 이때 모든 분기를 보여주기 위해서는 메모리가 절대적으로 부족하고 아깝습니다. 따라서 Promising(유망성)을 검사하거나 Best Branch First 탐색을 하는 등의 기법이 있습니다. 위 방법은 Backtracking 알고리즘에 기반하므로 궁금하신 분들은 검색해 보는것도 괜찮을 것입니다.
DFS와 BFS
DFS와 BFS는 한 그래프가 주어졌을때 탐색하는 방법입니다. 혹시 독자님들께서 이 개념을 모르신다면, 매우 유명한 알고리즘이고 인터넷에 정보가 많기 때문에 익히는데 어렵지 않을 것입니다. 이 두 방법을 사용하기에는 최악의 경우 모든 노드와 간선, 셀을 검사하게 되므로 시간이 매우 오래걸릴 수도 있다는 단점이 있습니다.
DFS에서는 이를 방지하기 위해 어느정도 깊게 들어가면 그만 찾는 방법으로 최악의 경우를 면하기도 합니다.
다익스트라 알고리즘과 A* 알고리즘
다익스트라 알고리즘은 다른 블로그에서 설명이 잘 되어 있기 때문에 자세한 설명은 진행하지 않겠습니다. 다익스트라 방법은 결과적으로 현 위치에서부터 모든 정점까지의 최단거리를 알 수 있습니다.
따라서 다익스트라 알고리즘은 주로 맵에 산발되어 있는 아이템 팩, 힐링 팩 등 까지의 위치를 계산하는 데에 사용합니다.(아이템 팩은 맵에 흩뿌려져 있을 것이므로).
A* 알고리즘은 기본 원리는 다익스트라 알고리즘과 비슷하지만, 우선순위 큐에 넣을 때 단순 가중치가 아닌 휴리스틱 가중치를 넣는 것입니다. 휴리스틱 가중치란(유클리디언 거리를 사용했을때) 지금 지점부터 목표 지점까지의 직선거리를 기준으로 PQ에 넣음을 의미합니다. 자세한 가중치 F는 다음과 같습니다.
F = G + H
H는 휴리스틱 가중치, G는 노드에 이르는 누적 비용(다익스트라와 같음)
A*알고리즘은 최적이라는 것이 증명되었으며, 다익스트라 알고리즘과는 달리 단일 목표지점까지의 최단거리를 찾는 데에 사용이 됩니다.
매 순간 길찾기 알고리즘을 사용하면 많은 연산으로 인해 프레임이 떨어지는 일이 생길수도 있습니다. 이때 미리 계산된 비용 을 사용해서 사전에 거리를 전부 계산해 두던가, 아니면 시간별 경로 계획하기 를 통해 여러번의 길찾기 알고리즘 전체를 1개의 요청 후에 다음 요청을 처리하는것이 아닌, 각 프레임 단계별로 전체의 일부분을 실행하는 것 입니다. 이때 일부분이라함은 우선순위큐의 top을 꺼내고 그 원소에 연결된 것들의 최단거리를 갱신하는 것 입니다. 마지막으로는 계층적 경로찾기가 있는데, 이는 맵 전체를 몇개의 지역으로 나눈 후, 현재 지역내에서는 길찾기 알고리즘을 실행하고, 다음으로 방문할 지역은 대략적인 위치만 나타내는 것 입니다.
그래프는 우리 상상 이상으로 많은 곳에 쓰이고 특히 AI프로그래머로서 잘 알아야 하는 개념이라고 생각됩니다.
이상으로 그래프 포스팅을 마치겠습니다.
댓글
댓글 쓰기