Skip to content

Dungeon Generation

자동으로 던정을 생성하는 기법에 대한 내용

Categories

Libraries

테라리아 스타일

Terraria#pygame-ce 클론 코딩 항목 참조.

2D 탑다운 던전 생성 알고리즘 조사

WARNING

Deep research 생성 결과

게임 개발에서 던전 생성 알고리즘은 절차적 콘텐츠 생성(PCG)의 일종으로, 매번 새로운 탑다운 던전 맵을 자동으로 생성해 줍니다.

랜덤 방 배치 (Random Room Placement)

개요: 전체 맵에 여러 사각형 방(room)을 무작위로 배치하고 연결하는 가장 간단한 던전 생성 기법입니다. 먼저 맵에 일정 개수의 직사각형 방을 겹치지 않도록 무작위 위치에 배치합니다. 각 방을 배치할 때 이미 놓인 다른 방과 중복되면 폐기하고, 겹치지 않으면 확정합니다​. 그런 다음 복도(corridor)를 만들어 모든 방들을 연결합니다. 복도는 일반적으로 각 방의 중심점들 사이를 직선 또는 L자 경로로 파서 생성합니다. 이렇게 하면 방들이 통로로 서로 이어진 하나의 던전이 됩니다.

장점: 구현이 매우 간단하고 직관적입니다. 방의 크기, 개수를 조절하여 던전의 밀도를 쉽게 바꿀 수 있습니다. 복도를 어떻게 연결하느냐에 따라 다양한 형태의 맵을 얻을 수 있습니다.

단점: 방을 무작위 배치하기 때문에 원하는 구조(예: 특정 패턴의 방 연결)를 얻기 어렵습니다. 방과 방을 잇는 복도가 단순한 일자 통로로 끝나기 쉬워 지형이 단순할 수 있습니다. 또한 충분히 많은 시도를 하지 않으면 방 배치 실패로 던전이 작게 생성될 수 있습니다.

탑다운 게임 적합성: ✅ 적합합니다. 대부분의 로그라이크 게임들이 사용하는 기본 방식으로, 2D 탑다운에서 명확한 방과 통로 구조를 제공하여 탐험 게임플레이에 적합합니다.

랜덤 방 배치 알고리즘은 실제 Rogue나 Angband 같은 게임에서 활용되어 왔으며, “임의 위치에 여러 방을 배치하고 그들을 무작위 복도로 연결한다”는 단순한 절차로 던전을 생성합니다​. 아래는 이 알고리즘의 간략한 파이썬 구현입니다. 방을 겹치지 않게 놓고, 이전 방들과 차례로 L자형 통로로 연결하는 방식으로 동작합니다. 

import random

def generate_random_rooms(map_width, map_height, max_rooms=15, room_min_size=5, room_max_size=10):
    dungeon = [[1 for _ in range(map_width)] for _ in range(map_height)]  # 1=벽, 0=바닥
    rooms = []
    for _ in range(max_rooms):
        # 무작위 크기의 방 생성
        w = random.randint(room_min_size, room_max_size)
        h = random.randint(room_min_size, room_max_size)
        x = random.randint(1, map_width - w - 2)
        y = random.randint(1, map_height - h - 2)
        # 다른 방과 겹치는지 검사
        if any(x < rx+rw and x+w > rx and y < ry+rh and y+h > ry 
               for (rx, ry, rw, rh) in rooms):
            continue  # 겹치면 이 방은 버림
        # 방을 맵에 새기기 (배열에 0으로 채우기)
        for iy in range(y, y+h):
            for ix in range(x, x+w):
                dungeon[iy][ix] = 0
        rooms.append((x, y, w, h))
    # 모든 방들을 복도로 연결 (여기선 순차적으로 이전 방과 연결)
    for i in range(1, len(rooms)):
        x1, y1 = rooms[i-1][0] + rooms[i-1][2]//2, rooms[i-1][1] + rooms[i-1][3]//2  # 이전 방 중심
        x2, y2 = rooms[i][0] + rooms[i][2]//2, rooms[i][1] + rooms[i][3]//2          # 현재 방 중심
        # 무작위로 가로->세로 또는 세로->가로 경로로 연결
        if random.random() < 0.5:
            # 가로 먼저
            for x in range(min(x1, x2), max(x1, x2)+1):
                dungeon[y1][x] = 0
            for y in range(min(y1, y2), max(y1, y2)+1):
                dungeon[y][x2] = 0
        else:
            # 세로 먼저
            for y in range(min(y1, y2), max(y1, y2)+1):
                dungeon[y][x1] = 0
            for x in range(min(x1, x2), max(x1, x2)+1):
                dungeon[y2][x] = 0
    return dungeon

