들어가기에 앞서, 이 글은 테스트 자동화 환경을 구축하게 된 사고의 흐름과 소감을 다루나, 환경을 구축하기 위한 세세한 절차들을 모두 명시하지는 않았음을 밝힌다.
1년간 게임 인재원에서 진행한 게임 개발 프로젝트들은 모두 약 2주~4주의 개발기간을 갖는 소규모 프로젝트들이었다. 이런 프로젝트들은 개발 도중 기능에 문제가 생길 때마다 센스와 직관으로 디버깅을 하면서 진행을 해도 큰 탈이 없었다. 하지만 게임인재원 5학기 일정을 시작하면서 1년동안 진행될 장기 프로젝트에서도 이런 식으로 개발을 할 수 있을지 의문이 들었다. 장기 프로젝트일수록 필요한 기능들을 산더미 파불고기처럼 많이 구현하게 될 텐데, 기능 중 하나가 고장이 났을 때 산더미같은 기반 코드 중 정확히 어디에서 문제가 터진 것인지 진단하는 것이 예삿일이 아닐 것 같았다.
소규모 프로젝트(좌)에서는 하나의 기능에 문제가 생겼을 때 해당 기능이 의존적인 기능들을 전수조사하는 것에 대한 부담이 적었으나, 대규모 프로젝트(우)의 경우 문제가 생긴 부분을 찾아내기 매우 힘들것이라는 예상이 들었다.
이 문제에 대한 진지한 고민은 학기 초에 빌드머신을 세팅할 때부터 시작했다. 빌드머신용 컴퓨터에 젠킨스 서버를 설치하고 이를 깃허브 리포지터리와 연동해 마스터 브랜치가 업데이트될때마다 자동으로 빌드를 시도하게 만들었지만 이것만으로는 아쉽다는 생각이 들었다. 젠킨스는 프로젝트 빌드가 성공했을 때 해당 빌드를 성공적인 빌드로 마킹하는데, 프로젝트가 그저 컴파일가능하다는 것 하나만으로 프로젝트의 안정성이 보장될 수는 없다고 보았기 때문이다.
빌드머신에 젠킨스를 구축해 깃허브 저장소가 업데이트될때마다 자동빌드를 시킨 모습. 하지만 코드가 빌드가능하다는 것만으로 전체 프로젝트의 안정성을 보장할 수는 없겠다는 생각이 들었다.
빌드머신의 절차를 어떻게 더 고도화시킬 수 없을까 고민을 하다가 대학을 다닐때 소프트웨어 테스팅에 대한 강의를 들은 기억이 났다. 개발중인 소프트웨어의 복잡성이 증가할수록 뭘 더 개발하는 것이 어려워질테니, 구현된 기능들을 반복적으로 검증할 수 있는 체계를 마련해야 지속가능한 개발을 꾀할 수 있다는 교수님의 말씀이 떠올랐다. 비주얼 스튜디오에서 테스트와 관련된 견본 솔루션을 찾아보니 과연 유닛 테스트들을 작성할 수 있는 솔루션이 있었고, 이를 우리 프로젝트에 적용하기로 했다.
비주얼 스튜디오에서 제공하는 테스트케이스 솔루션(좌)과 팀 프로젝트를 진행하면서 생성한 테스트케이스 목록(우)
테스트 주도 개발 방식을 적용하면서 하나의 기능을 구현할 때마다 하나의 테스트 코드를 작성하기로 했다. 예를 들어 게임엔진에 물리엔진을 이식한 경우, 나는 중력과 물리 충돌이 잘 작동하는지 확인하기 위해 평면 위에 상자를 떨어뜨린 뒤 몇 초 후 상자의 y축 좌표를 확인하는 코드를 짰다.
가설을 세우고 그 가설에 맞는 유닛테스트를 실행한 모습, 시뮬레이션을 잠깐 실행한 후 Assert문이 실행되며, 내부 조건이 참이라면 프로그램은 정상코드로 종료한다.
나는 이 테스트케이스들이 누적될수록 프로젝트의 안정성 또한 보장될 것이라 판단했고, 이걸 잘 이용하면 젠킨스의 빌드 검증절차의 부족한 점을 보완할 수 있을 것 같았다. 나는 빌드머신에서 빌드 직후 수록된 모든 테스트들을 돌려 테스트가 하나라도 실패하면 빌드를 실패로 띄우게 만들었다. 이를 통해 마스터 브랜치에 커밋이 들어올 때마다 해당 커밋이 기존에 잘 작동하던 동작들을 망가뜨리지 않는지 확인할 수 있었고, 마스터 브랜치의 안정적인 빌드 히스토리를 추적할 수 있었다.
빌드 후 batch 파일을 실행해 등록된 테스트들을 전부 실행하고, 테스트가 단 하나라도 실패하면 빌드 결과를 실패로 기록하도록 절차를 만들었다.
테스트 케이스 코드 중 빌드 검증에 동원되지 않는 테스트코드들도 프로젝트에 넣을 수 있게 했다. 검증에 동원되지 않는 테스트라니, 팥없는 붕어빵이 아닌가 하는 생각이 들겠지만 사람의 눈으로 봐야 검증이 가능한 그래픽스 기능 테스트, 혹은 특정 기능을 시연하는 쇼케이스 코드와 같이 그저 아카이빙하고 싶은 실행코드들도 있을 수 있기 때문이다. 이런 테스트코드들은 프로젝트의 조각, 편린이라는 의미로 Snippet 코드라고 부르기로 했다. 빌드머신에서 실행되는 테스트용 batch 파일은 모든 테스트들을 실행하지만, 접두어로 Snippet이 붙은 테스트들은 무시하도록 만들었다.
Debug
Release
EditorUnitTests
디버그 버전 게임 + 툴 단위테스트 빌드
릴리즈 버전 게임 + 툴 단위테스트 빌드
UnitTests
디버그 버전 게임 단위 테스트 빌드
릴리즈 버전 게임 단위 테스트 빌드
GraohucsExe
그래픽스 디버깅 빌드
그래픽스 확인용 빌드
EditorExe
툴 디버깅 빌드
툴 배포 빌드
Exe
게임 디버깅 빌드
게임 출시 빌드
우리 프로젝트의 빌드 설정은 위와 같이 총 10개로 나뉘었다. 빌드머신은 마스터 브랜치가 업데이트 될 때마다 이 중 GraphicsExe 빌드를 제외한 나머지 8개 빌드가 컴파일에 성공하고, EditorUnitTests, UnitTests에 해당하는 4가지 버전에서 실행되는 단위 테스트들을 모두 통과해야 해당 빌드를 안정적인 것으로 간주했다.
테스트케이스라고 해서 자동화 테스트의 대상이 되는 코드만 있는 것은 아니다. 사람의 눈으로 봐야 검증이 되는 테스트, 기능의 사용법을 알려주기 위한 데모용 코드, 기능의 정상 동작을 시연하는 쇼케이스 테스트들은 따로 아카이빙 되었다.
프로세스를 개선한 소감
새로운 작업방식에 대한 팀원들의 반응은 모두 호평 일색이었다. 다들 '내가 커밋을 하면 갑자기 멀쩡한 프로젝트가 절단나진 않을까?' 하는 불안을 품고 있었는데 '테스트들이 모두 검증을 통과하면 안정적인 빌드로 간주한다.'는 원칙이 생기니까 팀원들이 마스터 브랜치에 커밋을 넣는 부담이 줄었다. 로컬 PC에서 자체적으로 테스트를 진행하고 커밋을 해도 되고, 그런 절차 없이 바로 커밋하더라도 빌드머신에 로그가 남아 어떤 커밋이 어떤 테스트를 실패하게 만들었는지 바로 추적할 수 있기 때문에 잘못된 커밋에 대한 부담이 덜했다.
테스트용으로 한번 쓰고 버리던 코드들을 Snippet 코드로 따로 뺄 수 있는 것도 반응이 매우 좋았다. 과거의 테스트 환경을 그대로 남기고 언제든 실행할 수 있게 만든다는 것은 생각보다 큰 의미가 있었다. 스니펫 코드들은 기능의 사용법을 설명하는 메뉴얼 역할을 했고, 구현된 기능을 시연하는 보고자 역할을 했다. 이전에 마구잡이로 개발할 때는 임시로 개발해 놓은 테스트용 코드들을 다음 테스트를 위해 지울때마다 뭔가 아깝다는 생각이 들었는데, 이제는 그럴 때마다 스니펫 코드로 저장한다. 이런 코드들은 묵혀두면 언젠가는 반드시 유용하게 쓰일 일이 생기더라.
내가 처음 빌드머신을 세팅하려고 한 동기는 지속적 통합 / 지속적 배포( Continus Integration / Continuous Delivery )가 개발 프로세스에 미치는 영향을 온몸으로 체감하고 싶었던 이유가 컸다. 빌드머신을 세팅하고 나니 이 중 CD는 몰라도 CI, 지속적 통합이 왜 중요한지는 뼈저리게 느끼게 되었다. 작업물의 지속적 통합에 대한 대책을 마련하지 않은 타 팀의 경우 '지금 내가 브랜치를 합쳐도 되느냐?', '내용을 커밋했을 때 문제가 생길까봐 겁난다.' 등 서로의 작업물들을 통합하는 것에 대해 상당한 부담감을 호소하는 경우가 잦았다. 부담감이 큰 만큼 서로의 작업이 통합되는 빈도가 잦지 않았고, 어쩌다 타인의 작업물을 합친다 한들 구현된 기능에 대한 품질검증이 이루어지지 않기 때문에 불안한 상태에서 작업을 계속해야 했다. 잘 동작하던 기능에 갑자기 문제가 발견될 경우 이 문제가 어느 커밋으로부터 비롯된 건지 특정하는 것도 힘들었다. 이는 팀원간 불신이 쌓이기 쉬운 환경이었고, 이런 환경 위에서 효율적인 협업을 기대하기는 힘들 것이었다. 지속적 통합의 가치는 지속적 통합이 부재한 경우 생기는 협업의 한계에서명백히 드러났다.
아쉬웠던 점
만약 게임 엔진에서 그래픽스 출력 기능을 끄고 테스트할 수 있었다면 좋았을 것이다. 젠킨스 서버를 돌리는 프로세스에는 그래픽스 출력 장치에 대한 접근 권한이 없어 이 문제를 우회하는 편법을 써야 했고, 또 필요 없는 기능에 컴퓨터 자원이 소모되는 것이 아쉬웠다.
또 원래 내가 생각했던 프로세스는 마스터 브랜치에 푸시가 들어올 때마다 빌드를 시도하는 게 아니라 풀 리퀘스트가 올라올 때마다 빌드머신에서 풀 리퀘스트를 반영해 테스트를 진행하고 문제가 없으면 마스터 브랜치와 병합하는 것이었다. 이렇게 절차를 만들었다면 마스터 브랜치에는 항상 안정적인 버전만 남길 수 있었을 텐데 아쉽다.
원래 의도했던 프로세스, 만약 이대로 동작했다면 마스터 브랜치에는 항상 안정적인 버전만 남길 수 있었을 것이다.
다음은 내가 테스트 자동화 환경을 구축하기 위해 사용한 기술들이다.
- Jenkins : 빌드머신 구축하는데 필요
- Ngrok : 빌드머신의 IP주소와 포트번호를 도메인 네임 서버에 등록해야 github webhook을 연동할 수 있기 때문에 필요
- psexec : 빌드머신은 System 계정으로 구동되는데, System 계정은 그래픽 출력 장치에 대한 권한이 없음. User계정에게 원격으로 CMD 명령어를 실행시켜 테스트를 진행시키고 싶을 때 필요
- Batch 파일 작성 : 일괄 테스트를 실행하면 한 프로세스에서 테스트코드들이 순차적으로 실행됨, 한 프로세스당 한 테스트코드를 실행시키면서 일괄테스트를 시키고 싶을 때, 어떤 테스트코드들은 빌드 검증에 관여하지 않게 만들고 싶을 때, 아무튼 자기 입맛에 맞게 임의로 테스트를 진행하고 싶다면 batch 파일 작성법을 배워야 함.
먼저 PhysX 씬을 생성하는 부분이다. sceneDesc에 filterShader와 simulationEventCallback를 제대로 설정해야 씬에서 생기는 충돌 이벤트를 잘 처리할 수 있다. simulationEventCallback은 당연히 물리 시뮬레이션 진행 도중 이벤트가 생길 때마다 호출되는 콜백객체고, filterShader는 타입이 PxSimulationFilterShader로 명명된 함수 포인터다. 이 함수 포인터 타입에 대한 설명은 다음과 같다.
/**
\brief Filter method to specify how a pair of potentially colliding objects should be processed.
Collision filtering is a mechanism to specify how a pair of potentially colliding objects should be processed by the
simulation. A pair of objects is potentially colliding if the bounding volumes of the two objects overlap.
In short, a collision filter decides whether a collision pair should get processed, temporarily ignored or discarded.
If a collision pair should get processed, the filter can additionally specify how it should get processed, for instance,
whether contacts should get resolved, which callbacks should get invoked or which reports should be sent etc.
The function returns the PxFilterFlag flags and sets the PxPairFlag flags to define what the simulation should do with the given collision pair.
\note A default implementation of a filter shader is provided in the PhysX extensions library, see #PxDefaultSimulationFilterShader.
This methods gets called when:
\li The bounding volumes of two objects start to overlap.
\li The bounding volumes of two objects overlap and the filter data or filter attributes of one of the objects changed
\li A re-filtering was forced through resetFiltering() (see #PxScene::resetFiltering())
\li Filtering is requested in scene queries
\note Certain pairs of objects are always ignored and this method does not get called. This is the case for the
following pairs:
\li Pair of static rigid actors
\li A static rigid actor and a kinematic actor (unless one is a trigger or if explicitly enabled through PxPairFilteringMode::eKEEP)
\li Two kinematic actors (unless one is a trigger or if explicitly enabled through PxPairFilteringMode::eKEEP)
\li Two jointed rigid bodies and the joint was defined to disable collision
\li Two articulation links if connected through an articulation joint
\note This is a performance critical method and should be stateless. You should neither access external objects
from within this method nor should you call external methods that are not inlined. If you need a more complex
logic to filter a collision pair then use the filter callback mechanism for this pair (see #PxSimulationFilterCallback,
#PxFilterFlag::eCALLBACK, #PxFilterFlag::eNOTIFY).
\param[in] attributes0 The filter attribute of the first object
\param[in] filterData0 The custom filter data of the first object
\param[in] attributes1 The filter attribute of the second object
\param[in] filterData1 The custom filter data of the second object
\param[out] pairFlags Flags giving additional information on how an accepted pair should get processed
\param[in] constantBlock The constant global filter data (see #PxSceneDesc.filterShaderData)
\param[in] constantBlockSize Size of the global filter data (see #PxSceneDesc.filterShaderDataSize)
\return Filter flags defining whether the pair should be discarded, temporarily ignored, processed and whether the
filter callback should get invoked for this pair.
@see PxSimulationFilterCallback PxFilterData PxFilterObjectAttributes PxFilterFlag PxFilterFlags PxPairFlag PxPairFlags PxSceneDesc.filterShader
*/
typedef PxFilterFlags (*PxSimulationFilterShader)
(PxFilterObjectAttributes attributes0, PxFilterData filterData0,
PxFilterObjectAttributes attributes1, PxFilterData filterData1,
PxPairFlags& pairFlags, const void* constantBlock, PxU32 constantBlockSize);
PhysX의 충돌 객체들은 서로의 바운딩 볼륨의 영역이 서로 겹치고 난 다음에야 더 정밀한 충돌체크를 하든, 트리거 이벤트를 발생시키든 추가적인 작업을 한다. PxSimulationFilterShader는 두 충돌체의 바운딩 볼륨이 겹쳤을 때 어떤 작업을 해야 하는지, 콜백 함수를 불러야 한다면 어떤 함수를 불러야 하는지를 정의한다. 충돌체들이 서로 어떤 관계를 가져야 하는지 정의하는 함수가 바로 FilterShader라고 할 수 있겠다.
이 함수는 PxFilterFlag를 반환하며, PxPairFlags의 값들을 수정하는 것으로 물리 시뮬레이션이 충돌체 쌍을 어떻게 처리해야하는지에 대한 정보를 저장한다.
이 함수는 두 충돌체의 바운딩 볼륨이 겹치기 시작할때, 혹은 바운딩 볼륨이 겹쳐진 상태에서 한 오브젝트의 속성값이 바뀌었을때 호출된다.
이 함수는 여러 스레드에 의해 수없이 많이 불리기 때문에 퍼포먼스에 심각한 영향을 줄 수 있다. 정말 제대로 물리 이벤트가 터졌을 때 호출되는 함수가 아니라 충돌체들이 어느정도 가까워지기만 하면 호출되기 때문이다. 함수가 어떤 상태에 따라 동작이 달라져서는 아니될 것이며, 심지어는 함수 호출조차 인라인 함수만 사용해야 한다.
함수의 각 파라미터들에 대한 정보는 다음과 같다.
attribute0 [in] : 첫번째 오브젝트의 필터 속성
filterData0 [in] : 첫번째 오브젝트의 사용자 정의 필터 데이터
attribute1 [in] : 두번째 오브젝트의 필터 속성
filterData1 [in] : 두번째 오브젝트의 사용자 정의 필터 데이터
pairFlags [out] : 충돌체 쌍이 어떻게 처리되어야 할지 추가 정보를 저장할 플래그 정보
constantBlock [in] : 전역 필터 데이터, 물리 시뮬레이션을 시작하기 전에 전역으로 임의의 필터링 플래그를 세워두고 이 전역 플래그에 따라 필터링 동작을 다르게 하고 싶을 때 쓸 수 있다.
constantBlockSize [in] : 전역 필터 데이터의 사이즈
이중 attribute와 filterData는 PxShape로부터 데이터를 추출한다.
FilterShader 함수를 부를 가치조차 없는 충돌체 쌍들도 존재한다. 다음과 같은 경우들은 바운딩 볼륨이 겹치든 말든 어차피 뭔가를 처리할 필요가 없기 때문에 무시된다.
- 위치와 회전이 항상 고정된 정적 충돌체들로만 이루어진 쌍(Pair of static rigid actors)
- 트랜스폼 상태를 바꿀 수는 있지만 물리법칙에 상태가 영향받지는 않는 키네마틱 충돌체로 이루어진 쌍 (Two Kinematic actors)
- 키네마틱 충돌체와 정적 충돌체로 이루어진 쌍 (A static rigid actor and a kinematic actor)
- etc...
static PxFilterFlags contactReportFilterShader( PxFilterObjectAttributes attributes0, PxFilterData filterData0,
PxFilterObjectAttributes attributes1, PxFilterData filterData1,
PxPairFlags& pairFlags, const void* constantBlock, PxU32 constantBlockSize)
{
PX_UNUSED(attributes0);
PX_UNUSED(attributes1);
PX_UNUSED(filterData0);
PX_UNUSED(filterData1);
PX_UNUSED(constantBlockSize);
PX_UNUSED(constantBlock);
// all initial and persisting reports for everything, with per-point data
pairFlags = PxPairFlag::eSOLVE_CONTACT | PxPairFlag::eDETECT_DISCRETE_CONTACT
| PxPairFlag::eNOTIFY_TOUCH_FOUND
| PxPairFlag::eNOTIFY_TOUCH_PERSISTS
| PxPairFlag::eNOTIFY_CONTACT_POINTS;
return PxFilterFlag::eDEFAULT;
}
SnippetContactReport 프로젝트의 filterShader는 충돌체 객체들의 속성이나 필터 데이터에 상관없이 무조건 고정된 플래그들을 반환하게 만들어놨다. 이 플래그들은 각각 다음과 같은 의미를 가진다.
PxPairFlag::eSOLVE_CONTACT : 충돌이 일어났을때 충돌체들이 서로 파고들지 않게 dynamics solver로 충돌체들의 트랜스폼 값들을 수정하게 한다.
PxPairFlag::eDETECT_DISCRETE_CONTACT : 충돌체들의 충돌여부를 체크하는 방식으로 discrete_contact를 사용한다. discrete는 연속적으로 충돌여부를 체크하는 CCD(Continuous Collision Detection) 방식과 대비되는 고효율 저정밀 충돌체크 방식이다. PxPairFlag::eNOTIFY_TOUCH_FOUND : 충돌체간에 접촉을 시작할때 접촉 콜백 함수를 호출한다. PxPairFlag::eNOTIFY_TOUCH_PERSISTS : 충돌체가 다른 충돌체와 접촉을 유지하고 있을 때 콜백 함수를 호출한다. PxPairFlag::eNOTIFY_CONTACT_POINTS : 충돌체가 다른 충돌체와 접촉을 그만두었을 때 콜백 함수를 호출한다.
/**
\brief An interface class that the user can implement in order to receive simulation events.
With the exception of onAdvance(), the events get sent during the call to either #PxScene::fetchResults() or
#PxScene::flushSimulation() with sendPendingReports=true. onAdvance() gets called while the simulation
is running (that is between PxScene::simulate() or PxScene::advance() and PxScene::fetchResults()).
\note SDK state should not be modified from within the callbacks. In particular objects should not
be created or destroyed. If state modification is needed then the changes should be stored to a buffer
and performed after the simulation step.
<b>Threading:</b> With the exception of onAdvance(), it is not necessary to make these callbacks thread safe as
they will only be called in the context of the user thread.
@see PxScene.setSimulationEventCallback() PxScene.getSimulationEventCallback()
*/
class PxSimulationEventCallback
{
...
sceneDesc의 simulationEventCallback은 라이브러리의 사용자가 상속받아 구현할 수 있는 인터페이스다. PhysX의 시뮬레이션 연산은 Cpu에서 멀티스레딩으로 동작하거나 GPU 상에서 동작하는데, PxSimulationEventCallback의 함수들은 한 틱의 물리 시뮬레이션을 다 끝내고 사용자가 직접 메인 스레드에서 PxScene::fetchResults() 함수를 호출할 때 실행되기 때문에 스레드 안전성을 고민할 필요까지는 없다.
PxFoundation은 PhysX와 관련된 모든 객체들의 기반이 되는 싱글톤 객체라고 한다. 이 파운데이션 객체에 매달린 객체들이 먼저 모두 릴리즈되어야 파운데이션 객체도 릴리즈할 수 있다.
gPvd = PxCreatePvd(*gFoundation);
PxPvdTransport* transport = PxDefaultPvdSocketTransportCreate(PVD_HOST, 5425, 10);
gPvd->connect(*transport,PxPvdInstrumentationFlag::eALL);
PxCreatePvd함수는 파운데이션 객체에 의존하는 PxPvd 클래스를 생성한다. PVD는 PhysX Visual Debugger라는 의미로, 이 클래스로부터 connect 함수를 호출하면 PhysX 기반으로 물리연산을 하는 어플리케이션으로부터 물리정보를 받아 PhysX Visual Debugger 프로그램에서 물리엔진의 동작 상태를 시각적으로 확인할 수 있다.
좌측의 프로그램은 PhysX를 기반으로 물리시뮬레이션을 돌리는 프로그램, 오른쪽은 PhysX Visual Debugger. PVD는 알짜 물리연산 정보들만 사용자에게 표시해준다,
CreateShape 함수는 Shape의 속성을 나타내는 PxShapeFlags를 매개변수로 받는데 여기에 어떤 플래그를 활성화시키느냐에 따라 같은 Shape를 물리 시뮬레이션이 되는 덩어리 물질로 쓸수도 있고, 다른 물질이 닿았는지만 체크하는 볼륨 트리거로 쓸 수도 있다.
renderCallback은 매 렌더 업데이트마다 호출되는 함수다. 먼저 씬의 simulate 함수에 델타 타임을 매개변수로 넣어 시뮬레이션을 돌리고 그 결과를 받는다. 이 예제 코드에서는 업데이트된 액터들의 상태를 토대로 렌더링만 시키는데 내 게임엔진에서는 액터들의 상태를 이용해 컴포넌트들의 콜백 함수를 호출하거나 상태를 바꾸면 될 것 같다.
이 글에서는 RecastNavigation 라이브러리의 함수와 기능을 내 게임 엔진에 이식한 결과를 소개한다.
2. 구상
내 게임엔진의 클라이언트 프로그램은 RecastNavigation 라이브러리가 어떤 녀석인지 전혀 몰라도 길찾기 기능을 사용할 수 있어야 한다.
버텍스 좌표와 인덱스 좌표를 받아 네비게이션 필드를 만드는 NavigationField 클래스와 이동 명령을 받고 길을 찾아 움직이는 NavigationAgent 클래스만 만들어 주면 클라이언트 입장에서 손쉽게 활용이 가능할 것이다.
3. NavigationField
#pragma once
#include "YunutyEngine.h"
#include "Component.h"
#include "Vector3.h"
#include <vector>
#include <assert.h>
#ifdef YUNUTY_EXPORTS
#define YUNUTY_API __declspec(dllexport)
#else
#define YUNUTY_API __declspec(dllimport)
#endif
namespace yunutyEngine
{
class NavigationAgent;
class YUNUTY_API NavigationField : public Component
{
public:
class Impl;
struct BuildSettings
{
// 길찾기 주체들의 최대 개체수
int maxCrowdNumber{ 1024 };
// 길찾기 주체들의 최대 충돌반경
float maxAgentRadius{ 0.6 };
// 오를수 있는 경사
float walkableSlopeAngle{ 30 };
// 오를 수 있는 단차
float walkableClimb{ 0.2 };
// 천장의 최소 높이
float walkableHeight{ 0.3 };
// x축,z축 공간 분할의 단위, 단위가 작을수록 판정이 더 세밀해지지만, 네비게이션 빌드와 길찾기 시스템의 부하가 늘게 된다.
float divisionSizeXZ{ 0.3 };
// y축 공간 분할의 단위, 단위가 작을수록 판정이 더 세밀해지지만, 네비게이션 빌드와 길찾기 시스템의 부하가 늘게 된다.
float divisionSizeY{ 0.2 };
// 공간 분할은 xz축으로 250*330, y축으로 200개 정도 분할되는 정도면 순식간에 네비게이션 빌드도 되면서 길찾기도 무리없이 하게 되는 정도다.
// xz축으로 743* 989개 정도 분할이 되도 큰 부하는 없다.
};
NavigationField();
virtual ~NavigationField();
virtual void Update();
void BuildField(const float* worldVertices, size_t verticesNum, const int* faces, size_t facesNum, const BuildSettings& buildSettings = BuildSettings{});
void BuildField(std::vector<Vector3f> worldVertices, std::vector<int> faces, const BuildSettings& buildSettings = BuildSettings{})
{
static_assert(sizeof(Vector3f) == sizeof(float) * 3);
assert(!worldVertices.empty() && !faces.empty());
assert(faces.size() % 3 == 0);
BuildField(reinterpret_cast<float*>(&worldVertices[0]), worldVertices.size(), &faces[0], faces.size() / 3, buildSettings);
}
private:
Impl* impl{ nullptr };
friend NavigationAgent;
};
}
( YunutyNavigationField.h )
#pragma once
#include "YunutyNavigationField.h"
#include "Recast.h"
#include "DetourNavMesh.h"
#include "DetourNavMeshBuilder.h"
#include "DetourNavMeshQuery.h"
#include "DetourCrowd.h"
namespace yunutyEngine
{
// Impl은 그저 데이터만 쌓아두는 곳으로 쓴다.
class NavigationField::Impl
{
private:
Impl(NavigationField* navFieldComponent) :navFieldComponent(navFieldComponent)
{
navQuery = dtAllocNavMeshQuery();
crowd = dtAllocCrowd();
context = std::make_unique<rcContext>(rcContext());
}
virtual ~Impl()
{
dtFreeCrowd(crowd);
dtFreeNavMeshQuery(navQuery);
}
friend NavigationField;
public:
NavigationField* navFieldComponent;
std::unique_ptr<rcContext> context;
rcPolyMesh* polyMesh;
rcConfig config;
rcPolyMeshDetail* polyMeshDetail;
class dtNavMesh* navMesh;
class dtNavMeshQuery* navQuery;
class dtCrowd* crowd;
};
}
( YunutyNavigationFieldImpl.h )
NavigationField 클래스는 클라이언트에게 헤더파일이 노출되는 클래스이다. 클라이언트 개발자는 구태여 RecastNavigation의 존재를 알 필요가 없기 때문에 RecastNavigation과 관련된 선언은 따로 이너 클래스 Impl을 만들어 그 안에 집어 넣는다.
네비게이션 메시 빌드 함수는 버텍스 정보와 페이스 정보를 매개변수로 받아 동작하도록 만들었다. 그 외의 부분은 RecastDemo 프로젝트의 빌드 코드를 거의 복사해서 붙여넣었다. 실패는 용납할 수 없기 때문에 빌드과정에서 차질이 있거나(dtStatusFailed(status)) 객체가 제대로 생성되지 않았을 경우(navMesh...etc !=nullptr)바로 런타임 에러를 일으킬 수 있도록 assert를 박았다.
- 페이스를 구성하는 인덱스들은 세 점을 이어 화살표를 만들었을 때 시계방향으로 도는 모양이 되어야 한다. 외적연산을 통해 도출되는 평면의 수직방향이 중요하게 취급되기 때문이다.
- polyMesh는 밟을 수 있는 평면들(polygon)에 대한 정보를 담고 있다. 각 평면들의 필터는 반드시 0이 아닌 값이 들어가야 한다. NavigationAgent는 통행할 수 있는 평면들을 필터링하기 위해 논리곱 비트플래그 연산(&)을 사용하는데 평면의 필터값이 0이면 참 값이 반환될수가 없다. 이 필터링 동작을 간과한 것 때문에 족히 여섯시간을 날렸다.
네비게이션 메시 위에서 dtAgent들이 돌아다니려면, dtAgent들의 집합인 dtCrowd의 업데이트 함수를 불러줘야 한다. 유닛들의 이동은 서로가 서로의 상태에 의해 영향을 받기 때문에 유닛별로 업데이트를 시키는 것이 아니라 군중에 대해 업데이트를 시키는 것이다. 매 게임엔진 업데이트 주기마다 프레임간 시간 간격을 매개변수로 군중의 이동 상태를 업데이트해준다.
유닛에게 이동 명령을 내릴 때는 명령의 대상지점으로부터 가장 가까운 접근가능지점을 찾아 그 위치에 requestMoveTarget 함수를 호출하면 된다. NavigationAgent클래스의 역할은 이렇게 유닛의 상태를 바꾸는 것 뿐이고, 유닛의 상태에 따라 위치정보를 업데이트하는 것은 NavigationField 클래스의 역할이 된다.
이제 테스트용 코드를 만들어내어 엔진에서 잘 작동하는지 확인해야 한다. CreateNavPlane함수는 사각형 메시의 좌측하단의 점과 우측상단의 점을 매개로 사각형 평면을 만들고 버텍스 정보와 페이스 정보를 추가한다. 이 정보를 토대로 BuildField 함수를 호출하고 완성된 네비게이션 필드에 유닛을 3기 추가시킨다. 평면과 유닛 객체에는 모두 디버그 메시를 달아놓아 그 형체를 구분할 수 있게 하고 화면 우클릭에 해당하는 콜백함수를 달아 유닛의 MoveTo 함수를 호출할 수 있게 한다.
RecastDemo 프로젝트에서는 프로그램을 실행하고 네비게이션을 빌드한 후, 경로 위에 dtAgent 객체들을 배치하고 임의의 지점으로 이동명령을 내릴 수 있다.dtAgent는 길 위에 배치하고 움직이게 만들 수 있는 하나의 길찾기 주체이며, DetourCrowd는 dtAgent 객체들의 군집을 일컫는 말이다. 스타크래프트에 익숙한 우리네 정서에 맞게 dtAgent는지금부터 유닛이라 부르겠다.
2. AddAgent
void CrowdToolState::addAgent(const float* p)
{
if (!m_sample) return;
dtCrowd* crowd = m_sample->getCrowd();
dtCrowdAgentParams ap;
memset(&ap, 0, sizeof(ap));
ap.radius = m_sample->getAgentRadius();
ap.height = m_sample->getAgentHeight();
ap.maxAcceleration = 8.0f;
ap.maxSpeed = 3.5f;
ap.collisionQueryRange = ap.radius * 12.0f;
ap.pathOptimizationRange = ap.radius * 30.0f;
ap.updateFlags = 0;
if (m_toolParams.m_anticipateTurns)
ap.updateFlags |= DT_CROWD_ANTICIPATE_TURNS;
if (m_toolParams.m_optimizeVis)
ap.updateFlags |= DT_CROWD_OPTIMIZE_VIS;
if (m_toolParams.m_optimizeTopo)
ap.updateFlags |= DT_CROWD_OPTIMIZE_TOPO;
if (m_toolParams.m_obstacleAvoidance)
ap.updateFlags |= DT_CROWD_OBSTACLE_AVOIDANCE;
if (m_toolParams.m_separation)
ap.updateFlags |= DT_CROWD_SEPARATION;
ap.obstacleAvoidanceType = (unsigned char)m_toolParams.m_obstacleAvoidanceType;
ap.separationWeight = m_toolParams.m_separationWeight;
int idx = crowd->addAgent(p, &ap);
if (idx != -1)
{
if (m_targetRef)
crowd->requestMoveTarget(idx, m_targetRef, m_targetPos);
// Init trail
AgentTrail* trail = &m_trails[idx];
for (int i = 0; i < AGENT_MAX_TRAIL; ++i)
dtVcopy(&trail->trail[i*3], p);
trail->htrail = 0;
}
}
dtCrowdAgentParams는 CrowdAgent, 즉 유닛의 길찾기 관련 설정을 지정하기 위해 쓰이는 구조체이다. 유닛의 크기, 높이, 최대 속도와 최대 가속도, 길찾기 원칙 등을 저장한다. 이 매개변수 구조체의 필드값을 알맞게 설정하고 dtCrowd->addAgent 함수를 호출하면 유닛이 생성된다.
3. SetMoveTarget
void CrowdToolState::setMoveTarget(const float* p, bool adjust)
{
......
navquery->findNearestPoly(p, halfExtents, filter, &m_targetRef, m_targetPos);
......
{
for (int i = 0; i < crowd->getAgentCount(); ++i)
{
const dtCrowdAgent* ag = crowd->getAgent(i);
if (!ag->active) continue;
crowd->requestMoveTarget(i, m_targetRef, m_targetPos);
}
}
}
}
유닛을 생성하고 이동모드로 지면을 클릭하면 클릭된 위치로 유닛이 이동한다. 이 함수의 코드의 양도 여차저차 내용이 길지만, 핵심적인 부분은 클릭한 지점으로부터 가장 가까운 지점을 query->findnearestPoly 함수로 찾아 목표지로 지정하는 부분과 유닛 군집(dtCrowdAgent)을 순회하며 개개의 유닛들에게 requestMoveTarget 함수를 통해 목표지까지의 이동을 부탁하는 부분이다. 필요할때맏 유닛들의 길찾기 상태만 이렇게 바꾸어 주면 유닛들이 매 순간 이동하면서 생기는 필요연산은 CrowdUpdate 함수에서 처리된다.
4. CrowdUpdate
void CrowdToolState::updateTick(const float dt)
{
if (!m_sample) return;
dtNavMesh* nav = m_sample->getNavMesh();
dtCrowd* crowd = m_sample->getCrowd();
if (!nav || !crowd) return;
TimeVal startTime = getPerfTime();
if (m_toolParams.m_showCorners)
crowd->update(dt, &m_agentDebug);
TimeVal endTime = getPerfTime();
// Update agent trails
for (int i = 0; i < crowd->getAgentCount(); ++i)
{
const dtCrowdAgent* ag = crowd->getAgent(i);
AgentTrail* trail = &m_trails[i];
if (!ag->active)
continue;
// Update agent movement trail.
trail->htrail = (trail->htrail + 1) % AGENT_MAX_TRAIL;
dtVcopy(&trail->trail[trail->htrail * 3], ag->npos);
}
m_agentDebug.vod->normalizeSamples();
m_crowdSampleCount.addSample((float)crowd->getVelocitySampleCount());
m_crowdTotalTime.addSample(getPerfTimeUsec(endTime - startTime) / 1000.0f);
}
군집들의 상태설정만 필요할때마다 해주면 각각의 길찾기 주체들의 상태 업데이트는 crowd->Update 함수만 주기적으로 호출하면 알아서 실행된다. RecastDemo 프로젝트에서는 updateTick이라는 함수에서 군집의 Update 함수를 호출해준다.
다음은 지금까지 파악한 네비게이션 메시 빌드와 dtAgent,dtCrowd들을 이용해 나의 게임엔진에 길찾기 시스템을 이식하는 내용을 다룰 것이다.
일전에 네비게이션 빌드의 결과로 navQuery와 navMesh 객체를 생성하는 것을 확인했다. 이제 빌드된 네비게이션 맵 위에 경로의 시작점과 끝 점을 설정했을 때 경유해야할 지점들을 어떻게 얻어낼 수 있는지 알아보자.
그림 1. Start와 End 지점이 찍혔을 때 사이의 경로가 점선으로 찍히는 모습
RecastDemo 프로젝트를 실행한 후 Test Navmesh 옵션이 활성화된 상태에서 지면에 마우스를 클릭하면 경로의 시작점과 종점을 지정할 수 있다. 이렇게 경로를 지정할때마다 NavMeshTesterTool 클래스의 recalc 함수가 호출되는데, 시작점과 종점이 모두 지정된 상태라면 일전에 생성한 navQuery 객체로부터 findPath 함수가 호출된다.
findPath 함수는 시작좌표와 끝 좌표로부터 가장 가까운 시작 폴리곤, 끝 폴리곤의 레퍼런스를 가져오고, 시작부터 끝 폴리곤까지 가면서 경유하게 되는 폴리곤들의 레퍼런스들도 가져온다.
경로의 시점이 포함된 폴리곤은 주황색으로, 종점이 포함된 폴리곤은 초록색으로 표시되었다. 갈색으로 표시된 폴리곤은 경로를 이동하면서 지나가게 되는 폴리곤이다. 이 경우 경유 폴리곤의 갯수는 시점 폴리곤과 종점 폴리곤을 포함해 총 5개가 된다.
3. 부드러운 경로 탐색
if (m_npolys)
{
// Iterate over the path to find smooth path on the detail mesh surface.
dtPolyRef polys[MAX_POLYS];
memcpy(polys, m_polys, sizeof(dtPolyRef)*m_npolys);
int npolys = m_npolys;
float iterPos[3], targetPos[3];
m_navQuery->closestPointOnPoly(m_startRef, m_spos, iterPos, 0);
m_navQuery->closestPointOnPoly(polys[npolys-1], m_epos, targetPos, 0);
static const float STEP_SIZE = 0.5f;
static const float SLOP = 0.01f;
m_nsmoothPath = 0;
dtVcopy(&m_smoothPath[m_nsmoothPath*3], iterPos);
m_nsmoothPath++;
이제 시작점부터 종착점까지 전진거리(STEP_SIZE)를 0.5로 잡고 경로에 위치한 경유지점들을 찾아내야 한다. 시작점과 종착점을 시점 폴리곤과 종점 폴리곤 위에 사영시켜 이터레이터용 좌표변수(iterPos)를 시점으로부터 초기화한다.
// Move towards target a small advancement at a time until target reached or
// when ran out of memory to store the path.
while (npolys && m_nsmoothPath < MAX_SMOOTH)
{
// Find location to steer towards.
float steerPos[3];
unsigned char steerPosFlag;
dtPolyRef steerPosRef;
if (!getSteerTarget(m_navQuery, iterPos, targetPos, SLOP,
polys, npolys, steerPos, steerPosFlag, steerPosRef))
break;
bool endOfPath = (steerPosFlag & DT_STRAIGHTPATH_END) ? true : false;
bool offMeshConnection = (steerPosFlag & DT_STRAIGHTPATH_OFFMESH_CONNECTION) ? true : false;
지금부터는 반복문에 진입하여 부드러운 경로(smoothPath)를 만들어내는 구간이다.
getSteerTarget함수는 네비게이션 메시가 목적지까지 가기 위해 직진하다가 경로를 꺾어야(Steer) 하는 지점을 찾아준다. 더 이상 경로를 꺾을 것도 없이 직진만 해도 목표지점에 도달할 수 있다면 endOfPath가 참 값이 된다.
만약 경로를 꺾어야 하는 지점이 네비게이션 메시 바깥에 존재한다면 offMeshConnection이 참 값이 된다.
// Find movement delta.
float delta[3], len;
dtVsub(delta, steerPos, iterPos);
len = dtMathSqrtf(dtVdot(delta, delta));
// If the steer target is end of path or off-mesh link, do not move past the location.
if ((endOfPath || offMeshConnection) && len < STEP_SIZE)
len = 1;
else
len = STEP_SIZE / len;
float moveTgt[3];
dtVmad(moveTgt, iterPos, delta, len);
먼저 전환점(steerPos)과 현재위치(iterPos)의 변위벡터(delta)를 구한 다음, 이로부터 현재위치와 전환점 사이의 거리(len = dtMathSqrtf(dtVdot(delta,delta)))를 구한다. 그리고 현재위치로부터 변위벡터 방향으로 보폭(STEP_SIZE)만큼 떨어진 곳을 이동대상지점(moveTgt)으로 정한다. 목표 경유지까지 딱 한걸음만 이동하려는 것이다. 만약 거리가 보폭보다 짧다면 딱 전환점까지만 이동한다.
이제 네비게이션 쿼리의 moveAlongSurface 함수를 호출하면 목표위치로 이동을 시도하고, 이동이 끝난 좌표를 result에 저장한다. 길을 찾아 진행하는 과정에서 어떤 네비게이션 폴리곤들을 탐색하였는지에 대한 결과를 visitied,nvisited 변수로 받아온다. fixupShortcuts 함수는 탐색된 경로에 유턴이 없는지 확인하고 수정한다. fixUpCorridor도 유사하게 잘못된 경로를 수정하는 역할인 것 같은데, 정확하게 뭔지는 모르겠다.
// Handle end of path and off-mesh links when close enough.
if (endOfPath && inRange(iterPos, steerPos, SLOP, 1.0f))
{
// Reached end of path.
dtVcopy(iterPos, targetPos);
if (m_nsmoothPath < MAX_SMOOTH)
{
dtVcopy(&m_smoothPath[m_nsmoothPath*3], iterPos);
m_nsmoothPath++;
}
break;
}
만약 경로의 끝(endOfPath)에 도달했다면 현재위치를 종착점으로 바꾸고 반복문을 종료한다.
else if (offMeshConnection && inRange(iterPos, steerPos, SLOP, 1.0f))
{
// Reached off-mesh connection.
float startPos[3], endPos[3];
// Advance the path up to and over the off-mesh connection.
dtPolyRef prevRef = 0, polyRef = polys[0];
int npos = 0;
while (npos < npolys && polyRef != steerPosRef)
{
prevRef = polyRef;
polyRef = polys[npos];
npos++;
}
for (int i = npos; i < npolys; ++i)
polys[i-npos] = polys[i];
npolys -= npos;
// Handle the connection.
dtStatus status = m_navMesh->getOffMeshConnectionPolyEndPoints(prevRef, polyRef, startPos, endPos);
if (dtStatusSucceed(status))
{
if (m_nsmoothPath < MAX_SMOOTH)
{
dtVcopy(&m_smoothPath[m_nsmoothPath*3], startPos);
m_nsmoothPath++;
// Hack to make the dotted path not visible during off-mesh connection.
if (m_nsmoothPath & 1)
{
dtVcopy(&m_smoothPath[m_nsmoothPath*3], startPos);
m_nsmoothPath++;
}
}
// Move position at the other side of the off-mesh link.
dtVcopy(iterPos, endPos);
float eh = 0.0f;
m_navQuery->getPolyHeight(polys[0], iterPos, &eh);
iterPos[1] = eh;
}
}
만약 다음 목표지가 현재 탐색중인 폴리곤 바깥에 존재한다면(offMeshConnection) 현재 폴리곤을 다음 경유 폴리곤으로 바꾼다.
// Store results.
if (m_nsmoothPath < MAX_SMOOTH)
{
dtVcopy(&m_smoothPath[m_nsmoothPath*3], iterPos);
m_nsmoothPath++;
}
반복문의 마지막 단계에서는 경유지 포인트의 정보를 m_moothPath로 지정한다. 이 코드 이후는 얻어낸 경유지마다 디버그 그래픽스 객체를 그리는 내용이다.
한번 경로계산이 끝나고 smoothPath에 경유지가 101개 찍힌 모습.101개의 경유지를 거쳐 목적지까지 가는 길이 표시된 모습
4. 요약
전체 프로세스를 간략하게 표시하면 이렇게 된다.
다음 글에서는 detour 군집(dtCriwd)에게 이동 명령을 내렸을 때 이 주체들이 어떻게 각자 충돌 크기를 가지고 실시간으로 경로를 계산하며 이동하는지 확인해보겠다.
게임개발에 길찾기 기능이 필요하게 되어 RecastNavigation이라는 오픈소스 길찾기 라이브러리를 내 게임엔진에 통합할 일이 생겼다. 깃허브에서 소스 코드를 다운로드 받으면 라이브러리 프로젝트와 함께 라이브러리 기능의 시연용 프로젝트로 RecastDemo라는 프로젝트가 있는데, 이 글은 시연용 프로젝트의 기능 중 네비게이션 메시를 생성하는 빌드 함수를 분석한 내용을 정리한 것이다.
Recast Demo 프로젝트를 실행하고, 메시를 로드한 후 빌드 버튼을 누르면 푸른색으로 이동경로 맵이 생성된다.
이때 실행되는 함수는 sample 객체의 handleBuild 함수다. 이 글의 이후 내용은 모두 이 handleBuild 함수의 본문이 어떻게 전개되는지를 다룬다.
2. 빌드 설정값 초기화
사전에 불러들인 지오메트리의 데이터를 이용해 네비게이션 메시 빌드에 필요한 정보들을 초기화하는 모습
handleBuild는 실질적인 네비게이션 메시 빌드 함수를 부르기 전에 필요한 설정값을 먼저 초기화한다. 먼저 지오메트리에서 가져온 메시로부터 버텍스 리스트와 페이스 리스트, 바운더리에 대한 정보를 가져와 변수에 담는다.
빌드에 필요한 설정값들을 m_cfg 구조체에 다 집어넣는 모습
m_cfg는 길찾기 주체(Agent)들의 보행가능 경사각(WalkableSlopeAngle), 보행가능 높이(WalkableClimb) 등 앞으로의 네비게이션 메시 빌드과정에 두고 두고 쓰이게 될 설정값들을 몰아서 저장하는 구조체 변수이다. 일전에 구해둔 공간 바운더리 정보(bmin,bmax)도 rcConfig의 멤버변수 값으로 저장한다.
3. 네비게이션 메시 빌드
네비게이션 빌드가 시작되면서 rcContext 클래스가 빌드의 시작을 알리는 로그를 남기는 모습
네비게이션 빌드와 관련된 코드에 진입하면서 빌드의 시작을 알리는 로깅 함수가 호출된다. m_ctx는 네비게이션 빌드가 진행될 때의 진행내역을 로그로 남기는 역할을 하는 맥락(rcContext) 변수다. 맥락이라는 클래스 이름은 이 클래스의 역할이 네비게이션 빌드 작업의 진행 내역을 로그로 계속 추적하는 역할을 맡고 있기에 이런 것이리라. 코드를 해석하려는 사람 입장에선 이런 로깅 함수가 사용되는 부분들이 코드의 역할과 진행상황을 설명해주는 주석 역할을 해준다.
빌드가 시작되면 먼저 높이필드(HeightField)라는 객체를 생성한다. rcAllocHeightfield 함수로 메모리를 할당받고, rcCreateHeightfield 함수로 높이필드의 3차원 볼륨(m_cfg.bmin, bmax), 2차원 면적(width, height) 등의 정보를 토대로 높이필드의 상태를 초기화한다.
이어 폴리곤 데이터를 저장할 수 있는 배열을 동적 생성한 후, 먼저 보행가능 경사각(WalkableSlopeAngle)을 보고 rcMarkWalkableTriangles 함수를 통해 걸어다닐 수 있는 영역을 걸러낸다. 그 다음 rcRasterizeTriangles를 통해 보행가능 높이(walkableClimb) 안에서 고저차가 있는 가파른 지형들을 서로 연결시켜 이어준다. 계단같은 경우 고저차는 낮지만 경사각이 가팔라 통행이 불가능한데, 보행가능 높이를 적절히 높여주면 계단의 영역들이 서로 이어져 건널 수 있는 통로가 된다.
rcMarkWalkableTriangles 함수는 보행가능 경사각(WalkableSlopeAngle)을 보고 폴리곤(Triangles)중 걸어다닐 수 있는(Walkable) 영역을 표시(Mark)한다. 왼쪽은 경사각을 20도로 두었을 때, 오른쪽은 경사각을 45도로 두었을 때 네비게이션 메시 빌드의 결과다.
rcRasterizeTriangles 함수는 보행가능 높이(WalkableClimb)를 토대로 무시할 수 있는 고저차를 두고 떨어져 있는 폴리곤(Triangles)들 사이의 공백을 채워(Rasterize) 준다.
그 후 필터링 단계에서는 절벽 가장자리, 장애물의 유무 등 다른 다양한 조건들을 보고 접근불가한 부분을 판별한다. 이 부분은 필터링 옵션에 따라 진행할수도, 진행하지 않을 수도 있다.
경로에 대한 정보들이 다 정리가 되어 높이필드(rcHeightField)가 만들어지면, 이를 적절히 가공해서 경로계산 연산에 최적화된 형태의 데이터로 만든다. 이 최적화된 데이터 형태를 밀집 높이필드(rcCompactHeightfield)라 하는데, 아마 데이터를 밀집시켜서 캐시 히트율을 높이는 것으로 연산시간의 감소를 노린 것 같다. 밀집 높이필드가 생성되면 더이상 쓸모가 없는 복셀 높이필드는 할당해제한다. 밀집 높이필드가 할당되고 나면 연이어 최적화 함수들을 더 호출해서 필요한 데이터의 양은 더욱 압축시키고, 서로 연관성이 높은 데이터들은 더욱 응집시킨다.
rcErodeWalkableArea 함수는 유닛의 최소 충돌크기(m_cfg.walkableRadius)에 따라 접근가능한 영역을 더 제한한다. 아마 지형 가장자리의 접근영역을 유닛의 반지름크기만큼 잘라내는 역할일 것이다.
Mark Area는 지역의 특징을 플래그로 지정한다. 네비게이션 주체는 나중에 이 플래그를 보고 특정 지역을 통행할 수 있는지 없는지 판단하게 된다.
높이필드의 분할방법에 대한 장단점을 개발자가 주석으로 남겨놓았다.분할 방식에 따라 코드가 갈리는 모습
다음으로, 네비게이션 영역을 적절히 분할한다. 분할방법은 Watershed, Monotone, Layer 이 세가지로 나뉘어 각각 장단점이 있다고 한다. 심화 길찾기 알고리즘의 구현방법에 대한 나의 이해가 부족하기 때문에 triangulation, tesselation 등이 무슨 말을 하는 건지 알 수 없었지만, Layer 분할 방식이 타일형 맵에 적합하다고 하는 것 같기에 우선 이걸 쓰면 될 것 같다.
사용하는 분할방식에 따라 부르는 함수도 달라지는 것을 볼 수 있다.
윤곽선 집합(Countour set) 정보를 만들어내는 모습
다음으로 완성된 경로의 가장자리 정보를 만들어낸다.
그리고 완성된 윤곽선 정보로부터 네비게이션 메시를 만들어낸다.
일반 네비게이션 메시와 디테일 메시가 또 다른가보다. 일반메시로부터 디테일 메시를 만들어내고, 디테일 메시까지 제대로 생성되면 이제 쓰임이 다한 밀집 높이필드(CompatctHeightField)와 윤곽선 집합(CountourSet)을 할당해제한다.
"지금부터는 Detour 기능을 사용하는 구간입니다" 라는 표지판 역할을 하는 주석문
여기까지는 Recast 라이브러리를 사용해서 일반 메시로부터 네비게이션용 메시를 생성하는 코드였고, 이 데모 프로젝트에서는 이렇게 한번 가공된 메시 데이터를 추려 Detour 라이브러리용 네비게이션 메시를 만드는 데에 사용한다. Recast가 순수 지형메시로부터 네비게이션이 적용될 구간을 추리는 역할을 한다면, Detour는 런타임 중 길찾기 연산을 시도할 때 사용될 네비게이션 메시를 생성하는 것 같다.
메시의 분할된 영역들에는 여러가지 플래그를 저장할 수 있다. 앞에서 MarkArea 함수를 통해 지정한 각 구역(area)의 특징에 따라 지형 메시의 플래그를 설정한다. 이 플래그들은 나중에 네비게이션 주체들의 필터 플래그들과 대조되어 유닛이 특정 구역을 통행할 수 있는지의 여부를 판단하는데에 쓰이게 된다.
Detour 네비게이션 메시 생성에 쓰이는 파라미터 구조체의 초기화
params, navData, navMesh를 차례로 할당,초기화하고 navMesh와 navQuery에서 init 함수를 호출하면 이로서 빌드가 모두 끝난다.
장구한 네비게이션 메시 빌드 함수가 참 값을 반환하며 끝나는 부분, 빌드 타이머를 종료시키고 빌드에 걸린 시간을 로그에 기록하는 것을 볼 수 있다.
4. 요약
RecastDemo에서 사용된 네비게이션 메시 빌드 함수의 수행단계를 이해하기 쉽게 그림을 그려 정리해보자.
이 기나긴 빌드 프로세스의 최종 결과물은 dtNavMesh, dtNavMeshQuery이다. 얘들을 이용한 런타임 길찾기는 어떻게 진행되는건지 다음 포스트에서 알아보자.
이전 설계에서 말도 안되는 부분을 발견했다. 3d 애니메이션을 구현하기 위해 게임 엔진에서 애니메이션이 적용된 본들의 TM들을 본의 이름을 키값으로 하는 map에 넣어 그래픽스 엔진에 통째로 전달하면 그래픽스 엔진이 노드들의 상태를 반영해 메시를 그리는 방식으로 설계를 짰었다. 하지만 매 프레임 각각의 메시 인스턴스들에게 map을 만들어서 넘겨주고, 또 그래픽스 엔진에서는 이를 받아 문자열 해싱을 통해 본을 찾아서 적용한다? 이 설계 아래에서 그래픽스 엔진이 최적화를 할 수 있는 여지도 없을 것 같고, 해싱같은 비싼 연산을 매 업데이트마다, 매 메시마다, 매 본마다 수행한다는게 매우 탐탁지 않다.
그래서 애니메이션 인스턴스 하나에 대응되는 인터페이스를 만들고, 오프셋 시간을 매개변수로 전달해 메시에 적용하는 식으로 구조를 바꿨다.
모든 리소스에 범용 고유 식별자(uuid)를 넣어 리소스들을 관리할 생각이었지만, 일단 리플렉션, 시리얼라이제이션을 구현하기 전까지는 리소스에 대한 키 값은 파일경로로 대체해야 할 것 같다.
