[C#, Unity, 절차적 생성] 절차적 던전 생성 - 3. BSP 알고리즘 개선

2025/05/15
- 조건부 분할 위치를 계산하는 부분에서 offset * 2를 기준으로 방 최소 사이즈를 만족하는지 확인하는 코드 수정.
- 코드 변경에 따른 최종 결과 갱신.

■ BSP 알고리즘 개선

[분할된 공간에 방이 생성된 결과]

현재 구현된 BSP 알고리즘은 분할 조건이 단순하기 때문에, 분할 방향이 한쪽(가로 또는 세로)으로만 생성되어 지나치게 긴 복도가 생성되는 경우가 존재한다.

• 따라서 추가 조건을 생성하여 균등하게 공간이 분할될 수 있도록 수정한다.

 

1. 분할 방향 조건 추가

var widthStatus = node.Width >= _data.RoomMinWidth * 2;
var heightStatus = node.Height >= _data.RoomMinHeight * 2;

var splitDir = (widthStatus, heightStatus) switch
{
	(true, true) => (ELine)Random.Range(0, 2),
	(false, true) => ELine.Horizontal,
	(true, false) => ELine.Vertical,
	_ => ELine.None
};

기존에는 수직, 수평 분할이 모두 가능하다면 완전 랜덤하게 분할이 되기 때문에 한쪽으로만 쏠릴 수 있다.

• 이를 해결하기 위해 가로와 세로 비율을 계산한 뒤, 분할 방향을 결정한다.

 

private ELine CheckSizeRatio(RoomNode node)
{
	var ratio = (float)node.Width / node.Height;
	var line = ELine.None;
	
	if (ratio >= _data.HorizontalRatio) line = ELine.Vertical;
	else if (ratio < _data.VerticalRatio) line = ELine.Horizontal;
	else line = (ELine)Random.Range(0, 2);
	
	return line;
}

(float)node.Width / node.Height; 를 통해 가로, 세로 비율을 계산한다.

• 값이 HorizontalRatio(1.25)보다 크면 너비가 넓은 공간이므로, 세로 분할을 진행한다.
• 값이 VerticalRatio(0.6)보다 작으면 길이가 긴 공간이므로, 가로 분할을 진행한다.
• 가로와 세로가 비슷한 길이라면, 랜덤한 분할 방향을 선택한다.

 

2. 분할 범위 조건 추가

newPos = Random.Range(curPos.BL.x + _data.RoomMinWidth, 
		curPos.BR.x - _data.RoomMinWidth);

기존의 분할 위치 계산 방식은, 노드의 꼭짓점에서 방의 최소 크기만큼 이동한 범위를 기준으로 분할 위치를 랜덤 하게 정한다.

• 최소 크기만을 고려해 분할할 경우, 분할 위치가 한쪽에 매우 가까운 비대칭 분할이 생길 수 있다.

[분할 범위를 중앙으로 조정]

private int GetSplitPos(int size, int minSize, int corner)
{
    var range = (size - minSize * 2) / 2;
    var mid = corner + size / 2;

    var splitRatio = _data.SplitRange;
    var offset = (int)(range * splitRatio);

    var splitPos = Random.Range(mid - offset, mid + offset);

    var sizeCheck1 = Mathf.Abs(splitPos - corner);
    var sizeCheck2 = Mathf.Abs(size - sizeCheck1);

    if (sizeCheck1 < minSize || sizeCheck2 < minSize)
    {
    	return mid;
    }

    return splitPos;
}

분할 위치가 한쪽으로 쏠리는 문제를 방지하기 위해, 범위를 지정할 때 중앙 부근에 위치할 수 있도록 위와 같이 구현하였다.

 

1. range

전체 길이에서 양쪽 최소 크기를 뺀 후 중앙 기준으로 양쪽에 쓸 수 있는 거리를 계산한다.

• size = 50, minSize = 10 이면 $(50-20) / 2=15$ → 중앙 기준으로 최대 15씩 이동한 범위를 사용한다.

2. Offset

지정한 비율(splitRatio)만큼만 중앙에서 벗어나도록 제한한다.

• splitRatio값이 커질수록 중앙에서 멀어지고, 작아질수록 중앙에 가까운 범위가 생성된다.

 

3. 분할 위치 확인(예외 처리)

분할 위치를 기준으로 좌,우측(혹은 상,하단)이 방 최소 길이를 만족하는지 확인한다. 이 코드는 생략하고 바로 분할 위치를 반환해도 된다.

• 이미 범위가 최소 길이를 보장하지만, splitRatio가 1을 초과한 값이 들어올 수 있으므로 예외 처리 코드를 추가하였다.

 

// 수평 분할 기준 랜덤 좌표 구하기
case ELine.Horizontal:
	newPos = _checkConditions ? 
		GetSplitPos(node.Height, _data.RoomMinHeight, curPos.BL.y) :
		Random.Range(curPos.BL.y + _data.RoomMinHeight, curPos.TL.y - _data.RoomMinHeight);
	                
	pos1 = new NodePosition(curPos.BL, new Vector2Int(curPos.BR.x, newPos));
	pos2 = new NodePosition(new Vector2Int(curPos.BL.x, newPos), curPos.TR);
                
	break;

// 수직 분할 기준 랜덤 좌표 구하기
case ELine.Vertical:
	newPos = _checkConditions ?
		GetSplitPos(node.Width, _data.RoomMinWidth, curPos.BL.x) :
		Random.Range(curPos.BL.x + _data.RoomMinWidth, curPos.BR.x - _data.RoomMinWidth);
	
	pos1 = new NodePosition(curPos.BL, new Vector2Int(newPos, curPos.TL.y));
	pos2 = new NodePosition(new Vector2Int(newPos, curPos.BL.y), curPos.TR);
    
	break;

_checkConditions변수를 통해 완전 무작위 분할과 조건부 분할을 선택할 수 있도록 설정한다.

 

■ 전체 코드 및 결과

[splitRatio : 0.1 (중앙에 가까운 범위)]

[splitRatio : 0.5 (중앙에서 떨어진 범위)]

[splitRatio : 1 (전체 범위)]

using System;
using System.Collections.Generic;
using UnityEngine;
using Random = UnityEngine.Random;

public enum ELine
{
    None = -1,
    Horizontal = 0,
    Vertical = 1
}

public class BinarySpacePartitioning
{
    private DungeonData _data;
    private bool _checkConditions;
    
    public List<RoomNode> BSP(DungeonData data, bool checkConditions = true)
    {
        _data = data;
        _checkConditions = checkConditions;

        var rootPos =
            new NodePosition(new Vector2Int(0, 0), new Vector2Int(_data.Width, _data.Height));
        var rootNode = new RoomNode(null, rootPos, 0);

        var result = new List<RoomNode> { rootNode };
        var graph = new Queue<RoomNode>(new[] { rootNode });
        var iter = 0;

        while (iter < _data.Iteration && graph.Count > 0)
        {
            iter++;

            var curNode = graph.Dequeue();
            SplitSpace(curNode, graph, result);
        }

        return result;
    }

    private void SplitSpace(RoomNode node, Queue<RoomNode> graph, List<RoomNode> nodeList)
    {
        var widthStatus = node.Width >= _data.RoomMinWidth * 2;
        var heightStatus = node.Height >= _data.RoomMinHeight * 2;

        var splitDir = (widthStatus, heightStatus) switch
        {
            (true, true) when _checkConditions => CheckSizeRatio(node),
            (true, true) => (ELine)Random.Range(0, 2),
            (false, true) => ELine.Horizontal,
            (true, false) => ELine.Vertical,
            _ => ELine.None
        };

        var curPos = node.Pos;
        var newPos = 0;
        NodePosition pos1 = null;
        NodePosition pos2 = null;

        switch (splitDir)
        {
            case ELine.Horizontal:
                newPos = _checkConditions ? 
                    GetSplitPos(node.Height, _data.RoomMinHeight, curPos.BL.y) :
                    Random.Range(curPos.BL.y + _data.RoomMinHeight, curPos.TL.y - _data.RoomMinHeight);
                
                pos1 = new NodePosition(curPos.BL, new Vector2Int(curPos.BR.x, newPos));
                pos2 = new NodePosition(new Vector2Int(curPos.BL.x, newPos), curPos.TR);
                
                break;

            case ELine.Vertical:
                newPos = _checkConditions ?
                    GetSplitPos(node.Width, _data.RoomMinWidth, curPos.BL.x) :
                    Random.Range(curPos.BL.x + _data.RoomMinWidth, curPos.BR.x - _data.RoomMinWidth);

                pos1 = new NodePosition(curPos.BL, new Vector2Int(newPos, curPos.TL.y));
                pos2 = new NodePosition(new Vector2Int(newPos, curPos.BL.y), curPos.TR);
                break;

            case ELine.None:
            default:
                return;
        }
        
        var node1 = new RoomNode(node, pos1, node.Index + 1);
        var node2 = new RoomNode(node, pos2, node.Index + 1);
        
        graph.Enqueue(node1);
        nodeList.Add(node1);

        graph.Enqueue(node2);
        nodeList.Add(node2);
    }

    private int GetSplitPos(int size, int minSize, int corner)
    {
        var range = (size - minSize * 2) / 2;
        var mid = corner + size / 2;

        var splitRatio = _data.SplitRange;
        var offset = (int)(range * splitRatio);

        var splitPos = Random.Range(mid - offset, mid + offset);

        var sizeCheck1 = Mathf.Abs(splitPos - corner);
        var sizeCheck2 = Mathf.Abs(size - sizeCheck1);

        if (sizeCheck1 < minSize || sizeCheck2 < minSize)
        {
            return mid;
        }

        return splitPos;
    }

    private ELine CheckSizeRatio(RoomNode node)
    {
        var ratio = (float)node.Width / node.Height;
        var line = ELine.None;

        if (ratio >= _data.HorizontalRatio) line = ELine.Vertical;
        else if (ratio < _data.VerticalRatio) line = ELine.Horizontal;
        else line = (ELine)Random.Range(0, 2);

        return line;
    }
}

[BinarySpacePartitioning.cs]

using System.Collections.Generic;
using UnityEngine;

public class RoomGenerator
{
    private Vector2Int _offset;
    private float _minWeight;
    private float _maxWeight;

    public void GenerateRoom(List<RoomNode> leafNode, DungeonData data)
    {
        _offset = data.Offset;
        _minWeight = data.BottomLeftWeight;
        _maxWeight = data.TopRightWeight;

        foreach (var node in leafNode)
        {
            CreateRoomSpace(node);
        }
    }

    private void CreateRoomSpace(RoomNode node)
    {
        var curPos = node.Pos;

        // 최소, 최대 범위 계산
        var min = new Vector2Int(curPos.BL.x + _offset.x, curPos.BL.y + _offset.y);
        var max = new Vector2Int(curPos.TR.x - _offset.x, curPos.TR.y - _offset.y);
        
        // 방이 생성될 수 있는 길이 구하기
        var roomWidth = max.x - min.x;
        var roomHeight = max.y - min.y;

        var roomBL = new Vector2Int(
            Random.Range(min.x, min.x + (int)(roomWidth * _minWeight)),
            Random.Range(min.y, min.y + (int)(roomHeight * _minWeight)));
        
        // BL보다 무조건 커야함. 
        var minTRX = roomBL.x + (int)(roomWidth * _maxWeight);
        var minTRY = roomBL.y + (int)(roomHeight * _maxWeight);
        
        var roomTR = new Vector2Int(
            Random.Range(minTRX, max.x),
            Random.Range(minTRY, max.y));

        node.AddRoomPosition(new NodePosition(roomBL, roomTR));
    }
}

[RoomGenerator.cs]

using System;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Serialization;

public class DungeonGenerator : MonoBehaviour
{
    [Header("Component")] 
    [SerializeField] private LineDisplay lineDisplay;
    [SerializeField] private MeshGenerator meshGenerator;

    [Header("Create Setting")] 
    [SerializeField] private bool checkConditions;
    [SerializeField] private DungeonData dungeonData;
    
    private List<RoomNode> _roomNodeList;
    private List<RoomNode> _leafNode;

    private void Start()
    {
        GenerateDungeon();
    }

    private void GenerateDungeon()
    {
        var bsp = new BinarySpacePartitioning();
        var roomGenerator = new RoomGenerator();
        
        _roomNodeList = bsp.BSP(dungeonData, checkConditions);
        _leafNode = GetAllLeafNode();
        
        roomGenerator.GenerateRoom(_leafNode, dungeonData);
        lineDisplay.DisplayLine(_roomNodeList[0]);
        lineDisplay.DisplayLine(_leafNode);
        
        _leafNode.ForEach(x => meshGenerator.CreateMesh(x.RoomPosition));
    }

    private List<RoomNode> GetAllLeafNode()
    {
        var leafNodes = new List<RoomNode>();
        var queue = new Queue<RoomNode>(new[] { _roomNodeList[0] });

        while (queue.Count > 0)
        {
            var node = queue.Dequeue();

            if (node.ChildNode.Count <= 0)
            {
                leafNodes.Add(node);
                continue;
            }

            foreach (var chile in node.ChildNode)
            {
                queue.Enqueue((RoomNode)chile);
            }
        }

        return leafNodes;
    }
}

[DungeonGenerator.cs]

다음에는 방과 방을 잇는 복도를 생성하고, 최종적으로 벽을 생성하여 절차적 던전 생성을 마무리해보자.