# AI 꾸러미 — 공간 나누기 (쿼드트리) — Quadtree
> 물체가 많은 칸만 4칸씩 더 쪼개는 쿼드트리를 만들어, 범위 찾기 · 충돌 검사 때 겹치는 칸 안의 물체만 열어 보아 검사 수를 크게 줄인다.  
> 견본: https://ai-techstudio.web.app/#t/i263

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

## 주문서

### 만들어 줘: 공간 나누기 (쿼드트리) — Quadtree

#### 1. 목표
몰려다니는 물체 수백 개를 쿼드트리로 빠르게 찾게 해 줘 — 물체가 칸 용량(4)을 넘으면 그 칸만 4칸으로 쪼개고(최대 깊이 7), 찾을 땐 상자와 겹치는 칸만 연다. 화면은 칸 선 · 검사 수가 보이는 설명 화면.

#### 2. 핵심 기술 용어
- **Quadtree** — 네모를 넷으로 계속 쪼개는 공간 나무
- **Spatial partitioning** — 공간 나누기 — 가까운 것만 찾기
- **Range query (AABB overlap)** — 상자 안 물체 찾기 — 겹치지 않는 칸은 통째로 건너뜀
- **Node capacity · max depth** — 칸 하나에 둘 물체 수 · 최대 깊이

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

#### 4. 조건
- 칸 용량(cap)과 최대 깊이(7)를 둬서 같은 자리에 겹친 물체로 끝없이 쪼개지지 않게
- 쪼갤 때 들어 있던 물체를 아이 칸으로 다시 나누기
- 찾기에서 겹치지 않는 칸은 아래를 통째로 건너뛰기
- 검사 수 / 전체 수를 화면에 보여 주기 (효과 확인)
- 물체 수 · 칸 용량 조절, 칸 선 보기 켬/끔

#### 5. 완성 기준 (이게 보이면 성공)
- 물체가 몰린 곳만 칸이 잘게 쪼개지고, 무리가 움직이면 칸도 따라 바뀐다
- 노란 찾기 상자가 지나가면 겹친 칸만 노랗게 열리고, 검사 수가 전체 수보다 훨씬 적다
- 칸 용량을 키우면 칸이 덜 쪼개지고 검사 수가 는다
- 찾은 물체 수는 모두 검사했을 때와 같다

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

## 원리
- 전체 네모가 뿌리 칸. 물체를 넣다가 칸에 4개(cap)를 넘으면 그 칸을 4칸으로 쪼개고, 들어 있던 물체를 아이 칸으로 다시 나눈다. 깊이는 7까지.
- 물체가 몰린 곳만 잘게, 빈 곳은 큰 칸 그대로 — 고른 격자보다 몰림에 강하다.
- 찾기(질의): 칸이 찾는 상자와 안 겹치면 그 아래는 통째로 건너뛴다. 겹치는 잎 칸 안 물체만 하나씩 검사한다.
- 견본은 물체가 움직이므로 매 프레임 나무를 새로 짓는다 (260개 · 짓기 가벼움). 검사 수(checked)를 모든 물체 수와 비교해 보여 준다.

## 핵심 코드 — 쿼드트리 짓기 (용량 넘으면 쪼개기) + 상자 찾기
(발췌: demos/demosMapA.ts i263 build() · q() 를 정리)
```ts
interface Pt { x: number; y: number } // 0~1 좌표
interface QN { x: number; y: number; s: number; d: number; items: number[]; kids: QN[] | null }

function build(pts: Pt[], cap = 4, maxDepth = 7): QN {
  const root: QN = { x: 0, y: 0, s: 1, d: 0, items: [], kids: null };
  const ins = (n: QN, i: number): void => {
    if (n.kids) {
      const p = pts[i]!;
      const k = (p.x >= n.x + n.s / 2 ? 1 : 0) + (p.y >= n.y + n.s / 2 ? 2 : 0); // 0 왼위 1 오위 2 왼아 3 오아
      ins(n.kids[k]!, i);
      return;
    }
    n.items.push(i);
    if (n.items.length > cap && n.d < maxDepth) { // 넘치면 넷으로
      const h = n.s / 2;
      n.kids = [
        { x: n.x, y: n.y, s: h, d: n.d + 1, items: [], kids: null },
        { x: n.x + h, y: n.y, s: h, d: n.d + 1, items: [], kids: null },
        { x: n.x, y: n.y + h, s: h, d: n.d + 1, items: [], kids: null },
        { x: n.x + h, y: n.y + h, s: h, d: n.d + 1, items: [], kids: null },
      ];
      const it = n.items;
      n.items = [];
      for (const j of it) ins(n, j); // 들어 있던 것 다시 나누기
    }
  };
  for (let i = 0; i < pts.length; i++) ins(root, i);
  return root;
}

function query(n: QN, pts: Pt[], qx: number, qy: number, qw: number, qh: number, out: number[], stat = { checked: 0 }) {
  if (n.x > qx + qw || n.x + n.s < qx || n.y > qy + qh || n.y + n.s < qy) return; // 안 겹치면 통째로 건너뜀
  if (n.kids) { for (const k of n.kids) query(k, pts, qx, qy, qw, qh, out, stat); return; }
  for (const i of n.items) {
    stat.checked++;
    const p = pts[i]!;
    if (p.x >= qx && p.x <= qx + qw && p.y >= qy && p.y <= qy + qh) out.push(i);
  }
}
// 매 프레임: const root = build(pts); const found: number[] = []; query(root, pts, qx, qy, 0.26, 0.2, found);
```

