왜 드라군만 유독 멍청할까? (심화편) | 온라인 게임 내 패스파인딩 문제 복잡성 겉 핥기

출처: MS Bing Image Creator, getimg.ai

 

유튜브를 보다가 前 스타크래프트 프로게이머 "흑운장" 이성은 님의 채널에서 되게 흥미로운 영상을 본 적이 있다. 스타크래프트의 유닛들이 멍청해 보이게 행동하는 이유에 대해서 설명하는 영상이었고, A* 알고리즘과 같이 기술적으로도 깊이가 어느 정도 있는 주제도 다뤄서 시청자 입장에서 엄청 재밌게 봤던 영상이었다. (참고: 흑운장 패스파인딩 시리즈 1부, 2부)

출처: 흑운장 채널

 

하지만, 게임 개발 쪽 출신은 아니시다 보니, 스타크래프트를 플레이하는 입장에서 경험하고 공부한 내용들로 설명이 이루어져 기술적 측면의 깊은 이해가 필요한 부분들에서는 설명이 미흡했던 부분들이 몇몇 있었다. 가령 A* 알고리즘의 구체적인 특성들이라든지, 혹은 덩치 큰 지상 유닛들 중에서 유달리 드라군이 멍청해 보이는 이유라든지... 그래서 패스파인딩에 대해 궁금증이 생긴 기념으로 공부를 간단히 해보았고, 다음과 같은 항목들을 조사해 보았다:

1. A* 알고리즘이 낡고 안 좋은 알고리즘인 걸까?
2. 동적 다중 에이전트 패스파인딩의 복잡성
3. 그래서 왜 드라군만 유독 멍청할까?

※ 이 이후부터는 개인적인 조사내용과 해석이 들어가 있어, 보다 자세하고 정확한 정보를 원하시는 분들은 본문 내 링크들을 통해 원문을 읽고 각자 판단해 주시길 바랍니다.

 

1.

듄 II(1992), 워크래프트(1994), 커맨드 앤 컨커(1995)와 같은 옛날 클래식 게임들부터 최근 인기 있는 리그오브레전드(2009)까지, 패스파인딩 알고리즘은 정말 다양한 온라인 게임에 요구된다. "패스(path)" "파인딩(finding)" — 즉 길을 찾아서 이동해야 하는 — 기능이 요구되는 게임에는 다 들어가는 것이다. FPS, AOS(MOBA), RPG 등 장르에서 플레이어가 직접 조작하는 단일 캐릭터들 혹은 그 단일 캐릭터들을 상대하기 위해 조작되는 AI 봇들에도 목적지까지 길을 찾아 이동하는 기능이 필요하고, RTS, MMORPG 등 장르에서 한 곳을 향해 다 같이 움직이는 병력 및 몬스터들에도 해당 기능이 필요하다.

 

"온라인 게임 패스파인딩"에 대해 검색하면 A* 알고리즘과 이 A* 알고리즘이 어떻게 다른 패스파인딩 알고리즘들이랑 다른지에 대한 비교자료들이 많이 나온다. 흔히 A* 알고리즘의 비교 상대로는 대학 알고리즘 수업에 단골손님으로 등장하는 DFS/BFS 및 다익스트라 알고리즘이 등장하곤 한다.

 

Depth-First Search (DFS), 깊이 우선 탐색

 

프랑스 수학자 찰스 피에르 트레마욱스(Charles Pierre Trémaux)가 19세기에 미로 탐색 문제에 대한 해답으로 제안한 방법이다. DFS는 분기점을 만나면 한 경로를 끝까지 따라가 본 후 다른 경로를 시도하기 전에 이전의 교차점으로 되돌아가는 방식으로 그래프를 탐색한다. 석유를 찾고자 하는 채굴자가 한 번에 한 우물만 파는 것에 비유할 수 있다. (최대한 깊이 내려가고, 석유를 찾지 못하면 다시 올라와서 다른 우물을 파는 것과 비슷하다.)

