240104 BSP Algorithm을 이용한 Random Map Generator

BSP 알고리즘 아이디어

1. 전체공간을 가지고있는 RootNode를 가지고 시작한다.

2. 가로 세로 중 긴 축을 기준으로 랜덤 비율을 사용하여 자른다.

3. 왼쪽 영역을 LeftChildNode, 오른쪽 영역을 RightChildNode라고 정의한다.

4. LeftChildNode의 가로, 세로 중 긴 축을 기준으로 랜덤비율을 사용하여 자른다

5. 위쪽 영역을 LeftChildNode, 아래쪽 영역을 Right ChildNode라고 정의한다.

 

 

 

---

조건

1. 가로 세로의 크기는 정해진다.

2. 공간이 아닌 부분은 모두 1로 막혀있어야 한다(전체 테두리와 -1로 제공된 부분의 테두리)

3. 모든 공간은 문으로 연결되어있다.

4. 공간(Room)의 개수가 주어진다

5. 공간(Room)의 최소 크기가 주어진다

6. 문의 크기가 주어진다. 

---

노드 정보 만들기

class RectInt // 공간의 정보
{
public:
	RectInt(int _x, int _y, int _h, int _w)
		:x(_x), y(_y), height(_h), width(_w)
	{
	}
	RectInt()
		:x(0), y(0), width(0), height(0)
	{
	}
	int x;		// 시작점x
	int y;		// 시작점 y
	int height; // x의 길이
	int width;  // y의 길이
};

class Node
{
public:
	Node* parNode;			// 부모노드
	Node* leftNode;			// 왼쪽 자식 노드
	Node* rightNode;		// 오른쪽 자식 노드
	RectInt nodeRect;		// 공간 정보

	//생성자
	Node(RectInt rect)
	{
		nodeRect = rect;
		parNode = nullptr;
		leftNode = nullptr;
		rightNode = nullptr;
	}
};

 

 

맵 생성 클래스 만들기

class GenerateRoom
{
	static GenerateRoom* Room;
public:
	// constrcuter destructer
	GenerateRoom();
	~GenerateRoom();

	// delete Function
	GenerateRoom(const GenerateRoom& _Other) = delete;
	GenerateRoom(GenerateRoom&& _Other) noexcept = delete;
	GenerateRoom& operator=(const GenerateRoom& _Other) = delete;
	GenerateRoom& operator=(GenerateRoom&& _Other) noexcept = delete;


	static void SetRate(float _Rate)
	{
		m_rate = _Rate;
	}

	static void CreateMap(std::vector<std::vector<int>>& _Map, int roomcnt, int _size);

	static void Print(const std::vector<std::vector<int>>& _Map);


protected:

private:
	// 땅이 없는 부분(-1)의 테두리에 벽을 세우는 함수
	static void SetWallBFS(int x, int y, std::vector<std::vector<int>>& Map);

	// x,y가 현재 map size 인덱스 내에 있는지 확인하는 작업
	static bool In_range(int x, int y);

	// 현재 Node를 n개로 나누고싶다는 의미
	static bool Divide(Node* tree,int n, int _size, float _rate);

	//자식 노드를 만들고 구분선을 그리는 함수 _cur 사각형에 대한 splite구분선이다
	static void DrawLine(const RectInt& _cur, int splite, bool is_height, int n); 

	// 해당 인덱스까지 모든 넓이의 합을 dp로 구함
	static void CalMapSizeIndex(const std::vector<std::vector<int>>& Map, std::vector<std::vector<int>>& MapIndex);
	// RectInt에 해당하는 부분의 넓이
	static int GetRoomSize(const RectInt Rectinfo);

	// 현재 Rect를 나누어 Left와 Right노드의 크기를 가져올 수 있도록 함
	static void GetChildRect(const RectInt& _cur, int _split, bool is_height, RectInt& Left, RectInt& Right);


	// 현재 Map사이즈로 사전작업을 하기위한 initialize
	static void Init();
	
	// 테스트용 맵에 cpy하는 과정
	static void CpyMap(const std::vector<std::vector<int>>& _Map);

	// generate완료 후 노드를 삭제하기 위함
	static void ReleaseNode(Node* _cNode);



	static std::vector<std::vector<bool>> isvisited;		// SetWallBFS()에서 중복체크를 피하기 위함
	static std::vector<std::vector<int>>  MapSizeIndex;		// RectInt에 해당하는 부분의 넓이를 빠르게 구하기 위함
	static std::vector<std::vector<int>>  TryMap;			// 랜덤맵 생성 가능여부를 테스트하기 위함

	static int lx;		// 맵의 세로길이
	static int ly;		// 맵의 가로길이

