BSP 알고리즘을 이용한 랜덤 맵 생성 ㅡ로그라이크

앞선 로그라이크 맵 생성 방식 글을 통해 현재 가장 보편적으로 사용되는 로그라이크 맵 생성 알고리즘 중 하나가 BSP 알고리즘이라는 것을 알았습니다. 그래서 이제, 이를 직접 구현해보며 공부해보려고 합니다.

 

먼저, BSP 알고리즘을 이용한 랜덤 맵 생성 알고리즘의 절차는 다음과 같습니다.

 

1. 공간을 두 개로 계속해서 나눈다. (나눈 공간을 트리로 구성)
2. 나눈 공간에 공간을 벗어나지 않는 크기의 방을 만든다.
3. 방끼리 서로 이어준다.

 

1. 공간을 두 개로 계속해서 나눈다.

BSP 알고리즘이 실질적으로 사용되는 단계로 이름에서도 알 수 있듯이 Binary Space Partitioning, 즉 공간을 두 개로 나누어 트리로 저장하는 알고리즘입니다. BSP 알고리즘 자체는 어떤 모양의 공간으로든 나눌 수 있지만 저는 Pixel Dungeon 게임과 같이 사각형으로 이루어진 던전을 만들고자 하기 때문에 사각형으로 공간을 나누겠습니다. 이 과정을 그림으로 나타내면 다음과 같습니다.

 

이렇게 트리로 저장하는 과정에서 각 노드에 공간의 왼쪽 상단 위치 정보와 공간의 가로, 세로 길이를 저장하는 방식으로 구현해보고자 합니다. 그러기 위해서는 일단 트리의 노드 클래스와 위치, 공간 크기를 저장할 구조체를 먼저 정의해야합니다.

struct Rect
{
    int x; int y;
    int width; int height;
};

class Node
{
    public:
        Node* leftNode;
        Node* rightNode;
        Rect rect;
    
    public:
        Node(int x, int y, int width, int height);
};

Node::Node(int x, int y, int width, int height)
{
    rect.x = x; rect.y = y;
    rect.width = width; rect.height = height;
}

위치 정보를 저장하는 Rect 구조체에는 공간의 왼쪽 상단 위치인 x, y 좌표를 저장하는 변수와 사각형으로 나눈 공간의 크기를 저장하기 위해 가로, 세로 길이를 저장하는 변수도 같이 선언합니다. 그리고, 노드에는 자신의 자식 노드를 저장할 수 있는 leftNode, rightNode를 선언하고 Rect라는 위치, 공간 정보를 저장할 수 있는 rect 변수를 선언합니다.

 

그럼 이제, 공간을 나눌 지도를 만들어야 하는데 여기서는 간단하게 2차원 배열로 표현하겠습니다.

#define mapWidth 60
#define mapHeight 60

int map[mapHeight][mapWidth];

 

맵도 만들었고 트리를 위한 노드와 위치, 공간 크기를 위한 구조체도 선언했으니 이제 맵을 두 개로 계속해서 나누는 함수를 한번 생각해보겠습니다.

 

공간을 두 개로 나눌려면 어떻게 해야할까요? 먼저 최초의 공간을 나타내는 root 노드가 있어야겠지요. 그럼, 최초의 공간(노드)인 root노드의 공간 위치 정보는 왼쪽 상단 좌표를 저장하기로 하였으니 (0, 0)이고 width, height이 각각 60임을 생각할 수 있습니다. 이를 일단 세로로 분할해 2개의 공간으로 나눈다고 하겠습니다. 그럼 왼쪽에 있는 공간(노드)와 오른쪽에 있는 공간(노드)으로 나뉘는데 각각 위치 정보는 (0,0), (n, 0)이고 width는 root.width - right.width right.width, height은 root.height입니다.

 

이번엔 가로로 분할한다고 가정해보겠습니다. 그럼 위쪽에 있는 공간(노드)와 아래쪽에 있는 공간(노드)으로 나뉘는데 위쪽에 있는 공간이 배열 상 더 작은 좌표에 해당하므로 왼쪽에 있는 공간으로 하겠습니다. 각각 위치 정보는 (0,0), (0, n)이고 width는 root.width, height은 root.height - right.height, right.height입니다.

 

