2D 무한 던전 생성 알고리즘

구성 요소:

1. 청크 기반 무한 타일맵
2. Cellular Automata를 이용한 동굴형 벽 생성
3. BSP를 이용한 방 배치와 연결
4. Flood Fill 및 A*를 이용한 도달 가능성 검증
5. 시드 기반 결정론적 랜덤
6. 엔트로피와 밀도 파라미터 제어

---

1. 주요 파라미터

worldSeed              : 전체 월드 시드
chunkSize              : 청크 크기, 예: 64 x 64
cellularFillProbability: 초기 벽 확률, 0.0 ~ 1.0
cellularIterations     : CA 반복 횟수
wallBirthThreshold     : 주변 벽 수가 이 값 이상이면 벽 생성
wallSurvivalThreshold  : 주변 벽 수가 이 값 이상이면 벽 유지
roomMinSize            : BSP 방 최소 크기
roomMaxSize            : BSP 방 최대 크기
bspMinRegionSize       : BSP 분할 최소 영역 크기
corridorWidth          : 복도 너비
targetDensity          : 최종 벽 또는 바닥 밀도
entropy                : 방 위치 및 분할 변동성
maxGenerationAttempts  : 연결성 검증 실패 시 재생성 횟수

권장 초기값:

chunkSize               = 64
cellularFillProbability = 0.45
cellularIterations      = 5
wallBirthThreshold      = 5
wallSurvivalThreshold   = 4
roomMinSize             = 8
roomMaxSize             = 20
bspMinRegionSize        = 24
corridorWidth           = 2
entropy                  = 0.7
targetDensity           = 0.55

---

2. 데이터 구조

타일 타입

enum TileType:
    VOID          // 아직 생성되지 않은 영역
    WALL
    FLOOR
    CORRIDOR

타일

struct Tile:
    type        : TileType
    walkable    : bool
    regionId    : int
    localSeed   : uint64

정수 좌표

struct Int2:
    x : int
    y : int

직사각형

struct Rect:
    minX : int
    minY : int
    maxX : int
    maxY : int

    function width():
        return maxX - minX + 1

    function height():
        return maxY - minY + 1

    function center():
        return Int2(
            floor((minX + maxX) / 2),
            floor((minY + maxY) / 2)
        )

청크

struct Chunk:
    chunkCoord : Int2
    tiles      : Tile[chunkSize][chunkSize]
    rooms      : List<Room>
    bspRoot    : BSPNode
    generated  : bool

방

struct Room:
    id          : int
    bounds      : Rect
    center      : Int2
    connected   : bool

BSP 노드

struct BSPNode:
    bounds : Rect
    left   : BSPNode?
    right  : BSPNode?
    room   : Room?

전역 월드

struct DungeonWorld:
    seed        : uint64
    chunks      : Map<Int2, Chunk>
    globalRooms : Map<Int2, List<Room>>
    connectivityCache : Map<Int2, bool>

---

3. 시드 기반 랜덤

청크 좌표와 전역 시드를 결합하여 각 청크가 항상 동일하게 생성되도록 한다.

function hashChunkSeed(worldSeed, chunkCoord):
    value = worldSeed
    value = Hash(value, chunkCoord.x)
    value = Hash(value, chunkCoord.y)
    return value

타일 단위 랜덤이 필요한 경우:

function hashTileSeed(chunkSeed, localX, localY):
    value = chunkSeed
    value = Hash(value, localX)
    value = Hash(value, localY)
    return value

function Random01(seed):
    return DeterministicHash(seed) / MAX_UINT

같은 worldSeed, 청크 좌표, 로컬 좌표를 사용하면 생성 순서와 관계없이 같은 결과를 얻을 수 있다.

---

4. 무한 청크 생성

function GetOrGenerateChunk(world, chunkCoord):
    if world.chunks.contains(chunkCoord):
        return world.chunks[chunkCoord]

    chunk = GenerateChunk(world, chunkCoord)
    world.chunks[chunkCoord] = chunk

    StitchChunkBorders(world, chunk)
    ValidateLocalConnectivity(world, chunk)

    return chunk

월드 좌표 변환:

function WorldToChunk(worldPosition):
    return Int2(
        floorDiv(worldPosition.x, chunkSize),
        floorDiv(worldPosition.y, chunkSize)
    )