이진 공간 분할 (Binary Space Partitioning, BSP)

개요: BSP 알고리즘은 던전 전체 공간을 이진 트리 형태로 재귀적 분할하여 방을 배치하는 기법입니다​. 먼저 맵 전체를 둘로 나누고, 각 부분을 다시 무작위 방향으로 둘로 나누는 작업을 재귀적으로 반복합니다. 분할은 영역이 최소 크기보다 충분히 클 때까지 이루어지며, 이렇게 하면 큰 맵이 트리 형태의 작은 구역들로 나뉩니다. 그런 다음 분할된 최종 구역마다 하나씩 방을 배치합니다 (구역 경계 내에 무작위 위치/크기로 방 생성). 마지막으로 이 분할 트리를 따라 인접한 구역의 방들을 복도로 연결합니다​. 예를 들어, BSP 트리에서 같은 부모를 가진 두 자식 노드의 방 사이에 복도를 만들고, 이를 상위로 거슬러 올라가며 전체 던전이 하나로 연결되도록 합니다. 이렇게 생성된 던전은 격자처럼 구획된 구조를 가집니다.

장점: BSP를 사용하면 방들 간 겹침이 애초에 발생하지 않으며, 공간을 효율적으로 사용할 수 있습니다​. 또한 트리 구조를 이용해 모든 방이 연결된 경로를 비교적 쉽게 보장할 수 있습니다. 결과 던전은 방들이 균형 있게 퍼져 있어 맵 구성의 조절(방 크기, 밀집도 등)이 용이합니다​.

단점: 분할 방식에 따라 던전 모양이 다소 규칙적으로 느껴질 수 있습니다. 복도가 계단 형태(L자)로 많이 발생하여 직선적이고 기하학적인 느낌을 줄 수 있습니다. 또한 구현 시 재귀 분할과 트리 연결에 대한 이해가 필요해 난이도가 약간 높습니다.

탑다운 게임 적합성: ✅ 적합합니다. 방이 불규칙하게 퍼지면서도 모두 연결되므로, 큰 맵의 구조를 안정적으로 생성하는 데 유용합니다. 많은 로그라이크 게임 엔진 및 툴킷에서 기본 알고리즘으로 제공될 만큼 검증되어 있습니다.

BSP 기반 던전 생성은 공간을 이분하여 방을 놓는 방식으로, 방들이 적절히 떨어져 있고 통로로 연결된 던전을 만들어냅니다​. 아래 코드는 BSP 알고리즘의 간략한 구현입니다. 맵을 재귀적으로 분할한 후 각 최종 구역에 방을 넣고, 분할 트리 구조를 따라 인접 구역의 방을 복도로 연결합니다. 

def generate_bsp_dungeon(map_width, map_height, min_size=5, max_size=12, max_depth=4):
    dungeon = [[1 for _ in range(map_width)] for _ in range(map_height)]
    # BSP 분할을 위한 스택 (x, y, w, h, depth)
    stack = [(1, 1, map_width-2, map_height-2, 0)]  # 테두리 1칸은 벽으로 남김
    regions = []  # 최종 분할된 구역들
    while stack:
        x, y, w, h, depth = stack.pop()
        if depth < max_depth and w > 2*min_size and h > 2*min_size and random.random() < 0.75:
            # 무작위 방향으로 분할 (가로/세로)
            if w > h:
                split = random.randint(min_size, w - min_size)  # 세로 분할 위치
                stack.append((x, y, split, h, depth+1))
                stack.append((x + split + 1, y, w - split - 1, h, depth+1))
            else:
                split = random.randint(min_size, h - min_size)  # 가로 분할 위치
                stack.append((x, y, w, split, depth+1))
                stack.append((x, y + split + 1, w, h - split - 1, depth+1))
        else:
            # 더 이상 분할하지 않고 구역을 확정
            regions.append((x, y, w, h))
    # 각 구역에 하나씩 방 배치
    room_centers = []
    for (x, y, w, h) in regions:
        rw = random.randint(min_size, min(w, max_size))
        rh = random.randint(min_size, min(h, max_size))
        rx = random.randint(x, x + w - rw)  # 구역 내 랜덤 위치
        ry = random.randint(y, y + h - rh)
        for iy in range(ry, ry+rh):
            for ix in range(rx, rx+rw):
                dungeon[iy][ix] = 0
        cx, cy = rx + rw//2, ry + rh//2  # 방 중심 좌표
        room_centers.append((cx, cy))
    # 방들을 연결 - 여기서는 MST(최소 신장 트리)로 연결 보장
    connected = [room_centers[0]]
    not_connected = room_centers[1:]
    while not_connected:
        # 가장 가까운 연결되지 않은 방 선택
        c = connected[-1]
        # 가까운 방 찾기
        nearest = min(not_connected, key=lambda t: (c[0]-t[0])**2 + (c[1]-t[1])**2)
        x1, y1 = c; x2, y2 = nearest
        # L자형 복도 생성
        if random.random() < 0.5:
            for x in range(min(x1, x2), max(x1, x2)+1):
                dungeon[y1][x] = 0
            for y in range(min(y1, y2), max(y1, y2)+1):
                dungeon[y][x2] = 0
        else:
            for y in range(min(y1, y2), max(y1, y2)+1):
                dungeon[y][x1] = 0
            for x in range(min(x1, x2), max(x1, x2)+1):
                dungeon[y2][x] = 0
        connected.append(nearest)
        not_connected.remove(nearest)
    return dungeon

