240201 BSP 알고리즘을 이용한 랜덤맵 생성

기록

240201 BSP 알고리즘을 이용한 랜덤맵 생성

hayo_su 2024. 2. 2. 15:56

전에 벽으로 나누어진 랜덤맵을 만든 내용을 바탕으로 이를 확장하였다.

240104 BSP Algorithm을 이용한 Random Map Generator

BSP 알고리즘 아이디어 1. 전체공간을 가지고있는 RootNode를 가지고 시작한다. 2. 가로 세로 중 긴 축을 기준으로 랜덤 비율을 사용하여 자른다. 3. 왼쪽 영역을 LeftChildNode, 오른쪽 영역을 RightChildNode

hayo-su.tistory.com

1. Leaf Node 저장

2. Leaf Node 랜덤 룸 생성

3. 룸을 연결하는 통로 생성

4. 결과

1. Leaf Node 저장

말단 노드를 확인하였을 때 LeafNodeList에 저장하도록 하였다.

// 현재 Node를 n개로 나누고싶다는 의미
bool URectRoomMapGenerator::DivideNode(std::shared_ptr<Node> tree, int n, int _size, float _rate)
{
    if (n == 1) // 더이상 방을 나눌 필요가 없을 때
    {
        if (_size > GetRoomSize(tree->nodeRect)) // 최소 방 크기를 만족하지 않는다면
        {
            return false;
        }
        LeafNodeList.push_back(tree);
        return true;
    }

인덱스, x축 시작점, y축 시작점, x축 끝점, y축 끝점 순으로 leaf노드(말단노드)에 해당하는 노드드를 저장하도록 하였다.

2. Leaf Node 랜덤 룸 생성

    for (std::shared_ptr<Node> _leaf : LeafNodeList)
    {
        CreateRoom(_leaf);
    }

모든 말단 노드에 만들 수 있는 도형을 랜덤으로 create하도록 하였다.

삼각형

// 삼각형
if (CurRect.width >= 5 && CurRect.height >= 5)
{
	int point_len = GameEngineRandom::MainRandom.RandomInt(0, CurRect.width - 2);
	int b_x = CurRect.x;
	int b_y = CurRect.y + point_len;


	int a_x = CurRect.x + CurRect.height - 2;
	int a_y = CurRect.y;

	int c_x = CurRect.x + CurRect.height - 2;
	int c_y = CurRect.y + CurRect.width - 2;

	if (base_map[b_x][b_y] != 0 || base_map[a_x][a_y] != 0 || base_map[c_x][c_y] != 0)
	{
		return;
	}

	for (int i = CurRect.x; i < CurRect.x + CurRect.height; ++i)
	{
		for (int j = CurRect.y; j < CurRect.y + CurRect.width; ++j)
		{
			if ((i * (b_y - a_y) < ((b_x - a_x) * (j - b_y) + b_x * (b_y - a_y))) || (i * (b_y - c_y) > ((b_x - c_x) * (j - b_y) + b_x * (b_y - c_y))))
			{
				if (base_map[i][j] == 0)
				{
					base_map[i][j] = 1;
				}
			}
		}
	}
}

사각형

// 사각형
if (CurRect.width >= 5 && CurRect.height >= 5)
{

    int start_x = GameEngineRandom::MainRandom.RandomInt(CurRect.x, CurRect.x + CurRect.height / 4);
    int start_y = GameEngineRandom::MainRandom.RandomInt(CurRect.y, CurRect.y + CurRect.width / 4);
    int len_x = GameEngineRandom::MainRandom.RandomInt(CurRect.height / 2, CurRect.x + CurRect.height- start_x); 
    int len_y = GameEngineRandom::MainRandom.RandomInt(CurRect.width / 2, CurRect.y + CurRect.width - start_y);


    for (int i = CurRect.x; i < CurRect.x + CurRect.height; ++i)
    {
        for (int j = CurRect.y; j < CurRect.y + CurRect.width; ++j)
        {
            if (i < start_x || start_x >= start_x + len_x || j < start_y || j >= start_y + len_y)
            {
                if (base_map[i][j] == 0)
                {
                    base_map[i][j] = 1;
                }
            }
        }
    }
}

마름모

// 마름모
if (CurRect.width >= 3 && CurRect.height >= 3)
{
    int point_x = (CurRect.height) / 2 - 1;
    int point_y = (CurRect.width) / 2 - 1;

    int a_x = CurRect.x + point_x;
    int a_y = CurRect.y;

    int b_x = CurRect.x;
    int b_y = CurRect.y + point_y;


    int c_x = CurRect.x + point_x;
    int c_y = CurRect.y + point_y * 2;


    int d_x = CurRect.x + point_x * 2;
    int d_y = CurRect.y + point_y;

    for (int i = CurRect.x; i < CurRect.x + CurRect.height; ++i)
    {
        for (int j = CurRect.y; j < CurRect.y + CurRect.width; ++j)
        {
            if (
                (i * (b_y - a_y) < ((b_x - a_x) * (j - b_y) + b_x * (b_y - a_y))) || (i * (b_y - c_y) > ((b_x - c_x) * (j - b_y) + b_x * (b_y - c_y))) ||
                (i * (d_y - a_y) > ((d_x - a_x) * (j - d_y) + d_x * (d_y - a_y))) || (i * (d_y - c_y) < ((d_x - c_x) * (j - d_y) + d_x * (d_y - c_y)))
                )
            {
                if (base_map[i][j] == 0)
                {
                    base_map[i][j] = 1;
                }
            }
        }
    }
}

3. 룸을 연결하는 통로 생성

이 때 leaf 노드가 항상 인접한 노드가 아니기 때문에 divide하는 순서를 먼저 바꾸어 줬다.

before

return DivideNode(tree->leftNode, leftnodecnt, _size, nrate) && 
DivideNode(tree->rightNode, rightnodecnt, _size, nrate);

after

    if (true == is_height)
    {
        return DivideNode(tree->leftNode, leftnodecnt, _size, nrate) && 
        DivideNode(tree->rightNode, rightnodecnt, _size, nrate); //왼쪽, 오른쪽 자식 노드들도 나눠준다.
    }
    else
    {
        return DivideNode(tree->rightNode, rightnodecnt, _size, nrate) && 
        DivideNode(tree->leftNode, leftnodecnt, _size, nrate); //왼쪽, 오른쪽 자식 노드들도 나눠준다.
    }

두 노드를 연결한다.

bool URectRoomMapGenerator::MakeRoad(const RectInt f_rect, const RectInt s_rect)
{
    // x축(세로)가 공통인지 확인
    if ((f_rect.x <= s_rect.x && s_rect.x < f_rect.x + f_rect.height) || (f_rect.x >= s_rect.x && s_rect.x + s_rect.height > f_rect.x))
    {
		int midx = (f_rect.GetMidx() + s_rect.GetMidx() - 1) / 2;
        int miny, maxy;

 
        if (s_rect.GetMidy() > f_rect.GetMidy())
        {
            miny = f_rect.GetMidy()-1;
			maxy = s_rect.GetMidy() + 1;
        }
        else
        {
            maxy = f_rect.GetMidy()+1;
            miny = s_rect.GetMidy()-1;
        }
        for (int j = miny; j < maxy; ++j)
        {
            if (base_map[midx][j] == 1)
            {
                if (base_map[midx][j - 1] == 0 || base_map[midx][j + 1] == 0)
                {
                    base_map[midx][j] = 2;
                }
                else
                {
                    base_map[midx][j] = 3;
                }
            }
        }
        return true;
    }
    // y 축(가로)가 공통인지 확인
    else if ((f_rect.y <= s_rect.y && s_rect.y < f_rect.y + f_rect.width) || (f_rect.y > s_rect.y && s_rect.y + s_rect.width > f_rect.y))
    {
		int midy = (f_rect.GetMidy() + s_rect.GetMidy() - 1) / 2;
        int minx, maxx;


        if (s_rect.GetMidx() > f_rect.GetMidx())
        {
			minx = f_rect.GetMidx() - 1;
			maxx = s_rect.GetMidx() + 1;
        }
        else
        {
			maxx = f_rect.GetMidx() + 1;
			minx = s_rect.GetMidx() - 1;
        }
        for (int j = minx; j < maxx; ++j)
        {
            if (base_map[j][midy] == 1)
            {
				if (base_map[j - 1][midy] == 0 || base_map[j + 1][midy] == 0)
                {
                    base_map[j][midy] = 2;
                }
                else
                {
                    base_map[j][midy] = 3;
                }
            }
        }
        return true;
    }
    else
    {
        int a = 0;
        return false;
        // err
    }
}

4. 결과

통로 연결이 문제가 있어 노드를 재 탐색할지 고민중이다.

티스토리