나뉜 노드에 대해서도 이 두 가지 가정이 계속해서 반복될 것이라고 생각이 드시나요? 그럼 이는 재귀적으로 구현할 수 있을 것 같습니다. 하지만, 재귀의 과정에서 어떤 공간을 가로 또는 세로로 나누어야 하는지는 정하지 못했습니다. 저는 단순하게 길이가 긴 쪽에 대해 수직으로 분할하기로 했습니다. 즉, 가로가 더 길면 세로로 자르고 세로가 더 길면 가로로 자르는 것입니다. 단, 콘솔에 출력 시 같은 크기라도 가로보다 세로가 더 커보이므로 가로랑 세로가 같은 크기면 가로로 자르도록 했습니다.

 

그럼 재귀적으로 구현해야함도 알았고 나누는 기준도 생각했습니다. 마지막으로 나눌때 n과 right.height 또는 right.width을 정해주는 방법만 알면 되는데 얘는 그냥 특정 비율 사이의 값을 랜덤하게 가져오도록 하면 됩니다. 왜 특정 비율 사이의 값을 가져오냐면, 값이 너무 작거나 크면 한 공간은 무용지물이 되기 때문입니다.

 

제가 구현한 맵을 두 개로 계속해서 나누는 함수, Divide는 다음과 같습니다.

double minRatio = 0.4, maxRatio = 0.7;
int maxDepth = 4;

// low ~ high 사이의 값 반환
int random(int low, int high)
{
    return low + rand() % (high - low + 1);
}

void Divide(Node *node, int depth)
{
    if (depth == maxDepth) return;

    int maxLen = node->rect.width > node->rect.height ? node->rect.width : node->rect.height;
    int split = random(round(maxLen * minRatio), round(maxLen * maxRatio));

    if (node->rect.width >= node->rect.height)
    {
        node->leftNode = new Node(node->rect.x, node->rect.y, split, node->rect.height);
        node->rightNode = new Node(node->rect.x + split, node->rect.y, node->rect.width - split, node->rect.height);

		for (int i = node->leftNode->rect.y; i < node->leftNode->rect.y + node->leftNode->rect.height; i++)
            map[i][node->rightNode->rect.x] = 1;
    } else 
	{
        node->leftNode = new Node(node->rect.x, node->rect.y, node->rect.width, split);
        node->rightNode = new Node(node->rect.x, node->rect.y + split, node->rect.width, node->rect.height - split);

		for (int i = node->leftNode->rect.x; i < node->leftNode->rect.x + node->leftNode->rect.width; i++)
            map[node->rightNode->rect.y][i] = 1;
    }

    Divide(node->leftNode, depth + 1);
    Divide(node->rightNode, depth + 1);
}

// 맵을 출력하기 위한 함수
void PrintMap()
{
    for (int i = 0; i < mapHeight; i++) {
        for (int j = 0; j < mapWidth; j++)
            cout << map[i][j];
        cout << endl;
    }
}

제대로 나뉜 것을 확인할 수 있죠?

 

 

2. 나눈 공간을 벗어나지 않는 크기의 방을 만든다.

이제 공간도 나누었고 각 공간의 위치 정보와 크기 정보도 저장해놓았습니다. 이를 이용해 각 공간에 방을 만들 수 있을 것 같습니다. 이전 과정에서 비율을 통해 나누는 크기를 정하였듯이 방의 위치, 크기 정보를 비율에 사이의 정수 값으로 랜덤하게 정하도록 하겠습니다. 그리고 공간을 어떻게 나누었든 최종 leaf 노드들 내에 방을 만들어야 하므로 leaf 노드가 나올때까지 재귀 호출해야겠네요.

 

여기서 주의할 점은 위치 정보를 먼저 결정해버리면 크기 정보를 정하는 과정에서 공간을 벗어나거나 너무 작은 공간이 생길 수 있습니다. 그러므로 크기 정보를 먼저 결정하고 후에 위치 정보를 결정하는 방식이 더 편할 것 같네요.

 

저는 이렇게 구현하였습니다.