셀룰러 오토마타 (Cellular Automata)

개요: 셀룰러 오토마타를 이용한 던전 생성은 맵을 격자 셀로 보고, 각 셀을 벽 또는 바닥의 상태로 간주하여 반복적인 규칙 적용으로 지형을 만드는 방법입니다. 먼저 맵의 셀을 무작위로 벽(1)이나 바닥(0)으로 채웁니다. 이후 일정 횟수 동안 매 셀의 이웃(주변 8칸)의 벽 개수를 계산해서 규칙에 따라 벽/바닥을 업데이트합니다. 대표적인 규칙은 4-5 규칙으로 불리며, 주변에 벽이 5개 이상 있으면 해당 셀을 벽으로 만든다는 식입니다​. 여러 세대(iteration)를 거치면 초기의 랜덤 노이즈가 점차 동굴처럼 연결된 방과 통로 형태로 수렴합니다. 이렇게 생성된 맵은 자연스러운 동굴 지형이나 불규칙적인 던전에 적합합니다.

장점: 자연스러운 형태의 던전을 얻을 수 있습니다. 사람이 손으로 그린 듯한 유기적(organic)인 동굴, 굴곡진 통로 등의 모양을 자동으로 만들어주기 때문에, 방형 던전의 획일성을 피할 수 있습니다​. 구현 난이도도 낮은 편이며, 파라미터(초기 벽 확률, 이웃 기준 등)를 조절하여 다양한 모양을 실험할 수 있습니다.

단점: 제대로 조절하지 않으면 이어지지 않은 고립된 공간들이 생길 수 있습니다​. 예를 들어 동굴 여러 개가 떨어져 나오면 플레이어가 일부 영역에 접근 못하는 문제가 발생합니다. 이를 해소하려면 추가로 Flood Fill 등을 통해 가장 큰 연결 영역만 남기고 나머지는 벽으로 메우는 후처리가 필요합니다​. 또한 원하는 형태를 정확히 통제하기 어려워, 규모가 큰 맵에서는 충분한 반복과 튜닝이 필요합니다.

탑다운 게임 적합성: ✅ 대체로 적합합니다. 자연스러운 동굴이나 야외 지형 느낌의 던전을 만들 때 유용합니다. 다만 로그라이크처럼 모든 구역이 연결되어야 하는 게임에서는, 생성 후에 연결성 보정 절차를 추가하는 것이 좋습니다.

셀룰러 오토마타 기반 알고리즘은 랜덤한 초기맵에서 시작해 단순 규칙을 반복 적용함으로써 계속해서 주변과 비슷하게 바뀌어가는 맵을 만들어냅니다​. 아래 구현은 초기 45% 확률로 벽을 배치한 후, 4회의 iteration 동안 다음 규칙을 적용합니다: 주변 8칸 중 벽이 5개 이상이면 현재 셀을 벽으로, 그렇지 않으면 바닥으로. 마지막으로 연결되지 않은 작은 빈 공간들은 찾아내 모두 메워 하나의 큰 동굴만 남도록 후처리합니다. 