function WorldToLocal(worldPosition):
    return Int2(
        mod(worldPosition.x, chunkSize),
        mod(worldPosition.y, chunkSize)
    )

---

5. 청크 생성 순서

function GenerateChunk(world, chunkCoord):
    chunkSeed = hashChunkSeed(world.seed, chunkCoord)

    chunk = CreateEmptyChunk(chunkCoord)

    // 1. Cellular Automata로 기본 동굴 생성
    InitializeCellularMap(chunk, chunkSeed)
    RunCellularAutomata(chunk)

    // 2. BSP로 방과 복도 생성
    bspRoot = CreateBSP(chunk.bounds, chunkSeed)
    rooms = CreateRoomsFromBSP(bspRoot, chunkSeed)
    ConnectBSPRooms(chunk, bspRoot, rooms)

    // 3. 방과 복도를 동굴 맵에 결합
    MergeBSPWithCave(chunk, rooms)

    // 4. 작은 고립 지역 제거
    RemoveSmallRegions(chunk)

    // 5. 경계 연결점 생성
    CreateChunkPortals(chunk, chunkSeed)

    chunk.bspRoot = bspRoot
    chunk.rooms = rooms
    chunk.generated = true

    return chunk

---

6. Cellular Automata 동굴 생성

초기화

function InitializeCellularMap(chunk, seed):
    for y in 0 .. chunkSize - 1:
        for x in 0 .. chunkSize - 1:
            tileSeed = hashTileSeed(seed, x, y)
            randomValue = Random01(tileSeed)

            if IsChunkBoundary(x, y):
                chunk.tiles[x][y].type = WALL
            else if randomValue < cellularFillProbability:
                chunk.tiles[x][y].type = WALL
            else:
                chunk.tiles[x][y].type = FLOOR

주변 벽 수 계산

8방향 기준:

function CountWallNeighbors(chunk, x, y):
    count = 0

    for dy in -1 .. 1:
        for dx in -1 .. 1:
            if dx == 0 and dy == 0:
                continue

            nx = x + dx
            ny = y + dy

            if IsOutsideChunk(nx, ny):
                count += 1
            else if chunk.tiles[nx][ny].type == WALL:
                count += 1

    return count

CA 반복

function RunCellularAutomata(chunk):
    for iteration in 1 .. cellularIterations:
        nextMap = CopyTileTypes(chunk)

        for y in 1 .. chunkSize - 2:
            for x in 1 .. chunkSize - 2:
                wallCount = CountWallNeighbors(chunk, x, y)
                currentType = chunk.tiles[x][y].type

                if currentType == WALL:
                    if wallCount >= wallSurvivalThreshold:
                        nextMap[x][y] = WALL
                    else:
                        nextMap[x][y] = FLOOR
                else:
                    if wallCount >= wallBirthThreshold:
                        nextMap[x][y] = WALL
                    else:
                        nextMap[x][y] = FLOOR

        ApplyTileTypes(chunk, nextMap)

일반적인 동굴 효과:

wallBirthThreshold    = 5
wallSurvivalThreshold = 4
iterations            = 4 ~ 7

---

7. BSP 분할

BSP 생성

function CreateBSP(rootBounds, seed):
    root = new BSPNode(rootBounds)

    SplitBSP(root, seed, depth = 0)

    return root

function SplitBSP(node, seed, depth):
    region = node.bounds

    if region.width() < bspMinRegionSize * 2
       and region.height() < bspMinRegionSize * 2:
        return

    random = Random01(Hash(seed, depth, region.minX, region.minY))

    canSplitHorizontal = region.height() >= bspMinRegionSize * 2
    canSplitVertical   = region.width()  >= bspMinRegionSize * 2

    if canSplitHorizontal and canSplitVertical:
        splitHorizontal = random < 0.5
    else:
        splitHorizontal = canSplitHorizontal

    entropyOffset = EntropyOffset(entropy, random)

    if splitHorizontal:
        split = Lerp(
            bspMinRegionSize,
            region.height() - bspMinRegionSize,
            random
        )
        split += entropyOffset

        node.left  = BSPNode(
            Rect(region.minX, region.minY,
                 region.maxX, region.minY + split - 1)
        )

        node.right = BSPNode(
            Rect(region.minX, region.minY + split,
                 region.maxX, region.maxY)
        )
    else:
        split = Lerp(
            bspMinRegionSize,
            region.width() - bspMinRegionSize,
            random
        )
        split += entropyOffset

        node.left = BSPNode(
            Rect(region.minX, region.minY,
                 region.minX + split - 1, region.maxY)
        )

        node.right = BSPNode(
            Rect(region.minX + split, region.minY,
                 region.maxX, region.maxY)
        )

    SplitBSP(node.left,  Hash(seed, 1), depth + 1)
    SplitBSP(node.right, Hash(seed, 2), depth + 1)

