로블록스 절차적 던전 아키텍처: BSP 방 분할, 델로네 복도망 & 청크 스트리밍

절차적 맵 생성(Procedural Generation)은 로그라이크, 던전 RPG, 탈출 생존 장르의 핵심 엔진입니다. 알고리즘 설계가 미흡하면 부품 수 폭증으로 메모리 렉이 발생하고 방끼리 겹치는 물리 충돌 버그가 생깁니다.

이진 공간 분할(BSP)을 통한 재귀적 공간 균등 분할, 델로네 삼각분할과 프림 알고리즘 기반 순환 복도망 구축, 그리고 로블록스 내장 `StreamingEnabled` 청크 단위 최적화를 연결해 수백 개의 방을 지연 없이 렌더링하는 파이프라인을 구축합니다.

1. 이진 공간 분할(BSP)을 이용한 비중복 방 생성

균형 잡힌 방 배치를 위한 재귀적 공간 분할 수학:

• 재귀적 서브트리 분할: 전체 맵 영역을 가로 또는 세로로 랜덤 비율(0.4~0.6)로 쪼개어 리프 노드가 목표 크기에 도달할 때까지 반복 분할합니다.
• 패딩 및 가로세로 비율 제한: 지나치게 길쭉한 복도형 방이 생기지 않도록 가로세로 비율(1:1~1:2.5)을 제한하고 가장자리 여백을 확보합니다.
• 영역 내 방 내접: 분할된 리프 노드 영역 내부에만 방을 무작위 크기로 내접시키므로, 무거운 물리 충돌 검사 없이도 방 간 겹침이 100% 방지됩니다.

2. 자연스러운 복도망: 델로네 삼각분할 & 최소 신장 트리 (MST)

막다른 길을 없애고 유기적인 순환 동선을 구축하는 알고리즘:

• 중심점 점군(Point Cloud) 추출: 모든 방의 중심 좌표를 추출해 평면 2D 델로네 삼각분할 그래프를 생성하여 인접 후보 경로를 확보합니다.
• 프림/크루스칼 최소 신장 트리(MST): 모든 방이 최소 경로로 고립 없이 연결되도록 삼각망에서 중복 간선을 제거합니다.
• 순환 루프 재주입(15% 여유 간선): 트리에서 제거된 간선 중 12~18%를 무작위로 복원해 외길 진행을 방지하고 유기적인 순환 동선을 제공합니다.

3. 그리드 기반 복도 카빙 & 타일 인스턴싱

수학적 그래프 간선을 실제 로블록스 물리 지형으로 변환:

• 직각 L자형/S자형 복도 라우팅: 연결된 두 방 사이를 직각 절곡 경로로 잇고 방 외벽 접점에 문(Doorway) 임계점을 배치합니다.
• 타일맵 4비트 마스킹: 상하좌우 인접 타일 여부에 따라 평면 바닥, 직선 벽, 코너 벽, 교차로 메시를 자동 선택해 조립합니다.
• 무충돌 지오메트리 결합: 복도 타일들을 Welded Model로 묶거나 EditableMesh API를 활용해 단일 메시로 병합하여 파트 수를 90% 절감합니다.

-- 이진 공간 분할 (BSP) 던전 트리 생성 모듈
local BSPNode = {}
BSPNode.__index = BSPNode

function BSPNode.new(x, z, width, depth)
    local self = setmetatable({}, BSPNode)
    self.X, self.Z = x, z
    self.Width, self.Depth = width, depth
    self.LeftChild = nil
    self.RightChild = nil
    self.Room = nil
    return self
end

function BSPNode:Split(minSize)
    if self.LeftChild or self.RightChild then return false end
    
    local splitHorizontal = math.random() > 0.5
    if self.Width > self.Depth and (self.Width / self.Depth) >= 1.25 then
        splitHorizontal = false
    elseif self.Depth > self.Width and (self.Depth / self.Width) >= 1.25 then
        splitHorizontal = true
    end
    
    local maxDimension = (splitHorizontal and self.Depth or self.Width) - minSize
    if maxDimension <= minSize then return false end
    
    local splitPos = math.random(minSize, maxDimension)
    if splitHorizontal then
        self.LeftChild = BSPNode.new(self.X, self.Z, self.Width, splitPos)
        self.RightChild = BSPNode.new(self.X, self.Z + splitPos, self.Width, self.Depth - splitPos)
    else
        self.LeftChild = BSPNode.new(self.X, self.Z, splitPos, self.Depth)
        self.RightChild = BSPNode.new(self.X + splitPos, self.Z, self.Width - splitPos, self.Depth)
    end
    return true
end

return BSPNode

4. 메모리 컬링 & StreamingEnabled 청크 아키텍처

모바일 2GB RAM 기기에서도 끊김 없는 대형 던전 구현:

• ModelStreamingMode.Atomic 적용: 개별 방과 복도를 원자적 모델로 묶어 벽 일부만 로딩되어 캐릭터가 추락하는 현상을 방지합니다.
• 공간 섹터 분할(64x64 studs): 거대한 던전을 그리드 청크로 묶고 플레이어 시야 밖의 청크는 물리 연산을 비활성화합니다.
• 동적 오클루전 컬링(Occlusion Culling): 방 사이 통로에 안개 포털 및 닫힌 문을 배치해 로블록스 엔진이 시야 밖 방들의 렌더링을 완전히 생략하도록 유도합니다.

5. 시드(Seed) 동기화 & 서버 권한 엔티티 스폰

동기화 렉 없이 완벽한 보안과 공정한 게임성을 유지하는 방법:

• 결정론적 의사난수 시드 복제: 서버는 단 하나의 32비트 정수 시드만을 전송하고, 클라이언트는 동일한 시드로 로컬 그래픽 지형을 연산합니다.
• 서버 권한 엔티티 스폰: 바닥 타일은 로컬에서 생성되지만 몬스터, 보물상자, 함정 트리거는 철저히 서버에서만 생성하고 동기화합니다.
• 네비메시(NavMesh) 자동 생성: 생성된 바닥에 PathfindingModifier를 지정해 몬스터 AI가 낭떠러지와 벽을 피해 유저를 추적하도록 유도합니다.

Frequently Asked Questions