def generate_cellular_cave(map_width, map_height, fill_prob=0.45, iterations=4):
    # 초기 맵 랜덤 배치
    cave = [[1 if random.random() < fill_prob else 0 for _ in range(map_width)] 
            for _ in range(map_height)]
    # 지도 가장자리 영역을 모두 벽으로 고정 (외벽)
    for x in range(map_width):
        cave[0][x] = cave[map_height-1][x] = 1
    for y in range(map_height):
        cave[y][0] = cave[y][map_width-1] = 1
    # 정해진 횟수만큼 규칙 반복 적용
    for _ in range(iterations):
        new_cave = [row[:] for row in cave]  # 복사
        for y in range(1, map_height-1):
            for x in range(1, map_width-1):
                wall_count = 0
                # 주변 8방향 벽 개수 세기
                for ny in range(y-1, y+2):
                    for nx in range(x-1, x+2):
                        if nx == x and ny == y:
                            continue
                        if cave[ny][nx] == 1:
                            wall_count += 1
                # 규칙 적용
                if cave[y][x] == 1:
                    new_cave[y][x] = 1 if wall_count >= 4 else 0
                else:
                    new_cave[y][x] = 1 if wall_count >= 5 else 0
        cave = new_cave
    # 연결성 확보: 가장 큰 연결 영역 이외의 바닥은 모두 벽으로 메우기
    visited = [[False]*map_width for _ in range(map_height)]
    largest_region = []
    directions = [(1,0),(-1,0),(0,1),(0,-1)]
    for sy in range(1, map_height-1):
        for sx in range(1, map_width-1):
            if cave[sy][sx] == 0 and not visited[sy][sx]:
                region = []
                stack = [(sx, sy)]
                visited[sy][sx] = True
                while stack:
                    cx, cy = stack.pop()
                    region.append((cx, cy))
                    for dx, dy in directions:
                        nx, ny = cx+dx, cy+dy
                        if 0 <= nx < map_width and 0 <= ny < map_height:
                            if cave[ny][nx] == 0 and not visited[ny][nx]:
                                visited[ny][nx] = True
                                stack.append((nx, ny))
                if len(region) > len(largest_region):
                    largest_region = region
    # largest_region이 아닌 모든 바닥은 벽으로 변경
    floor_set = set(largest_region)
    for y in range(map_height):
        for x in range(map_width):
            if cave[y][x] == 0 and (x, y) not in floor_set:
                cave[y][x] = 1
    return cave

드렁커드 워크 (Drunkard’s Walk, 무작위 균열)

개요: 드렁커드 워크 알고리즘은 술 취한 사람이 비틀거리듯이 맵 위를 무작위로 걸으며 통로를 뚫어가는 방식입니다​. 초기에는 맵 전체를 벽으로 두고, 한 지점(예: 중앙)에서 시작하여 그 위치를 바닥으로 판 뒤 임의 방향으로 한 칸 이동합니다. 이동한 셀이 벽이었다면 바닥으로 바꿉니다. 그런 다음 다시 무작위 방향으로 이동을 반복합니다. 이 과정을 충분한 횟수 진행하면, 이동 경로를 따라 군데군데 넓어진 동굴 통로 형태의 던전이 만들어집니다​. 마치 미로를 파는 광부가 랜덤하게 돌아다닌 흔적 같아서, 좁은 복도와 갑자기 확장된 공간이 뒤섞인 맵을 얻을 수 있습니다. 일반적으로 전체 맵의 목표 바닥 비율(예: 40%)을 정해 놓고 그 수만큼 바닥이 생길 때까지 반복합니다.

장점: 구현이 간단하면서도 결과가 매번 크게 달라집니다. 폭이 불규칙한 통로와 열린 공간이 혼재된 맵을 얻을 수 있어, 예상치 못한 개성 있는 레이아웃이 나옵니다​. 또한 랜덤 워크 경로는 스스로 끊임없이 이어지므로 별도의 연결성 검사 없이 하나의 연결된 던전을 생성하는 점도 장점입니다.

단점: 완전히 무작위로 걷기 때문에 특정 구조를 통제하기 어렵고, 맵의 모양이 지나치게 운에 좌우됩니다. 필요한 공간이 충분히 파이지 않으면 매우 좁은 통로나 싱거운 형태가 될 수 있습니다. 또한 경로가 맵 가장자리에 치우쳐 몰릴 경우 일부 영역만 파이고 넓게 비게 될 수도 있습니다 (이를 완화하기 위해 때때로 워커를 맵 중앙이나 다른 위치로 재배치하기도 합니다).