entropy가 낮으면 분할 위치가 중앙에 가까워지고, 높으면 분할 위치가 더 불규칙해진다.

function EntropyOffset(entropy, random):
    return round((random - 0.5) * entropy * bspMinRegionSize)

---

8. BSP 방 생성

function CreateRoomsFromBSP(node, seed):
    rooms = []

    if node.left != null or node.right != null:
        if node.left != null:
            rooms += CreateRoomsFromBSP(node.left, Hash(seed, 11))

        if node.right != null:
            rooms += CreateRoomsFromBSP(node.right, Hash(seed, 22))

        return rooms

    region = node.bounds

    availableWidth  = region.width()  - 4
    availableHeight = region.height() - 4

    roomWidth = RandomRange(
        roomMinSize,
        min(roomMaxSize, availableWidth)
    )

    roomHeight = RandomRange(
        roomMinSize,
        min(roomMaxSize, availableHeight)
    )

    offsetX = RandomRange(
        2,
        region.width() - roomWidth - 1
    )

    offsetY = RandomRange(
        2,
        region.height() - roomHeight - 1
    )

    roomBounds = Rect(
        region.minX + offsetX,
        region.minY + offsetY,
        region.minX + offsetX + roomWidth - 1,
        region.minY + offsetY + roomHeight - 1
    )

    room = Room(
        id = GenerateRoomId(roomBounds),
        bounds = roomBounds,
        center = roomBounds.center(),
        connected = false
    )

    node.room = room
    rooms.append(room)

    return rooms

---

9. BSP 방 연결

BSP 트리의 왼쪽과 오른쪽 하위 영역을 재귀적으로 연결한다.

function ConnectBSPRooms(chunk, node, rooms):
    if node.left == null and node.right == null:
        return FindRepresentativeRoom(node)

    leftRoom  = null
    rightRoom = null

    if node.left != null:
        leftRoom = ConnectBSPRooms(chunk, node.left, rooms)

    if node.right != null:
        rightRoom = ConnectBSPRooms(chunk, node.right, rooms)

    if leftRoom != null and rightRoom != null:
        CreateCorridor(
            chunk,
            leftRoom.center,
            rightRoom.center,
            corridorWidth
        )

        leftRoom.connected = true
        rightRoom.connected = true

    if leftRoom != null:
        return leftRoom

    return rightRoom

직각 복도

function CreateCorridor(chunk, start, end, width):
    if Random01(Hash(start.x, start.y, end.x, end.y)) < 0.5:
        CarveHorizontal(chunk, start.x, end.x, start.y, width)
        CarveVertical(chunk, start.y, end.y, end.x, width)
    else:
        CarveVertical(chunk, start.y, end.y, start.x, width)
        CarveHorizontal(chunk, start.x, end.x, end.y, width)

function CarveHorizontal(chunk, x1, x2, y, width):
    for x in min(x1, x2) .. max(x1, x2):
        for dy in -floor(width / 2) .. floor(width / 2):
            if IsInsideChunk(x, y + dy):
                chunk.tiles[x][y + dy].type = CORRIDOR

function CarveVertical(chunk, y1, y2, x, width):
    for y in min(y1, y2) .. max(y1, y2):
        for dx in -floor(width / 2) .. floor(width / 2):
            if IsInsideChunk(x + dx, y):
                chunk.tiles[x + dx][y].type = CORRIDOR

---

10. Cellular Automata와 BSP 결합

방과 복도는 CA 결과보다 우선한다.