class Node
{
    public:
        Node* leftNode;
        Node* rightNode;
        Rect rect;
        Rect room; // 방 정보 저장을 위한 변수 추가
    
    public:
        Node(int x, int y, int width, int height);
};

Rect GenerateRoom(Node* node, int depth)
{
    Rect rect;

    if (depth == maxDepth)
    {
        rect.width = random(round(node->rect.width * minRatio), round(node->rect.width * maxRatio));
        rect.height = random(round(node->rect.height * minRatio), round(node->rect.height * maxRatio));

        rect.x = random(node->rect.x + 1, node->rect.x + (node->rect.width-rect.width));
        rect.y = random(node->rect.y + 1, node->rect.y + (node->rect.height-rect.height));
    } else
    {
        node->leftNode->room = GenerateRoom(node->leftNode, depth + 1);
        node->rightNode->room = GenerateRoom(node->rightNode, depth + 1);
    }

    return rect;
}

// 방을 출력하기 위한 함수
void PrintRoom(Node* node, int depth)
{
    if (depth == maxDepth)
    {
        for (int j = node->room.y; j < node->room.y + node->room.height; j++)
            for (int i = node->room.x; i < node->room.x + node->room.width; i++)
                map[j][i] = 3;
    } else {
        PrintRoom(node->leftNode, depth + 1);
        PrintRoom(node->rightNode, depth + 1);
    }
}

방을 의미하는 3이 공간을 벗어나지 않고 잘 생성되었습니다. 그리고 여러 번 돌려보면 아시겠지만 계속 랜덤하게 방이 생성됨을 보실 수 있습니다.

 

 

3. 방끼리 서로 이어준다.

사실 가장 애를 먹었던 구간입니다. 먼저, 저는 이런식으로 길을 만들고 싶었습니다.

 

 

보시면 가로와 세로 경로가 모양은 같지만 배열로 표현하려면 x, y 좌표가 서로 다른 방식으로 표현됨을 예상할 수 있습니다. 그래서 가로로 이어주는 함수와 세로로 이어주는 함수로 나누어 구현하였습니다. 그리고 길을 3단계로 나누어 왼쪽 방부터 꺾이는 구간까지를 1단계, 꺾이는 구간을 2단계, 꺾이는 구간부터 오른쪽 방까지를 3단계로 하였습니다.

 

먼저, 가로로 분할 된 공간 속 방 두 개를 이어준다고 생각하고 단계별로 한번 구현해보겠습니다. 처음 1단계에서 왼쪽 방은 항상 방의 아래쪽에서 길이 이어집니다. 그럼, y 좌표는 고정되겠네요. 하지만 x 좌표는 상관이 없죠? 그래서 저는 중앙으로 고정시켜주었습니다. 왼쪽 방은 중간 아래 좌표가 항상 (room.x + (room.width/2), room.y + room.height)으로 정해져있습니다. 이 좌표에서 꺾이는 구간까지 y좌표만 1씩 증가시켜주면 될 거 같네요. 근데 이제 꺾이는 구간 좌표를 어떻게 정해줘야 할지 모르겠더군요.. 그런데 갑자기 아까 1단계에서 쓰인 split 변수가 생각이 났습니다. 왼쪽 방 중간 좌표에서 rect.y + split만큼 길을 그렸다가 (1단계) rect.y + split에서 꺾이는 구간을 만들면 쉽게 만들 수 있겠다는 생각이 들더군요.

 

2단계도 그럼 쉽게 구현이 되겠네요. y 좌표는 이미 알았고, x 좌표만 왼쪽 x 좌표에서 오른쪽 x 좌표로 이동시켜주면 되는데 왼쪽 x 좌표가 더 작을 수도 있지만, 클 수도 있잖아요? 그래서 왼쪽, 오른쪽 x 좌표를 비교해서 작은 쪽의 x 좌표에서 큰 쪽의 x 좌표로 이동시키면서 길을 그리도록 했습니다.

 