## 흔한 실수 · 확인 목록
- [ ] **같은 자리에 물체가 많으면 끝없이 쪼개진다** — 최대 깊이(7)를 둔다. 그 깊이에선 용량을 넘어도 그냥 담는다.
- [ ] **쪼갠 뒤 원래 물체를 옮기지 않으면 찾기에서 빠진다** — 쪼갤 때 들어 있던 물체를 아이 칸으로 다시 넣는다.
- [ ] **크기 있는 물체를 점으로만 넣으면 칸 경계에 걸친 충돌을 놓친다** — 찾을 상자를 물체 반지름만큼 넓혀 묻거나, 걸친 물체는 부모 칸에 둔다.
- [ ] **물체가 고르게 퍼져 있는데 쿼드트리를 쓰면 이득이 적다** — 그럴 땐 고른 격자 칸(해시)이 더 단순하다.

## 완성 기준 체크리스트
- [ ] 물체가 몰린 곳만 칸이 잘게 쪼개지고, 무리가 움직이면 칸도 따라 바뀐다
- [ ] 노란 찾기 상자가 지나가면 겹친 칸만 노랗게 열리고, 검사 수가 전체 수보다 훨씬 적다
- [ ] 칸 용량을 키우면 칸이 덜 쪼개지고 검사 수가 는다
- [ ] 찾은 물체 수는 모두 검사했을 때와 같다

## 이 기술 정보
- id: `i263` · 분류: 2D · 화면 › 2D 움직임 · 충돌 · 2D · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 짓기는 물체 수 × 깊이 정도 (260개면 아주 가볍다). 찾기는 모두 검사(260번) 대신 겹친 칸 안 몇십 개.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i263
- 쓰면 좋을 때: 물체가 수백 개 넘고 한곳에 몰려다닐 때 / 「이 근처에 뭐가 있나」를 자주 물을 때 (충돌 · 클릭 · 시야)
- 쓰지 말 때: 물체가 수십 개뿐 — 그냥 전부 검사하는 게 빠르다 / 물체가 화면에 고르게 퍼져 있을 때 — 고른 격자(칸 해시)가 더 단순하고 빠르다

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### txt — `src/demos/demosMapA.ts:86`
```ts
function txt(g: G, s: string, x: number, y: number, size: number, color = '#fff', align: CanvasTextAlign = 'center', weight = 700): void {
  g.font = `${weight} ${size}px ${F}`;
  g.textAlign = align;
  g.textBaseline = 'middle';
  g.fillStyle = color;
  g.fillText(s, x, y);
}
```

