[UE C++] Recursive Backtracking을 활용한 수집형 미로 생성 시스템 및 동적 좌표 최적화

프로젝트의 레벨 디자인에 무작위성을 부여하고 플레이어의 탐험 경험을 극대화하기 위해 절차적 콘텐츠 생성(PCG) 기반의 미로 생성 시스템을 구축했습니다. 단순히 미로를 구현하는 것을 넘어, '아이템 수집'이라는 게임 메카닉에 최적화된 알고리즘을 선정하고 이를 UE5 환경에 맞춰 최적화한 과정을 정리합니다.

1. 알고리즘 벤치마킹 및 기획적 선택

미로 생성 알고리즘은 각각 고유한 수학적 특성을 가지며, 이는 레벨의 난이도와 플레이어의 동선에 직결됩니다.

• Prim's & Kruskal's Algorithm: 무작위성이 강해 중심에서 사방으로 뻗어 나가는 조밀한 구조를 가집니다. 분기점이 많아 복잡해 보이지만 동선이 짧아 탐험의 깊이가 얕아질 우려가 있습니다.
• Recursive Backtracking (DFS 기반): 현재 위치에서 가능한 깊은 지점까지 파고든 후, 막히면 스택을 통해 역추적합니다.
  • 기술적 특징: 알고리즘 특성상 긴 복도와 적은 분기점을 생성합니다.
  • 전략적 채택 이유: 본 프로젝트는 출구를 찾는 것이 아닌 맵 전체를 돌며 아이템을 수집하는 것이 목적입니다. 이 알고리즘은 신장 트리(Spanning Tree) 구조를 형성하여 모든 구역의 도달 가능성을 수학적으로 보장합니다. 또한, DFS 특유의 깊은 탐색 경로는 플레이어가 맵의 구석구석을 이동하게 유도하여 '수집'이라는 목적에 부합하는 이동 동선을 강제하기에 최적의 선택이었습니다.

---

2. 효율적인 데이터 구조 설계

메모리 효율과 직렬화를 고려하여 USTRUCT로 셀 데이터를 정의했습니다.

USTRUCT(BlueprintType)
struct FMazeCell
{
    GENERATED_BODY()

    int32 X = 0;
    int32 Y = 0;
    bool bVisited = false;       // DFS의 방문 상태 기록
    bool bHasRightWall = true;   // 0번(우측) 방향 벽 유무
    bool bHasBottomWall = true;  // 2번(하단) 방향 벽 유무
};

여기서 핵심은 모든 면의 벽을 데이터로 관리하는 대신 우측(Right)과 하단(Bottom) 벽만 관리하는 방식입니다. 이는 인접 셀 간의 중복 데이터를 제거하여 메모리 사용량을 절반으로 줄이고, 이후 액터 스폰 과정에서의 연산 오버헤드를 줄이는 최적화 기법입니다.

---

3. 알고리즘 구현 분석

이론적으로는 Recursive Backtracking 모델을 사용하되, 구현은 Non-Recursive(비재귀) 방식을 택했습니다.

[1] 명시적 스택(Explicit Stack)의 도입 이유

일반적인 재귀 호출은 시스템 스택 메모리를 사용합니다. 미로의 크기가 커질수록 재귀 깊이가 깊어져 Stack Overflow의 위험이 있습니다. 이를 방지하기 위해 TArray를 이용한 명시적 스택 자료구조를 구축, 힙 메모리를 활용함으로써 대규모 미로 생성 시에도 시스템 안정성을 확보했습니다.

[2] 방향성 벡터를 통한 확장성 확보

// 방향 배열 (우, 좌, 하, 상)
int32 DX[] = { 1, -1, 0, 0 };
int32 DY[] = { 0, 0, 1, -1 };

while (Stack.Num() > 0)
{
    FMazeCell* Current = Stack.Last();
    TArray<int32> UnvisitedNeighbors;

    // 인접 셀 필터링 및 경계 유효성 검사
    for (int32 i = 0; i < 4; i++)
    {
        int32 NextX = Current->X + DX[i];
        int32 NextY = Current->Y + DY[i];

        if (NextX >= 0 && NextX < MapWidth && NextY >= 0 && NextY < MapHeight)
        {
            if (!Grid[NextX][NextY].bVisited) { UnvisitedNeighbors.Add(i); }
        }
    }
    // ... 무작위 방향 선택 및 경로 확장 ...
}

 

---

4. UE5 프레임워크 통합 및 한계점 분석

알고리즘을 월드 좌표계에 투영하는 과정에서 발생한 문제와 해결 과정을 기술합니다.

[1] 하드코딩된 오프셋의 문제점 분석

초기 구현 시 StartOffset을 고정값(-3000, -3000)으로 설정하여, 스테이지별 가변적인 맵 크기(6000 → 5000 → 4000)에 유연하게 대응하지 못하고 벽 액터가 영역 밖으로 스폰되는 현상이 발생했습니다.

[2] 동적 좌표 정렬 (Spatial Translation)

맵의 중심(0, 0)을 기준으로 미로를 정확히 안착시키기 위해, 스테이지의 실제 크기를 기반으로 한 동적 오프셋 계산 로직을 도입했습니다.

// 맵 크기에 따른 동적 오프셋 계산 (절반 크기만큼 마이너스)
float HalfWidth = (MapWidth * TileSize) * 0.5f;
float HalfHeight = (MapHeight * TileSize) * 0.5f;
FVector StartOffset = FVector(-HalfWidth, -HalfHeight, 0.0f);

이 수식을 통해 맵의 해상도가 달라져도 미로가 항상 지형 내부에 정확히 위치하도록 수정했습니다. 또한, DrawDebugLine을 활용하여 알고리즘의 탐색 경로와 실제 액터 스폰 위치 간의 정합성을 시각적으로 검증했습니다

 

문제 발생 전 / 문제 해결

---

5. 결과

재귀적 역추적 알고리즘의 특성을 활용하여 수집형 게임에 최적화된 동선을 확보했습니다. 이번 과정에서 데이터 구조의 경량화와 런타임 안정성을 위한 명시적 스택 설계, 그리고 하드코딩 리터럴의 위험성을 깊이 체감했습니다.

 

다음 포스팅에서는 생성된 미로 데이터를 활용하여 지형의 고저차에 관계없이 아이템을 배치하는 LineTrace 기반 동적 스폰 시스템을 분석해 보겠습니다.