DFS는 그래프의 완전한 순회가 필요한 시나리오에 특히 유용하지만, 깊이를 우선시하기 때문에 반드시 최단 경로를 먼저 찾지는 않는다. 디트로이트: 비컴 휴먼(2018) 게임의 모든 엔딩을 보겠다고 마음먹은 게이머가 매 회차마다 다른 선택을 해서 모든 엔딩을 본다고 한다면, 이 게이머가 게임의 전체 스토리 구조를 잘 파악할 수 있겠다고는 기대할 수 있겠지만, 가장 짧은 엔딩을 빨리 찾으리라고는 쉽게 기대하기 어려운 것과 마찬가지다. 따라서, 최단 경로 탐색 기능이 필요한 온라인 게임에서 패스파인딩 알고리즘으로는 선호되지 못하는 것으로 보인다.

 

Breadth-First Search (BFS), 너비 우선 탐색

 

1900년대 중반에 등장한 BFS는 DFS와 상반되는 접근법을 이용한다. 석유를 찾는 채굴자 비유를 다시 들자면, 팔 수 있는 모든 우물을 동시에 파내려 가는 것에 비유할 수 있다. 계층별 탐색 원리를 사용하여 출발 노드로부터 주변 노드로, 그리고 그 주변 노드로 확장해 나가는 방식으로 작동하는 것이다.

BFS는 도달 가능한 노드에 대한 최단 경로를 가중치가 없는 그래프에서 가능한 경로를 체계적으로 탐색하여 우선적으로 찾을 수 있게 해 준다. 모든 이동 비용이 같은 무가중 그래프에서는 항상 가장 짧은 경로를 먼저 찾을 수 있게 보장하는 효과적인 방법이다.

참고로, BFS를 속도적인 측면에서 개선한 탐욕적 너비 우선 탐색(Greedy BFS) 알고리즘도 있는데, 탐욕적 너비 우선 탐색의 경우는 "석유 탐지기"를 들고 파내려 가는 것에 비유할 수 있다. 탐지기가 석유에 가깝다고 하는 방향부터 우선적으로 파내려 갔다가, 팔 수 없는 장애물을 만나면 그 지점부터 너비 우선 탐색을 실시하고, 석유와 가까워지는 방향이 다시 탐지기에 나타나면 또 그 방향 먼저 파내려 가는 것과 비슷하다. 이 경우에는 기본 BFS와는 달리 항상 제일 짧은 경로를 찾는다는 보장이 없고, 특히 장애물이 있을 때 더 돌아갈 확률이 높다.

 

Dijkstra's algorithm, 다익스트라 알고리즘

 

네덜란드 컴퓨터 공학자 에츠허르 비버 다익스트라(Edsger Wybe Dijkstra)에 의해 1956년에 고안된 다익스트라 알고리즘은 가중 그래프를 처리할 수 있도록 BFS 접근 방식을 확장한다. 또다시 석유 채굴자 비유를 들자면, 이번엔 지반의 경도가 고르지 않은 것과 비슷하다. 이런 환경에서는 단계별 목적지를 향해 나아갈 때, 조금 더 파기 수월한 경로가 있을 것이다. 다익스트라 알고리즘은 중간 목적지에 대한 최단 경로가 한번 계산되면, 해당 중간 목적지까지의 최단 경로를 다시 찾지 않는 방식으로 작동한다.

 

A* algorithm, 에이-스타 알고리즘

 

쉐이키(Shakey)라는 로봇의 개발 과정에서 고안된 A* 알고리즘은 1968년에 처음 등장했다. A*는 탐색 과정에 휴리스틱(=간편법)을 도입한다는 설명이 인터넷 곳곳에서 자주 발견되는데, 한 블로그 글(시각화 자료가 너무 잘 되어 있어 꼭 한번 읽어보기를 추천.)에서는 A* 알고리즘을 다익스트라와 탐욕적 너비 우선 탐색의 특성들을 합친 알고리즘으로 소개한다.

또또 다시 석유 채굴자 비유를 들자면, 다익스트라 알고리즘과 같이 중간 목표 지점까지 가장 파내려 가기 쉬운 길을 찾아가면서, 탐욕적 너비 우선 탐색에서 사용됐던 "석유 탐지기"를 참고하는 것이다.

이 경우, 다익스트라 알고리즘처럼 최단 거리를 찾기도 유용하며, 탐욕적 너비 우선 탐색처럼 속도도 향상된다는 장점이 있다. 많은 현대 패스파인딩 알고리즘들이 A*를 기반으로 개발되는 이유가 이 정확성과 속도에 있다.

 

