[C#, Unity, 절차적 생성] 절차적 던전 생성 - 1. Binary Space Partitioning

728x90

2025-05-15 (수정사항)
- NodePosition을 초기화 할 때 (좌상단, 우하단)기준에서 (좌하단, 우상단)기준으로 초기화하도록 수정.

■ 이진 공간 분할법 - Binary Space Partitioning(BSP)

BSP 알고리즘은 공간을 재귀적으로 둘로 분할해 가며 이진트리를 구성하는 알고리즘이다. 최종적으로 자식이 없는 리프 노드에 각 분할된 공간이 저장된다.

이를 활용하여 던전등의 지형을 절차적으로 생성할 수 있다.

BSP 알고리즘 동작 순서

현재 공간의 분할 방향(수직, 수평)을 결정한다.
선택된 방향으로 공간을 2개로 분할, 이 공간을 큐에 추가한다.
분할된 공간에 대해 1~2번의 과정을 더 이상 분할이 불가능할때까지 반복한다.

■ BSP 구현

1. BSP 트리 노드 구성

using System.Collections.Generic;

public abstract class BSP_Node
{
    public BSP_Node ParentNode;
    public List<BSP_Node> ChildNode;
   
    public NodePosition Pos;
    public int Index;

    public BSP_Node(BSP_Node parent)
    {
        ParentNode = parent;
        ChildNode = new List<BSP_Node>();
        
        ParentNode?.AddChildNode(this);
    }

    public void AddChildNode(BSP_Node node)
    {
        ChildNode?.Add(node);
    }
}

BSP 트리에서 노드들은 다음과 같은 정보를 가진다.

ParentNode : 부모 노드를 저장할 변수
ChildNode : 분할된 하위 노드들을 저장할 변수.
Pos : 사각형 영역의 네 꼭짓점 좌표를 저장할 클래스.
Index : 트리 상의 깊이값.

노드는 생성 시 부모 노드에 자신을 자동으로 등록하며, BSP알고리즘에 의해 재귀적으로 트리 구조를 완성한다.

using UnityEngine;

public class NodePosition
{
    public Vector2Int TL { get; private set; }
    public Vector2Int TR { get; private set; }
    public Vector2Int BL { get; private set; }
    public Vector2Int BR { get; private set; }

    public NodePosition(Vector2Int bottomLeft, Vector2Int topRight)
    {
        BL = bottomLeft;
        TR = topRight;
        BR = new Vector2Int(TR.x, BL.y);
        TL = new Vector2Int(BL.x, TR.y);
    }

    public Vector2Int[] GetPositionArray()
    {
        return new[] { BL, TL, TR, BR };
    }
}

NodePosition 클래스는 좌하단(BL), 우상단(TR)좌표를 사용하여 사각형 영역을 정의한다. 나머지 두 위치는 생성자 내부에서 자동으로 계산한다.

GetPositionArray() 함수를 통해 4개의 꼭짓점을 배열로 반환하여 반복문 작업에 적합하게 한다.

using UnityEngine;

public class RoomNode : BSP_Node
{
    public int Width => Mathf.Abs(Pos.BR.x - Pos.TL.x);
    public int Height => Mathf.Abs(Pos.TL.y - Pos.BL.y);
        
    public RoomNode(BSP_Node parent, NodePosition position, int index) : base(parent)
    {
        Pos = position;
        Index = index;
    }
}

마지막으로 BSP_Node를 상속받아 방 생성 정보를 저장할 노드 클래스를 생성한다.

분할된 공간의 너비와 높이를 반환하는 프로퍼티를 통해 크기를 빠르게 계산할 수 있도록 구현한다.

2. 던전 생성 정보

using UnityEngine;

[CreateAssetMenu(fileName = "DungeonData", menuName = "PCG/DungeonData")]
public class DungeonData : ScriptableObject
{
    [SerializeField] private int width;
    [SerializeField] private int height;
    [SerializeField] private int roomMinWidth;
    [SerializeField] private int roomMinHeight;
    [SerializeField] private int iteration;

    public int Width => width;
    public int Height => height;
    public int RoomMinWidth => roomMinWidth;
    public int RoomMinHeight => roomMinHeight;
    public int Iteration => iteration;
}

던전 생성에 필요한 정보는 스크립터블 오브젝트로 관리한다. 전체 맵 크기(width, height), 방의 최소 크기(roomMinWidth, roomMinHeight), 분할 반복 횟수(iteration)를 저장한다.

3. 공간 분할(BSP)

public class BinarySpacePartitioning
{
    private DungeonData _data;

    public List<RoomNode> BSP(DungeonData data)
    {
        _data = data;

        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;
    }
}

전체 맵 크기를 기반으로 루트 노드를 생성한 뒤, 재귀적으로 분할하여 자식 노드들을 생성한다.

재귀 호출을 사용하지 않고 Queue를 사용하여 먼저 저장된 노드가 먼저 분할될 수 있도록 한다.

분할 방향 결정

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

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) => (ELine)Random.Range(0,2),
				(false, true) => ELine.Horizontal,
				(true, false) => ELine.Vertical,
				_ => ELine.None
		};
}

공간을 분할하기 위해 현재 노드가 가진 영역을 기준으로 분할 가능한 방향을 정한다.

