728x90
■ 복도 생성
BSP로 완성된 이진트리를 역방향으로 순회하며, 자식 노드에 생성된 방 사이를 복도로 연결한다. 복도 생성은 다음과 같은 흐름으로 진행된다.
복도 생성 절차
- 트리의 가장 깊은 곳부터 시작하여, 자식 노드를 가진 부모 노드를 찾는다.
- 두 자식 노드의 상대적인 위치(상,하,좌,우)를 파악한다.
- 두 방이 연결 가능한 위치에 있는지 확인한다.
- 연결이 가능하다면 복도를 생성한다. 연결이 불가능하다면, 다른 노드를 대상으로 연결 가능 여부를 다시 체크한다.
■ 상세 구현 내용
1. 연결 대상 찾기
using System.Collections.Generic;
using System.Linq;
public class CorridorGenerator
{
private List<RoomNode> _roomNodes;
private DungeonData _data;
public List<CorridorNode> GenerateCorridor(List<RoomNode> rooms, DungeonData data)
{
var sortedRoom = rooms.OrderByDescending(x => x.Index).ToList();
var corridorList = new List<CorridorNode>();
foreach (var node in sortedRoom)
{
if (node.ChildNode.Count == 0)
{
continue;
}
var corridor = new CorridorNode((RoomNode)node.ChildNode[0], (RoomNode)node.ChildNode[1],
data.CorridorWidth, data.DistanceFromWall);
corridorList.Add(corridor);
}
return corridorList;
}
}
BSP로 공간을 분할하고 방을 생성한 결과(List<RoomNode>)를 Index(트리의 깊이) 기준으로 내림차순 정렬하여, 가장 깊은 노드부터 복도를 생성한다.
- 자식 노드가 없다면 연결 대상이 없으므로 건너뛴다.
- 자식 노드를 가진 경우, 두 자식 노드의 연결 가능성을 평가하고 복도를 생성한다.
2. CorridorNode
public enum ERelative
{
Right,
Left,
Top,
Bottom
}
public class CorridorNode : BSP_Node
{
private readonly int _width;
private readonly int _interval;
public CorridorNode(RoomNode node1, RoomNode node2, int width,
int distanceFromWall) : base(null)
{
_width = width;
_interval = distanceFromWall;
GenerateCorridor(node1, node2);
}
}
복도 생성을 담당하는 CorridorNode는 BSP_Node를 상속받아 구현하였다. 생성자에서 연결할 두 개의 방(RoomNode)과 설정값을 전달받아 복도를 생성한다.
- _width : 복도의 폭(넓이)
- _interval : 복도와 방 사이에 확보할 여유 공간.
ERelative는 두 방의 상대적 위치 관계(상,하,좌,우)를 나타낸다.
3. 상대적 위치 파악
private ERelative GetRelativePosition(RoomNode node1, RoomNode node2)
{
var mid1 = (node1.Pos.TR + node1.Pos.BL) / 2;
var mid2 = (node2.Pos.TR + node2.Pos.BL) / 2;
var angle = Mathf.Atan2(mid2.y - mid1.y, mid2.x - mid1.x);
angle *= Mathf.Rad2Deg;
if (45f < angle && angle < 135f) return ERelative.Top;
if (-135f < angle && angle < -45f) return ERelative.Bottom;
if ((0 <= angle && angle < 45) || (-45 < angle && angle <= 0)) return ERelative.Right;
return ERelative.Left;
}
두 노드의 중점을 계산한 후, 이 두 중점의 차를 통해 Node1에서 Node2로 향하는 벡터를 구한다. 해당 벡터가 x축과 이루는 각도를 Atan2() 함수를 통해 계산한다.
앞서 구한 각도를 통해 상대적인 위치를 판단한다.
예를 들어, 각도가 45º이상 135º이하인 경우, Node2는 Node1의 위쪽에 위치하므로, Node1의 위쪽 경계와 Node2의 아래쪽 경계를 기준으로 복도를 생성한다.
private void GenerateCorridor(RoomNode node1, RoomNode node2)
{
var relative = GetRelativePosition(node1, node2);
switch (relative)
{
case ERelative.Right:
ConnectCorridorLeftRight(node1, node2);
break;
case ERelative.Left:
ConnectCorridorLeftRight(node2, node1);
break;
case ERelative.Top:
ConnectCorridorBottomTop(node1, node2);
break;
case ERelative.Bottom:
ConnectCorridorBottomTop(node2, node1);
break;
default:
return;
}
}
노드 간 상대 위치가 좌우일 때와 상하일 때는 복도를 연결하는 방식이 다르기 때문에, 각 방향에 따라 별도로 처리해야 한다.
- 좌우 방향(Left, Right)일 경우, 복도는 양쪽 노드의 좌우 경계면을 기준으로 생성된다.
- 상하 방향(Top, Bottom)일 경우, 복도는 각 노드의 상단 또는 하단 경계면을 기준으로 생성된다.
4. 복도가 좌우 방향에 위치할 때
좌측 노드 선택
파라미터로 넘어온 노드 중, 실제 연결될 “좌측 방”을 먼저 찾는다. 이때 양쪽 노드는 모두 방 생성 정보가 저장된 “단말 노드”여야 한다.
- 예시로, 좌측 노드가 1번 노드라면, 그 자식 노드인 3번, 9번, 10번 노드가 연결 대상(좌측)이 된다.
좌측 노드의 자식 방들을 우측 노드에 더 가까운 순서대로 정렬하기 위해, 각 방의 좌상산(TR)의 x좌표를 기준으로 내림차순 정렬한다.
이는 x값이 더 클수록 우측 노드에 더 가까이 위치하기 때문에, 연결 가능성이 높은 방들을 앞에 위치시킨다.
- 이후, 가장 x값이 큰 노드를 기준으로 x좌표 차이가 일정 범위를 벗어나는 방은 연결 대상에서 제외한다.
- 복도가 방을 뚫고 생성되는 문제(예시 : 9번과 5번 노드의 연결)를 방지한다.
private void ConnectCorridorLeftRight(RoomNode leftRoom, RoomNode rightRoom)
{
// 연결할 좌측 노드 찾기
RoomNode selectedLeftRoom = null;
// 좌측 노드에서 자식 노드를 모두 찾고 좌상단 X축을 기준으로 내림차순 정렬
var leftRoomList = NodeUtility.GetAllLeafNode(leftRoom)
.OrderByDescending(x => x.RoomPosition.TR.x).ToList();
if (leftRoomList.Count <= 1)
{
selectedLeftRoom = leftRoom;
}
else
{
var maxX = leftRoomList[0].RoomPosition.TR.x;
// 연결 불가능한 노드를 제외
leftRoomList = leftRoomList.Where(
x => Mathf.Abs(maxX - x.RoomPosition.TR.x) < 10)
.ToList();
// 연결 가능한 노드들 중 랜덤으로 선택
var index = Random.Range(0, leftRoomList.Count);
selectedLeftRoom = leftRoomList[index];
}
}
leftRoomList의 원소 갯수가 1 이하라면, leftRoom은 자식이 없는 단말 노드이므로, 별도의 정렬 과정 없이 해당 노드를 연결 대상으로 지정한다.
복도 위치 계산(노드가 좌,우에 위치할 경우)
좌측 노드에 대해 우측 노드가 어떤 형태로 배치되었는지 파악해야 한다. 이는 두 방이 겹치는 부분을 기준으로 하여 복도를 생성할 수 있기 때문이다.
- 좌측 방이 우측 방보다 작은 경우.
- 좌측 방이 우측 방보다 큰 경우.
- 좌측 방이 우측 방 상단에 위치한 경우.
- 좌측 방이 우측 방 하단에 위치한 경우.
두 방 중 하나의 크기가 더 작은 경우는, 작은 쪽을 기준으로 복도 생성 위치를 계산하면 된다.
하지만 다음과 같이 좌측 노드가 우측 노드의 상단, 혹은 하단에 걸쳐 있는 경우라면, 다음과 같이 복도 생성 위치를 계산한다.
- 좌측 노드의 우하단(BR)의 y좌표 + interval(간격) 만큼 이동한 범위를 최솟값으로 사용.
- 우측 노드의 좌상단(TL)의 y좌표 - (interval + 복도 너비) 만큼 이동한 범위를 최댓값으로 사용한다.
이 범위의 중간 지점을 복도를 생성할 Y좌표로 결정한다.
private int FindConnectPositionInLeftRight(NodePosition left, NodePosition right)
{
var leftTop = left.TR;
var leftBottom = left.BR;
var rightTop = right.TL;
var rightBottom = right.BL;
var min = new Vector2Int(-1, -1);
var max = new Vector2Int(-1, -1);
// 좌측 방이 우측 방보다 작다면
if (leftTop.y <= rightTop.y && leftBottom.y >= rightBottom.y)
{
min = leftBottom + new Vector2Int(0, _interval);
max = leftTop - new Vector2Int(0, _interval + _width);
}
// 좌측 방이 우측 방보다 크다면
else if (leftTop.y >= rightTop.y && leftBottom.y <= rightBottom.y)
{
min = rightBottom + new Vector2Int(0, _interval);
max = rightTop - new Vector2Int(0, _interval + _width);
}
// 좌측 방이 우측 방보다 상단에 위치한다면
else if (leftBottom.y >= rightBottom.y && leftBottom.y <= rightTop.y)
{
min = leftBottom + new Vector2Int(0, _interval);
max = rightTop - new Vector2Int(0, _interval + _width);
}
// 좌측 방이 우측 방보다 하단에 위치한다면
else if (leftTop.y >= rightBottom.y && leftTop.y <= rightTop.y)
{
min = rightBottom + new Vector2Int(0, _interval);
max = leftTop - new Vector2Int(0, _interval + _width);
}
// 예외처리
if (max.y - min.y < _width)
{
return -1;
}
return CalculateMidPoint(min, max).y;
}
private Vector2Int CalculateMidPoint(Vector2Int v1, Vector2Int v2)
{
return (v1 + v2) / 2;
}
만약 복도가 생성될 수 있는 범위(max.y - min.y)가 복도의 너비보다 작다면, 복도는 생성될 수 없으므로 -1을 반환한다.
우측 노드 선택
private void ConnectCorridorLeftRight(RoomNode leftRoom, RoomNode rightRoom)
{
// 좌측 노드 찾기 생략..
// 연결할 우측 노드 찾기
RoomNode selectedRightRoom = null;
var rightRoomList = NodeUtility.GetAllLeafNode(rightRoom).Where(x =>
FindConnectPositionInLeftRight(selectedLeftRoom.RoomPosition, x.RoomPosition) != -1)
.OrderBy(x => x.RoomPosition.BR.x).ToList();
}
선택된 좌측 노드에 대해 연결 가능한 노드를 우측 노드의 자식들 중에서 찾는다.
- FindConnectPositionInLeftRight() 함수에서 반환된 값이 -1이면 연결이 불가능하므로 제외.
- 연결 가능한 우측 노드들을 오름차순으로 정렬한다.
var pos = -1;
if (rightRoomList.Count <= 0)
{
// 현재 좌측 노드와 연결할 우측 노드가 존재하지 않는 상태. 파라미터로 넘어온
// 우측 노드를 기준으로 연결 가능한 좌측 노드를 다시 찾는다.
selectedRightRoom = rightRoom;
pos = FindConnectPositionInLeftRight(selectedLeftRoom.RoomPosition,
selectedRightRoom.RoomPosition);
while (leftRoomList.Count > 0 && pos == -1)
{
leftRoomList.Remove(selectedLeftRoom);
selectedLeftRoom = leftRoomList[0];
pos = FindConnectPositionInLeftRight(selectedLeftRoom.RoomPosition,
selectedRightRoom.RoomPosition);
}
}
else
{
// 연결 가능한 노드가 존재하니까, 가장 가까운 노드를 선택
selectedRightRoom = rightRoomList[0];
pos = FindConnectPositionInLeftRight(selectedLeftRoom.RoomPosition,
selectedRightRoom.RoomPosition);
}
rightRoomList의 원소 수가 0이라면, 현재 선택된 좌측 노드에 대해 연결할 수 있는 우측 노드가 없다는 의미이다.
- 따라서, 연결 가능한 좌측 노드 목록(leftRoomList)에서 파라미터로 넘어온 우측 노드와 연결 가능한 노드를 찾는다.
- 연결 가능한 노드가 존재하면, 우측 노드 목록 중 X축 값이 가장 큰(좌측 노드와 가장 가까운) 노드를 선택해 연결한다.
5. 복도 생성
Pos = (pos == -1)
? null
: new NodePosition(
new Vector2Int(selectedLeftRoom.RoomPosition.BR.x, pos),
new Vector2Int(selectedRightRoom.RoomPosition.TL.x, pos + _width));
노드가 좌,우에 위치한 경우 복도는 수평 방향으로 생성된다. 따라서 다음과 같이 복도의 좌하단(BL), 우상단(TR) 좌표가 계산된다.
- BL(Bottom Left): 좌측 방의 BR.x, 그리고 앞서 계산한 y좌표(pos)
- TR(Top Right): 우측 방의 TL.x, 그리고 pos + 복도 너비(_width)
6. 노드가 상-하에 위치한 경우
두 노드가 위아래(상, 하)로 위치한 경우, 좌우와 똑같이 진행하지만 y축 기준이 아닌 x축 좌표를 기준으로 판단한다.
- 연결할 상,하 노드를 선택할 때는, 각 노드의 자식 방을 x축 기준으로 정렬한 후 연결 가능한 방을 탐색한다.
■ 전체 코드 및 결과
using System.Linq;
using UnityEngine;
public enum ERelative
{
Right,
Left,
Top,
Bottom
}
public class CorridorNode : BSP_Node
{
private readonly int _width;
private readonly int _interval;
public CorridorNode(RoomNode node1, RoomNode node2, int width, int distanceFromWall) : base(null)
{
_width = width;
_interval = distanceFromWall;
GenerateCorridor(node1, node2);
}
private void GenerateCorridor(RoomNode node1, RoomNode node2)
{
var relative = GetRelativePosition(node1, node2);
switch (relative)
{
case ERelative.Right:
ConnectCorridorLeftRight(node1, node2);
break;
case ERelative.Left:
ConnectCorridorLeftRight(node2, node1);
break;
case ERelative.Top:
ConnectCorridorBottomTop(node1, node2);
break;
case ERelative.Bottom:
ConnectCorridorBottomTop(node2, node1);
break;
default:
return;
}
}
private void ConnectCorridorLeftRight(RoomNode leftRoom, RoomNode rightRoom)
{
// 연결할 좌측 노드 찾기
RoomNode selectedLeftRoom = null;
var leftRoomList = NodeUtility.GetAllLeafNode(leftRoom)
.OrderByDescending(x => x.RoomPosition.TR.x).ToList();
if (leftRoomList.Count <= 1)
{
selectedLeftRoom = leftRoom;
}
else
{
var maxX = leftRoomList[0].RoomPosition.TR.x;
leftRoomList = leftRoomList.Where(
x => Mathf.Abs(maxX - x.RoomPosition.TR.x) < 10)
.ToList();
var index = Random.Range(0, leftRoomList.Count);
selectedLeftRoom = leftRoomList[index];
}
// 연결할 우측 노드 찾기
RoomNode selectedRightRoom = null;
var rightRoomList = NodeUtility.GetAllLeafNode(rightRoom).Where(x =>
FindConnectPositionInLeftRight(selectedLeftRoom.RoomPosition, x.RoomPosition) != -1)
.OrderBy(x => x.RoomPosition.BR.x).ToList();
var pos = -1;
if (rightRoomList.Count <= 0)
{
// 현재 좌측 노드와 연결할 우측 노드가 존재하지 않는 상태. 파라미터로 넘어온
// 우측 노드를 기준으로 연결 가능한 좌측 노드를 다시 찾는다.
selectedRightRoom = rightRoom;
pos = FindConnectPositionInLeftRight(selectedLeftRoom.RoomPosition,
selectedRightRoom.RoomPosition);
while (leftRoomList.Count > 0 && pos == -1)
{
leftRoomList.Remove(selectedLeftRoom);
selectedLeftRoom = leftRoomList[0];
pos = FindConnectPositionInLeftRight(selectedLeftRoom.RoomPosition,
selectedRightRoom.RoomPosition);
}
}
else
{
// 연결 가능한 노드가 존재하니까, 가장 가까운 노드를 선택
selectedRightRoom = rightRoomList[0];
pos = FindConnectPositionInLeftRight(selectedLeftRoom.RoomPosition,
selectedRightRoom.RoomPosition);
}
Pos = (pos == -1)
? null
: new NodePosition(
new Vector2Int(selectedLeftRoom.RoomPosition.BR.x, pos),
new Vector2Int(selectedRightRoom.RoomPosition.TL.x, pos + _width));
}
private void ConnectCorridorBottomTop(RoomNode bottom, RoomNode top)
{
RoomNode selectedBottomRoom = null;
var bottomList = NodeUtility.GetAllLeafNode(bottom)
.OrderByDescending(x => x.RoomPosition.TL.y).ToList();
if (bottomList.Count <= 1)
{
selectedBottomRoom = bottom;
}
else
{
var maxY = bottomList[0].RoomPosition.TL.y;
bottomList = bottomList.Where(x => Mathf.Abs(maxY - x.RoomPosition.TL.y) < 10).ToList();
selectedBottomRoom = bottomList[Random.Range(0, bottomList.Count)];
}
RoomNode selectedTopRoom = null;
var topList = NodeUtility.GetAllLeafNode(top)
.Where(x =>
FindConnectPositionInBottomTop(selectedBottomRoom.RoomPosition, x.RoomPosition) !=
-1).OrderBy(x => x.RoomPosition.BR.y).ToList();
var pos = -1;
if (topList.Count <= 0)
{
selectedTopRoom = top;
pos = FindConnectPositionInBottomTop(selectedBottomRoom.RoomPosition,
selectedTopRoom.RoomPosition);
while (pos != -1 && bottomList.Count > 0)
{
bottomList.Remove(selectedBottomRoom);
selectedBottomRoom = bottomList[0];
pos = FindConnectPositionInBottomTop(selectedBottomRoom.RoomPosition,
selectedTopRoom.RoomPosition);
}
}
else
{
selectedTopRoom = topList[0];
pos = FindConnectPositionInBottomTop(selectedBottomRoom.RoomPosition,
selectedTopRoom.RoomPosition);
}
Pos = (pos == -1)
? null
: new NodePosition(
new Vector2Int(pos, selectedBottomRoom.RoomPosition.TL.y),
new Vector2Int(pos + _width, selectedTopRoom.RoomPosition.BR.y)
);
}
private int FindConnectPositionInLeftRight(NodePosition left, NodePosition right)
{
var leftTop = left.TR;
var leftBottom = left.BR;
var rightTop = right.TL;
var rightBottom = right.BL;
var min = new Vector2Int(-1, -1);
var max = new Vector2Int(-1, -1);
// 좌측 방이 우측 방보다 작다면
if (leftTop.y <= rightTop.y && leftBottom.y >= rightBottom.y)
{
min = leftBottom + new Vector2Int(0, _interval);
max = leftTop - new Vector2Int(0, _interval + _width);
}
// 좌측 방이 우측 방보다 크다면
else if (leftTop.y >= rightTop.y && leftBottom.y <= rightBottom.y)
{
min = rightBottom + new Vector2Int(0, _interval);
max = rightTop - new Vector2Int(0, _interval + _width);
}
// 좌측 방이 우측 방보다 상단에 위치한다면
else if (leftBottom.y >= rightBottom.y && leftBottom.y <= rightTop.y)
{
min = leftBottom + new Vector2Int(0, _interval);
max = rightTop - new Vector2Int(0, _interval + _width);
}
// 좌측 방이 우측 방보다 하단에 위치한다면
else if (leftTop.y >= rightBottom.y && leftTop.y <= rightTop.y)
{
min = rightBottom + new Vector2Int(0, _interval);
max = leftTop - new Vector2Int(0, _interval + _width);
}
// 예외처리
if (max.y - min.y < _width)
{
return -1;
}
return CalculateMidPoint(min, max).y;
}
private int FindConnectPositionInBottomTop(NodePosition bottom, NodePosition top)
{
var bottomLeft = bottom.TL.x;
var bottomRight = bottom.TR.x;
var topLeft = top.BL.x;
var topRight = top.BR.x;
var min = new Vector2Int(-1, -1);
var max = new Vector2Int(-1, -1);
// 하단에 위치한 방이 더 작다면
if (topLeft <= bottomLeft && topRight >= bottomRight)
{
min = new Vector2Int(bottomLeft + _interval, 0);
max = new Vector2Int(bottomRight - (_interval + _width), 0);
}
// 상단에 위치한 방이 더 작다면
else if (topLeft >= bottomLeft && topRight <= bottomRight)
{
min = new Vector2Int(topLeft + _interval, 0);
max = new Vector2Int(topRight - (_interval + _width), 0);
}
// 상단 방이 우측에 위치할 때
else if (bottomLeft <= topLeft && topLeft <= bottomRight)
{
min = new Vector2Int(topLeft + _interval, 0);
max = new Vector2Int(bottomRight - (_interval + _width), 0);
}
// 상단 방이 좌측에 위치할 때
else if(bottomLeft <= topRight && topRight <= bottomRight)
{
min = new Vector2Int(bottomLeft + _interval, 0);
max = new Vector2Int(topRight - (_interval + _width), 0);
}
// 예외처리
if (max.x - min.x < _width)
{
return -1;
}
return CalculateMidPoint(min, max).x;
}
private Vector2Int CalculateMidPoint(Vector2Int v1, Vector2Int v2)
{
return (v1 + v2) / 2;
}
private ERelative GetRelativePosition(RoomNode node1, RoomNode node2)
{
var mid1 = (node1.Pos.TR + node1.Pos.BL) / 2;
var mid2 = (node2.Pos.TR + node2.Pos.BL) / 2;
var angle = Mathf.Atan2(mid2.y - mid1.y, mid2.x - mid1.x);
angle *= Mathf.Rad2Deg;
if (45f < angle && angle < 135f) return ERelative.Top;
if (-135f < angle && angle < -45f) return ERelative.Bottom;
if ((0 <= angle && angle < 45) || (-45 < angle && angle <= 0)) return ERelative.Right;
return ERelative.Left;
}
}
[CorridorNode.cs]
using System.Collections.Generic;
using System.Linq;
public class CorridorGenerator
{
private List<RoomNode> _roomNodes;
private DungeonData _data;
public List<CorridorNode> GenerateCorridor(List<RoomNode> rooms, DungeonData data)
{
var sortedRoom = rooms.OrderByDescending(x => x.Index).ToList();
var corridorList = new List<CorridorNode>();
foreach (var node in sortedRoom)
{
if (node.ChildNode.Count == 0)
{
continue;
}
var corridor = new CorridorNode((RoomNode)node.ChildNode[0], (RoomNode)node.ChildNode[1],
data.CorridorWidth, data.DistanceFromWall);
corridorList.Add(corridor);
}
return corridorList;
}
}
[CorridorGenerator.cs]
생각보다 복도 연결 구현이 복잡해서 오래 걸렸다. 다음에는 던전을 둘러싸는 벽을 생성해 절차적 던전 생성을 마무리하자.
728x90
'Unity,C# > 절차적생성(PCG)' 카테고리의 다른 글
| [C#, Unity, 절차적 생성] 절차적 던전 생성 - 5. 벽 생성 (0) | 2025.05.22 |
|---|---|
| [C#, Unity, 절차적 생성] 절차적 던전 생성 - 3. BSP 알고리즘 개선 (1) | 2025.05.12 |
| [C#, Unity, 절차적 생성] 절차적 던전 생성 - 2. 방 생성 (0) | 2025.05.12 |
| [C#, Unity, 절차적 생성] 절차적 던전 생성 - 1. Binary Space Partitioning (1) | 2025.05.07 |
| [C#, Unity, 절차적 생성] 절차적 지형 생성 - 3.터레인 생성 (0) | 2025.04.28 |