트리구조

게임브리오에서는 트리구조를 다룸에 있어서 가변형 배열(Array)를 사용하고 있습니다.

 

링크드 리스트를 이용할 경우 싱글 링크드 리스트를 이용한다면, 가변형 배열과 비슷한 자료 크기를 가지고 있습니다.  그러나 가장 큰 약점은 하나의 노드를 여러개의 노드가 자식으로 가질 수 없다는 점입니다.

 

그렇다고 해서 게임브리오가 이 조건을 만족하는가 하면 그것은 아닙니다.  게임브리오는 기본적으로 하나의 노드를 여러개의 노드가 자식으로 가질 수 없습니다.

 

트리를 구성함에 있어서는 다음과 같은 경우를 따져보아야 합니다.

 

하나의 노드는 여러개의 부모를 가질 수 있는가?

 

이 것은 트리를 설계할 때 가장 중요한 부분입니다.

 

그래픽 엔진을 개발할 때에는 이것을 허용하는 쪽으로 하는 것이 원칙이라고 생각됩니다.  그러면 함수면에서도 다음과 같이 제공되어야 하겠죠.

 

NiAVObject 노드였다면,

GetParent(int nIndex) 형태의 메소드 함수를 제공하는 것이 맞습니다.

 

그러나 게임브리오는 이것을 제공치 않습니다.  (현재까지는요.)

 

사실 게임브리오를 이용하면서 아쉬운 점들이 여러곳 존재했었는데요.  충돌 검사, 노드 업데이트, 추려내기, 노드 구조... 등등..

이것도 그중에 하나입니다. 

 

제가 게임을 개발할 때에는 일반적으로 리소스 관리자가 하나의 원본을 가지고 있고 그것을 복사해서 사용합니다.  그런데 원본에 많은 노드가 존재하고, 복사해서 사용하는 쪽이 그리 많지 않은 경우 엄청난 메모리 리소스를 낭비하게 됩니다.  Clone 이란 함수를 이용하면 실제 노드들은 복사됩니다.  이 노드들이 차지하는 메모리가 적지 않게 소모되죠.

 

여하튼.. 게임브리오에서 그동안 잘못된 부분들이 많이 보입니다만.. 이 부분은 각설하고요.. (사실 와우(WoW)를 보면서 감탄을 금치 못 합니다.  게임브리오를 가지고 이정도로 게임엔진을 다루어서 성능이나 효과를 연출했다는 것은 경이롭다고 봅니다.)

 

게임브리오에서 트리구조를 알기 위해서는 NiTArray 라고 하는 템플릿 클래스를 알아둘 필요가 있습니다.

 

이 템플릿 클래스는 가변 크기를 지원하는 배열 클래스입니다.

 

NiNode에서 자식 노드들을 관리할 때 NiTArray를 사용합니다.  그렇게 하다 보니 모든 자식들을 검토할 때 코드는 반드시 다음과 같이 짜야 합니다.

 

for( int i = 0 ; i < pNode->GetArrayCount() ; i++ )
{
   NiAVObject *pkTmp = pkNode->GetAt(i);
   if( pkTmp == NULL )
       continue;
   .....
}

 

for 루프안에 if( pkTmp == NULL ) 이 있는 점과 GetObjectCount() 가 아니라 GetArrayCount() 를 가지고 사용하는 점에 대해서는 바로 NiTArray 템플릿 클래스때문에 발생합니다.

 

NiTArray 템플릿 클래스는 가변 개수 배열을 이용하기 위해서 유지하는 변수들이 총 3가기자가 있습니다.  (여기서 기술되는 변수명은 실제 템플릿 클래스 변수명과는 다릅니다.)

nArraySize 는 배열의 크기입니다.  이것은 현재 배열이 모두 찼을 경우를 검사합니다.

nArrayCount는 현재 들어가 있는 마지막 데이터의 위치 더하기 1입니다.  더 정확한 의미로는 새로운 데이터가 들어올 경우 이 위치에 들어갑니다.

nObjectCount는 현재 들어가 있는 데이터의 갯수입니다.

 

가변 배열을 이용한 경우 데이터의 삽입과 삭제가 빈번하게 발생하는 경우 가변 배열의 크기가 계속 커집니다.  데이터 적재율에 비해서 배열의 크기가 커지기 때문에, 실제 데이터를 검색하는 비용이 많이 듭니다.  그래서 NiNode의 AttachChild()에서는 다음과 같은 옵션을 제공합니다.

 

NiNode::AttachChild(NiAVObject *pkObject, bool bFirst = false);

보통 두번째 파라미터는 기본값이 false인 관계로 잘 모르고 지나칠 수 있습니다.  그러나 이 옵션이 상당히 중요한 역할을 합니다.

 

Zone-IN-Zone-Out 방식이 아닌 MMORPG를 작성할 때, 플레이어가 이동함에 따라서 월드 오브젝트들은 무수하게 생성되고 무수하게 삭제될겁니다.  그러면, 월드오브젝트가 생성될 때, AttachChild의 두번째 파라미터에 true라고 기록하지 않았다면, 월드 오브젝트들이 생성된 갯수만큼 배열의 크기가 커지게 되어, 검색비용이 엄청나게 들게 됩니다.  예를 들어서 1000개의 오브젝트가 생성되고 900개의 오브젝트가 삭제되었다면, 한번의 검색비용은 100이 아닌 1000이 된다는 사실입니다.

 

적재되는 갯수가 100이고, 매분 100개의 오브젝트가 생성되고 100개의 오브젝트가 삭제된다면..

1시간이 지날경우 검색비용은 6000, 2시간이 지날 경우 120000.. 식으로 증가하게 됩니다.  결국 메모리는 메모리대로 차지하게 되고 검색비용이 늘게 됨에 따라 렌더링 속도는 줄어들게 되죠.

 

그래서 이런 특성을 알고서 프로그램 하는 것이 맞겠죠.

 

전에 게임브리오 사이트에서 어떤분은 아예 게임브리오 소스를 고쳐서 기본으로 AttachChild의 두번째 파라미터가 true가 되게 했다는 분도 있었습니다.  물론 이것도 한 방법이긴 하겠죠.  추가하는 횟수에 비해서 검색하는 횟수가 상대적으로 훨씬 많으니까요.  즉 분당 100개의 월드 오브젝트가 생성된다고 위에서 가정했어도.. 초당 30 프레임이라면.. 1분이면.. 1800번 검색을 할거니까요.  추가 비용이 좀 더 비싸도 검색비용이 싸지니 바람직하겠죠.