현재 노드의 너비가 roomMinWidth * 2 이상이라면, 좌우 두 공간 모두 최소 너비를 만족하므로 세로 분할을 진행한다.
현재 노드의 높이가 roomMinHeight * 2 이상이라면, 상하 두 공간 모두 최소 높이를 만족하므로 가로 분할을 진행한다.
두 조건 모두 만족 시 랜덤한 방향으로 분할을 진행하며, 두 방향 모두 분할이 불가능할 경우엔 리프 노드로 간주한다.

분할 위치 계산

private void SplitSpace(RoomNode node, Queue<RoomNode> graph, List<RoomNode> nodeList)
{
    // ... 분할 방향 결정 코드 생략

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

    switch (splitDir)
    {
        case ELine.Horizontal:
            newPos = 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 = 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;
    }
}

분할 방향을 결정한 후, 실제 공간을 나눌 위치를 계산해야 한다. 이때 분할되는 영역이 모두 방의 최소 크기 이상을 확보할 수 있는 범위 내에서 랜덤한 위치를 선택한다.

가로 분할 : 좌하단(BL)의 Y 값 + 최소 높이 ~ 좌상단(TL) 의 Y값 - 최소 높이 사이에서 랜덤한 위치를 선택한다.
세로 분할 : 좌하단(BL)의 X 값 + 최소 너비 ~ 우하단(BR) 의 X값 - 최소 너비 사이에서 랜덤한 위치를 선택한다.

분할 위치를 기준으로 두 개의 새로운 공간을 생성해야 한다. 이때, 기존 노드의 꼭짓점을 활용하여 자식 노드의 좌상단(TL)과 우하단(BR) 좌표를 계산할 수 있다.

수평 분할
- Node1(상단 영역) 의 좌상단, 우하단 좌표 : 기존 노드의 좌상단(TL)과 동일 / (BR,x, newPos)
- Node2(하단 영역)의 좌상단, 우하단 좌표 : (BL.x, newPos) / 기존 노드의 우하단(BR)과 동일
수직 분할
- Node1(좌측 영역) 의 좌상단, 우하단 좌표 : 기존 노드의 좌상단(TL)과 동일 / (newPos, BL.y)
- Node2(우측 영역) 의 좌상단, 우하단 좌표 : (newPos, TL.y) / 기존 노드의 우하단(BR)과 동일

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);

마지막으로 분할된 공간을 큐와 리스트에 넣고 마무리한다.

4. 시각화

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

public class LineDisplay : MonoBehaviour
{
    [Header("Line Setting")] 
    [SerializeField] private float width;
    [SerializeField] private Material lineMat;

    public void DisplayLine(RoomNode rootNode)
    {
        var queue = new Queue<RoomNode>();
        queue.Enqueue(rootNode);

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

            var obj = new GameObject($"Room{node.Index}").AddComponent<LineRenderer>();
            obj.transform.SetParent(transform);
            obj.positionCount = 5;
            obj.startWidth = obj.endWidth = width;
            obj.material = lineMat;

            var posArr = node.Pos.GetPositionArray();
            for (var i = 0; i < posArr.Length + 1; ++i)
            {
                var cur = posArr[i % posArr.Length];
                obj.SetPosition(i, new Vector3(cur.x, 0, cur.y));
            }

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

}

Root노드부터 시작해 너비 우선 탐색으로 자식 노드들을 탐색하며 LineRenderer컴포넌트를 통해 분할된 영역을 시각화한다.

4개의 꼭짓점을 배열로 받아온 후, i % posArr.Length 방식으로 인덱스를 순환시켜 마지막 점과 첫 번째 점을 이어 사각형을 닫는다.

5. DungeonGenerator.cs

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

public class DungeonGenerator : MonoBehaviour
{
    [Header("Create Setting")] 
    [SerializeField] private DungeonData dungeonData;
    
    private List<RoomNode> _roomNodeList;

    private void Start()
    {
        GenerateDungeon();
    }

    private void GenerateDungeon()
    {
        var bsp = new BinarySpacePartitioning();
        _roomNodeList = bsp.BSP(dungeonData);
        
        GetComponent<LineDisplay>().DisplayLine(_roomNodeList[0]);
    }
}

게임 시작 시, 공간 분할을 진행할 수 있도록 Start() 함수에서 BSP 알고리즘을 실행하여 공간을 분할하고, 그 결과를 LineDisplay를 통해 시각화한다.

■ 최종 결과

다음엔 분할된 공간에 방을 생성하는 기능을 구현해 보자.

728x90

'Unity,C# > 절차적생성(PCG)' 카테고리의 다른 글

[C#, Unity, 절차적 생성] 절차적 던전 생성 - 3. BSP 알고리즘 개선 (1)	2025.05.12
[C#, Unity, 절차적 생성] 절차적 던전 생성 - 2. 방 생성 (0)	2025.05.12
[C#, Unity, 절차적 생성] 절차적 지형 생성 - 3.터레인 생성 (0)	2025.04.28
[C#, Unity, 절차적 생성] 절차적 지형 생성 - 2.프랙탈 합 (2)	2025.04.24
[C#, Unity, 절차적 생성] 절차적 지형 생성 - 1.PerlinNoise (1)	2025.04.16

■ 이진 공간 분할법 - Binary Space Partitioning(BSP)

■ BSP 구현

1. BSP 트리 노드 구성

2. 던전 생성 정보

3. 공간 분할(BSP)

4. 시각화

5. DungeonGenerator.cs

■ 최종 결과

'Unity,C# > 절차적생성(PCG)' 카테고리의 다른 글

티스토리툴바