목차
1. 서문
2. 빌드 설정값 초기화
3. 네비게이션 메시 빌드
4. 요약
1. 서문
게임개발에 길찾기 기능이 필요하게 되어 RecastNavigation이라는 오픈소스 길찾기 라이브러리를 내 게임엔진에 통합할 일이 생겼다. 깃허브에서 소스 코드를 다운로드 받으면 라이브러리 프로젝트와 함께 라이브러리 기능의 시연용 프로젝트로 RecastDemo라는 프로젝트가 있는데, 이 글은 시연용 프로젝트의 기능 중 네비게이션 메시를 생성하는 빌드 함수를 분석한 내용을 정리한 것이다.
RecastNavigation 깃허브 주소 : https://github.com/recastnavigation/recastnavigation
GitHub - recastnavigation/recastnavigation: Navigation-mesh Toolset for Games
Navigation-mesh Toolset for Games. Contribute to recastnavigation/recastnavigation development by creating an account on GitHub.
github.com
Recast Demo 프로젝트를 실행하고, 메시를 로드한 후 빌드 버튼을 누르면 푸른색으로 이동경로 맵이 생성된다.
이때 실행되는 함수는 sample 객체의 handleBuild 함수다. 이 글의 이후 내용은 모두 이 handleBuild 함수의 본문이 어떻게 전개되는지를 다룬다.
2. 빌드 설정값 초기화
handleBuild는 실질적인 네비게이션 메시 빌드 함수를 부르기 전에 필요한 설정값을 먼저 초기화한다. 먼저 지오메트리에서 가져온 메시로부터 버텍스 리스트와 페이스 리스트, 바운더리에 대한 정보를 가져와 변수에 담는다.
m_cfg는 길찾기 주체(Agent)들의 보행가능 경사각(WalkableSlopeAngle), 보행가능 높이(WalkableClimb) 등 앞으로의 네비게이션 메시 빌드과정에 두고 두고 쓰이게 될 설정값들을 몰아서 저장하는 구조체 변수이다. 일전에 구해둔 공간 바운더리 정보(bmin,bmax)도 rcConfig의 멤버변수 값으로 저장한다.
3. 네비게이션 메시 빌드
네비게이션 빌드와 관련된 코드에 진입하면서 빌드의 시작을 알리는 로깅 함수가 호출된다. m_ctx는 네비게이션 빌드가 진행될 때의 진행내역을 로그로 남기는 역할을 하는 맥락(rcContext) 변수다. 맥락이라는 클래스 이름은 이 클래스의 역할이 네비게이션 빌드 작업의 진행 내역을 로그로 계속 추적하는 역할을 맡고 있기에 이런 것이리라. 코드를 해석하려는 사람 입장에선 이런 로깅 함수가 사용되는 부분들이 코드의 역할과 진행상황을 설명해주는 주석 역할을 해준다.
빌드가 시작되면 먼저 높이필드(HeightField)라는 객체를 생성한다. rcAllocHeightfield 함수로 메모리를 할당받고, rcCreateHeightfield 함수로 높이필드의 3차원 볼륨(m_cfg.bmin, bmax), 2차원 면적(width, height) 등의 정보를 토대로 높이필드의 상태를 초기화한다.
이어 폴리곤 데이터를 저장할 수 있는 배열을 동적 생성한 후, 먼저 보행가능 경사각(WalkableSlopeAngle)을 보고 rcMarkWalkableTriangles 함수를 통해 걸어다닐 수 있는 영역을 걸러낸다. 그 다음 rcRasterizeTriangles를 통해 보행가능 높이(walkableClimb) 안에서 고저차가 있는 가파른 지형들을 서로 연결시켜 이어준다. 계단같은 경우 고저차는 낮지만 경사각이 가팔라 통행이 불가능한데, 보행가능 높이를 적절히 높여주면 계단의 영역들이 서로 이어져 건널 수 있는 통로가 된다.
그 후 필터링 단계에서는 절벽 가장자리, 장애물의 유무 등 다른 다양한 조건들을 보고 접근불가한 부분을 판별한다. 이 부분은 필터링 옵션에 따라 진행할수도, 진행하지 않을 수도 있다.
경로에 대한 정보들이 다 정리가 되어 높이필드(rcHeightField)가 만들어지면, 이를 적절히 가공해서 경로계산 연산에 최적화된 형태의 데이터로 만든다. 이 최적화된 데이터 형태를 밀집 높이필드(rcCompactHeightfield)라 하는데, 아마 데이터를 밀집시켜서 캐시 히트율을 높이는 것으로 연산시간의 감소를 노린 것 같다. 밀집 높이필드가 생성되면 더이상 쓸모가 없는 복셀 높이필드는 할당해제한다. 밀집 높이필드가 할당되고 나면 연이어 최적화 함수들을 더 호출해서 필요한 데이터의 양은 더욱 압축시키고, 서로 연관성이 높은 데이터들은 더욱 응집시킨다.
rcErodeWalkableArea 함수는 유닛의 최소 충돌크기(m_cfg.walkableRadius)에 따라 접근가능한 영역을 더 제한한다. 아마 지형 가장자리의 접근영역을 유닛의 반지름크기만큼 잘라내는 역할일 것이다.
Mark Area는 지역의 특징을 플래그로 지정한다. 네비게이션 주체는 나중에 이 플래그를 보고 특정 지역을 통행할 수 있는지 없는지 판단하게 된다.
다음으로, 네비게이션 영역을 적절히 분할한다. 분할방법은 Watershed, Monotone, Layer 이 세가지로 나뉘어 각각 장단점이 있다고 한다. 심화 길찾기 알고리즘의 구현방법에 대한 나의 이해가 부족하기 때문에 triangulation, tesselation 등이 무슨 말을 하는 건지 알 수 없었지만, Layer 분할 방식이 타일형 맵에 적합하다고 하는 것 같기에 우선 이걸 쓰면 될 것 같다.
사용하는 분할방식에 따라 부르는 함수도 달라지는 것을 볼 수 있다.
다음으로 완성된 경로의 가장자리 정보를 만들어낸다.
그리고 완성된 윤곽선 정보로부터 네비게이션 메시를 만들어낸다.
일반 네비게이션 메시와 디테일 메시가 또 다른가보다. 일반메시로부터 디테일 메시를 만들어내고, 디테일 메시까지 제대로 생성되면 이제 쓰임이 다한 밀집 높이필드(CompatctHeightField)와 윤곽선 집합(CountourSet)을 할당해제한다.
여기까지는 Recast 라이브러리를 사용해서 일반 메시로부터 네비게이션용 메시를 생성하는 코드였고, 이 데모 프로젝트에서는 이렇게 한번 가공된 메시 데이터를 추려 Detour 라이브러리용 네비게이션 메시를 만드는 데에 사용한다. Recast가 순수 지형메시로부터 네비게이션이 적용될 구간을 추리는 역할을 한다면, Detour는 런타임 중 길찾기 연산을 시도할 때 사용될 네비게이션 메시를 생성하는 것 같다.
메시의 분할된 영역들에는 여러가지 플래그를 저장할 수 있다. 앞에서 MarkArea 함수를 통해 지정한 각 구역(area)의 특징에 따라 지형 메시의 플래그를 설정한다. 이 플래그들은 나중에 네비게이션 주체들의 필터 플래그들과 대조되어 유닛이 특정 구역을 통행할 수 있는지의 여부를 판단하는데에 쓰이게 된다.
params, navData, navMesh를 차례로 할당,초기화하고 navMesh와 navQuery에서 init 함수를 호출하면 이로서 빌드가 모두 끝난다.
4. 요약
RecastDemo에서 사용된 네비게이션 메시 빌드 함수의 수행단계를 이해하기 쉽게 그림을 그려 정리해보자.
이 기나긴 빌드 프로세스의 최종 결과물은 dtNavMesh, dtNavMeshQuery이다. 얘들을 이용한 런타임 길찾기는 어떻게 진행되는건지 다음 포스트에서 알아보자.
'자체엔진 Yunuty > RecastNavigation' 카테고리의 다른 글
| 자체 게임 엔진에 RecastNavigation 이식하기 (0) | 2023.11.01 |
|---|---|
| RecastNavigation - Detour Crowd의 분석 (0) | 2023.10.25 |
| RecastNavigation의 경로계산 (0) | 2023.10.23 |