3단계는 1단계와 비슷한 방식으로 구현이 됩니다. 오른쪽 방은 항상 중앙 위 좌표에서 길을 그리며 중앙 좌표는 (room.x + (room.width/2), room.y)입니다. x 좌표는 고정한채 rect.y + split부터 room.y까지 그리면 되겠군요. 세로로 분할 된 경우도 같은 방식으로 생각하면 쉽게 해결가능합니다.

 

그럼 이제 이 두 함수를 이용해서 길을 만드는 함수를 작성해야 하는데, 저는 leaf 노드부터 트리를 타고 가면서 왼쪽, 오른쪽 노드에 길을 이어주는 방식을 생각했습니다. 하지만, 저희는 방 정보를 leaf 노드에만 저장하고 부모 노드들에는 저장하지 않았습니다. 이러면 문제는 왼쪽, 오른쪽 leaf 노드만 길이 이어져서 결국 모든 방이 연결되는 경우가 생기지 않습니다.

 

그래서 애초에 방을 생성하는 함수 GenerateRoom에서 부모 노드에 각 leaf 노드에 생성된 방 정보 중 하나를 저장하도록 해야합니다. 그래서 저는 else 문에 왼쪽, 오른쪽 방 정보 중 랜덤하게 선택하여 이를 부모에게 넘겨주는 식으로 코드를 살짝 수정했습니다.

 

그럼 이제 leaf 노드까지 간 후 트리를 타고 올라가면서 서로 길을 이어주기만 하면 완성입니다. 단, 부모 노드의 길을 이어주는 과정에서 방을 통과하는 경우가 생길 수 있어서 방 정보를 이용해 길을 이어 준 뒤 먼저 출력하고 방을 출력하는 식으로 구현했습니다.

Rect GenerateRoom(Node* node, int depth)
{
    if (depth == maxDepth)
    {
        ... // 이전과 같아서 생략하겠습니다.
    } else
    {
        ...
        if (random(0, 2)) // 랜덤하게 선택하여 부모에게 왼쪽 혹은 오른쪽 노드의 방 정보를 넘겨준다.
            rect = node->leftNode->room;
        else
            rect = node->rightNode->room;
    }
	...
}


void RoomSplitHorizon(Node* node) // 세로로 분할된 공간의 길 이어줄 때 사용
{
    int lCenterY = node->leftNode->room.y + node->leftNode->room.height;
    int lCenterX = node->leftNode->room.x + (node->leftNode->room.width/2);

    int rCenterY = node->rightNode->room.y;
    int rCenterX = node->rightNode->room.x + (node->rightNode->room.width/2);

    for (int y = lCenterY; y <= node->leftNode->rect.y + node->leftNode->split; y++)
        map[y][lCenterX] = 7;

    int from = lCenterX <= rCenterX ? lCenterX : rCenterX;
    int to = lCenterX <= rCenterX ? rCenterX : lCenterX;

    for (int x = from; x <= to; x++)
        map[node->leftNode->rect.y + node->leftNode->split][x] = 7;

    for (int y = node->leftNode->rect.y + node->leftNode->split; y < rCenterY; y++)
        map[y][rCenterX] = 7;
}

void RoomSplitVertical(Node* node) // 가로로 분할된 공간의 길 이어줄 때 사용
{
    int lCenterY = node->leftNode->room.y + (node->leftNode->room.height/2);
    int lCenterX = node->leftNode->room.x + node->leftNode->room.width;

    int rCenterY = node->rightNode->room.y + (node->rightNode->room.height/2);
    int rCenterX = node->rightNode->room.x;

    for (int x = lCenterX; x <= node->leftNode->rect.x + node->leftNode->split; x++)
        map[lCenterY][x] = 7;

    int from = lCenterY <= rCenterY ? lCenterY : rCenterY;
    int to = lCenterY <= rCenterY ? rCenterY : lCenterY;

    for (int y = from; y <= to; y++)
        map[y][node->leftNode->rect.x + node->leftNode->split] = 7;

    for (int x = node->leftNode->rect.x + node->leftNode->split; x < rCenterX; x++)
        map[rCenterY][x] = 7;
}

void GeneratePath(Node* node, int depth) // 길 생성
{
    if (depth == maxDepth) return;

    GeneratePath(node->leftNode, depth + 1);
    GeneratePath(node->rightNode, depth + 1);

    if (node->leftNode->rect.x == node->rightNode->rect.x)
        RoomSplitHorizon(node);
    else
        RoomSplitVertical(node);
}