탑다운 게임 적합성: ✅ 적합합니다. 특히 동굴형 던전이나 미로 같은 통로를 원할 때 유용합니다. 좁은 길과 넓은 방이 불규칙하게 연결된 던전은 탐험 요소를 높여주지만, 너무 예측 불가능한 형태가 싫다면 다른 알고리즘과 혼합하여 사용하기도 합니다.

드렁커드 워크로 생성된 던전은 하나의 연속된 경로로 이루어져 있어 항상 연결되어 있다는 특징이 있습니다​. 아래 구현에서는 맵 중앙에서 시작해 무작위로 네 방향을 걸어가며 전체 셀의 40% 정도를 바닥으로 팔 때까지 반복합니다. 경로가 가장자리에 몰리면 가끔 랜덤한 기존 바닥 지점으로 이동하여 균형을 잡습니다. 

def generate_drunkards_walk(map_width, map_height, floor_ratio=0.4):
    dungeon = [[1 for _ in range(map_width)] for _ in range(map_height)]
    total_cells = map_width * map_height
    target_floor_count = int(total_cells * floor_ratio)
    # 시작 위치 (중앙)
    x, y = map_width // 2, map_height // 2
    dungeon[y][x] = 0
    floor_count = 1
    directions = [(0,1),(0,-1),(1,0),(-1,0)]  # 하, 상, 우, 좌
    while floor_count < target_floor_count:
        dx, dy = random.choice(directions)
        nx, ny = x + dx, y + dy
        # 경계 밖으로 나가면 무시 (다른 방향으로 계속 시도)
        if not (0 < nx < map_width-1 and 0 < ny < map_height-1):
            # 가끔 워커를 맵 내 랜덤 바닥 위치로 순간이동시켜 분산
            if random.random() < 0.3:
                rx, ry = random.randrange(1, map_width-1), random.randrange(1, map_height-1)
                if dungeon[ry][rx] == 0:
                    x, y = rx, ry
            continue
        # 이동
        x, y = nx, ny
        if dungeon[y][x] == 1:  # 벽이면 판다
            dungeon[y][x] = 0
            floor_count += 1
    return dungeon

미로 기반 생성 (Maze-based, 깊이우선 탐색 등)

개요: 미로 생성 알고리즘을 던전에 응용하는 기법으로, 가장 대표적인 것은 재귀적 백트래킹(깊이우선 탐색)을 이용한 완전 미로(perfect maze) 생성입니다. 이 알고리즘에서는 우선 맵 전체를 벽으로 막은 후, 한 셀에서 시작해 DFS(Depth-First Search) 방식으로 인접한 벽을 뚫으며 나아갑니다. 구체적으로, 현재 위치에서 방문하지 않은 이웃 셀을 무작위로 선택해 벽을 허물고 이동하고, 더 갈 곳이 없으면 되돌아가 다른 방향을 탐색합니다​. 이렇게 하면 루프가 없는 하나의 통로망이 만들어지는데, 이런 미로는 모든 셀이 서로 하나의 경로로 연결되어 있는 특징이 있습니다​. 미로 기반 던전은 일반적으로 폭 1칸짜리의 복도들이 격자 형태로 이어진 미로 구조의 던전을 생성합니다.

장점: 보장된 연결성 – 미로 알고리즘으로 생성된 맵은 어느 두 지점 사이에도 정확히 한 가지 경로만 존재하는 완전 연결 그래프가 됩니다​. 따라서 플레이어가 모든 구역을 탐험할 수 있고, 경로 파악이 용이합니다. 구현도 DFS만 활용하면 되므로 비교적 간단하며, 속도도 빠릅니다​. 좁은 통로 위주의 복잡한 퍼즐 같은 지형을 원할 때 적합합니다.

