[UE C++] LineTrace와 Shuffle 알고리즘을 활용한 중복 없는 아이템 스폰 시스템

미로 생성 알고리즘이 '길'을 만들었다면, 이제 그 위에 아이템을 배치할 차례입니다. 하지만 단순히 랜덤 좌표에 물체를 던져넣는 방식은 아이템 간의 겹침(Overlapping)과 지형 고저차로 인한 부자연스러운 배치 문제를 야기합니다. 본 포스팅에서는 이를 해결하기 위해 사용한 기술적 해법을 분석합니다.

1. 기술적 도전 과제

아이템 스폰 시스템을 구축하며 해결해야 했던 핵심 과제는 두 가지였습니다.

1. 시각적 안정성: 지형의 실제 $Z$축 높이를 감지하여 아이템이 공중에 뜨거나 바닥에 묻히지 않게 할 것.
2. 논리적 무결성: 한 번 아이템이 배치된 좌표에는 다른 아이템이 생성되지 않도록 중복을 완벽히 차단할 것.

---

2. 해결 전략 1: LineTrace 기반 지면 밀착 시스템

아이템의 스폰 위치를 확정하기 전, 월드에 직접 물리적인 질의(Query)를 수행하는 LineTrace(Raycasting) 기법을 도입했습니다.

• 동작 원리: $X, Y$ 좌표의 상공($Z=500$)에서 바닥($Z=-500$) 방향으로 ECC_Visibility 채널 광선을 발사합니다.
• 보정 수식: $Location_{final} = ImpactPoint_{Z} + Offset_{Z}$
  • 충돌 지점의 $Z$값에 아이템 절반 높이만큼 오프셋을 더해 지면에 완벽히 안착시킵니다.
• 결과: 이를 통해 평지가 아닌 지형에서도 아이템의 시각적 안정성을 확보했습니다.

AActor* ASpawnVolume::SpawnItem(TSubclassOf<AActor> ItemClass, const FVector& InLocation)
{
    if (!ItemClass) return nullptr;

    // Line Trace를 통한 바닥 정밀 감지
    FVector Start = FVector(InLocation.X, InLocation.Y, 500.0f);
    FVector End = FVector(InLocation.X, InLocation.Y, -500.0f);

    FHitResult HitResult;
    FCollisionQueryParams Params;
    Params.AddIgnoredActor(this);

    // 월드에서 MazeGenerator를 다시 찾지 않고, 필요한 경우만 무시 설정
    AActor* MazeGenActor = UGameplayStatics::GetActorOfClass(GetWorld(), AMazeGenerator::StaticClass());
    if (MazeGenActor) Params.AddIgnoredActor(MazeGenActor);

    FVector FinalSpawnLocation = InLocation;

    if (GetWorld()->LineTraceSingleByChannel(HitResult, Start, End, ECC_Visibility, Params))
    {
        // ImpactPoint(충돌 지점)를 사용하여 정확한 바닥 안착
        FinalSpawnLocation = HitResult.ImpactPoint;
        FinalSpawnLocation.Z += 100.0f; // 일정 높이만큼 스폰 위치 지정
    }

    return GetWorld()->SpawnActor<AActor>(ItemClass, FinalSpawnLocation, FRotator::ZeroRotator);
}

거울맵: LineTrace 디버깅 이미지

---

3. 해결 전략 2: RandomShuffle 알고리즘을 통한 중복 스폰 원천 차단

가장 까다로웠던 문제는 아이템 겹침이었습니다. 매번 랜덤하게 하나를 뽑는 방식은 아이템 개수가 늘어날수록 이미 사용된 좌표를 다시 뽑을 확률이 높아져 비효율적인 중복 체크 루프가 발생합니다.

저는 이를 배치 처리와 RandomShuffle 알고리즘으로 해결했습니다.

3.1. 기존 방식: 무작위 추출 (Random Pick with Check)

매번 랜덤하게 좌표를 뽑고 중복 여부를 검사하는 방식입니다.

graph TD
    Start([시작: N개의 아이템 스폰 요청]) --> Loop{반복문 시작}
    Loop --> Random[전체 좌표 중<br> 임의의 좌표 P 선택]
    Random --> Check{P에 아이템이 <br/>이미 존재하는가?}

    %% 중복 발생 시 루프 (빨간색 강조)
    Check -- "Yes (중복 발생)" --> Random

    %% 중복 없을 시 스폰
    Check -- "No (빈 공간)" --> Spawn[아이템 스폰 및 <br/>좌표 점유 표시]
    Spawn --> Count{N개 모두 <br/>스폰했는가?}

    Count -- "아니오" --> Random
    Count -- "예" --> End([종료])

    %% 스타일링
    style Random fill:#e1f5fe,stroke:#01579b,stroke-width:2px