(추천 자료: DFS, BFS, Dijkstra, A* 알고리즘 비교 영상)

 

여기까지 글을 읽었다면, 최소한 "길을 찾는 방법이 여러 가지가 있다"는 사실은 이해했을 것이다. 하지만, 이를 게임에 적용 시 문제가 발생하는 데, 온라인 게임의 환경 상 대부분의 경우 이렇게 정적인 맵에서 단일 대상을 움직이는 것이 아니라 여러 대상이 서로의 길을 가로막으며 제갈길을 가려고 하는 환경에 놓이게 된다는 것이다. 아는 것도 없으면서 괜히 유식해 보이는 척해보자면, 이는 "Dynamic Multi-agent Pathfinding" 과제라고 할 수 있다. 

2.

위에서 살펴본 알고리즘들은 모두 단일 대상이 특정 방식으로 경로를 계산 후 이동하는 방식에 대해 다루고 있다. 하지만 이 알고리즘들을 이용했을 때, 계산 당시에는 없었던 또다른 대상이 먼저 중간 목적지에 와서 길을 막아버리는 경우에 대해서는 대응 방법이 없다. 즉, A*가 아니라 A* 할아버지가 오더라도 단순 패스파인딩 알고리즘으로는 계산이 완료된 후 이동하다가 길이 갑자기 막혀버리는 경우에 대해서는 할 수 있는 것이 없는 것이다. (새로 경로를 계산하는 것 외에는)

출처: youtu.be/t2PXgu3G91E (좌 - 2:15, 우 - 2:49)

 

흑운장 패스파인딩 시리즈 1부 영상의 이 두 장면을 보면, 스타 유닛들은 이동 중에 장애물의 변경 유무를 고려하지 않고 그대로 처음 계산한 경로대로 움직인다는 것을 유추할 수 있다. 이동 중에 특별한 문제가 없다면 패스파인딩 알고리즘을 한 번만 돌려서 도출된 경로대로 움직이는 것이다.

출처: youtu.be/t2PXgu3G91E (3:17)

 

영상의 다음 실험을 보면 이동 중에 경로 상 장애물이 생기는 경우, 스타 유닛이 어떻게 행동하는 지를 볼 수 있다. 초기 경로대로 움직이다가 진행이 불가능해지면 충돌 이후 다시 경로를 계산해서 이동하는 것이다.

이를 응용해보면, 여러 유닛들이 이동하다가 서로 부딪히는 경우, 그리고 좁은 내리막길에 병목 현상이 생겨 무리의 뒤쪽 유닛들이 진행할 수 없는 경우, 경로를 재탐색한다는 것을 알 수 있다. (그리고 경로를 재탐색해서 이상하게 돌아가는 유닛들에게 광클로 다시 명령을 내려줘야 하는 이유도 알 수 있다.) 특정 유닛 종류에 국한된 문제가 아니라 모든 유닛들이 공유하는 문제인 것이다.

 

출처: youtu.be/2ErJY5cbgHY (1:01)

 

흑운장 패스파인딩 시리즈 2부 영상을 이어서 보면 리전에 대해서 소개하는데, 패스파인딩 알고리즘에 대해 공부를 조금 해보면 자주 등장하는 내비게이션 매쉬(NavMesh)의 개념과 밀접한 시스템으로 생각된다. 영상을 잘 보면, 이동 가능한 리전들끼리 초록색 선으로 연결되어 있고, 이동 불가능한 리전들끼리 빨간색 선으로 연결되어 있는 것을 볼 수 있는데, 이를 통해 각 리전 간 거리가 미리 계산되어 있다는 것을 예상해 볼 수 있다.

A* 알고리즘이 무겁다는 것이 흑운장 영상에서도, 패스파인딩 관련 인터넷 글들에서도 많이 언급된다. 그렇다면 패스파인딩을 할때 타일을 하나하나 계산해 가는 것보다 인접 타일들끼리 하나의 리전으로 묶어 대략의 거리를 미리 계산해 놓으면 훨씬 계산이 수월할 것이라고 생각해 볼 수 있다. 이는 멀리 떨어진 리전들 사이의 길을 찾을 때 특히 유용할 것이다.

플레이어들의 입장에서는 게임 시스템이 미리 연산된 리전 간 거리를 이용할 때 몇몇 예외 케이스들:

출처: youtu.be/2ErJY5cbgHY (2:14)