단점: 루프가 없기 때문에 경로가 '''지나치게 일자형으로 단조롭거나 막다른 길(dead end)이 많이 생길 수 있습니다. 한 번 만든 미로는 구조가 복잡하지만 공간적으로 협소한 느낌을 줄 수 있고, 전투 공간이나 특별한 방이 부족합니다. 이를 보완하기 위해 미로 일부에 방을 추가하거나 일부 벽을 허물어 루프를 만들기도 합니다.

탑다운 게임 적합성: ⚠️ 부분적으로 적합합니다. 미로 형태의 던전은 퍼즐 요소나 길찾기 재미를 주지만, 전투나 이벤트 공간을 만들려면 추가 작업이 필요합니다. 따라서 완전한 던전보다는 던전의 일부 구역(예: 복잡한 통로 구간)에 적용하거나, 다른 알고리즘과 혼합해 사용하는 경우가 많습니다.

재귀적 백트래킹을 이용한 미로 생성은 가장 이해하기 쉬운 미로 알고리즘 중 하나로, 대부분의 셀을 한번씩 방문하면서 길을 뚫습니다​. 아래 구현은 격자를 홀수 좌표에 통로를 내는 방식으로 1-셀 너비의 복도를 만듭니다. (시작점을 (1,1)에서 시작하고, 두 칸씩 점프해 가며 벽을 허무는 방식입니다.) 이렇게 생성된 미로는 루프가 없고 모든 통로가 연결된 구조를 가집니다. 

def generate_maze(map_width, map_height):
    # 맵 크기를 홀수로 조정 (외곽을 벽으로 유지)
    if map_width % 2 == 0: map_width -= 1
    if map_height % 2 == 0: map_height -= 1
    maze = [[1 for _ in range(map_width)] for _ in range(map_height)]
    # DFS 스택 초기화
    stack = [(1, 1)]
    maze[1][1] = 0  # 시작점
    while stack:
        x, y = stack[-1]
        # 방문하지 않은 이웃 셀 (2칸 띄운 위치 기준)
        neighbors = []
        for dx, dy in [(2,0),(-2,0),(0,2),(0,-2)]:
            nx, ny = x + dx, y + dy
            if 1 <= nx < map_width-1 and 1 <= ny < map_height-1 and maze[ny][nx] == 1:
                neighbors.append((nx, ny))
        if neighbors:
            nx, ny = random.choice(neighbors)
            # 현재 위치와 선택 이웃 사이의 벽 허물기
            wall_x = x + (nx - x)//2
            wall_y = y + (ny - y)//2
            maze[wall_y][wall_x] = 0
            maze[ny][nx] = 0
            stack.append((nx, ny))  # 이동
        else:
            stack.pop()  # 백트래킹
    return maze

로그라이크 생성 방식 (Rogue-like Generation)

개요: 로그라이크 스타일 던전 생성은 전통적인 Rogue 게임의 절차를 따른 방법으로, 여러 방과 복도를 보다 규칙적인 구조로 배치합니다. 예를 들어, 원조 Rogue에서는 맵을 3x3 그리드 형태로 나누고 각 구역에 방이 생길 확률을 두어 최대 9개의 방을 배치했습니다. 그런 다음 인접한 방들 사이를 반드시 복도로 연결하여 전체 맵이 하나의 연결된 네트워크를 이루도록 했습니다. 현대적인 로그라이크 생성 방식도 이와 비슷하게, 랜덤 방 배치 알고리즘을 기반으로 하되 방의 위치를 격자 형태로 제한하고 인접 방들은 항상 통로로 연결되게 합니다​. 또한 게임마다 특별 규칙(예: 일부 방은 없앨 수도 있고, 중간에 교차로를 추가해 루프 생성 등)을 적용해 재미 요소를 높입니다.

장점: 게임 플레이 균형을 잡기 쉽습니다. 방들이 규칙적인 구역에 퍼져 있고 반드시 연결되므로 탐험할 수 없는 막힌 구역이 없습니다. 또한 복도를 일부러 구부러뜨리거나 교차시켜 전략적인 지형을 만들 수 있고, 방과 통로의 비율을 조절하기 수월합니다. 기본적으로 랜덤 방 배치의 장점을 모두 가지며, 구조적 일관성이 좀 더 있습니다.

단점: 자유도가 낮아 매번 비슷한 형태의 맵이 나올 수 있습니다. 격자 기반으로 방을 배치하면 패턴이 드러날 수 있으며, 지나치게 규칙적이면 던전이 인공적으로 보일 위험이 있습니다. 또한 복잡한 변형 규칙을 추가하지 않으면 단순 방-복도 나열에 그칠 수 있습니다.

탑다운 게임 적합성: ✅ 적합합니다. 로그라이크 장르 자체가 이 방식을 발전시켜왔으므로, 턴제 로그라이크나 던전 크롤러 등 탑다운 게임에 잘 어울립니다. 방 사이의 연결성이 높고 게임 진행에 문제가 없도록 설계하기에 용이하여 게임플레이 측면에서 안정적입니다.

로그라이크 방식 던전 생성은 일종의 하이브리드로 볼 수 있습니다. 기본은 랜덤 방 배치와 유사하지만 방 위치를 격자로 제한하고, 최소 신장 트리(MST) 등을 사용해 모든 방을 효율적으로 연결하는 등 추가 규칙이 있습니다. 아래 코드는 맵을 3x3 영역으로 나누어 각 영역에 방을 놓고, 방들 사이를 MST 기반으로 복도 연결하는 예시 구현입니다. 이는 원조 Rogue의 방식과 유사하게, 인접하지 않더라도 모든 방이 하나의 그래프를 이루도록 보장합니다. 

def generate_roguelike_dungeon(map_width, map_height, grid_rows=3, grid_cols=3):
    dungeon = [[1 for _ in range(map_width)] for _ in range(map_height)]
    region_w = (map_width - 2) // grid_cols
    region_h = (map_height - 2) // grid_rows
    room_centers = []
    # 각 그리드 셀마다 방을 놓을지 결정하고 생성
    for r in range(grid_rows):
        for c in range(grid_cols):
            rx1 = 1 + c * region_w
            ry1 = 1 + r * region_h
            rx2 = 1 + (c+1) * region_w if c < grid_cols-1 else map_width - 1
            ry2 = 1 + (r+1) * region_h if r < grid_rows-1 else map_height - 1
            # 80% 확률로 해당 구역에 방 생성
            if random.random() < 0.8:
                rw = random.randint(4, min(8, rx2 - rx1 - 1))
                rh = random.randint(4, min(8, ry2 - ry1 - 1))
                rx = random.randint(rx1, rx2 - rw - 1)
                ry = random.randint(ry1, ry2 - rh - 1)
                for y in range(ry, ry+rh):
                    for x in range(rx, rx+rw):
                        dungeon[y][x] = 0
                cx, cy = rx + rw//2, ry + rh//2
                room_centers.append((cx, cy))
            else:
                room_centers.append(None)
    # None 제거 (존재하는 방들의 중심 리스트)
    centers = [c for c in room_centers if c is not None]
    # 최소 신장 트리를 사용하여 모든 방 연결
    if centers:
        connected = [centers[0]]
        not_connected = centers[1:]
        while not_connected:
            c = connected[-1]
            nearest = min(not_connected, key=lambda t: (c[0]-t[0])**2 + (c[1]-t[1])**2)
            x1, y1 = c; x2, y2 = nearest
            if random.random() < 0.5:
                for x in range(min(x1, x2), max(x1, x2)+1):
                    dungeon[y1][x] = 0
                for y in range(min(y1, y2), max(y1, y2)+1):
                    dungeon[y][x2] = 0
            else:
                for y in range(min(y1, y2), max(y1, y2)+1):
                    dungeon[y][x1] = 0
                for x in range(min(x1, x2), max(x1, x2)+1):
                    dungeon[y2][x] = 0
            connected.append(nearest)
            not_connected.remove(nearest)
    return dungeon

파이게임을 사용한 알고리즘 데모

위에서 설명한 모든 알고리즘을 pygame-ce를 통해 시각적으로 확인할 수 있는 데모를 구현했습니다. 실행하면 하나의 창에 메인 메뉴가 표시되고, 사용자가 선택한 알고리즘으로 던전 지도를 생성한 후 2D 그리드 형태로 그려 보여줍니다. 메뉴로 돌아가 다른 알고리즘을 시도할 수도 있습니다. 각 알고리즘은 위에서 작성한 함수를 이용하여 맵을 생성하며, 벽은 어두운 색, 바닥(통로와 방)은 밝은 색으로 표시했습니다.

아래 코드를 실행하면 ESC 키 또는 창 닫기로 프로그램을 종료할 수 있고, 숫자 키 1~6을 눌러 각 알고리즘을 선택할 수 있습니다. 

import pygame
import random

# 앞서 정의한 던전 생성 함수들이 이미 있다고 가정합니다.
# generate_random_rooms, generate_bsp_dungeon, generate_cellular_cave,
# generate_drunkards_walk, generate_maze, generate_roguelike_dungeon 함수를 사용.

# 색상 정의
COLOR_FLOOR = (200, 200, 200)  # 바닥 색 (밝은 회색)
COLOR_WALL = (50, 50, 50)      # 벽 색 (어두운 회색)
COLOR_TEXT = (240, 240, 240)   # 메뉴 텍스트 색 (거의 흰색)
COLOR_BG = (30, 30, 30)       # 배경 색 (짙은 회색)

# 화면 크기 및 셀 크기
MAP_WIDTH, MAP_HEIGHT = 51, 51    # 맵 타일 개수 (51x51 격자)
CELL_SIZE = 10                   # 한 타일을 그릴 때의 픽셀 크기
SCREEN_WIDTH = MAP_WIDTH * CELL_SIZE
SCREEN_HEIGHT = MAP_HEIGHT * CELL_SIZE

# 파이게임 초기화
pygame.init()
screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))
pygame.display.set_caption("Dungeon Generation Demo")
font = pygame.font.SysFont(None, 24)

# 메뉴 표시 텍스트 렌더링 함수
def draw_menu():
    screen.fill(COLOR_BG)
    menu_lines = [
        "Select Dungeon Generation Algorithm:",
        "1 - Random Room Placement",
        "2 - Binary Space Partitioning (BSP)",
        "3 - Cellular Automata Cave",
        "4 - Drunkard's Walk Cave",
        "5 - Maze (Recursive Backtracking)",
        "6 - Rogue-like Generation",
        "ESC - Quit"
    ]
    # 화면 중앙에 메뉴 텍스트 표시
    start_y = SCREEN_HEIGHT // 2 - len(menu_lines)*15
    for i, line in enumerate(menu_lines):
        text_surf = font.render(line, True, COLOR_TEXT)
        text_rect = text_surf.get_rect(center=(SCREEN_WIDTH//2, start_y + i*30))
        screen.blit(text_surf, text_rect)
    pygame.display.flip()

# 던전 맵(grid)을 화면에 그리는 함수
def draw_dungeon(grid):
    for y in range(len(grid)):
        for x in range(len(grid[0])):
            color = COLOR_FLOOR if grid[y][x] == 0 else COLOR_WALL
            pygame.draw.rect(screen, color, (x*CELL_SIZE, y*CELL_SIZE, CELL_SIZE, CELL_SIZE))
    pygame.display.flip()

# 메인 루프
running = True
showing_menu = True
while running:
    if showing_menu:
        draw_menu()
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.KEYDOWN:
            if showing_menu:
                # 메뉴에서 키 입력 처리
                if event.key == pygame.K_ESCAPE:
                    running = False
                elif event.key == pygame.K_1:
                    dungeon_map = generate_random_rooms(MAP_WIDTH, MAP_HEIGHT)
                    showing_menu = False
                elif event.key == pygame.K_2:
                    dungeon_map = generate_bsp_dungeon(MAP_WIDTH, MAP_HEIGHT)
                    showing_menu = False
                elif event.key == pygame.K_3:
                    dungeon_map = generate_cellular_cave(MAP_WIDTH, MAP_HEIGHT)
                    showing_menu = False
                elif event.key == pygame.K_4:
                    dungeon_map = generate_drunkards_walk(MAP_WIDTH, MAP_HEIGHT)
                    showing_menu = False
                elif event.key == pygame.K_5:
                    dungeon_map = generate_maze(MAP_WIDTH, MAP_HEIGHT)
                    showing_menu = False
                elif event.key == pygame.K_6:
                    dungeon_map = generate_roguelike_dungeon(MAP_WIDTH, MAP_HEIGHT)
                    showing_menu = False
                if not showing_menu:
                    # 선택된 알고리즘의 던전 맵을 생성했으므로 그리기
                    draw_dungeon(dungeon_map)
            else:
                # 던전 표시 화면에서 키 누르면 메뉴로 돌아가기
                showing_menu = True

pygame.quit()

이 데모 프로그램을 실행하면, 각 알고리즘에 따라 다양한 스타일의 던전이 생성되어 나타나는 것을 확인할 수 있습니다. 예를 들어 랜덤 방 배치는 사각형 방 여러 개와 그 사이를 잇는 복도가 보이고, 셀룰러 오토마타는 불규칙하게 생긴 동굴 지형을 보여줄 것입니다. 이를 통해 앞서 설명한 알고리즘들의 특성을 직접 눈으로 비교해볼 수 있습니다.

See also

Favorite site

Creating a random 2d game world map

Samples

Tutorials

References

  1. Creating_a_random_2d_game_world_map_-_Part_1.pdf ↩

  2. Creating_a_random_2d_game_world_map_-_Part_2_Adding_rivers_and_lakes.pdf ↩

  3. Creating_a_random_2d_game_world_map_-_Part_3_Cities_caves_and_snow.pdf ↩