# AI 꾸러미 — 방 + 복도 던전 (BSP) — BSP dungeon generation (binary space partitioning)
> 공간을 반씩 쪼개는 나무(BSP)를 만들고 잎마다 방 하나, 형제 칸끼리 꺾인 복도로 이어 늘 연결된 던전을 만든다.  
> 견본: https://ai-techstudio.web.app/#t/i247

이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요.

## 주문서

### 만들어 줘: 방 + 복도 던전 (BSP) — BSP dungeon generation (binary space partitioning)

#### 1. 목표
미로 탐험 던전을 BSP 로 만들어 줘 — 공간을 반씩 쪼개는 선 → 칸마다 방 → 형제끼리 복도 순서로 지어지는 모습이 보이게. 분위기는 도트 던전.

#### 2. 핵심 기술 용어
- **BSP dungeon generation (binary space partitioning)** — 공간을 반씩 쪼개 방 놓기
- **Leaf node room placement** — 더 안 쪼갠 칸마다 방 하나
- **L-shaped corridor** — 가로 먼저 · 세로 먼저 꺾인 복도

#### 3. 환경
- 플랫폼: HTML Canvas 2D (TypeScript), requestAnimationFrame 루프, 라이브러리 없이
- 화면: 2D · 브라우저 — PC 와 폰(390px 폭) 모두, devicePixelRatio 맞춰 또렷하게, 60fps 목표

#### 4. 조건
- 쪼개기는 너비 우선(큐)으로, 쪼갠 선 · 방 · 복도를 일어난 순서대로 사건 목록에 쌓아 하나씩 보여 주기
- 쪼갤 위치는 38~62% 사이 무작위 — 반반이면 판이 너무 반듯하다
- 방은 칸 경계에서 한 칸 이상 떨어뜨리기 (이웃 방과 붙지 않게)
- 복도는 방 칸을 덮어쓰지 않기 (빈 칸만 복도로)
- 시드 · 쪼개기 깊이 · 나누기 선 보기를 바꿀 수 있게

#### 5. 완성 기준 (이게 보이면 성공)
- 나누기 선이 깊이 순서대로 생기고, 그다음 방들, 그다음 복도가 이어진다
- 어떤 시드에서도 모든 방이 복도로 이어져 있다
- 깊이를 2 로 하면 큰 방 몇 개, 6 으로 하면 작은 방이 많다
- 시작(계단)과 끝(보물 상자)이 서로 다른 방에 놓인다

#### 6. 진행 방식
- 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘.
- 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘.
- 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘.
- 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘.
- 답변과 코드 주석은 한국어로 해 줘.

## 원리
- 판 전체(뿌리)를 가로나 세로로 38~62% 지점에서 둘로 쪼갠다. 길쭉한 쪽(비율 1.25 넘음)을 자르고, 비슷하면 동전 던지기.
- 정한 깊이(견본 4)에 닿거나 너무 작으면(폭 16 · 높이 12 미만) 그 칸은 잎이 된다.
- 잎마다 칸 크기의 40~78% 방을 칸 안에 하나 둔다.
- 나무를 아래에서부터 돌며 두 형제 쪽에서 방을 하나씩 골라, 가로 먼저 또는 세로 먼저로 꺾인 복도를 잇는다 — 형제끼리 다 이어지니 던전 전체가 하나로 이어진다.

