랜덤 던전을 만들고, 그중 가장 먼 방에 보스를 배치하는 법

개발 노트 — 절차적 던전 생성

왜 “그냥 랜덤”으로는 부족한가

던전 크롤러류 게임을 만들 때 흔히 마주치는 요구사항이 있습니다. “입장할 때마다 방 구조가 바뀌어야 하고, 보스방은 입구에서 최대한 멀리 있어야 한다”는 조건입니다.

개인 프로젝트로 3주간 개발한 2D 슈팅 액션 게임 Enter the Room에서도 이 요구사항이 있었습니다. 던전 입장 시 8개의 일반 방과 1개의 보스방이 랜덤으로 생성되고, 보스방은 항상 시작 방에서 가장 멀리 위치한 방에 배치됩니다.

이 글에서는 이 조건을 만족하는 던전을 어떻게 절차적으로 생성하는지, 두 단계로 나눠 정리합니다.

방들을 랜덤하게 연결해서 던전 구조 만들기
그중 시작 방에서 가장 먼 방을 찾아 보스방으로 지정하기

1단계: 랜덤으로 방 연결하기

던전을 하나의 그래프로 생각하면 접근이 쉬워집니다. 방 하나하나가 노드(node)이고, 방과 방 사이의 통로가 간선(edge)입니다.

가장 단순한 방식은 랜덤 워크(Random Walk) 기반 생성입니다. 시작 방에서 출발해서, 매번 상하좌우 중 아직 방이 없는 방향을 무작위로 골라 새 방을 만들고 이동하는 방식입니다.

public class DungeonGenerator
{
    private Dictionary<Vector2Int, Room> _rooms = new Dictionary<Vector2Int, Room>();
    private Vector2Int[] _directions =
    {
        Vector2Int.up, Vector2Int.down, Vector2Int.left, Vector2Int.right
    };

    public void Generate(int roomCount)
    {
        Vector2Int current = Vector2Int.zero;
        _rooms[current] = new Room(current, isStart: true);

        int created = 1;
        while (created < roomCount)
        {
            // 아직 방이 없는 인접 좌표들 중 무작위로 선택
            var candidates = GetEmptyNeighbors(current);

            if (candidates.Count == 0)
            {
                // 막다른 길이면, 이미 만든 방 중 하나로 되돌아가서 계속 진행
                current = _rooms.Keys.ElementAt(Random.Range(0, _rooms.Count));
                continue;
            }

            Vector2Int next = candidates[Random.Range(0, candidates.Count)];
            _rooms[next] = new Room(next, isStart: false);
            ConnectRooms(current, next);

            current = next;
            created++;
        }
    }

    private List<Vector2Int> GetEmptyNeighbors(Vector2Int pos)
    {
        return _directions
            .Select(dir => pos + dir)
            .Where(neighbor => !_rooms.ContainsKey(neighbor))
            .ToList();
    }
}

이 방식으로 생성하면, 방 개수(roomCount)만 정해주면 매번 다른 구조의 던전이 만들어집니다. 막다른 길에 도달했을 때 이미 만든 방으로 되돌아가서 계속 뻗어나가게 하는 처리가 핵심입니다 — 이게 없으면 방 개수를 다 채우지 못하고 생성이 멈출 수 있습니다.

2단계: 시작 방에서 가장 먼 방 찾기 — BFS

방 구조가 만들어졌다면, 이제 그중에서 시작 방으로부터 가장 멀리 떨어진 방을 찾아야 합니다. 여기서 “멀다”는 건 물리적 거리가 아니라 **몇 개의 방을 거쳐야 도달하는지(경로상 거리)**를 의미합니다. 이런 문제는 그래프 탐색 알고리즘인 **BFS(너비 우선 탐색)**로 깔끔하게 풀 수 있습니다.

BFS는 시작점에서 가까운 노드부터 순서대로 탐색하기 때문에, 마지막에 탐색되는 노드가 자연스럽게 “가장 먼 노드”가 됩니다.

public Room FindFarthestRoom(Vector2Int start)
{
    Queue<Vector2Int> queue = new Queue<Vector2Int>();
    Dictionary<Vector2Int, int> distances = new Dictionary<Vector2Int, int>();

    queue.Enqueue(start);
    distances[start] = 0;

    Vector2Int farthest = start;

    while (queue.Count > 0)
    {
        Vector2Int current = queue.Dequeue();

        foreach (var neighbor in GetConnectedNeighbors(current))
        {
            if (distances.ContainsKey(neighbor)) continue;

            distances[neighbor] = distances[current] + 1;
            queue.Enqueue(neighbor);

            // 마지막에 방문되는 노드가 가장 먼 노드
            farthest = neighbor;
        }
    }

    return _rooms[farthest];
}

이 함수로 찾은 방을 보스방으로 지정하면 됩니다.

Room bossRoom = FindFarthestRoom(startPosition);
bossRoom.SetAsBossRoom();

왜 DFS가 아니라 BFS인가

그래프 탐색에는 BFS 외에 **DFS(깊이 우선 탐색)**도 있습니다. 둘 다 “가장 먼 노드를 찾는다”는 목적에 어느 정도 쓸 수 있지만, 던전 생성에는 BFS가 더 안전합니다.

BFS: 가까운 노드부터 차례로 탐색하므로, 탐색이 끝났을 때 마지막 방문 노드가 경로 거리 기준으로 확실히 가장 먼 노드임이 보장됩니다.
DFS: 한쪽 방향으로 깊게 파고드는 방식이라, 우연히 먼저 탐색한 가지가 길기만 할 뿐 실제 최단 경로 기준 최장 거리가 아닐 수 있습니다.

거리를 정확히 비교해야 하는 문제이기 때문에, “레벨(단계)별로 순서대로 탐색”하는 BFS의 성질이 이 문제에 정확히 들어맞습니다.

실제 적용 결과

Enter the Room에서는 이 방식으로 던전에 입장할 때마다 8개 방 + 보스방 1개가 매번 다른 구조로 생성되고, 보스방은 항상 입구에서 최소 거리가 가장 먼 위치에 배치됩니다. 플레이어가 어느 방향으로 진행하든 결국 던전을 어느 정도 탐색해야 보스방에 도달하게 되므로, 매번 비슷한 루트로 보스방에 직행하는 상황을 방지할 수 있습니다.

정리

던전을 그래프로 모델링하면 방 배치 문제를 익숙한 자료구조 문제로 바꿀 수 있습니다.
랜덤 워크로 방을 연결하면 매번 다른 구조의 던전을 쉽게 만들 수 있습니다 (막다른 길 처리를 꼭 챙겨야 합니다).
BFS로 시작 노드부터 탐색하면, 마지막에 방문되는 노드가 곧 “경로상 가장 먼 노드”가 되어 보스방 위치로 쓸 수 있습니다.

절차적 던전 생성에서 “특정 조건을 만족하는 방을 어디에 배치할지” 고민하고 계시다면, 그래프 탐색 알고리즘을 활용하는 게 생각보다 간단하고 확실한 해법이 될 수 있습니다.