bsp 트리구조를 이용한 랜덤맵 생성

 이번에 directx 9을 이용하여 멀티플레이 하는 게임을 만들어 보자는 생각이 들어서 평소에 만들어보고 싶었던 랜덤맵 생성에 대해서 알고리즘을 짜보게 되었다. 맵을 서버에서 랜덤으로 생성하여 이차원 배열만 클라이언트에 넘겨주면 데이터 절약과 동시에 연산도 빠를거 같아서 이차원 배열을 이용하여 만들었다. 애초에 타일맵이라 이것말고는 생각이 나지 않는다.
 bsp 이진공간 분할법을 이용한 랜덤맵 생성이다.
알고리즘에 대하여 간단하게 설명하자면

1. 간단한 이진트리 구조를 만든다.
class TreeNode
{
     private:
     TreeNode *leftTree;
     TreeNode *rightTree;
     TreeNode *parentTree;
     public:
     TreeNode *GetLeftTree() { return leftTree; }
     TreeNode *GetRightTree() { return rightTree; }
     TreeNode *ParentTree() { return parentTree; }
}
대충 기본 구조를 이렇게 짰다. 객체들을 포인터로 해놓은 이유는 언제든지 메모리 추가가 가능하고, 자식구조에 대해서 접근이 가능하기 위해서이다. 그리고 트리안에 x, y, width, height 값을 저장하게 만든다.

일단 트리 하나를 만들어 좌표값을 넣어주면 이렇게 큰 네모가 머릿속에 그려질 것이다.

2. 둘로 쪼갠다.

왼쪽이 LeftTree, 오른쪽이 RightTree이다. 이전 부모의 좌표값을 토대로 랜덤하게 자른다.
랜덤값이 너무 크면 안되니까 30%에서 70%사이에 랜덤값을 주어 잘랐다.

3. 반복한다.

2번을 일정값 이하로 떨어지면 함수를 return 하게 하여 공간이 너무 작게 나오지 않도록 해준다.

4. 트리 안에 방을 만든다.

트리 안에 넣어둔 좌표값을 이용해 범위 안에 방을 만든다. 트리 구조로 잘라서 둘이 겹칠 일은 없다.

5. 마지막 자손 노드의 방부터 연결을 시켜준다.

나는 가로로 잘랐으면 가로로 연결하고 세로로 잘랐으면 세로로 연결하는 식으로 알고리즘을 짰다. 살짝 코드보기가 더럽고 안좋은 알고리즘이라 좀 더 좋은 알고리즘이 필요한거 같다.

6. 5번을 반복하며 부모 노드까지 연결시켜 준다.

처음이다보니 알고리즘 짜는데 좀 오래걸렸던거 같다... 이제 클라에서 이미지 넣어봐야 겠다. github 주소-> https://github.com/LeeYonggi/RandomMap_bspTree