### i263 견본 항목 — `src/demos/demosMapA.ts:4734`
```ts
  i263: {
    kind: '2d',
    caption: '물체가 많은 칸만 4칸으로 더 쪼개기(쿼드트리) — 노란 상자 안을 찾을 때 겹치는 칸만 열어 보니 검사 수가 확 줄어요',
    make() {
      let N = 260;
      let cap = 4;
      let query = true;
      let lines = true;
      interface Pt { x: number; y: number; vx: number; vy: number; cl: number }
      let pts: Pt[] = [];
      const gen = (): void => {
        pts = [];
        for (let i = 0; i < N; i++) {
          const cl = i < N * 0.6 ? (i % 2) + 1 : 0;
          if (cl) {
            // 무리 점은 vx, vy 에 무리 가운데로부터의 자리(가우스)를 담는다
            const r = Math.sqrt(-2 * Math.log(Math.random() + 1e-9)) * 0.065;
            const a = Math.random() * TAU;
            pts.push({ x: 0.5, y: 0.5, vx: Math.cos(a) * r, vy: Math.sin(a) * r, cl });
          } else pts.push({ x: Math.random(), y: Math.random(), vx: (Math.random() - 0.5) * 0.05, vy: (Math.random() - 0.5) * 0.05, cl });
        }
      };
      gen();
      interface QN { x: number; y: number; s: number; d: number; items: number[]; kids: QN[] | null }
      const build = (): QN => {
        const root: QN = { x: 0, y: 0, s: 1, d: 0, items: [], kids: null };
        const ins = (n: QN, i: number): void => {
          if (n.kids) {
            const p = pts[i]!;
            const k = (p.x >= n.x + n.s / 2 ? 1 : 0) + (p.y >= n.y + n.s / 2 ? 2 : 0);
            ins(n.kids[k]!, i);
            return;
          }
          n.items.push(i);
          if (n.items.length > cap && n.d < 7) {
            const h2 = n.s / 2;
            n.kids = [
              { x: n.x, y: n.y, s: h2, d: n.d + 1, items: [], kids: null },
              { x: n.x + h2, y: n.y, s: h2, d: n.d + 1, items: [], kids: null },
              { x: n.x, y: n.y + h2, s: h2, d: n.d + 1, items: [], kids: null },
              { x: n.x + h2, y: n.y + h2, s: h2, d: n.d + 1, items: [], kids: null },
            ];
            const it = n.items;
            n.items = [];
            for (const j of it) ins(n, j);
          }
        };
        for (let i = 0; i < pts.length; i++) ins(root, i);
        return root;
      };
      return {
        draw(g, w, h, t, dt) {
          reset(g);
          const d = Math.min(dt, 0.05);
          // 무리 둘이 빙빙 돌며 몰려다님
          const c1x = 0.5 + Math.cos(t * 0.5) * 0.28;
          const c1y = 0.5 + Math.sin(t * 0.7) * 0.28;
          const c2x = 0.5 + Math.cos(t * 0.37 + 2) * 0.3;
          const c2y = 0.5 + Math.sin(t * 0.45 + 1) * 0.3;
          for (const p of pts) {
            if (p.cl) {
              // 무리 점: 무리 가운데 + 제 자리(가우스) 를 천천히 돌림
              const tx = p.cl === 1 ? c1x : c2x;
              const ty = p.cl === 1 ? c1y : c2y;
              const a = t * (p.cl === 1 ? 0.6 : -0.45);
              const sx = p.vx * Math.cos(a) - p.vy * Math.sin(a);
              const sy = p.vx * Math.sin(a) + p.vy * Math.cos(a);
              p.x = clamp(tx + sx, 0.001, 0.999);
              p.y = clamp(ty + sy, 0.001, 0.999);
              continue;
            }
            p.x += p.vx * d;
            p.y += p.vy * d;
            if (p.x < 0.002 || p.x > 0.998) p.vx *= -1;
            if (p.y < 0.002 || p.y > 0.998) p.vy *= -1;
            p.x = clamp(p.x, 0.001, 0.999);
            p.y = clamp(p.y, 0.001, 0.999);
          }
          const root = build();
          const u = ui(scaleOf(w, h));
          g.fillStyle = '#0a1020';
          g.fillRect(0, 0, w, h);
          const S = Math.min(w - 16 * u, h - 10 * u);
          const ox = (w - S) / 2 + (w > S * 1.4 ? S * 0.22 : 0);
          const oy = (h - S) / 2;
          // 질의 상자
          const qw = 0.26;
          const qh = 0.2;
          const qx = 0.5 + Math.cos(t * 0.31) * 0.34 - qw / 2;
          const qy = 0.5 + Math.sin(t * 0.43) * 0.36 - qh / 2;
          let checked = 0;
          let found = 0;
          const visited = new Set<QN>();
          const hit = new Set<number>();
          const seen = new Set<number>();
          const q = (n: QN): void => {
            if (n.x > qx + qw || n.x + n.s < qx || n.y > qy + qh || n.y + n.s < qy) return;
            visited.add(n);
            if (n.kids) {
              for (const k of n.kids) q(k);
              return;
            }
            for (const i of n.items) {
              checked++;
              seen.add(i);
              const p = pts[i]!;
              if (p.x >= qx && p.x <= qx + qw && p.y >= qy && p.y <= qy + qh) {
                found++;
                hit.add(i);
              }
            }
          };
          if (query) q(root);
          // 칸
          let leaves = 0;
          const drawN = (n: QN): void => {
            if (n.kids) {
              for (const k of n.kids) drawN(k);
              if (lines) {
                g.strokeStyle = `hsla(${190 + n.d * 22},80%,${62 + n.d * 3}%,${0.75 - n.d * 0.07})`;
                g.lineWidth = Math.max(0.6, (2.2 - n.d * 0.28) * u);
                g.beginPath();
                g.moveTo(ox + (n.x + n.s / 2) * S, oy + n.y * S);
                g.lineTo(ox + (n.x + n.s / 2) * S, oy + (n.y + n.s) * S);
                g.moveTo(ox + n.x * S, oy + (n.y + n.s / 2) * S);
                g.lineTo(ox + (n.x + n.s) * S, oy + (n.y + n.s / 2) * S);
                g.stroke();
              }
              return;
            }
            leaves++;
            if (query && visited.has(n)) {
              g.fillStyle = 'rgba(255,214,74,0.13)';
              g.fillRect(ox + n.x * S, oy + n.y * S, n.s * S, n.s * S);
            } else if (n.items.length) {
              g.fillStyle = `rgba(90,180,255,${0.03 + n.d * 0.012})`;
              g.fillRect(ox + n.x * S, oy + n.y * S, n.s * S, n.s * S);
            }
          };
          g.fillStyle = '#111a30';
          g.fillRect(ox, oy, S, S);
          drawN(root);
          g.strokeStyle = 'rgba(120,200,255,0.7)';
          g.lineWidth = 1.5 * u;
          g.strokeRect(ox, oy, S, S);
          // 점
          for (let i = 0; i < pts.length; i++) {
            const p = pts[i]!;
            const x = ox + p.x * S;
            const y = oy + p.y * S;
            const isHit = hit.has(i);
            const isSeen = seen.has(i);
            g.beginPath();
            g.arc(x, y, (isHit ? 2.6 : 1.8) * u, 0, TAU);
            g.fillStyle = isHit ? '#ff8a3a' : isSeen ? '#fff3b0' : '#8fd0ff';
            g.fill();
          }
          if (query) {
            g.strokeStyle = '#ffd54a';
            g.lineWidth = 2 * u;
            g.setLineDash([5 * u, 3 * u]);
            g.strokeRect(ox + qx * S, oy + qy * S, qw * S, qh * S);
            g.setLineDash([]);
          }
          // 정보
          const ix = w > S * 1.4 ? 8 * u : ox + 4 * u;
          const lines2: [string, string][] = query
            ? [
                [`칸 ${leaves}개 · 점 ${pts.length}개`, '#cfe0ff'],
                [`검사 ${checked}번`, '#ffe680'],
                [`(쪼개기 없으면 ${pts.length}번)`, '#8a97b4'],
                [`찾음 ${found}개`, '#ff9a5a'],
              ]
            : [[`칸 ${leaves}개 · 점 ${pts.length}개`, '#cfe0ff']];
          if (w > S * 1.4) {
            lines2.forEach(([s, c], i) => txt(g, s, ix, 16 * u + i * 14 * u, 9 * u, c, 'left', 800));
          } else {
            pill(g, query ? `검사 ${checked} / ${pts.length}번 · 찾음 ${found}` : `칸 ${leaves}개`, ox + 4 * u, oy + 10 * u, 8 * u, 'rgba(10,14,30,0.85)');
          }
        },
        controls: [
          { type: 'range', label: '한 칸에 담을 수 (넘으면 쪼갬)', min: 1, max: 16, step: 1, value: 4, on: (v) => { cap = v; } },
          { type: 'range', label: '점 개수', min: 40, max: 800, step: 20, value: 260, on: (v) => { N = v; gen(); } },
          { type: 'toggle', label: '찾기 상자', value: true, on: (v) => { query = v; } },
          { type: 'toggle', label: '나누기 선', value: true, on: (v) => { lines = v; } },
        ],
      };
    },
  }
```

## 관련 기술
- 먼저 알면 좋은 기술: [지형 조각 캐시 (청크 · LRU)](https://ai-techstudio.web.app/ai/t/i78.md) `i78`
- 다음에 해 볼 기술: [분리축 충돌 (SAT · 다각형)](https://ai-techstudio.web.app/ai/t/i284.md) `i284` · [쓸고 지나는 충돌 (빠른 물체 뚫림 막기)](https://ai-techstudio.web.app/ai/t/i285.md) `i285` · [2D 시야 다각형 (빛 그림자)](https://ai-techstudio.web.app/ai/t/i235.md) `i235`
- 참고 문서: [Wikipedia — Quadtree](https://en.wikipedia.org/wiki/Quadtree)