## 핵심 코드 — BSP 쪼개기 → 잎마다 방 → 형제끼리 복도
(발췌: demos/demosMapA.ts i247 start() 를 정리)
```ts
interface Node { x: number; y: number; w: number; h: number; d: number; a?: Node; b?: Node; room?: [number, number, number, number] }
const root: Node = { x: 1, y: 1, w: TW - 2, h: TH - 2, d: 0 };
const q: Node[] = [root], leaves: Node[] = [];
while (q.length) {
  const n = q.shift()!;
  const canV = n.w >= 16, canH = n.h >= 12;
  if (n.d >= maxDepth || (!canV && !canH)) { leaves.push(n); continue; }
  let vert = n.w / n.h > 1.25 ? true : n.h / n.w > 1.25 ? false : r() < 0.5; // 길쭉한 쪽을 자른다
  if (vert && !canV) vert = false;
  if (!vert && !canH) vert = true;
  if (vert) {
    const sx = Math.round(n.w * (0.38 + r() * 0.24));
    n.a = { x: n.x, y: n.y, w: sx, h: n.h, d: n.d + 1 };
    n.b = { x: n.x + sx, y: n.y, w: n.w - sx, h: n.h, d: n.d + 1 };
  } else {
    const sy = Math.round(n.h * (0.38 + r() * 0.24));
    n.a = { x: n.x, y: n.y, w: n.w, h: sy, d: n.d + 1 };
    n.b = { x: n.x, y: n.y + sy, w: n.w, h: n.h - sy, d: n.d + 1 };
  }
  q.push(n.a, n.b);
}
for (const n of leaves) { // 칸의 40~78% 방
  const rw = ri(Math.max(4, Math.floor(n.w * 0.4)), Math.max(4, Math.floor(n.w * 0.78)));
  const rh = ri(Math.max(3, Math.floor(n.h * 0.4)), Math.max(3, Math.floor(n.h * 0.78)));
  n.room = [n.x + ri(1, n.w - rw - 1), n.y + ri(1, n.h - rh - 1), rw, rh];
}
const pick = (n: Node): [number, number, number, number] => n.room ?? pick(r() < 0.5 ? n.a! : n.b!);
const walk = (n: Node): void => {
  if (!n.a || !n.b) return;
  walk(n.a); walk(n.b);
  corridor(pick(n.a), pick(n.b), r() < 0.5); // 두 방 안의 한 점끼리 가로 먼저 / 세로 먼저 꺾인 길
};
walk(root);
```

## 흔한 실수 · 확인 목록
- [ ] **쪼갤 위치를 늘 반으로 하면 판이 바둑판처럼 반듯하다** — 38~62% 사이에서 무작위로, 길쭉한 칸은 긴 쪽을 자른다.
- [ ] **작은 칸까지 쪼개면 방이 안 들어간다** — 폭 16 · 높이 12 미만이면 더 쪼개지 않고 잎으로 둔다.
- [ ] **방끼리 아무렇게나 이으면 떨어진 방이 생긴다** — 나무를 아래에서부터 돌며 형제 쪽끼리 이으면 전체가 반드시 하나로 이어진다.

## 완성 기준 체크리스트
- [ ] 나누기 선이 깊이 순서대로 생기고, 그다음 방들, 그다음 복도가 이어진다
- [ ] 어떤 시드에서도 모든 방이 복도로 이어져 있다
- [ ] 깊이를 2 로 하면 큰 방 몇 개, 6 으로 하면 작은 방이 많다
- [ ] 시작(계단)과 끝(보물 상자)이 서로 다른 방에 놓인다