이제 각 단계를 적절히 섞어주면 최종 코드는 다음과 같습니다.

/*
    랜덤한 맵을 만들기 위한 절차적 콘텐츠 생성 (PCG) 방식의 BSP 알고리즘 (C++)
    0 -> 허공 void
    3 -> 던전 dungeon
    7 -> 길 path
*/

#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <time.h>

using namespace std;

#define mapWidth 60
#define mapHeight 60

int map[mapHeight][mapWidth];
int maxDepth = 4;
double minRatio = 0.4, maxRatio = 0.7; // 방의 크기와 같은 랜덤 요소에 사용되는 최소, 최대 비율

// 배열 내 위치 정보를 저장하기 위한 구조체
// 왼쪽 상단 위치에 해당함
struct Rect
{
    int x; int y;
    int width; int height;
};

class Node
{
    public:
        Node* leftNode;
        Node* rightNode;
        Rect rect;
        Rect room;
        int split;
    
    public:
        Node(int x, int y, int width, int height, int split);
};

Node::Node(int x, int y, int width, int height, int split)
{
    rect.x = x; rect.y = y;
    rect.width = width; rect.height = height;
    this->split = split;
}

// void initMap()  // 맵의 가장자리를 1로 바꾼다.
// {
//     for (int i = 0; i < mapHeight; i++) {
//         for (int j = 0; j < mapWidth; j++) {
//             if (i == 0 || i == mapHeight-1)
//                 map[i][j] = 1;
//             else {
//                 map[i][0] = 1;
//                 map[i][mapWidth-1] = 1;
//             }
//         }
//     }
// }

void PrintMap()
{
    for (int i = 0; i < mapHeight; i++) {
        for (int j = 0; j < mapWidth; j++)
            cout << map[i][j];
        cout << endl;
    }
}

int random(int low, int high) // low ~ high 범위의 랜덤 정수 하나를 뽑는다.
{
    return low + rand() % (high - low + 1);
}

void Divide(Node *node, int depth) // 공간을 나누면서 트리 생성함
{
    if (depth == maxDepth) return;

    // width와 height 중 긴 쪽을 선택해서 width면 세로로 분할, height이면 가로로 분할
    int maxLen = node->rect.width > node->rect.height ? node->rect.width : node->rect.height;
    // 너무 작거나 큰 방이 생성되는 것을 막기 위해 비율을 정해서 랜덤 추출
    int split = random(round(maxLen * minRatio), round(maxLen * maxRatio));

    if (node->rect.width >= node->rect.height) // 현재 노드의 가로가 더 크다면, 세로로 나눈다.
    {
        // width, height이 같은 크기라도 출력 시에는 height이 더 크게 출력되므로, 같은 크기라도 세로로 나누는 것이 낫다. 안그러면 방이 더 작아보임
        node->leftNode = new Node(node->rect.x, node->rect.y, split, node->rect.height, split);
        node->rightNode = new Node(node->rect.x + split, node->rect.y, node->rect.width - split, node->rect.height, split);

        // for (int i = node->leftNode->rect.y; i < node->leftNode->rect.y + node->leftNode->rect.height; i++)
        //     map[i][node->rightNode->rect.x] = 1;
    } else {                                   // 현재 노드의 세로가 더 크다면, 가로로 나눈다.
        node->leftNode = new Node(node->rect.x, node->rect.y, node->rect.width, split, split);
        node->rightNode = new Node(node->rect.x, node->rect.y + split, node->rect.width, node->rect.height - split, split);

        // for (int i = node->leftNode->rect.x; i < node->leftNode->rect.x + node->leftNode->rect.width; i++)
        //     map[node->rightNode->rect.y][i] = 1;
    }

    Divide(node->leftNode, depth + 1);
    Divide(node->rightNode, depth + 1);
}

