콘솔 로그라이크 BSP 던전 자동 생성

재귀 공간 분할과 Z자 복도, 1칸을 3칸으로

로그라이크는 층마다 맵이 달라야 하는데 100×100 타일을 손으로 그릴 수는 없다. 공간을 재귀로 쪼개 방을 놓고 트리를 거슬러 형제 방을 잇는 구조, 그리고 순회가 스스로를 오염시킨 문제.

게시 2026/03/25

By GoldBoll

8 분읽는 시간

콘솔 로그라이크 BSP 던전 자동 생성

팀 프로젝트로 만든 던전노조(가제)는 콘솔 화면 위에서 100×100 타일 던전을 내려가는 로그라이크 턴제 RPG다. 로그라이크인 이상 층마다 맵이 달라야 하는데, 100×100 타일을 손으로 그릴 수는 없다. 이 글에서는 그 던전을 매번 새로 만들어 내는 BSP 맵 자동 생성을 이야기하려 한다 — 공간을 재귀로 쪼개 방을 놓고 트리를 거슬러 올라가며 복도로 잇는 구현이 앞이고, 1칸 복도를 3칸으로 넓히다 순회가 스스로를 오염시킨 문제가 뒤의 트러블슈팅이다. 레퍼런스는 Shattered Pixel Dungeon.

전투·아이템·스폰 같은 나머지 시스템은 이 글의 주제에서 벗어나 덜어냈다. 기획 문서는 따로 모아 두었다: 스프레드시트, 플로우차트.excalidraw

맵을 만들려면 먼저 무엇을 찍을지가 있어야 하니, 타일 정의부터 본다.

맵과 타일

전체 맵은 100×100 타일이고, 각 층은 방 탐색 구조다 — 방마다 구조물(벽), 몬스터, 아이템을 배치한다. 다음 층 계단(>)은 방 리스트의 마지막 방에 생성한다.

타일 범례는 기획서와 구현 문서에 나뉘어 있던 것을 하나로 합쳤다.

기호	의미	10 이내면 생성 X
`#`	벽 (통과 불가)
`@`	플레이어 위치	X
`R`	바위 (좁은 장애물)
`W`	물 (넓은 장애물)
`M`	일반 몬스터
`E`	엘리트 몬스터
`B`	보스
`>`	계단 (다음 층)	X
`C`	보물 상자
(공백)	빈 공간 (이동 가능) — 투명 처리, 여기서만 생성

맵 자동 생성 — BSP 알고리즘

BSP(Binary Space Partitioning)는 공간을 재귀적으로 두 영역으로 계속 분할하는 알고리즘이다.

[전체 맵 공간]
        │
   ┌────┴────┐          ← 좌/우 (또는 상/하) 랜덤 분할
   │         │
 ┌─┴─┐     ┌─┴─┐        ← 다시 분할
 │   │     │   │
[방] [방] [방] [방]     ← 더 이상 분할 불가 → 각 영역에 방 하나씩 생성

전체 흐름은 다섯 단계다.

분할 — 공간이 최소 크기보다 크면 랜덤 방향(가로/세로)으로 절반씩 분할
방 생성 — 더 이상 분할할 수 없는 말단 영역(leaf)마다 랜덤 크기의 방 조각
복도 연결 — 트리를 거슬러 올라가며 형제 노드의 방 중심을 Z자형 복도로 연결
복도 확장 — 1칸 너비 복도를 4방향 팽창시켜 3칸 너비로 확장
방 타입 배정 — 첫 방 = Start, 마지막 방 = Stair, 나머지는 랜덤으로 Elite/Treasure/Normal 배정

코드에서는 이 흐름이 하나의 생성 파이프라인으로 이어진다.

Generate(map, params)
  │
  ├─ 1. map.Fill(Wall)          ← 전체 Wall로 초기화
  ├─ 2. BuildTree()             ← 파티션 재귀 분할 (BSP 트리 생성)
  ├─ 3. CarveRooms()            ← leaf 노드마다 랜덤 크기 방을 Floor로 조각
  ├─ 4. BuildRoomSnapshot()     ← 방 타일 스냅샷 저장 (복도/방 구분용)
  ├─ 5. ConnectTree()           ← Z자형 복도 중심선(1칸) 연결
  ├─ 6. DilateCorridor()        ← 복도를 4방향 팽창 → 3칸 너비로 확장
  ├─ 7. MarkDebugRoomWalls()    ← 방 경계 벽 색상 구분용 마킹
  └─ 8. AssignRoomTypes()       ← 방 타입 랜덤 배정

복도 구현 로직 상세

1단계 — HCorridor / VCorridor (복도 중심선 그리기)

  
// 수평 복도: 지정한 행(row)에서 startCol ~ endCol 구간을 Floor으로 채움
void HCorridor(Map& map, int startCol, int endCol, int row)
{
    for (int col = min(startCol,endCol); col <= max(startCol,endCol); ++col)
        map.SetTile(col, row, Tile::Floor);
}

// 수직 복도: 지정한 열(col)에서 startRow ~ endRow 구간을 Floor으로 채움
void VCorridor(Map& map, int col, int startRow, int endRow)
{
    for (int row = min(startRow,endRow); row <= max(startRow,endRow); ++row)
        map.SetTile(col, row, Tile::Floor);
}

2단계 — ConnectTree (Z자형 복도 연결)

모든 연결은 H복도 → V복도 → H복도 (Z자형) 또는 반대 순서로 이어진다.

[수직 분할: 좌||우]

  좌방 중심  spine열  우방 중심
      *──────── |           ← H복도
                |
                |───────*  ← V복도 → H복도

[수평 분할: 상=하]

  위방 중심
      *
      |             ← V복도
      |────────*  ← H복도
                |
                *   ← V복도
  아래방 중심

3단계 — DilateCorridor (1칸 → 3칸 확장)

 [확장 전]     [확장 후]

  # # # #      # # # #
  #   # #      #     #
  # # # #  →   #     #
  # # # #      #     #
  # # # #      # # # #

  중심선 1칸    주도 3칸

복도 중심선(Floor이면서 방이 아닌 타일)을 먼저 탐지한 뒤, 해당 타일의 4방향 좌표를 전부 수집해 두고 일괄로 Floor로 변환한다. 순회하면서 바로 타일을 바꾸면 방금 넓힌 칸이 다시 중심선으로 잡힐 수 있어서, 수집과 변환을 분리하는 방식이다.

핵심 요약 — BSP 던전 생성은 공간을 재귀 분할해 leaf마다 방을 만들고, 트리를 거슬러 올라가며 형제 노드의 방 중심을 Z자형 복도(H→V→H)로 잇는 구조다. 1칸 복도를 3칸으로 넓힐 때는 팽창 대상 좌표를 먼저 전부 수집한 뒤 일괄 변환해야 순회 중 오염이 없다.

회고

daily til

맵과 타일

맵 자동 생성 — BSP 알고리즘

복도 구현 로직 상세

인기 태그