BSP란
Binary SPac Partitioning 즉 전체맵을 양분하는 메서드를 큐를 활용하여 재귀를 통해 MaxSize 이하 MinSize이상의 직사각형으로 나누는작업이다
public class Leaf
{
public RectInt rect; // 현재 영역
public Leaf left, right; // 분할된 자식
public RectInt? room; // 실제 방이 생성된 영역 (Optional)
public Leaf(RectInt rect)
{
this.rect = rect;
}
public bool Split(int minSize, int maxSize)
{
if (left != null || right != null)
return false; // 이미 분할됨
bool splitHorizontally = UnityEngine.Random.value > 0.5f;
if (rect.width > rect.height && rect.width / rect.height >= 1.25f)
splitHorizontally = false;
else if (rect.height > rect.width && rect.height / rect.width >= 1.25f)
splitHorizontally = true;
int max = (splitHorizontally ? rect.height : rect.width) - minSize;
if (max <= minSize)
return false; // 더 이상 나눌 수 없음
int split = UnityEngine.Random.Range(minSize, max);
if (splitHorizontally)
{
left = new Leaf(new RectInt(rect.x, rect.y, rect.width, split));
right = new Leaf(new RectInt(rect.x, rect.y + split, rect.width, rect.height - split));
}
else
{
left = new Leaf(new RectInt(rect.x, rect.y, split, rect.height));
right = new Leaf(new RectInt(rect.x + split, rect.y, rect.width - split, rect.height));
}
return true;
}
}
우선 Leaf 클래스에는 구조체인 RectInt가 포함되며 이는 position값과 width와 height 값을 포함한다 또한 양분된 두개의 Leaf right, left를 가지게 된다
우선 50프로 확률로 horizontal split을 해줄지 정해준다 이때 현재 leaf의 종횡비가 1.25가 넘는지 확인하여 가로가 1.25배이상 길경우 verical split을 실행해준다.
이때 자르는 위치는 room의 minSize이상 이 되도록한다 따라서 minSize와 rect.height or rect.width - minSize사이의 값을 랜덤으로 받는다 이때 max값이 minSize이하가 된다면 두개의 minSize이상의 leaf가 생성되지 이렇게 자른 두개의 leaf를 left와 right에 할당해준다
split이 성공한다면 true반환 split에 실패하면 false 반환
public List<Leaf> SplitMap(RectInt rootRect, int minSize, int maxSize)
{
List<Leaf> leaves = new List<Leaf>();
Queue<Leaf> queue = new Queue<Leaf>();
Leaf root = new Leaf(rootRect);
queue.Enqueue(root);
leaves.Add(root);
while (queue.Count > 0)
{
Leaf leaf = queue.Dequeue();
if (leaf.rect.width > maxSize || leaf.rect.height > maxSize)
{
if (leaf.Split(minSize, maxSize))
{
queue.Enqueue(leaf.left);
queue.Enqueue(leaf.right);
leaves.Add(leaf.left);
leaves.Add(leaf.right);
}
}
}
return leaves;
}
맵 전체 크기의 rect 정보를 담은 leaf를 rootRect로 설정하고 이를 enqueue 해준다 또한 leaves에 add해준다
이후 queue가 비게 될때까지 split을 실행해준후 쪼개진 leaf들을 leave.add 와 enqueue를 실행해준다 이후 큐에 있는 leaf들을 순서대로 split을 해준다 이후 split이 불가능한 상태가 되고 queue가 비게 되면 실행을 멈춘후 leaves를 반환한다.
위 과정에서 rect의 size가 minsize에 가까울수록 높은확률을 제시하여 너무 잘게 쪼개지지 않는 코드를 집어넣을 예정이다
int roomCount = GetRoomCountForFloor(depth); // 예: 10개이후 각 층에 필요한 roomcount를 계산해준후
List<Leaf> selectedLeaves = RandomPick(leaves, roomCount);
랜덤으로 leaves를 골라준다
foreach (Leaf leaf in selectedLeaves)
{
RoomPreset preset = RoomPresetLibrary.GetRandom(); // 다양한 방 템플릿 보유
Vector2Int position = ChooseFitPosition(leaf, preset);
PlaceRoom(preset, position);
}
이후 프리셋에서 적절한 크기의 프리셋 room을 배치해준다.
여기서 현재 leaf의 rect 크기에 적절한 preset을 골라주는 메서드를 추가해야한다
A*알고리즘
타일 맵이 있다고 했을때 각 노드는 인접한 노드들과 모두 연결되어있고 수직 수평으로는 이동비용을 10 대각선으로는 14라고 가정한다.
이때 f(n) = g(n) + h(n) 이다
이때 g는 지금까지 이동에 사용된 cost 이며 h는 휴리스틱 즉 목적지까지의 장애물이 없을 경우의 예상 비용을 계산한것이다 이때 휴리스틱은 맨허튼 방식을 활용하겠다 맨허튼 방식은 맨허튼의 거리처럼 수직으로만 이동하는것을 가정한 계산 방식이다
시작시 시작노드를 openlist에 넣어준다 그뒤 이동가능한 노드들을 openlist에 넣어준다 이제 시작노드를 closedlist에 넣어준다 closedlist는 다시 볼필요가 없다는 뜻이다 openlist의 노드중에서 f값이 제일 낮은곳으로 이동한다
이제 이동한 노드의 부모노드를 이전노드로 지정해준다. 또한 openlist에서 빼준뒤 closedlist에 넣어준다 이제 이동한 노드의 인접 노드들 중에서 이미 closedlist에 있는 노드 이동이 불가능한 노드들을 제외한 노드들을 openlist에 넣어준다. 이때 열린 목록에 있는 노드들의 f g h 를 계산해준다. 이때 이미 기존의 열린 목록에 있다면 hashset true or false 인접한 사각현까지 이동할때 g 비용이 낮아지는지 확인한다 비용이 낮아질경우 해당노드의 부모노드을 현재노드로 바꿔준다
즉 현재노드로 이동한뒤 해당노드로 이동하는것이 비용이 절감된다는뜻이다. 비용이 절감되지않는경우는 오히려 돌아서 간다는 의미이므로 그대로 냅둔다
이제 다시 openlist의 f 비용이 제일 낮은 노드를 찾고 closedlist에 넣고 인접 노드들을 openlist에 넣고 부모노드로 설정해준뒤BSP란
Binary SPac Partitioning 즉 전체맵을 양분하는 메서드를 큐를 활용하여 재귀를 통해 MaxSize 이하 MinSize이상의 직사각형으로 나누는작업이다
public class Leaf
{
public RectInt rect; // 현재 영역
public Leaf left, right; // 분할된 자식
public RectInt? room; // 실제 방이 생성된 영역 (Optional)
public Leaf(RectInt rect)
{
this.rect = rect;
}
public bool Split(int minSize, int maxSize)
{
if (left != null || right != null)
return false; // 이미 분할됨
bool splitHorizontally = UnityEngine.Random.value > 0.5f;
if (rect.width > rect.height && rect.width / rect.height >= 1.25f)
splitHorizontally = false;
else if (rect.height > rect.width && rect.height / rect.width >= 1.25f)
splitHorizontally = true;
int max = (splitHorizontally ? rect.height : rect.width) - minSize;
if (max <= minSize)
return false; // 더 이상 나눌 수 없음
int split = UnityEngine.Random.Range(minSize, max);
if (splitHorizontally)
{
left = new Leaf(new RectInt(rect.x, rect.y, rect.width, split));
right = new Leaf(new RectInt(rect.x, rect.y + split, rect.width, rect.height - split));
}
else
{
left = new Leaf(new RectInt(rect.x, rect.y, split, rect.height));
right = new Leaf(new RectInt(rect.x + split, rect.y, rect.width - split, rect.height));
}
return true;
}
}
우선 Leaf 클래스에는 구조체인 RectInt가 포함되며 이는 position값과 width와 height 값을 포함한다 또한 양분된 두개의 Leaf right, left를 가지게 된다
우선 50프로 확률로 horizontal split을 해줄지 정해준다 이때 현재 leaf의 종횡비가 1.25가 넘는지 확인하여 가로가 1.25배이상 길경우 verical split을 실행해준다.
이때 자르는 위치는 room의 minSize이상 이 되도록한다 따라서 minSize와 rect.height or rect.width - minSize사이의 값을 랜덤으로 받는다 이때 max값이 minSize이하가 된다면 두개의 minSize이상의 leaf가 생성되지 이렇게 자른 두개의 leaf를 left와 right에 할당해준다
split이 성공한다면 true반환 split에 실패하면 false 반환
public List<Leaf> SplitMap(RectInt rootRect, int minSize, int maxSize)
{
List<Leaf> leaves = new List<Leaf>();
Queue<Leaf> queue = new Queue<Leaf>();
Leaf root = new Leaf(rootRect);
queue.Enqueue(root);
leaves.Add(root);
while (queue.Count > 0)
{
Leaf leaf = queue.Dequeue();
if (leaf.rect.width > maxSize || leaf.rect.height > maxSize)
{
if (leaf.Split(minSize, maxSize))
{
queue.Enqueue(leaf.left);
queue.Enqueue(leaf.right);
leaves.Add(leaf.left);
leaves.Add(leaf.right);
}
}
}
return leaves;
}
맵 전체 크기의 rect 정보를 담은 leaf를 rootRect로 설정하고 이를 enqueue 해준다 또한 leaves에 add해준다
이후 queue가 비게 될때까지 split을 실행해준후 쪼개진 leaf들을 leave.add 와 enqueue를 실행해준다 이후 큐에 있는 leaf들을 순서대로 split을 해준다 이후 split이 불가능한 상태가 되고 queue가 비게 되면 실행을 멈춘후 leaves를 반환한다.
위 과정에서 rect의 size가 minsize에 가까울수록 높은확률을 제시하여 너무 잘게 쪼개지지 않는 코드를 집어넣을 예정이다
int roomCount = GetRoomCountForFloor(depth); // 예: 10개
이후 각 층에 필요한 roomcount를 계산해준후
List<Leaf> selectedLeaves = RandomPick(leaves, roomCount);
랜덤으로 leaves를 골라준다
foreach (Leaf leaf in selectedLeaves)
{
RoomPreset preset = RoomPresetLibrary.GetRandom(); // 다양한 방 템플릿 보유
Vector2Int position = ChooseFitPosition(leaf, preset);
PlaceRoom(preset, position);
}
이후 프리셋에서 적절한 크기의 프리셋 room을 배치해준다.
여기서 현재 leaf의 rect 크기에 적절한 preset을 골라주는 메서드를 추가해야한다