function MergeBSPWithCave(chunk, rooms):
    for room in rooms:
        for y in room.bounds.minY .. room.bounds.maxY:
            for x in room.bounds.minX .. room.bounds.maxX:
                if IsInsideChunk(x, y):
                    chunk.tiles[x][y].type = FLOOR

    for y in 0 .. chunkSize - 1:
        for x in 0 .. chunkSize - 1:
            tile = chunk.tiles[x][y]

            if tile.type == FLOOR or tile.type == CORRIDOR:
                tile.walkable = true
            else:
                tile.walkable = false

CA 동굴이 지나치게 조밀하거나 희박한 경우 밀도 보정:

function AdjustDensity(chunk, targetDensity):
    currentDensity = CalculateFloorDensity(chunk)

    if currentDensity < targetDensity:
        CarveRandomWalls(chunk, targetDensity - currentDensity)
    else:
        AddRandomWalls(chunk, currentDensity - targetDensity)

단, 방과 복도에는 밀도 보정을 적용하지 않는다.

---

11. Flood Fill 연결성 검사

기본 Flood Fill

function FloodFill(chunk, start):
    visited = Set<Int2>()
    queue = Queue<Int2>()

    if not IsWalkable(chunk, start):
        return visited

    queue.push(start)
    visited.add(start)

    while not queue.empty():
        current = queue.pop()

        for neighbor in Get4Neighbors(current):
            if not IsInsideChunk(neighbor):
                continue

            if not IsWalkable(chunk, neighbor):
                continue

            if visited.contains(neighbor):
                continue

            visited.add(neighbor)
            queue.push(neighbor)

    return visited

모든 방 연결성 확인

function ValidateRoomConnectivity(chunk):
    if chunk.rooms.empty():
        return false

    start = chunk.rooms[0].center
    reachable = FloodFill(chunk, start)

    for room in chunk.rooms:
        if not reachable.contains(room.center):
            return false

    return true

고립 영역 제거

function RemoveSmallRegions(chunk):
    visitedGlobal = Set<Int2>()
    regions = []

    for each tile position p in chunk:
        if not IsWalkable(chunk, p):
            continue

        if visitedGlobal.contains(p):
            continue

        region = FloodFill(chunk, p)
        visitedGlobal.union(region)
        regions.append(region)

    largestRegion = MaxBySize(regions)

    for region in regions:
        if region != largestRegion:
            for p in region:
                chunk.tiles[p.x][p.y].type = WALL
                chunk.tiles[p.x][p.y].walkable = false

방을 반드시 유지해야 하는 경우:

function RemoveSmallRegionsPreservingRooms(chunk):
    requiredTiles = Set()

    for room in chunk.rooms:
        requiredTiles.add(room.center)

    regions = FindAllWalkableRegions(chunk)

    for region in regions:
        if not ContainsAny(region, requiredTiles):
            ConvertRegionToWalls(chunk, region)

---

12. A* 경로 검증

Flood Fill은 전체 연결성 검사용이고, A*는 특정 두 지점의 실제 경로 검사용이다.

function AStar(chunk, start, goal):
    openSet = PriorityQueue()
    cameFrom = Map<Int2, Int2>()
    costSoFar = Map<Int2, float>()

    openSet.push(start, 0)
    costSoFar[start] = 0

    while not openSet.empty():
        current = openSet.popLowestPriority()

        if current == goal:
            return ReconstructPath(cameFrom, current)

        for next in Get4Neighbors(current):
            if not IsInsideChunk(next):
                continue

            if not IsWalkable(chunk, next):
                continue

            newCost = costSoFar[current] + MovementCost(next)

            if next not in costSoFar
               or newCost < costSoFar[next]:

                costSoFar[next] = newCost
                priority = newCost + ManhattanDistance(next, goal)

                openSet.push(next, priority)
                cameFrom[next] = current

    return FAILURE

모든 방을 순차 검사:

function ValidateWithAStar(chunk):
    for i in 0 .. chunk.rooms.count - 2:
        start = chunk.rooms[i].center
        goal  = chunk.rooms[i + 1].center

        if AStar(chunk, start, goal) == FAILURE:
            return false

    return true

---

13. 검증 실패 시 재생성