	static float m_rate;		// 노드를 자르는 랜덤비율의 범위 1 - m_rate ~ 1 + m_rate
	static int door_size;		// 두 자식노드 사이를 연결하는 문의 길이
	static float spare;			// 노드를 자를 때 최소 여분 영역 제공 비율

	static Node* RootNode;		// 루트 노드
};

 

노드를 나누는 함수

bool GenerateRoom::Divide(Node* tree, int n, int _size, float _rate)
{
    if (n == 1) // 더이상 방을 나눌 필요가 없을 때
    {
        if (_size > GetRoomSize(tree->nodeRect)) // 최소 방 크기를 만족하지 않는다면
        {
            return false;
        }
        return true; 
    }


    // 방을 더 나눠야 할 때

    // 현재 노드의 방 정보
    const RectInt curRect = tree->nodeRect;

    // 가로로 나눌지 세로로 나눌지
    int maxLength = curRect.height > curRect.width ? curRect.height : curRect.width;;
    bool is_height = curRect.height > curRect.width ? true : false;

    // 5:5 비율로 나눈다고 가정
    int split = maxLength / 2;

    // 왼쪽노드의 방 개수
    int leftnodecnt = n / 2;
    // 오른쪽 노드의 방 개수
    int rightnodecnt = n - leftnodecnt;

    // 최대 방 크기 * 여분 비율
    int max_room_size = static_cast<int>((_size + 1) * 2 * _rate);


    // 5:5로 나누었을 때 Left와 Right임시값
    RectInt LeftRect, RightRect;
    GetChildRect(curRect, split, is_height, LeftRect, RightRect);

    int leftSize = GetRoomSize(LeftRect);
    int rightSize = GetRoomSize(RightRect);

    // 한쪽이 모두 -1인경우 방을 만들 수 없기 때문에 반대쪽 노드에 n개만큼 생성한다.
    if (leftSize == 0)
    {
        tree->rightNode = new Node(RightRect);
        tree->rightNode->parNode = tree;
        return Divide(tree->rightNode, n, _size, _rate);//왼쪽, 오른쪽 자식 노드들도 나눠준다.
    }
    else if (rightSize == 0)
    {
        tree->leftNode = new Node(LeftRect);
        tree->leftNode->parNode = tree;
        return Divide(tree->leftNode, n, _size, _rate);//왼쪽, 오른쪽 자식 노드들도 나눠준다.
    }


    // 홀수개의 방을 만들어야하는 경우 1 : 2 크기 비율로 split를 계산하기 위함
    if (n % 2 == 1)
    {
        int tmp = (maxLength * leftSize) / (leftSize + 2* rightSize);
		split = static_cast<int>(GameEngineRandom::MainRandom.RandomFloat(1.0f - m_rate, 1.0f + m_rate) * (tmp));
    }
    else
    {
        int tmp = (maxLength * leftSize) / (leftSize + rightSize);
		split = static_cast<int>(GameEngineRandom::MainRandom.RandomFloat(1.0f - m_rate, 1.0f + m_rate) * (tmp));
    }

    // 나올 수 있는 최대 길이와 최소 길이중에서 랜덤으로 한 값을 선택


	{
        // 방의 여분 비율을 맞추기 위해 split을 조정하는 과정
		int trycnt = 0;
		while (true)
		{
			trycnt++;
			if (trycnt > static_cast<int>(maxLength * (1.0f + m_rate)))
			{
				break;
			}
            GetChildRect(curRect, split, is_height, LeftRect, RightRect);
            leftSize = GetRoomSize(LeftRect);
            rightSize = GetRoomSize(RightRect);
			if (max_room_size * leftnodecnt > leftSize && max_room_size * rightnodecnt > rightSize)
			{
				return false;
			}
			else if (max_room_size * leftnodecnt > leftSize)
			{
				split++;
			}
			else if (max_room_size * rightnodecnt > rightSize)
			{
				split--;
			}
			else
			{
				break;
			}
		}
		// 방의 최소 크기를 맞추기 위함이다.

		//왼쪽 노드에 대한 정보다 
		tree->leftNode = new Node(LeftRect);

		//우측 노드에 대한 정보다 
		tree->rightNode = new Node(RightRect);

		//그 후 위 두개의 노드를 나눠준 선을 그리는 함수이다.        
		DrawLine(curRect, split, is_height, n);
	}

    tree->leftNode->parNode = tree; //자식노드들의 부모노드를 나누기전 노드로 설정
    tree->rightNode->parNode = tree;

    // 여분비율을 낮춘다
    float nrate = _rate * spare > 1.0 ? _rate * spare : 1.0f;

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

 

---

결과

 

잘 생성된다!