기록
240104 BSP Algorithm을 이용한 Random Map Generator
hayo_su
2024. 1. 4. 14:57
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); //왼쪽, 오른쪽 자식 노드들도 나눠준다.
}
결과
잘 생성된다!