void PrintRoom(Node* node, int depth)
{
    if (depth == maxDepth)
    {
        for (int j = node->room.y; j < node->room.y + node->room.height; j++)
            for (int i = node->room.x; i < node->room.x + node->room.width; i++)
                map[j][i] = 3;
    } else {
        PrintRoom(node->leftNode, depth + 1);
        PrintRoom(node->rightNode, depth + 1);
    }
}

Rect GenerateRoom(Node* node, int depth)
{
    Rect rect;

    if (depth == maxDepth)
    {
        // 나뉜 공간의 크기를 벗어나지 않는 선에서 width, height, x, y를 랜덤하게 정해준다.
        rect.width = random(round(node->rect.width * minRatio), round(node->rect.width * maxRatio));
        rect.height = random(round(node->rect.height * minRatio), round(node->rect.height * maxRatio));

        rect.x = random(node->rect.x + 1, node->rect.x + (node->rect.width-rect.width));
        rect.y = random(node->rect.y + 1, node->rect.y + (node->rect.height-rect.height));
    } else
    {
        node->leftNode->room = GenerateRoom(node->leftNode, depth + 1);
        node->rightNode->room = GenerateRoom(node->rightNode, depth + 1);

        if (random(0, 2)) // 랜덤하게 선택하여 부모에게 왼쪽 혹은 오른쪽 노드의 방 정보를 넘겨준다.
            rect = node->leftNode->room;
        else
            rect = node->rightNode->room;
    }

    return rect;
}

void RoomSplitHorizon(Node* node) // 세로로 분할된 공간의 길 이어줄 때 사용
{
    int lCenterY = node->leftNode->room.y + node->leftNode->room.height;
    int lCenterX = node->leftNode->room.x + (node->leftNode->room.width/2);

    int rCenterY = node->rightNode->room.y;
    int rCenterX = node->rightNode->room.x + (node->rightNode->room.width/2);

    for (int y = lCenterY; y <= node->leftNode->rect.y + node->leftNode->split; y++)
        map[y][lCenterX] = 7;

    int from = lCenterX <= rCenterX ? lCenterX : rCenterX;
    int to = lCenterX <= rCenterX ? rCenterX : lCenterX;

    for (int x = from; x <= to; x++)
        map[node->leftNode->rect.y + node->leftNode->split][x] = 7;

    for (int y = node->leftNode->rect.y + node->leftNode->split; y < rCenterY; y++)
        map[y][rCenterX] = 7;
}

void RoomSplitVertical(Node* node) // 가로로 분할된 공간의 길 이어줄 때 사용
{
    int lCenterY = node->leftNode->room.y + (node->leftNode->room.height/2);
    int lCenterX = node->leftNode->room.x + node->leftNode->room.width;

    int rCenterY = node->rightNode->room.y + (node->rightNode->room.height/2);
    int rCenterX = node->rightNode->room.x;

    for (int x = lCenterX; x <= node->leftNode->rect.x + node->leftNode->split; x++)
        map[lCenterY][x] = 7;

    int from = lCenterY <= rCenterY ? lCenterY : rCenterY;
    int to = lCenterY <= rCenterY ? rCenterY : lCenterY;

    for (int y = from; y <= to; y++)
        map[y][node->leftNode->rect.x + node->leftNode->split] = 7;

    for (int x = node->leftNode->rect.x + node->leftNode->split; x < rCenterX; x++)
        map[rCenterY][x] = 7;
}

void GeneratePath(Node* node, int depth) // 길 생성
{
    if (depth == maxDepth) return;

    GeneratePath(node->leftNode, depth + 1);
    GeneratePath(node->rightNode, depth + 1);

    if (node->leftNode->rect.x == node->rightNode->rect.x)
        RoomSplitHorizon(node);
    else
        RoomSplitVertical(node);
}

int main(void)
{
    srand(time(NULL)); // 난수 생성
    Node* root = new Node(0, 0, mapWidth, mapHeight, 0); // 트리의 root 노드 생성
    memset(map, 0, sizeof(map));

    Divide(root, 0);
    GenerateRoom(root, 0);
    GeneratePath(root, 0);

    // 공간 정보로 길을 그려주고, 방을 그려주어 방을 통과하는 길이 보이지 않도록 함
    PrintRoom(root, 0);
    PrintMap();

    return 0;
}