이 장면과 같이 실제 최단 거리보다 돌아가게 되는 경우,

출처: youtu.be/2ErJY5cbgHY (좌 - 4:51, 우 - 7:20)

그리고 이 장면과 같이 최단 거리와 리전 간 거리의 갭이 클 때 발생하는 리버 버그의 경우,

 

기타 등등 여러 예외 케이스들이 발생할 수 있다는 건 염두해 두는 것이 좋을 것이다. 모든 맵의 리전을 미리 뜯어보는 건 플레이어 입장에서 좀 오바고, 경험적으로 이런 버그가 발생할 수 있는 위험 지역들을 미리 감으로 익혀두는 건 의미가 있지 않을까 싶다.

3.

길 탐색 시 동적인 환경, 리전 설정 등 여러 이유 때문에 최단 거리를 제대로 못 계산하는 경우가 발생할 수 있다는 것은 알게 되었다. 그러면 왜 드라군만 유독 멍청한 걸까? 드라군과 크기나 속도가 비슷한 유닛이라면 모두 드라군처럼 멍청하게 굴어야 하는 것 아닐까?

사실 이에 대한 해답은 지금까지 알아본 패스파인딩 알고리즘과는 다소 무관한 한 유튜브 영상을 통해 얻을 수 있었다.

출처: youtu.be/24134OFfvFI

70여 개의 커스텀 캠페인을 제작했다고 말한 이 모더는 "유닛들의 히트 박스 크기가 이동에 따라 변한다", "경로 찾기 문제는 특정 유닛에만 국한된다"라는 대중들의 인식이 사실 오해에 비롯된 것(!)이라는 것을 설명한다.

 

출처: youtu.be/24134OFfvFI

해당 영상에서는 유닛들의 자연스러운 애니메이션을 담당하는 iScript를 보여준다. 드라군 및 드라군과 동일하게 32x32 히트 박스를 가진 시즈탱크, 골리앗, 럴커를 비교하는데, iscript에 따라서 특정 한 프레임마다 움직이는 픽셀 수가 다르게 설정되어 있다는 것을 설명한다. 시즈탱크는 바퀴로 굴러가는 단순한 애니메이션을 가져서 그런지 3개 프레임 내내 4 픽셀의 속도를 가졌다는 것을 볼 수 있다. 드라군과 골리앗, 럴커는 조금 더 들쭉날쭉한 편인데, 아마 제자리에서 다리를 뻗을 때 적게 나아가고 뻗은 다리를 오므릴 때 많이 나아가도록 설정된 모양이다. 따라서 드라군, 골리앗 같이 "멍청해"보이는 유닛들은 사실 재생되는 애니메이션 상 다소 불규칙하게 움직일 뿐, 여타 다른 유닛과 동일한 로직으로 움직이는 것이지, 절대 멍청하다는 것이 아니라는 것이다.

 

출처: youtu.be/24134OFfvFI 댓글란

해당 영상 댓글란에는 Caenen이라는 리그오브레전드 기술 유관자가 등장해서 "게임의 특정 측면에 대해 공개적으로 알려진 정보가 없을 때, 그 주변에 많은 뇌피셜들이 생겨난다"고 말했다. 이러한 뇌피셜들은 일단 한번 형성되면 그 게임의 "공식적인 정보"가 되어 오해를 더욱 고착화시킨다고 한다.

 

결론적으로 불쌍한 드라군은 스타크래프트의 모든 유닛들과 마찬가지로 패스파인딩 알고리즘과 iScript가 움직이라고 한 대로 움직였을 뿐인데 아무 죄 없이 멍청하다고 욕먹고 있었다는 것이다.

 

끝으로,

 

가장 초창기 RTS 중 하나인 커맨드 앤 컨쿼 2 개발에 참가한 직원의 패스파인딩 개발 일화 영상을 공유하며 글을 용두사미로 마친다. 게임 개발자들은 사실 최단 거리를 찾는 최적의 알고리즘을 짜는 것이 아니라, 그럴싸 해 보이는 길을 찾아 멍청해 보이지 않게 움직이는 알고리즘을 짜는 것이라고 설명하는 것을 보니, 역시 플레이어와 개발자가 보는 게임에 대한 시각은 달라도 정말 다를 수밖에 없다는 생각이 든다.