[인벤게임컨퍼런스(IGC) 발표자 소개] 2010년 펄어비스 설립 직후 입사한 후 검은사막 개발에 참여한 민경인 프로그래머는 현재는 검은사막 모바일 개발팀에서 모바일 버전 개발에 힘쓰고 있다.
금일(2일) IGC2017 in 성남 3일 차 강연에서는 펄어비스의 민경인 프로그래머가 나와 '검은사막'만의 독특한 네비게이션 기능인 복셀 네비게이션 라이브러리 개발기를 들려줬다. 기존 네비메쉬로는 불가능한, 담을 뛰어넘고 건물 위를 누비는 '검은사막'의 자유도를 완성시킨 복셀 기반의 네비게이션은 뭘까? 그리고 어떻게 탄생한 걸까?
그들이 복셀 기반 네비게이션 알고리즘을 만들면서 겪었던 일들과 그걸 해결하는 과정에 쌓은 노하우를 이번 강연을 통해 알아보자.
※본 강연 기사는 주제 특성 상 강연자의 시점에서 서술했습니다.
■ 강연주제 : MMORPG를 위한 VOXEL 기반 네비게이션 라이브러리 개발기
⊙ 네비게이션 메쉬와 A* 정리
우선 '검은사막'의 복셀 기반 네비게이션 라이브러리 개발기에 앞서 지금까지 어떤 상용 네비게이션 라이브러리가 사용됐는지부터 설명하겠습니다. 이런 상용 네비게이션 라이브러리들은 기본적으로 네비메쉬 라는 것을 이용해서 동작합니다. 이 방법의 특징은 이동가능한 영역을 폴리곤 형태의 메쉬로 구성해 이 위에서 경로를 탐색하는 방식입니다. 매우 빠르고 메모리도 적게먹고 지형 인식이라는 무거운 작업을 미리 계산해 둘 수 있는 가장 보편적인 방법이죠.
저희도 처음에는 이런 네비메쉬를 기반으로 네비게이션 시스템을 구축했습니다. 앞서 이 방식은 네비메쉬를 미리 계산하는 방법이라고 한 적이 있는데요. 문제는 '검은사막'같은 MMORPG은 계산할 것들이 너무 많아 프레임이 저하되는 일들이 발생하곤 했던 거였습니다. 15만이 넘는 Agent가 각자 자기만의 경로를 갖고 있고 무려 368㎞에 달하는 거대한 세계를 계산해야 했으니까요.
이처럼 네비게이션 경로를 계산하는 네비메쉬가 계산에 너무 오랜 시간이 걸리고 성능을 잡아먹자 A* 알고리즘도 큰 힘을 발휘하지 못했습니다.
결국, 이 문제를 해결하기 위해선 자체적으로 네비게이션 라이브러리를 개발할 필요가 있었습니다. A* 알고리즘을 사용하되 계산 효율을 극대화한 라이브러리를 말이죠.
⊙ Voxel Navigation 개요
저희가 주목한 건 복셀이었습니다. 복셀은 픽셀의 3D 버전이랄 수 있는데 여러 색을 가진 수많은 픽셀들이 모여서 하나의 이미지를 만들어내는 것 처럼 작은 복셀들을 모아서 하나의 커다란 형체를 표현할 수 있습니다. 저희는 복셀 하나하나에 지형 데이터값을 넣음으로써 복셀 네비게이션을 만들고자 했습니다.
왜냐하면 복셀은 모든 축에 대해 정렬된 데이터로 이루어져있기 때문에 각 축의 좌표만 알면 접근이 가능했기 때문입니다. 따라서 네비메쉬를 사용할 때처럼 연결 링크를 재구성할 필요가 없어서 실시간 스트리밍에 알맞은 구조라고 생각했습니다. 또한, 그 자체로 A* 알고리즘을 적용할 수 있단 점도 큰 장점이었죠. 또한, 앞서 수많은 복셀이 모여 하나의 형태를 이룬다고 했었는데 네비메쉬에서는 경로에서 제외했던 복잡한 지형의 네비게이션 데이터도 복셀을 이용하면 손쉽게 추출할 수 있었습니다.
여기에 칸별로 지형데이터를 담아둔다면 서버 검증이나 각종 컨텐츠 구현시 유용할 것이라고 판단했습니다. 특정 지형에 따른 효과를 받는다거나 수중, 공중, 건물 위와 같은 지형의 성질에 따라 다양한 액션을 직관적으로 선보일 수 있었으니까요.
하지만 이 모든 노드를 일일이 계산한다면 네비메쉬와 별다를 게 없었겠죠. 그래서 저희는 각각의 복셀 데이터를 노드화해 나뉘어진 데이터들을 실시간으로 로드, 언로드 할 수 있게 그리드로 만들었습니다. 나머지는 스트림 그리드를 통해 그리드에 일관되게 접근할 수 있도록 하면 되는 거였죠.
한편, 이런 복셀 데이터는 단순히 네비게이션에만 국한되지 않는데요. 복셀 데이터를 대상으로 레이캐스트를 수행해 몬스터의 가시성 판단을 구현할 수 있었고 그 덕분에 실제 게임 내에서 잠입미션이나 전투 대상 인식 등에 광범위하게 사용되고 있었습니다.
특히 범위 차폐 기능은 몬스터와의 전투나 공성전에서도 유용하게 쓰이는 기능입니다. 벽 뒤로 숨어 적의 공격을 피하는 것에서부터 공성전에서 대포를 쏴서 성채를 맞추는 등의 다양한 방식으로 이용되고 있습니다.
아울러 각각의 인자를 이용해 복셀 속성에 따라 수중에서 활동하는 몬스터라거나 공중을 나는 하피같은 독특한 이동 네비게이션을 가진 몬스터 구현할 수 있었습니다.
⊙ 폴리곤 to 복셀 샘플링 기법
복셀 기반의 네비게이션 라이브러리에 대한 설명은 이쯤하고 다음으로 저희의 노하우를 공유해드릴까 합니다.
저희는 처음에 복셀 데이터를 추출할 때 물리엔진을 통해서 충돌 유무만을 샘플링했습니다. 샘플링 속도도 빠르고, 구현도 간편했기 때문입니다. 하지만 한계도 명확했습니다. 복셀이 있으니 뭔가 있는 건 알겠는데 정확히 뭔지 판단하기 어려웠던 겁니다. 그리고 불필요한 부분도 샘플링하니 비용의 낭비가 너무 심하기도 했고요.
결국 전체 월드 샘플러를 만들 필요가 있었습니다. 샘플링할 대상의 모든 폴리곤을 순회하며 자동으로 샘플링할 수 있도록 한 거였습니다. 이렇게 샘플링 방식을 바꾸자 작업 효율이 거의 10배 이상 상승하는 효과를 볼 수 있었습니다.
⊙ 고정데이터 Map 메모리 절약
게임들을 보면 처음에 로딩을 거치고 나서 바뀌지 않는 데이터들이 몇 개 있습니다. '검은사막'에서는 맵 데이터, 복셀 데이터가 대표적입니다. 저희는 처음에 이런 맵 데이터를 STL 맵을 이용해 관리했는데 생각보다 연결된 벡터가 많다보니 많은 메모리를 필요로 했습니다.
그래서 이걸 개선하기 위해 내부 구현을 정렬 벡터로 바꾸고 인덱스를 통해 중복데이터 공유할 수 있도록 했습니다. 그 덕분에 메모리 부담을 최소화할 수 있었고 부수적으로 File I/O 과정이 축약되면서 로딩 속도를 개선할 수 있었습니다.
⊙ Sub Voxel Resolution
복셀의 크기 때문에 발생한 문제도 있었는데요. 복셀의 기본 사이즈를 1m로 잡다 보니 미묘한 크기의 오브젝트에 복셀이 생성되서 뚫려있지만 복셀 때문에 길이 막히는 문제가 발생했었습니다. 1.2m짜리 벽돌이 있다면 0.2m 부분에도 1m짜리 복셀이 생성되서 결과적으로 2m 크기의 공간을 쓸 수 없게 된 거였습니다.
이 문제는 복셀 사이즈를 줄이면 어느 정도 해결할 수 있는 문제였지만 이렇게 해상도가 늘어나면서 메모리 사용량이 기존의 몇 배는 늘어날 터였습니다. 그래서 저희는 복셀 사이즈를 줄이는 대신 서브 픽셀이라는 개념을 가져와 사용했습니다. 1개의 복셀을 8개의 서브 복셀로 나누어 존재 유무를 담는 방법으로 각 복셀당 1byte 만 추가하면 해상도를 2배 뻥튀기할 수 있습니다.
최종적으로는 복셀 사이즈가 1m였던 기존에 비해 좀 더 정교하게 지형 데이터를 복셀로 구현할 수 있었습니다. 더이상 캐릭터가 허공에 걸리는 일도 없어졌고요.
⊙ A* 길찾기 성능 최적화
끝으로 A* 길찾기 알고리즘을 최적화했습니다. A* 알고리즘의 핵심은 후보 노드를 등록하고 가장 유력한 후보를 탐색하는 걸 얼마나 빠르게 하느냐입니다. 그런데 복셀 기반 A* 알고리즘은 일반적인 네비메쉬보다 노드가 많아서 경우의 수도 많이 발생했습니다.
그래서 저희는 우선 아예 검사하지 않아도 되는 부분은 뺐습니다. 복셀에서 계산할 필요가 없는 부분을 뺌으로써 계산할 양을 우선 최소화한 거였죠. 이어서 A* 알고리즘을 Greedy First Search로 커스텀했습니다. A* 알고리즘은 분명 최단거리로 길을 찾을 수 있는 알고리즘이었지만 경로가 꺾이는 순간 다시 시작점부터 탐색하는 경우가 발생하는 문제가 있었습니다. 그러던 걸 Greedy First Search로 커스텀하면서 저희가 원하는 형태로 만들 수 있었습니다.
⊙ 맨 땅에서 프로토타입까지...
맨 처음 펄어비스에 입사하고 대표님께서 네비게이션 라이브러리 만들라고 하셨을 때는 정말 부담됐습니다. 그래도 만들라고 하셨는데 안 만들 수도 없었죠. 그래서 인터넷을 찾아보거나 하면서 여러 상용 네비게이션 라이브러리를 파헤친 끝에 복셀 기반 네비게이션 라이브러리를 만들 수 있었습니다.
'늦는 걸 두려워하지 말고 멈추는 걸 두려워하라'는 말이 있습니다. 전 걱정만 하는 건 아무것도 하지 않는 것과 마찬가지라고 생각합니다. 만약 제가 부담과 두려움에 네비게이션 라이브러리를 만드는데 도전하지 않았다면 아마 상용 네비게이션 라이브러리를 그대로 썼을 테고 여러 문제가 발생했을지도 모릅니다. 하지만 두려워하되 도전했기에 '검은사막'만의 특별한 네비게이션을 완성할 수 있었던 것 같습니다. 여러분, 도전하는 걸 두려워하지 마시고 멈추는 걸 두려워하며 도전하시길 바랍니다.
Nowl@inven.co.kr