3.2. 개선 방식: 셔플 후 배치 처리 (Shuffle & Batch)

전체 데이터를 먼저 섞은 뒤 순차적으로 사용하는 방식입니다.

graph TD
    Start([시작: N개의 아이템 스폰 요청]) --> Collect[미로의 모든 유효 좌표 수집 - Pool 생성]
    Collect --> Shuffle[전체 리스트 무작위 셔플 - Algo::RandomShuffle]

    Shuffle --> LoopStart{반복문 시작: i = 0 to N-1}
    LoopStart --> Pick[리스트의 i번째 인덱스 좌표 추출]

    %% 중복 검사 없이 즉시 진행 (녹색 강조)
    Pick --> Trace[LineTrace로 지면 높이 보정]
    Trace --> Spawn[아이템 스폰]

    Spawn --> Condition{N번 반복 완료?}
    Condition -- "아니오" --> LoopStart
    Condition -- "예" --> End([종료])

    %% 스타일링
    style Shuffle fill:#e1f5fe,stroke:#01579b,stroke-width:2px
    style Pick fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px
    style Spawn fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px

// SpawnVolume.cpp 내 핵심 로직
void ASpawnVolume::SpawnMultipleItems(int32 Count)
{
    // 1. MazeGenerator로부터 유효한 모든 경로 좌표 수집
    TArray<FVector> Locations = MazeGen->GetMazePathLocations();

    // 2. [핵심] Fisher-Yates 기반 셔플을 통해 위치 목록을 무작위로 섞음
    Algo::RandomShuffle(Locations); 

    // 3. 섞인 목록의 앞부분부터 순서대로 추출하여 스폰
    int32 ActualCount = FMath::Min(Count, Locations.Num());
    for (int32 i = 0; i < ActualCount; i++)
    {
        SpawnItem(ItemClass, Locations[i]); // 중복이 절대 발생하지 않음
    }
}

기술적 이점:

• 효율성: $O(n)$의 시간 복잡도로 한 번에 모든 배치를 끝냅니다.
• 확정성: "이미 뽑은 곳인가?"를 검사하는 무한 루프 위험 없이, 수학적으로 중복이 불가능한 구조를 설계했습니다.

---

4. 시스템 아키텍처: 단일 책임 원칙 (SRP)

유지보수성을 높이기 위해 세 가지 클래스의 역할을 명확히 분리했습니다.

클래스	역할	기술적 특징
MazeGenerator	Data Provider	미로 알고리즘을 통한 유효 좌표 데이터 생성 및 관리
SpawnVolume	Action Manager	확률 기반 아이템 선택, 셔플링, LineTrace 기반 물리 배치 수행
GameState	Coordinator	웨이브 시작 시 SpawnVolume에 배치 스폰을 요청하고 결과 집계

이러한 구조적 분리 덕분에 GameState는 복잡한 스폰 로직을 몰라도 되며, 단순히 "아이템 20개를 깔아줘"라는 메시지만 전달하고 생성된 리스트를 받아 관리하는 Batch Interface를 구축할 수 있었습니다.

sequenceDiagram
    participant GS as HighScoreGameState
    participant SV as SpawnVolume
    participant MG as MazeGenerator
    participant W as World (Level)

    Note over GS, W: 웨이브 시작 (StartWave)

    GS->>SV: SpawnMultipleItems(Count) 요청
    activate SV

    SV->>MG: GetMazePathLocations() 호출
    activate MG
    MG-->>SV: TArray<FVector> (유효 좌표 목록) 반환
    deactivate MG

    Note right of SV: 1. Algo::RandomShuffle()로 위치 무작위 섞기<br/>2. 중복 없는 고유 인덱스 순차 추출

    loop 아이템 개수만큼 반복
        SV->>W: LineTraceSingleByChannel()
        W-->>SV: HitResult (실제 지형 높이 Z값)
        SV->>W: SpawnActor<AActor>(ItemClass, FinalLocation)
    end

    SV-->>GS: TArray<AActor*> (스폰된 아이템 리스트) 반환
    deactivate SV

    Note over GS: 스폰된 아이템 중 코인 개수 집계 및 세션 관리

---

5. 결과 요약 및 회고

이번 작업을 통해 데이터 중심 설계의 중요성을 다시 확인했습니다.

• 단순 랜덤보다는 RandomShuffle을 통한 집합 처리가 중복 문제 해결에 훨씬 견고하다는 점.
• LineTrace는 단순 좌표 연산보다 물리적 환경 변화에 능동적으로 대처할 수 있다는 점.

아이템 스폰 시스템이 안정화되었으므로, 다음 포스팅에서는 플레이어에게 긴장감을 부여할 지뢰(MineItem)의 폭발 범위 시각화와 다이내믹 머티리얼 연출을 다뤄보겠습니다.