[Unity]BSP(Binary Space Partitioning)를 이용한 던전 룸 생성 - 01

Binary Space Partitioning(이하 BSP)를 먼저 간단하게 설명하자면 말 그래도 이진 공간 분할로 공간을 둘로 분할하며, 재귀적으로 나누어진 공간을 트리 형태로 구성하면 우리가 흔히 듣던 BSP Tree가 된다.

 

그럼 BSP를 이용해 던전을 구성해보자. 순서는 다음과 같다.

 

1. 한 공간을 수직 또는 수평으로 이분할 한다. 이 때, 분할된 공간을 노드로 취급하며, 이진 트리의 자식 노드로 추가한다.

2. 정해진 분할 개수만큼 1번을 반복한다.

3. 말단노드(Leaf Node)는 최종적으로 룸을 구성할 공간 노드가 되고, 나중에 이를 통해 룸을 구성한다.

 

 

---

1. 공간 분할하기

구현함에 있어 사람마다 다르게 구현한 걸 자주 볼 수 있었다. 예를 들면 노드의 순회 방식에 따라 깊이(depth)로 나누어서 불균형적인 모습으로 나누는 방법도 있다. 하지만 나는 전위순회(Root-Left-Right)를 통해, 각 공간별로 동일한 횟수로 분할하는 걸로 하겠다.

 

그림으로 보면 다음과 같다.

2번 반복했을 때의 모습이며, 처음 하나의 공간을 1,2노드로 분할. 그리고 1번 노드를 3,4로 분할, 2번 노드를 5,6 노드로 분할해가며 트리를 구성한다.

 

구현한 코드다. 포스팅 제일 하단에 깃헙링크가 있다.

---

    private void DivideSpace(RoomNode node, int iterations = 0)
    {
        if (iterations == _maxIterations)
            return;

        eSplitDirection splitDireciton = (node.Width > node.Height) ? eSplitDirection.VERTICAL : eSplitDirection.HORIZONTAL;
        node.SplittedDirection = splitDireciton;


        if (eSplitDirection.HORIZONTAL == splitDireciton)
        {
            //가로
            int dividedHeight = Mathf.RoundToInt(UnityEngine.Random.Range(node.Height * minDivideRatio, node.Height * maxDivideRatio));

            RectInt topRoomSize = new RectInt(
                node.BottomLeftPosition.x, node.BottomLeftPosition.y + dividedHeight,
                node.Width, node.Height - dividedHeight
            );

            RectInt bottomRoomSize = new RectInt(
                node.BottomLeftPosition.x, node.BottomLeftPosition.y,
                node.Width, dividedHeight
            );

            GameObject go = Resources.Load<GameObject>("TestLineRenderer");
            GameObject instance = GameObject.Instantiate(go);
            LineRenderer line = instance.GetComponent<LineRenderer>();
            line.SetPosition(0, new Vector3(node.BottomLeftPosition.x, 0, node.BottomLeftPosition.y + dividedHeight));
            line.SetPosition(1, new Vector3(node.TopRightPosition.x, 0, node.BottomLeftPosition.y + dividedHeight));

            RoomNode leftNode = new RoomNode(topRoomSize);
            RoomNode rightNode = new RoomNode(bottomRoomSize);

            node.Left = leftNode;
            node.Right = rightNode;
        }
        else
        {
            //세로
            int dividedWidth = Mathf.RoundToInt(UnityEngine.Random.Range(node.Width * minDivideRatio, node.Width * maxDivideRatio));

            RectInt leftRoomSize = new RectInt(
                node.BottomLeftPosition.x, node.BottomLeftPosition.y,
                dividedWidth, node.Height
            );

            RectInt rightRoomSize = new RectInt(
                node.BottomLeftPosition.x + dividedWidth, node.BottomLeftPosition.y,
                node.Width - dividedWidth, node.Height
            );

            GameObject go = Resources.Load<GameObject>("TestLineRenderer");
            GameObject instance = GameObject.Instantiate(go);
            LineRenderer line = instance.GetComponent<LineRenderer>();
            line.SetPosition(0, new Vector3(node.BottomLeftPosition.x + dividedWidth, 0, node.BottomLeftPosition.y));
            line.SetPosition(1, new Vector3(node.BottomLeftPosition.x + dividedWidth, 0, node.TopRightPosition.y));

            RoomNode leftNode = new RoomNode(leftRoomSize);
            RoomNode rightNode = new RoomNode(rightRoomSize);

            node.Left = leftNode;
            node.Right = rightNode;
        }

        DivideSpace(node.Left, iterations + 1);
        DivideSpace(node.Right, iterations + 1);
    }
}

공간을 수직 or 수평으로 나누고 다시 좌, 우 노드를 나누는 함수를 재귀적으로 호출하는 걸 볼 수 있다.

---

 

간단하게 라인렌더러를 이용해 출력한 결과물이다.

 

다음에 이 분할된 공간 안에 방을 생성하는 것을 알아보자.

 

Github: https://github.com/AntarticPenguin/DungeonRogueLike