← Blog

ENGINEERING NOTE

[Unreal Engine] 절차적 던전 생성 1

포켓몬 불가사의 던전에 쓰이는 절차적 던전 생성 알고리즘의 실제 구현 내용

Unreal Engine

들어가며

[[Algorithm] PMD Explorers of sky map generation 번역본](https://velog.io/@imeamangryang/Algorithm-PMD-Explorers-of-sky-map-generation-번역본)

예전 글에서 포켓몬 불가사의 던전에 쓰이는 절차적 던전 생성 알고리즘에 대해 포스팅한 적이 있다. 하지만 너무 가독성이 떨어져서 이번 기회에 Unreal Engine에서 구현하면서 조금 더 깔끔하고 직관적으로 볼 수 있도록 정리하려고 한다.

이번 글에서는 셀을 나누고 방과 복도를 만드는 기본 생성 과정을 살펴본 뒤, Floor Layout에 따라 던전의 전체 형태를 바꾸는 방법을 정리한다.



1. 구조체 정의

FFloorProperties

FFloorProperties는 한 층의 생성 규칙을 담는다. 그 안의 FRoomFlags는 방에 적용할 추가 옵션을 묶은 구조체다.

cpp
struct FRoomFlags
{
    // 보조 지형 생성 허용 여부
    bool f_secondary_terrain_generation = false;

    // 방 외곽에 불규칙한 변형을 적용할지 여부
    bool f_room_imperfections = false;
};

struct FFloorProperties
{
    // 전체 방·복도 배치 방식
    FloorLayout layout = FloorLayout::LAYOUT_SMALL;

    // 방 생성의 추가 옵션
    FRoomFlags room_flags;
    
    // 막다른 복도를 허용할지 여부
    bool allow_dead_ends = false;

    // 방으로 선택할 셀 수에 영향을 주는 값
    int32 room_density = 7;

    // 셀 사이의 연결을 시도하는 반복 횟수
    int32 floor_connectivity = 24;

    // 기본 연결 이후 추가로 생성할 복도 수
    int32 num_extra_hallways = 0;
};

layout의 타입인 FloorLayout은 Large, Small, Line, Cross 등 전체 배치 방식을 구분하는 열거형이다. 구체적인 사용 예시는 기본 생성 과정 후 변형 과정에서 쓰인다.

FGridCell

FGridCell은 실제 바닥 타일보다 한 단계 큰 배치 단위다. 셀 하나에는 방 또는 한 칸짜리 복도 연결점인 Anchor가 들어갈 수 있고, 생성 대상에서 제외될 수도 있다.

cpp
struct FGridCell
{
    // 생성 대상에서 제외하는 셀인지 여부
    bool is_invalid = false;

    // true면 방, false면 Anchor로 사용할 유효 셀
    bool is_room = false;

    // 복도 연결 처리에 참여했는지 기록하는 상태
    bool is_connected = false;

    // 이웃 셀과의 연결 계획
    bool connected_to_top = false;
    bool connected_to_bottom = false;
    bool connected_to_left = false;
    bool connected_to_right = false;

    // 실제 복도를 만들 때 소비하는 작업용 연결 플래그
    bool should_connect_to_top = false;
    bool should_connect_to_bottom = false;
    bool should_connect_to_left = false;
    bool should_connect_to_right = false;

    // 방 병합에 사용하는 상태
    bool has_been_merged = false;
    bool is_merged = false;
    
    // 셀 안에 생성한 방·Anchor의 범위.
    int32 start_x = 0;
    int32 start_y = 0;
    int32 end_x = 0;
    int32 end_y = 0;
};

주의할 점은 start_x부터 end_x까지의 범위가 셀 구획 전체가 아니라, 그 안에 만든 방이나 Anchor의 범위라는 것이다. 셀 구획의 경계는 뒤에서 계산할 columnBoundaries와 rowBoundaries 배열에 따로 보관한다.

예를 들어 전체 맵을 4 × 3 셀로 나누면 배치 구역은 12개다. 그중 일부만 방으로 선택하고, 각 방은 선택된 셀 안쪽에 여백을 두고 만든다. 따라서 셀 전체가 바닥이 되는 것은 아니다.

FTile

셀에서 배치와 연결을 결정했다면, 실제 벽과 바닥을 기록하는 한 칸과 그 결과를 기록하는 대상은 FTile이다. 지형 종류는 FTile 내부의 FTerrainFlags에 보관한다.

cpp
struct FTerrainFlags
{
    // 처음에는 벽으로 시작한다.
    TerrainType terrain_type = TerrainType::TERRAIN_WALL;

    // 맵 외곽처럼 통과할 수 없는 벽인지 여부
    bool f_impassable_wall = false;
};

struct FTile
{
    FTerrainFlags terrain_flags;

    // 소속된 방의 번호(0부터 시작). 0xFE(254)는 생성 중인 Anchor, 0xFF(255)는 방에 속하지 않는 타일을 의미한다.
    int32 room_index = 0xFF;
};

실제 맵은 dungeonData.list_tiles[x][y]에 저장한다. 방이나 복도를 만들 때 해당 타일의 terrain_type을 TERRAIN_WALL에서 TERRAIN_NORMAL로 바꾼다. 방 타일에는 같은 room_index를 기록해 어느 방에 속하는지 구분한다.

Anchor는 생성 중에 0xFE를 사용하고, 이후 연결점을 확정하는 과정에서 0xFF로 정리한다. 이 값은 방 번호와 복도 연결점을 구분하기 위한 표시다.



2. 기본 생성 흐름

코드 예시는 기본 지형 생성 과정을 쉽게 따라갈 수 있도록 일부 보정과 추가 옵션 처리를 생략하고, 핵심 흐름을 중심으로 정리했다.

먼저 일반적인 층을 생성하는 GenerateBaseFloor()를 보자. 아래는 방과 복도를 만드는 부분까지 발췌한 코드다.

cpp
void UDungeonGenerator::GenerateBaseFloor(
    int32 columnCount,
    int32 rowCount,
    const FFloorProperties& floorProperties)
{
    // 셀 경계와 기본 상태를 준비한다.
    TArray<int32> columnBoundaries;
    TArray<int32> rowBoundaries;
    BuildCellBoundaries(columnCount, rowCount, columnBoundaries, rowBoundaries);

    grid_cell_start_x = columnBoundaries;
    grid_cell_start_y = rowBoundaries;

    TArray<TArray<FGridCell>> cells = CreateCellGrid(columnCount, rowCount);

    // 방과 Anchor를 배치한다.
    ChooseRoomCells(cells, columnCount, rowCount, floorProperties.room_density);

    CarveRoomsAndAnchors(cells, columnCount, rowCount, columnBoundaries, rowBoundaries, floorProperties.room_flags);

    const int32 cursorColumn = dungeonRand.RandInt(columnCount);
    const int32 cursorRow = dungeonRand.RandInt(rowCount);

    // 연결 계획을 기록한 뒤 실제 복도를 생성한다.
    PlanCellConnections(cells, columnCount, rowCount, cursorColumn, cursorRow, floorProperties);
    CarveCellConnections(cells, columnCount, rowCount, columnBoundaries, rowBoundaries, false);

    RepairUnconnectedCells(cells, columnCount, rowCount, columnBoundaries, rowBoundaries);

    // 이후의 특수 방·장식 처리는 이번 글에서는 생략한다.
}

함수의 흐름은 크게 셀을 나누고 → 방과 Anchor를 배치하고 → 연결 계획을 세우고 → 복도를 뚫고 → 연결되지 않은 셀을 정리하는 과정이다.

columnCount·rowCount는 가로·세로 셀 개수이고, columnBoundaries·rowBoundaries는 각 셀의 경계 좌표 배열이다.

BuildCellBoundaries

BuildCellBoundaries()에서는 맵을 Grid Cell로 나누어 가로와 세로의 셀 경계를 계산한다. 가로·세로 셀 개수와 결과를 담을 배열을 받아, 배열에 경계 좌표를 기록한다.

cpp
void UDungeonGenerator::BuildCellBoundaries(
    int32 columnCount,
    int32 rowCount,
    TArray<int32>& columnBoundaries,
    TArray<int32>& rowBoundaries) const
{
    columnBoundaries.Empty();
    rowBoundaries.Empty();

    // 전체 타일 맵의 크기로 셀 간격을 구한다.
    const int32 cellWidth = FLOOR_MAX_X / columnCount;
    const int32 cellHeight = FLOOR_MAX_Y / rowCount;

    // 셀 수보다 경계 좌표를 하나 더 저장한다.
    for (int32 column = 0; column <= columnCount; ++column)
    {
        columnBoundaries.Add(column * cellWidth);
    }

    for (int32 row = 0; row <= rowCount; ++row)
    {
        rowBoundaries.Add(row * cellHeight);
    }
}

FLOOR_MAX_X, FLOOR_MAX_Y는 맵 크기 상수다. 이 프로젝트의 기본 맵 크기는 56 × 32를 사용했다.

예시처럼 4 × 3 셀로 나누면

  • 가로 경계는 0, 14, 28, 42, 56
  • 세로 경계는 0, 10, 20, 30

이 된다.

나눗셈 결과를 내림한 간격으로 누적하기 때문에 셀 영역이 맵 전체를 채우지는 않을 수 있다. 그림에서도 아래쪽 두 행은 셀 영역 바깥으로 남는다.

반복문의 <=는 마지막 경계까지 저장하기 위한 것이다. 셀이 4개라면 경계 좌표는 5개가 필요하다.

CreateCellGrid

CreateCellGrid()는 방과 연결 정보를 저장할 셀 배열을 초기화한다.

cpp
TArray<TArray<FGridCell>> UDungeonGenerator::CreateCellGrid(
    int32 columnCount,
    int32 rowCount)
{
    TArray<TArray<FGridCell>> cells;
    cells.SetNum(15);

    // 셀 정보를 저장할 15 × 15 배열을 준비한다.
    for (int32 column = 0; column < 15; ++column)
    {
        cells[column].SetNum(15);

        for (int32 row = 0; row < 15; ++row)
        {
            cells[column][row] = FGridCell();
        }
    }

    // 이번 층에서 사용할 범위의 셀 상태를 설정한다.
    for (int32 column = 0; column < columnCount; ++column)
    {
        for (int32 row = 0; row < rowCount; ++row)
        {
            // Small은 오른쪽 절반을 생성 대상에서 제외한다.
            if (statusData.floor_size == FloorSize::FLOOR_SIZE_SMALL &&
                column >= FMath::FloorToInt(
                    static_cast<float>(columnCount) / 2.0f))
            {
                cells[column][row].is_invalid = true;
            }
            // Medium은 오른쪽 약 1/4을 생성 대상에서 제외한다.
            else if (statusData.floor_size == FloorSize::FLOOR_SIZE_MEDIUM &&
                column >= FMath::FloorToInt(
                    (3.0f * static_cast<float>(columnCount)) / 4.0f))
            {
                cells[column][row].is_invalid = true;
            }
            else
            {
                cells[column][row].is_invalid = false;
            }

            // 우선 방 후보로 설정한다.
            cells[column][row].is_room = true;
        }
    }

    return cells;
}

배열은 cells[column][row], 즉 가로 좌표 → 세로 좌표 순서로 접근한다. 저장 공간은 예시에서는 15 × 15로 준비하지만, 생성에 사용하는 범위는 전달받은 columnCount × rowCount다.

statusData.floor_size는 FFloorProperties에서 FloorLayout의 선택한 레이아웃에 따라 정해지는 층 크기 구분으로, 셀 초기화와 복도 생성에서 사용할 영역을 제한하는 기준이 된다.

층 크기에 따라 오른쪽 셀 일부를 생성 대상에서 제외한다.

층 크기사용할 가로 범위4열인 경우
Large전체4열 사용
Small왼쪽 절반2열 사용
Medium왼쪽 약 3/43열 사용

is_invalid = true인 셀은 이후 방과 Anchor를 배치할 때 건너뛴다.

이 단계에서는 셀의 상태만 준비하며, 실제 바닥 타일은 만들지 않는다. 다음 ChooseRoomCells()에서 각 유효 셀을 방으로 사용할지 Anchor로 사용할지 결정한다.

ChooseRoomCells

셀 배열이 준비됐다면, ChooseRoomCells은 각 셀을 방으로 사용할지 Anchor로 사용할지 결정한다.

방법은 간단하다. 방으로 선택할 개수만큼 true를 준비하고, 나머지는 false로 채운다. 이 표시들의 위치를 무작위로 섞은 다음, 유효한 셀에 순서대로 적용한다.

순서처리
1. 방 후보 수 결정입력값에 따라 방으로 선택할 후보 수를 정한다.
2. 선택 표시 준비후보 수만큼 true, 나머지는 false로 채운다.
3. 위치 섞기두 위치의 값을 교환하는 작업을 64번 반복한다.
4. 셀에 적용유효한 셀에 표시를 하나씩 배정한다. true는 방, false는 Anchor다.

예를 들어 셀이 12개이고 방 후보 수가 7개라면, 방 표시 7개와 Anchor 표시 5개의 배치를 섞는 과정이라고 생각하면 된다. 단, 실제 적용 과정에는 셀 제외와 배치 조건이 추가로 반영된다.

cpp
void UDungeonGenerator::ChooseRoomCells(
    TArray<TArray<FGridCell>>& cells,
    int32 columnCount,
    int32 rowCount,
    int32 requestedRoomCount)
{
    const int32 cellCount = columnCount * rowCount;

    // 1. 방 후보 수만큼 true, 나머지는 false로 준비한다.
    TArray<bool> roomChoices;
    roomChoices.Init(false, cellCount);

    for (int32 index = 0;
         index < requestedRoomCount && index < cellCount;
         ++index)
    {
        roomChoices[index] = true;
    }

    // 2. 두 위치의 값을 교환하며 배치를 섞는다.
    for (int32 attempt = 0; attempt < 64; ++attempt)
    {
        const int32 firstIndex = dungeonRand.RandInt(cellCount);
        const int32 secondIndex = dungeonRand.RandInt(cellCount);

        const bool previousChoice = roomChoices[firstIndex];
        roomChoices[firstIndex] = roomChoices[secondIndex];
        roomChoices[secondIndex] = previousChoice;
    }

    // 3. 유효한 셀에 방 또는 Anchor 역할을 배정한다.
    int32 choiceIndex = 0;
    statusData.num_rooms = 0;

    for (int32 column = 0; column < columnCount; ++column)
    {
        for (int32 row = 0; row < rowCount; ++row)
        {
            FGridCell& cell = cells[column][row];

            if (cell.is_invalid)
            {
                continue;
            }

            cell.is_room = roomChoices[choiceIndex];
            choiceIndex++;

            if (cell.is_room)
            {
                statusData.num_rooms++;
            }
        }
    }
}

그림의 R은 방으로 선택된 셀, A는 Anchor로 선택된 셀이다. 모든 셀이 유효한 12개 셀에 방 표시 7개를 배정하면, 방 후보 7개와 Anchor 후보 5개가 만들어진다.

아직 실제 바닥은 만들지 않는다. 다음 단계에서 방으로 선택된 셀에는 직사각형 바닥을, Anchor로 선택된 셀에는 한 칸짜리 연결점을 만든다.

방으로 선택되지 않은 유효 셀에는 1 × 1 크기의 Anchor를 만든다. Anchor는 이후 복도의 시작점이나 연결점으로 사용한다.

CarveRoomsAndAnchors

CarveRoomsAndAnchors()는 앞에서 정한 셀의 역할을 실제 타일로 옮긴다.

방으로 선택된 셀은 전체를 바닥으로 만들지는 않는다. 셀 안에 여백을 남기고, 그보다 작은 직사각형 방을 배치한다.

방을 만드는 순서는 다음과 같다.

  • 1. 방의 크기를 정한다.

셀 안에 들어갈 수 있는 범위를 계산하고, 그 안에서 방의 가로·세로 길이를 무작위로 선택한다.

  • 2. 방의 모양을 다듬는다.

조건에 따라 길이를 홀수로 조정하고, 지나치게 가늘고 긴 방이 되지 않도록 가로·세로 비율을 제한한다.

  • 3. 방을 놓을 위치를 정한다.

정해진 크기의 방이 셀 안에 들어가도록 시작 좌표를 선택한다. 시작 위치는 셀의 왼쪽과 위쪽 경계에서 최소 두 칸을 띄운다.

  • 4. 해당 영역을 바닥으로 바꾼다.

시작 좌표부터 방의 크기만큼 타일을 바닥으로 바꾸고, 같은 방의 타일에는 동일한 room_index를 기록한다.

예를 들어 14 × 10 크기의 셀 안에 7 × 5 크기의 방을 만들고, 남은 공간 안에서 방의 위치를 바꾸는 방식이다. 따라서 같은 셀 배치를 사용해도 방의 크기와 위치는 매번 달라질 수 있다.

cpp
void UDungeonGenerator::CarveRoomsAndAnchors(
    TArray<TArray<FGridCell>>& cells,
    int32 columnCount,
    int32 rowCount,
    const TArray<int32>& columnBoundaries,
    const TArray<int32>& rowBoundaries,
    const FRoomFlags& roomFlags)
{
    int32 roomId = 0;

    for (int32 row = 0; row < rowCount; ++row)
    {
        for (int32 column = 0; column < columnCount; ++column)
        {
            FGridCell& cell = cells[column][row];

            if (cell.is_invalid)
            {
                continue;
            }

            // 현재 셀의 왼쪽·위쪽 좌표와 가로·세로 길이
            const int32 cellStartX = columnBoundaries[column];
            const int32 cellStartY = rowBoundaries[row];

            const int32 cellWidth = columnBoundaries[column + 1] - cellStartX;
            const int32 cellHeight = rowBoundaries[row + 1] - cellStartY;

            // 셀 경계에 여백을 남기기 위한 크기 계산 기준
            const int32 availableWidth = cellWidth - 4;
            const int32 availableHeight = cellHeight - 3;

            if (!cell.is_room)
            {
                // Anchor 위치 선택에 사용할 추가 여백
                const int32 leftInset = column == 0 ? 1 : 2;
                const int32 rightInset = column == columnCount - 1 ? 2 : 4;
                const int32 topInset = row == 0 ? 1 : 2;
                const int32 bottomInset = row == rowCount - 1 ? 2 : 4;

                const int32 anchorX = dungeonRand.RandRange(
                    cellStartX + 2 + leftInset,
                    cellStartX + 2 + availableWidth - rightInset);

                const int32 anchorY = dungeonRand.RandRange(
                    cellStartY + 2 + topInset,
                    cellStartY + 2 + availableHeight - bottomInset);

                // Anchor는 한 칸짜리 바닥으로 기록한다.
                cell.start_x = anchorX;
                cell.start_y = anchorY;
                cell.end_x = anchorX + 1;
                cell.end_y = anchorY + 1;

                FTile& anchorTile = dungeonData.list_tiles[anchorX][anchorY];
                anchorTile.terrain_flags.terrain_type = TerrainType::TERRAIN_NORMAL;
                
                // Anchor는 계산한 위치 한 칸을 일반 바닥으로 만들고, 방과 구분하기 위해 `room_index`에 `0xFE`를 기록한다.
                anchorTile.room_index = 0xFE;

                continue;
            }

            // 1. 셀 안에 들어갈 방의 가로·세로 크기를 선택한다.
            int32 roomWidth = dungeonRand.RandRange(5, availableWidth);
            int32 roomHeight = dungeonRand.RandRange(4, availableHeight);

            // 2-1. 범위가 허용하면 크기를 홀수로 조정한다.
            // 정수에 | 1을 적용하면 짝수는 1 증가하고 홀수는 유지된다.
            if ((roomWidth | 1) < availableWidth)
            {
                roomWidth |= 1;
            }

            if ((roomHeight | 1) < availableHeight)
            {
                roomHeight |= 1;
            }

            // 2-2. 어느 한쪽이 다른 쪽의 1.5배를 넘으면 줄인다.
            if (roomWidth > FMath::FloorToInt(roomHeight * 1.5f))
            {
                roomWidth = FMath::FloorToInt(roomHeight * 1.5f);
            }

            if (roomHeight > FMath::FloorToInt(roomWidth * 1.5f))
            {
                roomHeight = FMath::FloorToInt(roomWidth * 1.5f);
            }

            // 3. 남은 공간 안에서 방의 시작 위치를 선택한다.
            // 셀의 왼쪽·위쪽 경계에서 기본적으로 두 칸을 띄운다.
            const int32 roomStartX =
                cellStartX + 2 +
                dungeonRand.RandInt(availableWidth - roomWidth);

            const int32 roomStartY =
                cellStartY + 2 +
                dungeonRand.RandInt(availableHeight - roomHeight);

            const int32 roomEndX = roomStartX + roomWidth;
            const int32 roomEndY = roomStartY + roomHeight;

            // 이후 복도 생성에서 사용할 방의 범위를 저장한다.
            cell.start_x = roomStartX;
            cell.start_y = roomStartY;
            cell.end_x = roomEndX;
            cell.end_y = roomEndY;

            // 4. 방 영역을 바닥으로 바꾸고 같은 방 번호를 기록한다.
            // 끝 좌표는 포함하지 않는다.
            for (int32 tileX = roomStartX; tileX < roomEndX; ++tileX)
            {
                for (int32 tileY = roomStartY; tileY < roomEndY; ++tileY)
                {
                    FTile& tile = dungeonData.list_tiles[tileX][tileY];
                    tile.terrain_flags.terrain_type = TerrainType::TERRAIN_NORMAL;
                    tile.room_index = roomId;
                }
            }

            roomId++;
        }
    }
}

흰 영역은 생성된 바닥이고, 주황색 점은 Anchor 위치를 강조한 것이다. 방과 Anchor를 모두 합쳐 이 시점에는 227칸의 바닥이 열려 있다.

이렇게 셀 경계와 실제 방의 경계를 분리하면, 전체 배치는 유지하면서 각 방의 크기와 위치에 변화를 줄 수 있다.

PlanCellConnections

방을 만들었다면, 이제 어느 셀끼리 이어질지 정한다. PlanCellConnections()는 시작 셀에서 무작위 이동을 반복하며 지나간 셀 사이에 연결 플래그를 기록한다.

cpp
void UDungeonGenerator::PlanCellConnections(
    TArray<TArray<FGridCell>>& cells,
    int32 columnCount,
    int32 rowCount,
    int32 cursorColumn,
    int32 cursorRow,
    const FFloorProperties& floorProperties)
{
    // 무작위 연결 방향을 선택한다.
    // 현재 셀을 다음 방향의 셀과 연결한다:
    // 0: 동
    // 1: 북
    // 2: 서
    // 3: 남
    CardinalDirection direction = static_cast<CardinalDirection>(dungeonRand.RandInt(4));

    // floor_connectivity 횟수만큼 현재 셀을 다른 Grid Cell과 연결 시도
    for (int32 step = 0; step < floorProperties.floor_connectivity; ++step)
    {
        // 절반의 분기에서는 방향을 새로 뽑고, 나머지에서는 유지한다.

        const int32 directionChoice = dungeonRand.RandInt(8);
        const CardinalDirection candidateDirection = static_cast<CardinalDirection>(dungeonRand.RandInt(4));

        if (directionChoice < 4)
        {
            // 새로운 방향으로 섞는다.
            direction = candidateDirection;
        }

        // 방향이 경계 바깥으로 향하지 않도록 보정
        // 그 경우 반시계 방향으로 회전
        bool ok = false;
        while (!ok)
        {
            switch (direction)
            {
            case CardinalDirection::DIR_RIGHT:
                ok = cursorColumn < columnCount - 1;
                break;
            case CardinalDirection::DIR_UP:
                ok = cursorRow > 0;
                break;
            case CardinalDirection::DIR_LEFT:
                ok = cursorColumn > 0;
                break;
            case CardinalDirection::DIR_DOWN:
                ok = cursorRow < rowCount - 1;
                break;
            }

            if (!ok)
            {
                // 반시계 방향 회전
                direction = static_cast<CardinalDirection>((static_cast<int32>(direction) + 1) % 4);
            }
        }

        // 연결을 설정하고, 그 방향으로 이동한다.
        if (direction == CardinalDirection::DIR_RIGHT && !cells[cursorColumn + 1][cursorRow].is_invalid)
        {
            cells[cursorColumn][cursorRow].connected_to_right = true;
            cells[cursorColumn + 1][cursorRow].connected_to_left = true;
            cursorColumn++;
        }
        else if (direction == CardinalDirection::DIR_UP && !cells[cursorColumn][cursorRow - 1].is_invalid)
        {
            cells[cursorColumn][cursorRow].connected_to_top = true;
            cells[cursorColumn][cursorRow - 1].connected_to_bottom = true;
            cursorRow--;
        }
        else if (direction == CardinalDirection::DIR_LEFT && !cells[cursorColumn - 1][cursorRow].is_invalid)
        {
            cells[cursorColumn][cursorRow].connected_to_left = true;
            cells[cursorColumn - 1][cursorRow].connected_to_right = true;
            cursorColumn--;
        }
        else if (direction == CardinalDirection::DIR_DOWN && !cells[cursorColumn][cursorRow + 1].is_invalid)
        {
            cells[cursorColumn][cursorRow].connected_to_bottom = true;
            cells[cursorColumn][cursorRow + 1].connected_to_top = true;
            cursorRow++;
        }
    }
}

점선은 셀 사이의 연결 계획이다. 아직 벽을 바닥으로 바꾸지는 않으며, 실제 복도는 다음 단계에서 만든다.

연결은 시작 셀에서 이웃 셀로 이동하며 정한다. 이전 방향으로 계속 가거나 무작위로 방향을 다시 선택하고, 맵 밖을 향하면 반시계 방향으로 돌린다. 이동할 셀이 생성 대상에서 제외되어 있다면 그 회차는 건너뛴다. 이동할 때는 양쪽 셀에 연결을 함께 기록한다. 예를 들어 오른쪽으로 이동했다면, 현재 셀의 오른쪽 연결과 이웃 셀의 왼쪽 연결을 켠다.

floor_connectivity는 이 과정을 반복하는 횟수다. 이미 지나간 연결을 다시 지날 수도 있으므로 연결 개수와는 다르다. 그림에서는 24회 시도한 결과, 서로 다른 셀 연결 11개가 만들어졌다.

CarveCellConnections

이제 CarveCellConnections()가 연결 플래그를 읽고, 방 또는 Anchor의 좌표를 골라 CarveCorridor()를 호출한다. 아래는 위쪽 셀과 연결하는 분기의 일부다.

cpp
void UDungeonGenerator::CarveCellConnections(
    TArray<TArray<FGridCell>>& cells,
    int32 columnCount,
    int32 rowCount,
    const TArray<int32>& columnBoundaries,
    const TArray<int32>& rowBoundaries,
    bool disableRoomMerging)
{
    // ... 셀 순회, 연결 플래그 복사와 검증, 출구 좌표 선택은 생략한다.
    // cellColumn·cellRow는 현재 셀, corridorStartX는 미리 고른 출구 x 좌표다.

    if (cells[cellColumn][cellRow].should_connect_to_top)
    {
        // 위 셀과 연결
        if (!cells[cellColumn][cellRow - 1].is_invalid)
        {
            if (!cells[cellColumn][cellRow - 1].is_room)
            {
                // 앵커면 중앙 x 사용
                corridorEndX = cells[cellColumn][cellRow - 1].start_x;
            }
            else
            {
                // 방이면 내부 x 선택
                corridorEndX = dungeonRand.RandRange(
                    cells[cellColumn][cellRow - 1].start_x + 1,
                    cells[cellColumn][cellRow - 1].end_x - 1);
            }

            CarveCorridor(
                corridorStartX,
                cells[cellColumn][cellRow].start_y,
                corridorEndX,
                cells[cellColumn][cellRow - 1].end_y - 1,
                true,
                columnBoundaries[cellColumn],
                rowBoundaries[cellRow]);
        }

        cells[cellColumn][cellRow].should_connect_to_top = false;
        cells[cellColumn][cellRow - 1].should_connect_to_bottom = false;
        cells[cellColumn][cellRow].is_connected = true;
        cells[cellColumn][cellRow - 1].is_connected = true;
    }

    // ... 나머지 방향 연결과 조건부 방 병합은 생략한다.
}

앞에서 기록한 connected_to_*를 작업용 should_connect_to_*에 복사하고, 복도를 만들면서 양쪽 셀의 작업용 플래그를 해제해 같은 연결을 중복 처리하지 않는다.

초록색은 앞 단계보다 새로 열린 바닥이다. CarveCorridor()는 셀 경계의 꺾이는 좌표를 기준으로 최대 세 구간을 이어 복도를 만드는 함수다.

가로 방향 연결은 시작점에서 경계까지 가로 → 목표 높이까지 세로 → 끝점까지 가로, 세로 방향 연결은 이 순서에서 가로와 세로를 바꾼다. 좌표가 일치하는 구간은 길이가 0이 될 수 있다. 진행 중 기존 바닥을 만나면 연결된 것으로 보고 일찍 종료할 수도 있다.

RepairUnconnectedCells

RepairUnconnectedCells()는 앞 단계에서 연결 처리에 참여하지 못한 셀을 순회한다. invalid 셀, 이미 연결된 셀, 다른 방에 병합된 셀은 건너뛴다.

남아 있는 셀처리
연결되지 않은 방위 → 아래 → 왼쪽 → 오른쪽 순서로 조건에 맞는 연결된 이웃을 찾고 복도를 추가한다.
연결되지 않은 Anchor한 칸을 다시 벽으로 채운다.
보정 후에도 연결되지 않은 방방 영역을 벽으로 채우고 방 번호를 지운다.

아래는 위쪽 셀로 복도를 추가하는 부분이다.

cpp
void UDungeonGenerator::RepairUnconnectedCells(
    TArray<TArray<FGridCell>>& cells,
    int32 columnCount,
    int32 rowCount,
    const TArray<int32>& columnBoundaries,
    const TArray<int32>& rowBoundaries)
{
    // ... 연결되지 않은 방과 위쪽의 연결된 셀을 찾는 부분은 생략한다.
    // roomExitX·roomExitY와 corridorStartX는 앞에서 계산한 출구·입구 좌표다.

    CarveCorridor(
        roomExitX,
        cells[cellColumn][cellRow].start_y,
        corridorStartX,
        cells[cellColumn][cellRow - 1].end_y - 1,
        true,
        columnBoundaries[cellColumn],
        rowBoundaries[cellRow]);

    cells[cellColumn][cellRow].is_connected = true;
    cells[cellColumn][cellRow].connected_to_top = true;
    cells[cellColumn][cellRow - 1].connected_to_bottom = true;

    // ... 나머지 방향의 추가 연결과 고립된 셀 제거는 생략한다.
}

이번 예시에서는 주황색으로 표시한 7칸이 추가되고, 고립된 Anchor 한 칸이 제거되어 바닥이 341칸이 되었다. 주변 연결에 참여하지 못한 Anchor나 끝까지 연결되지 않은 방은 제거하는 처리도 있다.

다만 이 함수는 셀의 is_connected 상태를 바탕으로 보정하는 단계다. is_connected는 복도 연결 처리에 참여했다는 표시다. 서로 떨어진 두 묶음에 속한 셀도 각각 true일 수 있으므로, 이 값만으로 전체 맵이 하나로 이어졌다고 판단할 수는 없다.

여기까지가 방과 복도로 이루어진 기본 지형을 만드는 뼈대다. 이후 생성 함수 바깥에서 경계 행 정리와 연결점 확정같은 공통 처리가 이어진다.

Summary

그림으로 다시 전체적인 흐름을 보면 다음과 같다.



Floor Layout에 따라 모양 바꾸기

기본 뼈대를 만들었다면, 셀의 배치와 역할을 바꾸는 것만으로도 여러 형태의 던전을 만들 수 있다.

GenerateFloor()는 floorProperties.layout에 따라 생성 함수를 선택한다. Large·Small·Medium은 GenerateBaseFloor()를 공유하고, Line·Cross·Beetle 등은 전용 함수에서 배치와 연결 규칙을 지정한다.

Line

GenerateLineFloor()에서는 셀을 5 × 1로 고정한다.

cpp
void UDungeonGenerator::GenerateLineFloor(
    const FFloorProperties& floorProperties)
{
    const int32 columnCount = 5;
    const int32 rowCount = 1;

    TArray<int32> columnBoundaries = {0, 11, 22, 33, 44, 56};
    TArray<int32> rowBoundaries = {4, 15};

    grid_cell_start_x = columnBoundaries;
    grid_cell_start_y = rowBoundaries;

    TArray<TArray<FGridCell>> cells = CreateCellGrid(columnCount, rowCount);

    ChooseRoomCells(cells, columnCount, rowCount, floorProperties.room_density);
    CarveRoomsAndAnchors(
        cells,
        columnCount,
        rowCount,
        columnBoundaries,
        rowBoundaries,
        floorProperties.room_flags);

    const int32 cursorColumn = dungeonRand.RandInt(columnCount);
    const int32 cursorRow = dungeonRand.RandInt(rowCount);

    PlanCellConnections(cells, columnCount, rowCount, cursorColumn, cursorRow, floorProperties);
    CarveCellConnections(cells, columnCount, rowCount, columnBoundaries, rowBoundaries, true);

    RepairUnconnectedCells(cells, columnCount, rowCount, columnBoundaries, rowBoundaries);

    ...
}

이후에는 일반 생성과 같이 방을 선택하고, 방과 Anchor를 만든 뒤 연결한다. 셀의 세로 개수가 1이므로 전체 구조가 가로 방향으로 길게 이어진다. 방의 높이와 복도 위치에는 여전히 변화가 생긴다.

모든 셀이 항상 방인 것은 아니다. 이 예시는 방 밀도 설정에 따라 다섯 셀이 모두 방으로 선택된 경우다.

Cross

GenerateCrossFloor()에서는 3 × 3 셀 중 네 모서리를 invalid로 만들고, 중앙과 상하좌우의 다섯 방을 연결한다.

cpp
void UDungeonGenerator::GenerateCrossFloor(
    const FFloorProperties& floorProperties)
{
    const int32 columnCount = 3;
    const int32 rowCount = 3;

    TArray<int32> columnBoundaries = {11, 22, 33, 44};
    TArray<int32> rowBoundaries = {2, 11, 20, 30};

    grid_cell_start_x = columnBoundaries;
    grid_cell_start_y = rowBoundaries;

    TArray<TArray<FGridCell>> cells = CreateCellGrid(columnCount, rowCount);

    // 모든 셀을 방으로 설정
    for (int32 cellColumn = 0; cellColumn < columnCount; cellColumn++)
    {
        for (int32 cellRow = 0; cellRow < rowCount; cellRow++)
        {
            cells[cellColumn][cellRow].is_room = true;
        }
    }

    // 모서리 invalid
    cells[0][0].is_invalid = true;
    cells[0][rowCount - 1].is_invalid = true;
    cells[columnCount - 1][0].is_invalid = true;
    cells[columnCount - 1][rowCount - 1].is_invalid = true;

    CarveRoomsAndAnchors(
        cells,
        columnCount,
        rowCount,
        columnBoundaries,
        rowBoundaries,
        floorProperties.room_flags);

    cells[1][0].connected_to_bottom = true;
    cells[1][1].connected_to_top = true;
    cells[1][1].connected_to_bottom = true;
    cells[1][2].connected_to_top = true;
    cells[0][1].connected_to_right = true;
    cells[1][1].connected_to_left = true;
    cells[1][1].connected_to_right = true;
    cells[2][1].connected_to_left = true;

    CarveCellConnections(cells, columnCount, rowCount, columnBoundaries, rowBoundaries, true);

    RepairUnconnectedCells(cells, columnCount, rowCount, columnBoundaries, rowBoundaries);

    ...
}

일반 생성처럼 연결 방향을 무작위로 고르는 대신, 중앙 셀의 상하좌우 연결을 직접 지정한다. 방의 위치와 크기는 달라질 수 있어도, 중앙을 통해 네 방향으로 이어지는 전체 형태는 유지된다.

Beetle

GenerateBeetleFloor()는 3 × 3 셀에 방을 만들고 같은 행의 방끼리 연결한다. 이후 중앙 열을 세로로 병합한다.

cpp
void UDungeonGenerator::GenerateBeetleFloor(
    const FFloorProperties& floorProperties)
{
    const int32 columnCount = 3;
    const int32 rowCount = 3;

    TArray<int32> columnBoundaries = {5, 15, 35, 50};
    TArray<int32> rowBoundaries = {2, 11, 20, 30};

    grid_cell_start_x = columnBoundaries;
    grid_cell_start_y = rowBoundaries;

    TArray<TArray<FGridCell>> cells = CreateCellGrid(columnCount, rowCount);

    // 모든 셀을 방으로 설정
    for (int32 cellColumn = 0; cellColumn < columnCount; cellColumn++)
    {
        for (int32 cellRow = 0; cellRow < rowCount; cellRow++)
        {
            cells[cellColumn][cellRow].is_room = true;
        }
    }

    CarveRoomsAndAnchors(
        cells,
        columnCount,
        rowCount,
        columnBoundaries,
        rowBoundaries,
        floorProperties.room_flags);

    // 같은 행의 방들을 연결
    for (int32 cellRow = 0; cellRow < rowCount; cellRow++)
    {
        cells[0][cellRow].connected_to_right = true;
        cells[1][cellRow].connected_to_left = true;
        cells[1][cellRow].connected_to_right = true;
        cells[2][cellRow].connected_to_left = true;
    }

    CarveCellConnections(cells, columnCount, rowCount, columnBoundaries, rowBoundaries, true);

    // 중앙 열을 하나의 큰 방으로 병합
    MergeRoomsInColumn(1, 0, 1, cells);
    MergeRoomsInColumn(1, 0, 2, cells);

    RepairUnconnectedCells(cells, columnCount, rowCount, columnBoundaries, rowBoundaries);

    // 이후의 특수 방·추가 복도·장식 처리는 생략한다.
}

첫 호출은 중앙 열의 0번과 1번 행을 합치고, 두 번째 호출은 합쳐진 방에 2번 행까지 포함시킨다. 그 결과 중앙의 긴 방 하나와 양쪽의 방 여섯 개가 남는다.

앞에서 비교용으로 무작위 병합을 꺼두었어도, 이 두 번의 명시적인 병합은 실행된다. Beetle의 형태 자체를 만드는 규칙이기 때문이다.

Outer Ring

GenerateOuterRingFloor()는 6 × 4 셀을 사용한다. 바깥 테두리의 셀은 방으로 사용하지 않고, 안쪽 4 × 2 셀을 방으로 둔다.

cpp
void UDungeonGenerator::GenerateOuterRingFloor(
    const FFloorProperties& floorProperties)
{
    const int32 columnCount = 6;
    const int32 rowCount = 4;

    TArray<int32> columnBoundaries = {0, 5, 16, 28, 39, 51, 56};
    TArray<int32> rowBoundaries = {2, 7, 16, 25, 30};

    grid_cell_start_x = columnBoundaries;
    grid_cell_start_y = rowBoundaries;

    TArray<TArray<FGridCell>> cells = CreateCellGrid(columnCount, rowCount);

    // 바깥 고리를 방이 아니도록 표시
    for (int32 cellColumn = 0; cellColumn < columnCount; cellColumn++)
    {
        cells[cellColumn][0].is_room = false;
        cells[cellColumn][rowCount - 1].is_room = false;
    }

    for (int32 cellRow = 0; cellRow < rowCount; cellRow++)
    {
        cells[0][cellRow].is_room = false;
        cells[columnCount - 1][cellRow].is_room = false;
    }

    // 안쪽은 방으로 표시
    for (int32 cellColumn = 1; cellColumn < columnCount - 1; cellColumn++)
    {
        for (int32 cellRow = 1; cellRow < rowCount - 1; cellRow++)
        {
            cells[cellColumn][cellRow].is_room = true;
        }
    }

    ...
}

바깥 Anchor들을 잇는 고리 연결을 먼저 지정하고, 추가 연결을 정해 안쪽 방과 이어준다. 그래서 방 바깥을 둘러싸는 복도가 만들어진다.

이 레이아웃은 좌표 배열도 직접 지정한다. 바깥쪽 셀은 좁게, 안쪽 방이 들어갈 셀은 넓게 배치한다. 방과 Anchor를 타일로 만드는 부분도 전용 함수 내부에 구현되어 있다.

Crossroads

GenerateCrossroadsFloor()는 5 × 4 셀에서 바깥쪽을 방으로, 안쪽을 Anchor로 사용하고 네 모서리는 제외한다. 이후 안쪽을 가로지르는 세로·가로 연결을 지정한다.

cpp
void UDungeonGenerator::GenerateCrossroadsFloor(
    const FFloorProperties& floorProperties)
{
    const int32 columnCount = 5;
    const int32 rowCount = 4;

    TArray<int32> columnBoundaries = {0, 11, 22, 33, 44, 56};
    TArray<int32> rowBoundaries = {1, 9, 16, 23, 31};

    grid_cell_start_x = columnBoundaries;
    grid_cell_start_y = rowBoundaries;

    TArray<TArray<FGridCell>> cells = CreateCellGrid(columnCount, rowCount);

    // 바깥 고리를 방으로 표시
    for (int32 cellColumn = 0; cellColumn < columnCount; cellColumn++)
    {
        cells[cellColumn][0].is_room = true;
        cells[cellColumn][rowCount - 1].is_room = true;
    }

    for (int32 cellRow = 0; cellRow < rowCount; cellRow++)
    {
        cells[0][cellRow].is_room = true;
        cells[columnCount - 1][cellRow].is_room = true;
    }

    // 안쪽은 복도로 표시
    for (int32 cellColumn = 1; cellColumn < columnCount - 1; cellColumn++)
    {
        for (int32 cellRow = 1; cellRow < rowCount - 1; cellRow++)
        {
            cells[cellColumn][cellRow].is_room = false;
        }
    }

    // 코너는 invalid
    cells[0][0].is_invalid = true;
    cells[0][rowCount - 1].is_invalid = true;
    cells[columnCount - 1][0].is_invalid = true;
    cells[columnCount - 1][rowCount - 1].is_invalid = true;

    // ... 각 셀의 방·Anchor 타일을 생성하는 부분은 생략한다.

    for (int32 cellColumn = 1; cellColumn < columnCount - 1; cellColumn++)
    {
        for (int32 cellRow = 0; cellRow < rowCount - 1; cellRow++)
        {
            cells[cellColumn][cellRow].connected_to_bottom = true;
            cells[cellColumn][cellRow + 1].connected_to_top = true;
        }
    }

    for (int32 cellColumn = 0; cellColumn < columnCount - 1; cellColumn++)
    {
        for (int32 cellRow = 1; cellRow < rowCount - 1; cellRow++)
        {
            cells[cellColumn][cellRow].connected_to_right = true;
            cells[cellColumn + 1][cellRow].connected_to_left = true;
        }
    }

    CarveCellConnections(cells, columnCount, rowCount, columnBoundaries, rowBoundaries, true);

    RepairUnconnectedCells(cells, columnCount, rowCount, columnBoundaries, rowBoundaries);

    // 이후의 특수 방·장식 처리는 생략한다.
}

가운데 세 열은 세로로 이어지고, 가운데 두 행은 가로로 연결된다. 내부의 여러 교차점을 통해 바깥 방으로 이어지는 사다리 같은 모양이 된다.

Outer Ring과 비교하면 역할의 차이가 보인다. Outer Ring은 바깥에 복도 고리를 두고 안쪽에 방을 배치하지만, Crossroads는 안쪽에 연결점을 두고 바깥에 방을 배치한다. 이 함수도 방과 Anchor를 만드는 타일 대입을 내부에서 직접 처리한다.

Outer Rooms

GenerateOuterRoomsFloor()에서는 모든 셀을 방으로 설정한 뒤, 테두리를 제외한 내부 셀을 invalid로 바꾼다.

cpp
void UDungeonGenerator::GenerateOuterRoomsFloor(
    int32 columnCount,
    int32 rowCount,
    const FFloorProperties& floorProperties)
{
    TArray<int32> columnBoundaries;
    TArray<int32> rowBoundaries;
    BuildCellBoundaries(columnCount, rowCount, columnBoundaries, rowBoundaries);

    grid_cell_start_x = columnBoundaries;
    grid_cell_start_y = rowBoundaries;

    TArray<TArray<FGridCell>> cells = CreateCellGrid(columnCount, rowCount);

    // 모든 셀을 방으로 설정
    for (int32 cellColumn = 0; cellColumn < columnCount; cellColumn++)
    {
        for (int32 cellRow = 0; cellRow < rowCount; cellRow++)
        {
            cells[cellColumn][cellRow].is_room = true;
        }
    }

    // 내부 셀은 invalid
    for (int32 cellColumn = 1; cellColumn < columnCount - 1; cellColumn++)
    {
        for (int32 cellRow = 1; cellRow < rowCount - 1; cellRow++)
        {
            cells[cellColumn][cellRow].is_invalid = true;
        }
    }

    CarveRoomsAndAnchors(
        cells,
        columnCount,
        rowCount,
        columnBoundaries,
        rowBoundaries,
        floorProperties.room_flags);

    // ... 외곽 연결 플래그를 설정하는 분기는 생략한다.

    CarveCellConnections(cells, columnCount, rowCount, columnBoundaries, rowBoundaries, false);
    RepairUnconnectedCells(cells, columnCount, rowCount, columnBoundaries, rowBoundaries);

    // 이후의 특수 방·장식 처리는 생략한다.
}

Outer Ring이 바깥쪽을 복도로 둘렀다면, Outer Rooms는 바깥쪽에 방을 배치한다. 가운데가 비어 있고 방들이 테두리를 따라 이어지는 형태가 된다.

그림은 4 × 3 셀을 사용한 예시다. 외곽 방을 실제로 연결하는 분기에는 셀 수와 생성 설정이 함께 사용되므로, 내부 셀을 제외하는 것만으로 외곽 연결까지 완성되는 것은 아니다.


이렇게 실제 포켓몬 불가사의 던전에 쓰이는 던전 유형을 생성하는 규칙에 대해 알아보았다. 기본 생성 흐름에 셀의 역할과 연결 규칙을 바꾸면, 같은 방·복도 생성 방식을 사용하면서도 다양한 형태의 던전을 만들 수 있다.

다음 글에서는 이렇게 만든 기본 지형에 Secondary Terrain을 적용하는 과정을 써보려고 한다.