�ݺ�ߣ

Editor's Notes

• #2: 오늘 제가 소개해드릴 내용은��검은사막에서��자체 제작해서 실제로 사용중인��네비게이션��시스템에 대한 내용입니다.이를 구현하면서 겪었던 문제들,��해결했던 방법들에 대해 공유하는 시간으로 준비했습니다. 저는��펄어비스��모바일��개발팀의 프로그래머 민경인입니다.
• #6: 이미��잘 쓰고 있는��오픈소스��/��상용 라이브러리도 많이 있습니다.검은사막도��개발 초기에는 이런 라이브러리를 잘 사용하고 있었습니다
• #8: 빨간 박스로 지정된 영역들은��벽 부분들인데,��길찾기에��활용되지 않는 데이터라 모두 제거된 것을 볼 수 있음.
• #9: 이런��간단해보이는��지형이라도 이렇게 많은 삼각형으로 분할이 됩니다.
• #10: 삼각형끼리 인접한 면을 연결한��그래프를��만들어둔다면,��널리��알려져있는��최단거리��탐색 알고리즘들을 사용할 수 있습니다. 이때��I / H��간의 연결을 보면,��인접한��변이��일치하지 않아��강제로 링크를 연결을��해줘야��하는 경우도 생깁니다.
• #15: 여러개의��파일에 각각 독립적으로 저장하려면,��이와같이��분할을하게��됩니다.
• #16: 분할 결과는��이전 모습과 상당히 달라지죠. 이때 다시 재 연결을 얼마나 빠르게 할 수 있느냐가 관건 운이 좋으면 파란색 영역처럼 바로 인접 영역으로��삼을수도��있겠지만,��운이 나쁘면 빨간색 영역처럼 변이 맞지 않아 더 많은��연결정보를��추가해줘야��하는 경우가 생깁니다.
• #17: 개발��초기부터��벽��타고��오르는��액션이나��장거리 대포에 대한��아이디어들이 나오고��있을��시점이라,��서버에서의��이동검증이��매우��중요했음. 특히��벽타기는��기존��게임들의��이동방식과��특성이��달랐고,��거의��모든��지형에��대한��데이터를��가지고��있어야��할��필요성이��있었음
• #18: 검은사막��지형의 경우 매우 복잡한 형태의��지형들이 존재하고, 이 곳들에 대해 별도의 처리 없이 게임에 필요한 데이터를 추출할 수 있으면 좋겠다.
• #19: 이렇게 해서 먼저 어떤형태로 만들지에 대해��대략적인��설계를 하기 시작했습니다.�� 다른 여러가지 이유도 합쳐지긴 했지만, 핵심은 로딩 속도의 개선과 네비 데이터 추출과정에서 발생하는 수작업을 줄이는 것이 가장 큰 목표였죠. 그래서 선택한 도구가 복셀데이터 였습니다.
• #20: 복셀보다는 픽셀이 더 익숙한 개념이실텐데요. 픽셀은 아시다시피 이미지를 이루는 하나의 점을 가리키는 용어죠
• #21: 복셀은��픽셀의��3차원 버전으로 생각할 수 있습니다. 특징은��레고��블록��1칸과 비슷하기도 한데요. 여러 색을 가진 수많은 픽셀들이 모여서 사진을��만들어내는��것��처럼 작은��복셀들을��모아서 커다란 형체를 만들어 표현할 수 있습니다 뿐만아니라��앞으로��설명드릴��내용을��들어보시면��다루는 방식이 이미지 처리의 개념을 종종��채용해오는��것을 보실 수 있습니다
• #22: 복셀은��모든 축에 대해 정렬된 데이터로��이루어져있기��때문에 각 축의 좌표만 알면 접근이 가능합니다. 따라서 연결 링크를 재구성 할 필요가 없어서, 네비메쉬보다��실시간��스트리밍에��알맞은 구조라고 할 수 있습니다 또한 그 자체로��A*��알고리즘을 적용할 수 있다는 장점도 있습니다.
• #23: 칸별로��지형데이터를��담아둔다면,��서버 검증이나,��각종��컨텐츠��구현시��유용할 것 같다. 특정 지형에 따른 효과를 받는다거나 물속,��공중,��건물 위 등과 같은 지형의 성질을 ��직관적으로 판단 할 수 있습니다.
• #24: 1섹터는��128m��입방으로 이루어진 공간으로 결정했다.��이 안을��몇개의��복셀로��나눌것이냐가��관건 세밀하게 나눌수록 정확한 데이터를 가지고 있을 수 있긴 하다.��다만,��무턱대고��복셀을��작게��만들수도��없습니다.
• #25: 바로��복셀��사이즈가��작아질��수록 가지고 있어야 할 데이터가 기하급수적으로 늘어납니다. (무려��세제곱배) 사진이나 동영상의 경우도 고해상도일수록 용량이��급증하는것��처럼
• #26: 각��복셀당��1바이트라고만 잡아도 대략��471기가가 넘는 용량이 필요합니다 따라서 복셀에 대한 관리 전략이 필요해집니다. 이런 커다란 데이터를 어떻게 담아야할지 고민을 하기 시작했습니다
• #27: 복셀을��전부��Plane��Data로��저장할 수는 없기 때문에,��과거 학부에서 과제로 다뤘었던��Sparse��Matrix��특성을 차용합니다. Sparse Matrix는 속이 대부분 비어있는 희소행렬로,��지형데이터도 이와 유사한 특징을 가집니다.
• #28: 지형이라고 함은 캐릭터가 뛰어다닐 공간을 상정하고 만들기 마련인데요. 따라서 대부분의 공간은 허공으로 이루어져 있습니다. 즉 모든 데이터를 메모리상에서 관리할 필요는 없다는 것입니다. (데이터 없음 상태 자체를 허공으로 판정할 수 있습니다.)
• #29: 노드는��실제��복셀��데이터라고 보시면 됩니다.��길찾기��알고리즘이 인식할 최소 단위 그리드는��파일에 저장되는 단위라고 볼 수 있습니다. 이렇게��나뉘어진��데이터들은 실시간으로 로드��/��언로드가 되면서 실시간으로 변동 됩니다
• #30: 각각��분리되어있는��그리드들을��일관되게 접근할 수 있는 인터페이스를 만들었습니다 이를 통해��길찾기��알고리즘이 데이터 구조와 상관없이 동작할 수��있게 되었고 길찾기��수행여부와��상관없이��지형데이터의��로드��언로드��처리가��가능해졌습니다
• #31: 지금까지 내용이 정적인 데이터였다면 동적으로 변동되는 내역들도 최근의 게임들은 ��많이��존재할텐데요. 플레이어들,��또한 그들이 설치하는��설치물��등도��경로차폐기능이��필요한 경우가 많습니다. 적의 이동을 방해하는��바리케이트와��같은 건물들입니다. 이들을��Ai��캐릭터들과 서버에서��인식하기위해��구현한 것이��Obstacle��입니다. 일부��네비게이션��라이브러리들은��Obstacle��추가��삭제시에도��재구축��과정을 거치는 경우가 있지만 MMORPG와 같이 전 월드에서 수많은 장애물이 처리되는 상황에서는 그러한��재구축��처리를��하는것이��부담됩니다. 따라서 이��Obstacle��자체를 동적으로 충돌 처리를 수행하도록 만들었습니다.
• #32: 이런 방해물들은��실제 눈에��보여지는��형태보다 간략한 형태로 대략적인 처리를 수행함으로써,��빠르게 조회��/��수정을 할 수 있도록 했습니다. 이들의��변경시는��자신의 데이터만 수정하고 충돌될 좌표에 대한 조회가��발생할때에만��정확한 충돌 여부 계산을 수행하게 됩니다.
• #33: 네비게이션��복셀들과��달리��Lock을 거는 빈도가 높으므로��별도의 섹터를 두었습니다. 같은 섹터 내에서의 이동은 개체 하나의 메모리만 수정하면 작업이 끝날 수 있습니다. 미리 분리 작업을 하지 않는 이유는 이번 작업에 있어서 이러한 동적 장애물이 이동하는 빈도가 실제로 충돌이 발생되는 케이스가 더 적었기 때문입니다. 반대의 경우라면 당연하게도 미리 고정데이터로 굽는 형태를 선택해야 했겠지요.
• #34: 이 당시��측정결과로��보면,��순차적으로 한 셀씩 샘플링을 하는 것보다 섹터 공간을��8분할 하여 미리 커다란 공간들을 제외해 나가는 식의 접근을��했을때��커다란 속도 향상이 있었습니다. 다만,��한계점이 있었지요. 뭔가 있는건 알겠지만 정확하게 무엇이 있는지 판단할 방법이 제한적이었습니다.
• #35: 결국 전체 월드��샘플러를��만들기에 이릅니다 오브젝트 배치 데이터와��버텍스��/��인덱스 버퍼에 직접 접근하여��셈플링을��수행하면 사용되는 모델의 파일명,��텍스쳐명��부터��배치툴에서��지정되는 다양한 옵션을 사용할 수 있었습니다 이것이 가능해진다면 한 모델내에서 나무와 잎들을 구분하고,��수면 데이터를 뽑아내는 등 기존에 손으로 해야했던 상당수의 수작업들이 사라질 수 있었습니다. 물론 뽑아야할 대상이 많다보니 처리속도도 중요한 이슈입니다.
• #36: 점��3개로 이루어진 삼각형이��주어졌을때��복셀��샘플링을 어떻게��해야할까요? 또 얼만큼의 간격으로 샘플링을 해야 놓치는 부분 없이 샘플링이 가능할까요? 이에 대한 정리가 이 표본화 정리입니다. 이것은 음성녹음,��정보통신 등의 분야에서는 매우 기본으로 알려져 있는 정리입니다. 핵심만 집자면 신호대역의��2배로 샘플링 하면 후회가 없을것이다라는 내용인데요 복셀 공간에서 최소단위는 복셀의 크기입니다 따라서 복셀크기의 반이 권장 샘플링 단위가 됩니다
• #37: 위쪽 삼각형에서��나뉘어진��선분 대로 샘플링을��수행할경우 사각형의��2차원 배열을��순회하는것과��동일하여, 코드는 더��간단해지지만,��샘플링 밀도가 한곳에 너무 집중되어 시간이 낭비되는 경우가 발생합니다.
• #38: 생각보다 많은 고민이 필요했지만, 결국 결과물이 나오긴 하더랍니다. 기본적인��셈플 데이터를 추출하고, 간단한 길찾기 알고리즘을 만들어 붙여보았던 상태입니다.
• #39: 이때까지는 일부 셈플 데이터를 가지고, 추출과 기본 구현이 중심이었다면,�� 이후 부터는 실제 게임 전체에 적용해나가면서 부딛혔던 문제들에 대해 이야기를 해보려고 합니다.
• #40: 복셀��영역내에��존재하기만 한다면��복셀이��생성되므로 충분히 공간이 있는데도��복셀이��길을��막아버리는��현상들이 발생했습니다 기본 복셀 사이즈를 1m로 잡은 기초부터 흔들리기 시작했습니다. 복셀 사이즈를 2배 축소시키면, 어느정도 문제가 완화되겠지만, A*를 같은 비용으로 돌리더라도 진행할수 있는거리가��면접 비례로 줄어들것이고, 메모리는 지금의 몇배는 늘어날 터였습니다.
• #45: A*는 현재 위치에서 갈수 있는 곳에 대한 후보지들을 등록하고 가장 가능성이 높은(유력함을 나타내는 포인트 등으로 정렬된 녀석)��후보지로 이동해서 다음스탭을 진행합니다.
• #46: A* 알고리즘의 가장 중요한 성능포인트는�� 후보 노드를 등록하고 가장 유력한 후보를 탐색하는 부분을 얼마나 빠르게 하느냐가 관건입니다 후보노드의 숫자가 많다는 것은 그만큼 성능적으로 불리합니다.
• #47: 실제 인접한 노드 만으로도 이미 체크해야하는 연결이 많아지고,�� 이것으로 급한불은 껏다고 할 수 있겠지만�� 네비게이션 매쉬 방식에 비해 한번에 후보군을 탐색하는 거리도 짧으므로 느릴 수 밖에 없습니다.
• #48: A*를 돌리기 전에 직선으로 이동가능한지 샘플링 검사를 추가하는 것만으로도 상당수 길찾기에 성공합니다.
• #49: 직선으로 이동을 하지 못할 경우 최종적으로��A* 를 수행하면서 경로 탐색을 하게 되는데요 최적 노드를 선정하는 방법도 다음과 같습니다 현재까지 진행해온 거리��+��목적지까지 앞으로 진행해야할 예상 거리 이 부분에서도 개선을 할 부분이 있었습니다
• #50: A*는 최단 거리의 길을 찾는 방식이기 때문에 후보군을 등록하다가 더 나은 경로가 탐색되면 경로를 갱신하기도 하고 후보 위치중 가장 적합한 노드를 선정하는 가중치 계산식에 의해서도 다양한 시행착오를 계산하게 됩니다. 지금 그림상에는 장애물에 막혔을때 경로를 찾는 부분을 표현하였지만 경로가 꺾이는 순간부터는 다시 최초 시작점부터도 탐색을 시작하는 경우가 발생합니다.
• #51: 전통적인��Greedy��Best��First��형태는 가장 먼저 테스트에 성공한 시도를 기준으로 확장하는 방식입니다. 이때 적절한 계산식에 의해 실패라고 판단할 경우 다른 후보 노드를 수행하게 됩니다. MMORPG의 지형들에서는 복셀��1칸당 장애물이 있는형태의 미로형태는 거의 존재하지 않기 때문에 상당부분은 개활지를 진행하는 경우가 많습니다. 따라서 이미 지나온 거리가 멀어지더라도 목적지까지의 남은거리를 더 중요하도록 가중치를 조정했습니다. 이를 통해 한번 길찾기에 후보 노드 등록량이 줄어들었고 후보 노드를 관리하는��priority��queue의��Insert��/��find��횟수가 줄어들었고,��큐의 크기가 작아져��insert��/��find��의 수행 부담도 줄어들었습니다
• #52: 복셀��상의 좌표만으로��A*를��수행하면��45도로 각진 경로를 구하게 됩니다.�� 옛날��타일링��방식의��고전게임들에서��볼수��있는 경로인데요.��이를 대각선 이외의 다양한 각도로도 이동할 수 있다면��축약해주는��최적화 기능도 필요했습니다.
• #53: 이를 구현함에 있어서��직선경로��테스트가 유용하게 활용되었습니다 최초 시작 지점부터 순차적으로 경로 테스트를��수행해보고��성공한 지점까지��직선경로로��대체하면 됩니다.
• #54: 이를 통해서��Greedy��First��Test의 약간 멍청해 보일 수 있는 경로를��어느정도��개선하는 효과도 있었습니다 이 결과는��A* 자체만으로 최적의 길을 찾을 필요가 없을 수 있음을 보여줍니다. 모든경우를 대체하지는 못하지만 이로 인해 얻는 성능이득을 다른곳에 투자할수 있게 되었습니다
• #56: 패스 최적화와 비슷한 방식이지만,��회전각을 추가로 입력하여 이와 같이 곡선 패스를 구하는 방법도 구현합니다. 패스 최적화��탐색시��회전각을 반영하여 순차적으로 검색하는 방식으로,��구현한다면 모든 경우에 대해��곡선패스를��찾을 수는 없겠지만,��대부분의 경우에��납득할만한��결과를��보여줍니다.
• #57: 메모리��/��성능 측면에서의 개선을 한 뒤에 남는 여력으로 비로소 해상도를��2배 증가시킬 수 있었습니다. 최초��프로토��타입에 비해 좀더��지형데이터를��표현하기에��적합해졌습니다. 실사용 하는 툴이 되어서 눈이 좀��덜아프게��수정되고 속성별로 색을 달리해��볼수��있게 되었습니다.
• #58: 이전 버전과��비교해보면��조금더��명확합니다. 동그라미 친 부분을 보면 기존에 큰 박스��1개로 표현되던 부분이��개선버전에서는��그래도 계단 비슷하게 변경되었습니다. 높이가��1칸��차이나는��지형이라 경로��탐색시��통과 가능한 형태이지만 크게��눈에띄는��부분이라면 경계에��Npc��이동불가��속성을 지정하는 것으로 처리 가능할 수준이 되었습니다
• #59: 최소한 캐릭터 최소 바디 사이즈��/��√2��는 보장되어야 캐릭터 중심점 기준으로 직선 검사를 할 수가 있다! 현재 캐릭터의 반지름은��0.4m��이므로��0.28m��이하의��복셀로��이루어진��맵에서는��중심점 기준으로 직선검사를 하는 것이 가능해진다. 따라서��2배 이상 해상도를 늘려야 한다!
• #60: 기존처럼 해상도 자체를 늘리는 것은 메모리 제약이 크다. 따라서 기존��SubPixel��이라고 하는 개념을 가져와서 사용합니다. 1개의��복셀을��8개의 서브��복셀로��나누어 존재 유무를 담는 방법으로 각��복셀당��1byte��만 추가하면 해상도를��2배 뻥튀기 할 수 있습니다.
• #61: 서브 복셀을 적용해본 결과를 표현해보았습니다. 복셀의 해상도가��25cm��수준이 되어 복셀��1칸의 최대 길이도��35.35cm가 되어 기존 캐릭터의 중점이 벽에 걸리지 않도록 수정된 것을 볼 수 있습니다.
• #62: 서브��복셀��정보까지 포함된 최종 결과입니다 굳이 지형을 함께 보지 않더라도��어떤지형인지��눈으로 식별 가능한 수준까지��세밀해진��것을 볼 수 있습니다.
• #64: 복셀에 대한 조회와 샘플링 과정이 최적화 됨에 따라, 서버에서도 Raycast와 비슷한 형태의 쿼리를 만들어 줄 수 있었습니다. 이를 이요해 몬스터의 가시성 판단을 구현할 수 있었고, 실제로 게임내에서도 잠입미션이나, 기본 전투 대상인식등의 서버기반 컨텐츠에 광범위하게 사용되고 있습니다.
• #65: 실제 검은사막 에서 사용중인��덤불데이터입니다. 이 잎사귀 영역은 통행에는 지장이 없는 타입이지만, 가시성 판단에 사용하고 있습니다.
• #66: 동일한 원리로, 공격지점에서 공격 대상까지의 차폐물이 있는지에도 같은 기능이 사용됩니다. 스크린샷은 크자카 라는 월드보스인데요. 브레스를 사용할때 기둥뒤에 숨어있으면 데미지를 받지 않게 됩니다.
• #67: 클라이언트에서 인지할 수 없는 거리에 대한 충돌판정이 가능해진다. (검은사막의 대포류 발사체들은 서버에서 충돌판정이 발생한다.) 몬스터나 NPC들도 같은��대포��기능을 이용해��트리나 요새나 트롤 요새와 같이 대규모 전투장면을 구현할 수 있었습니다.
• #68: 동작별로 이동가능한 속성들이 고정되므로 (점프는 공중, 달리기는 지면… ) 성벽을 통과한다거나, 땅속이나 하늘을 날아다니는 이동 핵들을 원천적으로 검증할 수 있다.
• #69: 동작별로 이동가능한 속성들이 고정되므로 (점프는 공중, 달리기는 지면… ) 성벽을 통과한다거나, 땅속이나 하늘을 날아다니는 이동 핵들을 원천적으로 검증할 수 있다.
• #70: 동작별로 이동가능한 속성들이 고정되므로 (점프는 공중, 달리기는 지면… ) 성벽을 통과한다거나, 땅속이나 하늘을 날아다니는 이동 핵들을 원천적으로 검증할 수 있다.
• #71: 몬스터들도 같은 인자를 이용해서, 수중 몬스터나 하피 같은 공중을 날아다니는 네비게이션이 가능해졌습니다.
• #72: Dynamic SubLevel 이라고 하는 용어는 인터넷에서 본건데요. 보통은 이렇게 고정된 지형 위에서 움직이는 다양한 Agent들과 Obstacle이 존재하는 상황을 가정할 수 있습니다.
• #73: 하지만, 배,��엘리베이터,��유저가 설치한��바리케이트��등등��캐릭터가 올라탈 수 있는 발판들은 이야기가 달라지죠. Agent가 탐색해야될 대상이 월드의 데이터가 아닌, 탑승물을 기본으로 탐색할 수 있도록 동적인 처리가 가능해야 합니다. 이것들은 게임
• #74: 월드 공간이 아닌,��다른 캐릭터를 태우는 경우��네비게이션��데이터를 뽑아 일반 지형과 동일하게��네비게이션��데이터를 이용한 검증을 수행할 수 있도록 한다. 대양의 경우 파도의 폭이 큰데,��이 경우 배의��로컬좌표계로��통일하여 서버와 동기화 한다. 탑승물이��이동하면,��탑승자들이 전원 위치가 갱신되므로,��플레이어가 다른��탑승물에��타있을때��전송하는 데이터��전송량을��줄일 수 있다.