[모작 일지] - BSP(Binary Space Partitioning) 알고리즘 - 랜덤 맵 생성

간단한 2D 로그라이크 게임 개발을 진행하면서 랜덤 맵 생성 알고리즘에 대해 알아보았다.

 

우선시 생각한 부분은 

1. 맵을 각각의 작은 방으로 분할하여 해당 방에 일정한 숫자의 아이템 또는 몬스터를 스폰.
2. 맵을 서버에서 만들어서 클라이언트에게 전송해줄것이기 때문에 생성시간이 짧을수록 좋음.

 

따라서 BSP 알고리즘을 이용하여 랜덤하게 맵을 생성해 보았다.

 

BSP 알고리즘(이진 공간 분할법)이란

이진 공간 분할법(BSP)

공간, 평면을 그림과 같이 두개의 다각형으로 분할하여 공간을 재귀적으로 분할하는 방법이다. 본래는 3D 그래픽스에서 효과적으로 렌더링(ex 공간을 나눠 렌더링하는 방식)을 하는데에 사용되었는데, 2D 게임에서 BSP 알고리즘을 이용하여 공간을 분할하여 여러개의 방으로 나누고, 이 방들을 이어주는 방법을 통해 랜덤하게 맵을 생성하는데에 이용될 수도 있다.

 

알고리즘은 크게 3개의 스텝으로 으로 이루어지는데 

1. 공간을 두개로 분할한다 
2. 분할된 공간을 이어준다
3. 1번과 2번 과정을 특정 조건을 만족할 때까지 반복한다.

공간(Container)을 두개로 공간으로 분할하여 공간을 분할한 BSP 트리를 만들어 준다. 최종적으로 만들어진 BSP 트리의 말단 노드에 해당하는 공간 내부에 하나의 방(Room)을 생성하고 하고 이렇게 분할된 공간을 한개의 길(Road)로 이어주도록 알고리즘을 설계하였다.

 

자료구조는 Room, Road, Container로

• Room - 방의 위치와 크기를 저장
• Road - 각 방을 이어주는 길의 시작점과 끝점을 저장
• Container - 분할된 공간을 나타냄. 자식 컨테이너를 트리 구조로 갖고 있음.

자료구조 - Room, Road

자료구조 - Container

 

Container에서는 분할된 자식 Container를 기록해둔다.

전체적인 BSP 코드는 다음과 같다. 위에서 설명한대로 root에 해당하는 container(원하는 사이즈의)를 만들고 해당 root에서 시작하여 공간을 분할(Divide)하고 이렇게 분할된 공간을 연결(Connect) 해준다.

BSP 알고리즘

 

우선 공간을 분할(Divide)하는 것을 살펴보면 (코드는 매우 간단하게 구현하였다)

공간의 가로, 세로 크기를 통해 더 큰 쪽을 기준으로 공간을 분할해주었다. 이때 약간의 다양성을 주기 위해 각 방의 크기를 원래 크기의 최소 40%~ 최대 60% 크기 정도를 갖게하도록 하기 위해 ratio를 랜덤하게 받도록 선언해주었다.

이렇게 나눈 공간을 각각 _lChild, _rChild에 넣어주고 해당 _lChild, _rChild에 대해 재귀적으로 Divide를 해주었다.

재귀적으로 공간을 분할하다가 지정해놓은 최소 방의 크기보다 작아지지 않도록 조건을 정의하여 해당 크기에 도달하면 이제 나누어진 공간(리프 노드에 해당)에 방(Room)을 만들어주었다.

void Divide(Container* parent)
{
    int xLen = parent->_w;
    int yLen = parent->_h;

    int x = parent->_x;
    int y = parent->_y;
    int w = parent->_w;
    int h = parent->_h;

    int ratio = Container::GetRandomNum(4, 6);

    if (w - 4 <= minSizeX || h - 4 <= minSizeY)
    {
        Room* room = MakeRoom(parent);
        return;
    }
        

    if (xLen > yLen)
    {
        int slicedW = w * ratio / 10;

        // lchild;
        Container* lChild = Container::CreateContainer(x, y, slicedW, h);

        // rChild;
        Container* rChild = Container::CreateContainer(x + slicedW, y, w - slicedW, h);

        Divide(lChild);
        Divide(rChild);

        parent->_lChild = lChild;
        parent->_rChild = rChild;


    }
    else if (xLen <= yLen)
    {
        int slicedH = h * ratio / 10;

        // lchild;
        Container* lChild = Container::CreateContainer(x, y, w, slicedH);

        // rChild;
        Container* rChild = Container::CreateContainer(x, y + slicedH, w, h - slicedH);

        Divide(lChild);
        Divide(rChild);

        parent->_lChild = lChild;
        parent->_rChild = rChild;
    }
}

 

이제 나누어진 공간에 만들어진 방들을 이어주어야 하는데

어떻게 이어주는냐에 따라 또 다양한 모습의 랜덤 맵들이 생성될 수 있다.

일단 보여주기 위해 구현한 코드는 각 Container의 중심좌표를 구해서 해당 좌표들을 이어주도록 구현하였다.

방은 해당 구역의 중심을 무조건 지나치는 크기로 만들기 때문에 모든 방들이 반드시 이어지게 된다.

 

Root Container에서 시작해서 자식 노드(공간)끼리 이어주면 된다.

주의해야할 점은 중심좌표의 x가 같다면 해당 방은 세로 길이를 기준으로 분할된 방이므로, 연결해주는 길 또한 y축과 나란하게 이어주어야 한다. 반대로 y가 같다면 반대로 진행해주면 된다.

이때 Road에는 길의 시작좌표와 끝좌표만 저장하기 때문에 길의 모양을 구성하는 방식은 상황에 따라 맞게 구현해주면 된다. 물론 여기서는 축과 평행한, 일자 모양으로 만들었다..

void Connect(Container* root)
{
    if (root->_lChild == nullptr || root->_rChild == nullptr) return;
    
    Point lCenter = root->_lChild->GetCenter();
    Point rCenter = root->_rChild->GetCenter();

    Road* road = new Road(lCenter.x, lCenter.y, rCenter.x, rCenter.y);
    root->_road = road;

    if (lCenter.x == rCenter.x)
    {
        
        for (int i = lCenter.y ; i < rCenter.y; i++)
        {
            map[i][lCenter.x] = 2;
        }
    }
    else if (lCenter.y == rCenter.y)
    {
        for (int i = lCenter.x; i < rCenter.x; i++)
        {
            map[lCenter.y][i] = 2;
        }
    }
    
    Connect(root->_lChild);
    Connect(root->_rChild);
}

Divde -> Connect 과정 (검정, 빨간, 파란선은 구분선, 초록선은 Road)

 

종합적인 코드는 아래 Github를 참고하면 된다.

https://github.com/ajdxjdrnfl/BSP_2D

GitHub - ajdxjdrnfl/BSP_2D: 2D random space partitioning using Simple BSP algorithm

 

이제 이렇게 만든 알고리즘을 이용하여 맵을 랜덤 생성 / 스프라이트를 작업해줄 수 있는 툴을 개발해보아야겠다..