function GenerateValidatedChunk(world, chunkCoord):
    baseSeed = hashChunkSeed(world.seed, chunkCoord)

    for attempt in 0 .. maxGenerationAttempts - 1:
        attemptSeed = Hash(baseSeed, attempt)

        chunk = GenerateChunkWithSeed(
            world,
            chunkCoord,
            attemptSeed
        )

        if ValidateRoomConnectivity(chunk)
           and ValidateWithAStar(chunk):

            return chunk

    // 최종 실패 시 보정 연결 수행
    ForceConnectRooms(chunk)

    return chunk

강제 연결:

function ForceConnectRooms(chunk):
    regions = FindAllWalkableRegions(chunk)

    while regions.count > 1:
        regionA, regionB = FindClosestRegions(regions)

        pointA = ClosestPoint(regionA, regionB)
        pointB = ClosestPoint(regionB, regionA)

        CreateCorridor(
            chunk,
            pointA,
            pointB,
            corridorWidth
        )

        regions = FindAllWalkableRegions(chunk)

---

14. 청크 간 경계 연결

무한 월드에서는 각 청크 내부 연결만으로 충분하지 않다. 인접 청크 사이에 포털을 생성해야 한다.

struct ChunkPortal:
    localPosition : Int2
    direction     : Int2
    linked        : bool

포털 생성:

function CreateChunkPortals(chunk, seed):
    for direction in [NORTH, SOUTH, EAST, WEST]:
        random = Random01(Hash(seed, direction))

        if random < portalProbability:
            portal = SelectPortalPosition(chunk, direction)
            CarvePortal(chunk, portal)

이웃 청크와 연결:

function StitchChunkBorders(world, chunk):
    for direction in [NORTH, SOUTH, EAST, WEST]:
        neighborCoord = chunk.chunkCoord + direction
        neighbor = world.chunks.get(neighborCoord)

        if neighbor == null:
            continue

        borderA = FindNearestPortals(chunk, neighbor, direction)
        borderB = FindNearestPortals(neighbor, chunk, -direction)

        if borderA == null or borderB == null:
            CreateAlignedPortalPair(chunk, neighbor, direction)
        else:
            LinkPortals(borderA, borderB)

경계 포털이 없을 경우, 두 청크 가장자리의 가장 가까운 바닥 타일을 선택한다.

function CreateAlignedPortalPair(chunkA, chunkB, direction):
    edgeA = GetBoundaryWalkableTiles(chunkA, direction)
    edgeB = GetBoundaryWalkableTiles(chunkB, -direction)

    if edgeA.empty() or edgeB.empty():
        CarveBoundaryOpening(chunkA, direction)
        CarveBoundaryOpening(chunkB, -direction)
        return

    positionA = SelectBySeed(edgeA, chunkA.chunkCoord)
    positionB = MatchingPosition(positionA, chunkA, chunkB, direction)

    SetWalkable(chunkA, positionA)
    SetWalkable(chunkB, positionB)

---

15. 전체 알고리즘 요약

function GenerateInfiniteDungeon(worldSeed, requestedChunkCoords):
    world = DungeonWorld(seed = worldSeed)

    for chunkCoord in requestedChunkCoords:
        if not world.chunks.contains(chunkCoord):
            chunk = GenerateValidatedChunk(world, chunkCoord)
            world.chunks[chunkCoord] = chunk

    for chunkCoord in requestedChunkCoords:
        StitchChunkBordersAround(world, chunkCoord)

    ValidateGlobalChunkConnectivity(world, requestedChunkCoords)

    return world

핵심 생성 흐름:

시드 계산
  ↓
청크별 CA 초기화
  ↓
CA 반복으로 동굴 벽 생성
  ↓
BSP 영역 분할
  ↓
BSP 리프에 방 생성
  ↓
BSP 부모 노드 기준 복도 생성
  ↓
방과 복도를 바닥으로 강제 적용
  ↓
고립 영역 제거
  ↓
청크 경계 포털 생성
  ↓
Flood Fill 및 A* 검증
  ↓
실패 시 시드 변형 재생성 또는 강제 연결

이 구조에서는 Cellular Automata가 자연스러운 동굴 지형을 만들고, BSP가 방의 분포와 최소 연결성을 보장한다. 시드가 동일하면 청크 생성 순서와 관계없이 동일한 무한 던전이 생성된다.