## 이 기술 정보
- id: `i247` · 분류: 지도 · 길찾기 › 지도 생성 (절차) · 2D · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 64×40 칸 · 깊이 4 = 잎 16개 안팎. 짓기는 한순간이고, 견본은 보여 주려고 일부러 한 단계씩 나눠 그린다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i247
- 쓰면 좋을 때: 방과 복도가 또렷한 던전 · 건물 지도 / 방 개수 · 크기를 대략 조절하고 싶을 때 / 모든 방이 반드시 이어져야 할 때
- 쓰지 말 때: 자연스러운 동굴 — 대신 셀룰러 오토마타 동굴(i248) / 길이 꼬불꼬불한 미로 — 대신 미로 생성(i250)

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### i247 견본 항목 — `src/demos/demosMapA.ts:857`
```ts
  i247: {
    kind: '2d',
    caption: '공간을 반씩 쪼개고(BSP) → 칸마다 방 하나 → 형제 칸끼리 복도로 이어 던전 완성',
    make() {
      const TW = 64;
      const TH = 40;
      interface Node { x: number; y: number; w: number; h: number; d: number; a?: Node; b?: Node; room?: [number, number, number, number]; split?: [number, number, number, number] }
      type Ev = { k: 'split'; n: Node } | { k: 'room'; n: Node } | { k: 'cor'; path: P2[] } | { k: 'deco' };
      let map = new Uint8Array(TW * TH); // 0 빈 곳 1 방 2 복도
      let evs: Ev[] = [];
      let ei = 0;
      let wait = 0;
      let curT = 0;
      let curDur = 1;
      let splits: Node[] = [];
      let rooms: Node[] = [];
      let deco = false;
      let showLines = true;
      let maxDepth = 4;
      let dirty = true;
      let off = mkCanvas(1, 1);
      let offW = 0;
      let offH = 0;
      let chest: P2 = [0, 0];
      let stairs: P2 = [0, 0];
      const run = runner({
        rate: 60,
        hold: 2,
        start(seed) {
          const r = mulberry(seed);
          const ri = (a: number, b: number): number => a + Math.floor(r() * (b - a + 1));
          map = new Uint8Array(TW * TH);
          evs = [];
          splits = [];
          rooms = [];
          deco = false;
          ei = 0;
          wait = 0;
          dirty = true;
          const root: Node = { x: 1, y: 1, w: TW - 2, h: TH - 2, d: 0 };
          const q: Node[] = [root];
          const leaves: Node[] = [];
          while (q.length) {
            const n = q.shift()!;
            const canV = n.w >= 16;
            const canH = n.h >= 12;
            if (n.d >= maxDepth || (!canV && !canH)) {
              leaves.push(n);
              continue;
            }
            let vert = n.w / n.h > 1.25 ? true : n.h / n.w > 1.25 ? false : r() < 0.5;
            if (vert && !canV) vert = false;
            if (!vert && !canH) vert = true;
            if (vert) {
              const sx = Math.round(n.w * (0.38 + r() * 0.24));
              n.a = { x: n.x, y: n.y, w: sx, h: n.h, d: n.d + 1 };
              n.b = { x: n.x + sx, y: n.y, w: n.w - sx, h: n.h, d: n.d + 1 };
              n.split = [n.x + sx, n.y, n.x + sx, n.y + n.h];
            } else {
              const sy = Math.round(n.h * (0.38 + r() * 0.24));
              n.a = { x: n.x, y: n.y, w: n.w, h: sy, d: n.d + 1 };
              n.b = { x: n.x, y: n.y + sy, w: n.w, h: n.h - sy, d: n.d + 1 };
              n.split = [n.x, n.y + sy, n.x + n.w, n.y + sy];
            }
            evs.push({ k: 'split', n });
            q.push(n.a, n.b);
          }
          for (const n of leaves) {
            const rw = ri(Math.max(4, Math.floor(n.w * 0.4)), Math.max(4, Math.floor(n.w * 0.78)));
            const rh = ri(Math.max(3, Math.floor(n.h * 0.4)), Math.max(3, Math.floor(n.h * 0.78)));
            const rx = n.x + ri(1, n.w - rw - 1);
            const ry = n.y + ri(1, n.h - rh - 1);
            n.room = [rx, ry, rw, rh];
            evs.push({ k: 'room', n });
          }
          const pick = (n: Node): [number, number, number, number] => {
            if (n.room) return n.room;
            return pick(r() < 0.5 ? n.a! : n.b!);
          };
          const cors: Ev[] = [];
          const walk = (n: Node): void => {
            if (!n.a || !n.b) return;
            walk(n.a);
            walk(n.b);
            const A = pick(n.a);
            const B = pick(n.b);
            const ax = ri(A[0] + 1, A[0] + A[2] - 2);
            const ay = ri(A[1] + 1, A[1] + A[3] - 2);
            const bx = ri(B[0] + 1, B[0] + B[2] - 2);
            const by = ri(B[1] + 1, B[1] + B[3] - 2);
            const path: P2[] = [];
            const hFirst = r() < 0.5;
            let x = ax;
            let y = ay;
            path.push([x, y]);
            const goX = (): void => {
              while (x !== bx) {
                x += Math.sign(bx - x);
                path.push([x, y]);
              }
            };
            const goY = (): void => {
              while (y !== by) {
                y += Math.sign(by - y);
                path.push([x, y]);
              }
            };
            if (hFirst) {
              goX();
              goY();
            } else {
              goY();
              goX();
            }
            cors.push({ k: 'cor', path });
          };
          walk(root);
          evs.push(...cors, { k: 'deco' });
          const rs = leaves.map((n) => n.room!);
          const c0 = rs[0]!;
          const c1 = rs[rs.length - 1]!;
          stairs = [c0[0] + 1, c0[1] + 1];
          chest = [c1[0] + c1[2] - 2, c1[1] + 1];
        },
        step() {
          curT++;
          if (wait-- > 0) return false;
          const e = evs[ei++];
          if (!e) return true;
          curT = 0;
          if (e.k === 'split') {
            splits.push(e.n);
            curDur = 12;
          } else if (e.k === 'room') {
            const [rx, ry, rw, rh] = e.n.room!;
            for (let y = ry; y < ry + rh; y++) for (let x = rx; x < rx + rw; x++) map[y * TW + x] = 1;
            rooms.push(e.n);
            curDur = 7;
          } else if (e.k === 'cor') {
            for (const [x, y] of e.path) if (!map[y * TW + x]) map[y * TW + x] = 2;
            curDur = 9;
          } else {
            deco = true;
            curDur = 6;
          }
          wait = curDur;
          dirty = true;
          return false;
        },
      });
      run.restart();
      const renderOff = (w: number, h: number): void => {
        if (offW !== w || offH !== h) {
          off = mkCanvas(w, h);
          offW = w;
          offH = h;
          dirty = true;
        }
        if (!dirty) return;
        dirty = false;
        const g = c2(off);
        const ts = Math.min(w / TW, h / TH);
        const ox = (w - TW * ts) / 2;
        const oy = (h - TH * ts) / 2;
        g.fillStyle = '#16131c';
        g.fillRect(0, 0, w, h);
        g.fillStyle = 'rgba(255,255,255,0.035)';
        for (let y = 0; y < TH; y += 2) for (let x = (y / 2) % 2; x < TW; x += 2) g.fillRect(ox + x * ts + ts * 0.45, oy + y * ts + ts * 0.45, ts * 0.12, ts * 0.12);
        const at = (x: number, y: number): number => (x < 0 || y < 0 || x >= TW || y >= TH ? 0 : map[y * TW + x]!);
        // 벽
        for (let y = 0; y < TH; y++)
          for (let x = 0; x < TW; x++) {
            if (at(x, y)) continue;
            let near = false;
            for (const [dx, dy] of N8) if (at(x + dx, y + dy)) near = true;
            if (!near) continue;
            const X = ox + x * ts;
            const Y = oy + y * ts;
            g.fillStyle = '#3c3244';
            g.fillRect(X, Y, ts + 0.5, ts + 0.5);
            g.fillStyle = '#5d4f66';
            g.fillRect(X, Y, ts + 0.5, ts * 0.42);
            if (at(x, y + 1)) {
              g.fillStyle = '#251e2b';
              g.fillRect(X, Y + ts * 0.42, ts + 0.5, ts * 0.58);
              g.fillStyle = 'rgba(255,255,255,0.08)';
              g.fillRect(X + ts * 0.1, Y + ts * 0.62, ts * 0.35, ts * 0.12);
            }
          }
        // 바닥
        for (let y = 0; y < TH; y++)
          for (let x = 0; x < TW; x++) {
            const v = at(x, y);
            if (!v) continue;
            const X = ox + x * ts;
            const Y = oy + y * ts;
            const n = hash2(x, y, 9);
            const base: V3 = v === 1 ? [190, 158, 112] : [150, 124, 92];
            const c = mix(base, [120, 96, 70], n * 0.35);
            g.fillStyle = rgb(c);
            g.fillRect(X, Y, ts + 0.5, ts + 0.5);
            g.fillStyle = 'rgba(60,40,20,0.25)';
            g.fillRect(X, Y + ts - Math.max(1, ts * 0.08), ts, Math.max(1, ts * 0.08));
            g.fillRect(X + ts - Math.max(1, ts * 0.08), Y, Math.max(1, ts * 0.08), ts);
            if (at(x, y - 1) === 0) {
              g.fillStyle = 'rgba(20,10,20,0.35)';
              g.fillRect(X, Y, ts, ts * 0.3);
            }
          }
      };
      return {
        draw(g, w, h, t, dt) {
          reset(g);
          run.tick(dt);
          renderOff(Math.round(w), Math.round(h));
          g.drawImage(off, 0, 0, w, h);
          const u = ui(scaleOf(w, h));
          const ts = Math.min(w / TW, h / TH);
          const ox = (w - TW * ts) / 2;
          const oy = (h - TH * ts) / 2;
          // 방 등불
          if (deco) {
            g.globalCompositeOperation = 'lighter';
            for (const n of rooms) {
              const [rx, ry, rw, rh] = n.room!;
              const cx = ox + (rx + rw / 2) * ts;
              const cy = oy + (ry + rh / 2) * ts;
              const R = Math.max(rw, rh) * ts * 0.75;
              const fl = 0.85 + Math.sin(t * 7 + rx) * 0.08;
              const gr = g.createRadialGradient(cx, cy, 0, cx, cy, R);
              gr.addColorStop(0, `rgba(255,170,80,${0.13 * fl})`);
              gr.addColorStop(1, 'rgba(255,120,40,0)');
              g.fillStyle = gr;
              g.fillRect(cx - R, cy - R, R * 2, R * 2);
              // 횃불
              const tx = ox + (rx + 0.5) * ts;
              const ty = oy + (ry - 0.55) * ts;
              const fr = g.createRadialGradient(tx, ty, 0, tx, ty, ts * 1.6);
              fr.addColorStop(0, `rgba(255,220,120,${0.9 * fl})`);
              fr.addColorStop(1, 'rgba(255,120,30,0)');
              g.fillStyle = fr;
              g.fillRect(tx - ts * 2, ty - ts * 2, ts * 4, ts * 4);
            }
            g.globalCompositeOperation = 'source-over';
            // 계단 · 보물 상자
            const sx = ox + stairs[0] * ts;
            const sy = oy + stairs[1] * ts;
            for (let k = 0; k < 4; k++) {
              g.fillStyle = k % 2 ? '#2a2230' : '#7a6a80';
              g.fillRect(sx, sy + k * ts * 0.4, ts * 1.6, ts * 0.4);
            }
            const cx = ox + chest[0] * ts;
            const cy = oy + chest[1] * ts;
            rr(g, cx, cy + ts * 0.2, ts * 1.5, ts * 1.1, ts * 0.2);
            g.fillStyle = '#8a4b1f';
            g.fill();
            g.fillStyle = '#f1c40f';
            g.fillRect(cx, cy + ts * 0.6, ts * 1.5, ts * 0.18);
            g.fillRect(cx + ts * 0.65, cy + ts * 0.5, ts * 0.2, ts * 0.4);
          }
          // 나누기 선
          if (showLines) {
            const fade = run.holding ? 1 - smooth(0.2, 1.2, run.holdT) * 0.75 : 1;
            g.lineCap = 'round';
            splits.forEach((n, i) => {
              const s = n.split!;
              const last = i === splits.length - 1 && rooms.length === 0;
              const k = last ? ease(curT / 12) : 1;
              const hue = 45 + n.d * 55;
              g.strokeStyle = `hsla(${hue},85%,65%,${0.85 * fade})`;
              g.lineWidth = Math.max(1, (2.6 - n.d * 0.45) * u);
              g.setLineDash([5 * u, 3 * u]);
              g.beginPath();
              const x0 = ox + s[0] * ts;
              const y0 = oy + s[1] * ts;
              const x1 = ox + s[2] * ts;
              const y1 = oy + s[3] * ts;
              g.moveTo(x0, y0);
              g.lineTo(lerp(x0, x1, k), lerp(y0, y1, k));
              g.stroke();
            });
            g.setLineDash([]);
            g.strokeStyle = `rgba(255,220,140,${0.5 * fade})`;
            g.lineWidth = 1.5 * u;
            g.strokeRect(ox + ts, oy + ts, (TW - 2) * ts, (TH - 2) * ts);
          }
          const stage = run.holding ? `던전 완성 · 방 ${rooms.length}개` : rooms.length === 0 ? `① 반씩 쪼개기 ${splits.length}번` : !deco && evs[ei - 1]?.k === 'room' ? `② 칸마다 방 ${rooms.length}개` : '③ 형제 칸끼리 복도 잇기';
          pill(g, stage, 8 * ui(u), 13 * ui(u), 9 * ui(u), 'rgba(20,14,28,0.85)', '#ffe6b0');
        },
        controls: [
          seedCtl(run),
          speedCtl(run),
          { type: 'toggle', label: '나누기 선 보기', value: true, on: (v) => { showLines = v; } },
          { type: 'range', label: '쪼개기 깊이', min: 2, max: 6, step: 1, value: 4, on: (v) => { maxDepth = v; run.restart(run.seed); } },
        ],
      };
    },
  }
```

## 관련 기술
- 먼저 알면 좋은 기술: [시드 지도 (같은 수 = 같은 지도)](https://ai-techstudio.web.app/ai/t/i255.md) `i255`
- 다음에 해 볼 기술: [동굴 (셀룰러 오토마타)](https://ai-techstudio.web.app/ai/t/i248.md) `i248` · [A* 길찾기 (열린 · 닫힌 칸 보기)](https://ai-techstudio.web.app/ai/t/i264.md) `i264` · [시야 · 가림 (그림자 던지기 FOV)](https://ai-techstudio.web.app/ai/t/i268.md) `i268`
- 참고 문서: [RogueBasin — Basic BSP Dungeon generation](https://www.roguebasin.com/index.php/Basic_BSP_Dungeon_generation)