# AI 꾸러미 — 등각 깊이 정렬 (큰 물체 · 겹침) — Isometric depth sorting
> 등각 판에서 여러 칸을 차지하는 물체를 칸 번호 합으로 줄 세우면 생기는 겹침 오류를, 「완전히 뒤에 있나」 관계의 위상 정렬로 바로잡는다.  
> 견본: https://ai-techstudio.web.app/#t/i310

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

## 주문서

### 만들어 줘: 등각 깊이 정렬 (큰 물체 · 겹침) — Isometric depth sorting

#### 1. 목표
쌓기 · 도시 판의 등각 그리기 순서를 위상 정렬로 바로잡아 줘 — 여러 칸 물체도 겹침이 틀리지 않게, 칸 번호 합 정렬과 비교. 분위기는 밝은 장난감 마을.

#### 2. 핵심 기술 용어
- **Isometric depth sorting** — 등각 깊이 정렬 — 그리는 앞뒤 순서
- **Topological sort (DFS)** — 위상 정렬 — 「뒤에 있는 것 먼저」 관계로 줄 세우기
- **Painter's algorithm** — 뒤에서 앞으로 덮어 그리기
- **Axis-aligned footprint overlap** — 바닥 차지 칸이 겹치는지 축마다 보기

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

#### 4. 조건
- 물체마다 바닥 차지 범위(x, y, 폭 w, 깊이 d)를 들고 「완전히 뒤에 있나」로 비교
- 위상 정렬 방문 표시는 세 상태(안 봄 · 보는 중 · 끝) — 보는 중을 다시 만나면 그냥 넘어가 고리에서 멈추지 않게
- 움직이는 물체가 있으면 매 프레임 다시 정렬
- 칸 번호 합 정렬과 3초마다 번갈아 비교 + 그리는 순서 번호 보기

#### 5. 완성 기준 (이게 보이면 성공)
- 움직이는 버스가 울타리 · 집 앞뒤를 지날 때 위상 정렬로는 늘 바르게 겹친다
- 칸 번호 합 정렬로 바꾸면 버스가 울타리 위로 뚫고 나오는 순간이 보인다
- 「그리는 순서 번호」를 켜면 물체마다 몇 번째로 그렸는지 숫자가 뜬다

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

## 원리
- 등각 화면 좌표 = ((x − y) × 칸 폭 ÷ 2, (x + y) × 칸 높이 ÷ 2 − z × 높이). 뒤(작은 x + y)부터 그려 덮으면 된다.
- 한 칸 물체는 x + y 합으로 줄 세우면 맞지만, 2칸 · 4칸 물체(울타리 · 버스)는 합이 같아도 앞뒤가 틀려 「뚫고 나오는」 그림이 된다.
- 두 물체 A · B 가 있을 때, A 의 오른쪽 끝 ≤ B 의 왼쪽 끝이고 y 범위가 겹치면 A 가 뒤. y 쪽도 같게. 둘 다 작으면 역시 A 가 뒤.
- 이 「뒤에 있다」 관계로 깊이 우선 탐색 위상 정렬 — 내 뒤에 있는 것을 먼저 다 내보내고 나를 내보낸다.

## 핵심 코드 — 「완전히 뒤」 관계 + 위상 정렬
(발췌: demos/demos2dLook.ts mkI310() behind() · topoSort() 를 정리)
```ts
interface Obj { x: number; y: number; w: number; d: number; h: number }
const TW = 30, TH = 15, HZ = 17, OX = 140, OY = 30;
/** 등각 화면 좌표 */
const sp = (x: number, y: number, z: number): [number, number] =>
  [OX + ((x - y) * TW) / 2, OY + ((x + y) * TH) / 2 - z * HZ];

const ov = (a0: number, a1: number, b0: number, b1: number) => a0 < b1 - 1e-6 && b0 < a1 - 1e-6;
/** A 가 B 보다 뒤에 있나 (먼저 그려야 하나) */
function behind(A: Obj, B: Obj) {
  const ax1 = A.x + A.w, ay1 = A.y + A.d;
  if (ax1 <= B.x + 1e-6 && ov(A.y, ay1, B.y, B.y + B.d)) return true; // x 쪽으로 완전히 뒤
  if (ay1 <= B.y + 1e-6 && ov(A.x, ax1, B.x, B.x + B.w)) return true; // y 쪽으로 완전히 뒤
  return ax1 <= B.x + 1e-6 && ay1 <= B.y + 1e-6;                      // 대각선 뒤
}
function topoSort(os: Obj[]): Obj[] {
  const out: Obj[] = [];
  const st = new Map<Obj, number>();          // 1 = 보는 중, 2 = 끝
  const visit = (o: Obj) => {
    if (st.get(o)) return;                     // 끝났거나 보는 중(고리)이면 넘어감
    st.set(o, 1);
    for (const p of os) if (p !== o && behind(p, o)) visit(p); // 내 뒤를 먼저
    st.set(o, 2);
    out.push(o);
  };
  for (const o of os) visit(o);
  return out;                                  // 이 순서로 그리면 앞이 뒤를 덮는다
}
// 비교용 잘못된 정렬: [...os].sort((a, b) => a.x + a.y - (b.x + b.y))
```

## 흔한 실수 · 확인 목록
- [ ] **여러 칸 물체를 x + y 합으로 줄 세우면 앞 물체를 뚫고 나온다** — 합은 한 칸 물체에만 맞다. 바닥 범위로 「완전히 뒤」를 비교하는 위상 정렬을 쓴다.
- [ ] **물체가 서로 감싸면(고리) 재귀가 끝나지 않는다** — 「보는 중」 표시를 만나면 그냥 돌아간다 — 순서는 조금 틀려도 멈추지 않는다.
- [ ] **물체가 많으면 n² 비교가 무겁다** — 큰 물체를 칸 단위로 쪼개거나, 공간 격자로 가까운 물체만 비교한다.

## 완성 기준 체크리스트
- [ ] 움직이는 버스가 울타리 · 집 앞뒤를 지날 때 위상 정렬로는 늘 바르게 겹친다
- [ ] 칸 번호 합 정렬로 바꾸면 버스가 울타리 위로 뚫고 나오는 순간이 보인다
- [ ] 「그리는 순서 번호」를 켜면 물체마다 몇 번째로 그렸는지 숫자가 뜬다

## 이 기술 정보
- id: `i310` · 분류: 2D · 화면 › 2D 의사 3D · 2D · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 물체 n 개면 쌍 비교 n² — 견본 6개는 공짜. 100개 넘으면 칸 나누기나 공간 격자로 후보를 줄인다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i310
- 쓰면 좋을 때: 울타리 · 버스 · 큰 집처럼 여러 칸을 차지하는 물체가 있는 등각 판 / 물체가 움직여 앞뒤가 계속 바뀔 때
- 쓰지 말 때: 모든 물체가 한 칸짜리일 때 — x + y 합 정렬이면 충분하고 더 싸다 / 물체가 수천 개 — 모든 쌍 비교(n²)라 무겁다. 대신 큰 물체를 칸 단위로 나눈다

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### mkI310 — `src/demos/demos2dLook.ts:3415`
```ts
function mkI310() {
  interface Obj {
    x: number;
    y: number;
    w: number;
    d: number;
    h: number;
    col: string;
    kind: string;
    name: string;
  }
  let auto = true;
  let topo = true;
  let nums = false;
  const controls: Control[] = [
    { type: 'toggle', label: '자동 비교 (3초마다)', value: auto, on: (v) => (auto = v) },
    { type: 'toggle', label: '위상 정렬 (자동 끌 때)', value: topo, on: (v) => (topo = v) },
    { type: 'toggle', label: '그리는 순서 번호', value: nums, on: (v) => (nums = v) },
  ];
  const TW = 30;
  const TH = 15;
  const HZ = 17;
  const OX = 140;
  const OY = 30;
  const sp = (x: number, y: number, z: number): [number, number] => [OX + ((x - y) * TW) / 2, OY + ((x + y) * TH) / 2 - z * HZ];
  const shadeC = (c: string, k: number): string => {
    const v = hexRgb(c);
    return rgba([v[0] * k, v[1] * k, v[2] * k]);
  };
  const poly = (g: G, pts: [number, number][], fill: string): void => {
    g.beginPath();
    g.moveTo(pts[0]![0], pts[0]![1]);
    for (let i = 1; i < pts.length; i++) g.lineTo(pts[i]![0], pts[i]![1]);
    g.closePath();
    g.fillStyle = fill;
    g.fill();
    g.strokeStyle = 'rgba(30,20,50,.55)';
    g.lineWidth = 0.7;
    g.stroke();
  };
  const box = (g: G, o: Obj, z0 = 0, hh = o.h, col = o.col): void => {
    const x0 = o.x;
    const y0 = o.y;
    const x1 = o.x + o.w;
    const y1 = o.y + o.d;
    const z1 = z0 + hh;
    poly(g, [sp(x0, y1, z0), sp(x1, y1, z0), sp(x1, y1, z1), sp(x0, y1, z1)], shadeC(col, 0.82));
    poly(g, [sp(x1, y0, z0), sp(x1, y1, z0), sp(x1, y1, z1), sp(x1, y0, z1)], shadeC(col, 0.64));
    poly(g, [sp(x0, y0, z1), sp(x1, y0, z1), sp(x1, y1, z1), sp(x0, y1, z1)], shadeC(col, 1.05));
  };
  const drawObj = (g: G, o: Obj): void => {
    if (o.kind === 'house') {
      box(g, o);
      // 창
      for (const k of [0.3, 0.7]) {
        const p = sp(o.x + o.w * k, o.y + o.d, o.h * 0.55);
        g.fillStyle = '#8fdcff';
        g.beginPath();
        g.moveTo(p[0] - 4, p[1] - 2);
        g.lineTo(p[0] + 4, p[1] - 2 + 0);
        g.lineTo(p[0] + 4, p[1] + 5);
        g.lineTo(p[0] - 4, p[1] + 5);
        g.fill();
      }
      const z = o.h;
      const a = sp(o.x, o.y, z);
      const b = sp(o.x + o.w, o.y, z);
      const c = sp(o.x + o.w, o.y + o.d, z);
      const d = sp(o.x, o.y + o.d, z);
      const top = sp(o.x + o.w / 2, o.y + o.d / 2, z + 1.1);
      poly(g, [a, b, top], '#ff8a5c');
      poly(g, [d, c, top], '#ff7a4a');
      poly(g, [b, c, top], '#d9552c');
    } else if (o.kind === 'tower') {
      box(g, o);
      for (let k = 1; k < 4; k++) {
        const p = sp(o.x + o.w, o.y + o.d, (o.h * k) / 4);
        const q = sp(o.x, o.y + o.d, (o.h * k) / 4);
        g.strokeStyle = 'rgba(255,255,255,.6)';
        g.lineWidth = 1.2;
        g.beginPath();
        g.moveTo(q[0], q[1]);
        g.lineTo(p[0], p[1]);
        g.stroke();
      }
      const t = sp(o.x + 0.5, o.y + 0.5, o.h);
      g.strokeStyle = '#444';
      g.lineWidth = 1;
      g.beginPath();
      g.moveTo(t[0], t[1]);
      g.lineTo(t[0], t[1] - 16);
      g.stroke();
      g.fillStyle = '#ff4d6d';
      g.beginPath();
      g.moveTo(t[0], t[1] - 16);
      g.lineTo(t[0] + 9, t[1] - 13);
      g.lineTo(t[0], t[1] - 10);
      g.fill();
    } else if (o.kind === 'tree') {
      box(g, { ...o, x: o.x + 0.38, y: o.y + 0.38, w: 0.24, d: 0.24 }, 0, 0.7, '#8a5a3a');
      const c = sp(o.x + 0.5, o.y + 0.5, 1.25);
      g.fillStyle = '#3fae5a';
      g.strokeStyle = 'rgba(30,20,50,.55)';
      g.beginPath();
      g.arc(c[0], c[1], 13, 0, TAU);
      g.fill();
      g.stroke();
      g.fillStyle = '#7ee08a';
      g.beginPath();
      g.arc(c[0] - 4, c[1] - 4, 5, 0, TAU);
      g.fill();
    } else if (o.kind === 'bus') {
      box(g, o, 0.15, o.h - 0.15);
      for (let k = 0; k < 3; k++) {
        const p = sp(o.x + o.w, o.y + 0.3 + k * 0.55, o.h * 0.7);
        g.fillStyle = '#9fe4ff';
        g.beginPath();
        g.moveTo(p[0], p[1]);
        g.lineTo(p[0] + 6, p[1] - 3);
        g.lineTo(p[0] + 6, p[1] + 2);
        g.lineTo(p[0], p[1] + 5);
        g.fill();
      }
    } else box(g, o);
  };
  const statics: Obj[] = [
    { x: 1, y: 0, w: 2, d: 2, h: 1.2, col: '#fff1d6', kind: 'house', name: '집' },
    { x: 4, y: 0, w: 1, d: 1, h: 2.6, col: '#9aa7ff', kind: 'tower', name: '탑' },
    { x: 0, y: 4, w: 4, d: 1, h: 0.75, col: '#5fc96a', kind: 'hedge', name: '울타리' },
    { x: 5, y: 5, w: 1, d: 1, h: 1, col: '#3fae5a', kind: 'tree', name: '나무' },
    { x: 5, y: 3, w: 1, d: 1, h: 0.6, col: '#ffd84d', kind: 'crate', name: '상자' },
  ];
  const bus: Obj = { x: 0, y: 2, w: 1, d: 2, h: 1, col: '#ffcf3a', kind: 'bus', name: '버스' };
  const ov = (a0: number, a1: number, b0: number, b1: number): boolean => a0 < b1 - 1e-6 && b0 < a1 - 1e-6;
  const behind = (A: Obj, B: Obj): boolean => {
    const ax1 = A.x + A.w;
    const ay1 = A.y + A.d;
    if (ax1 <= B.x + 1e-6 && ov(A.y, ay1, B.y, B.y + B.d)) return true;
    if (ay1 <= B.y + 1e-6 && ov(A.x, ax1, B.x, B.x + B.w)) return true;
    return ax1 <= B.x + 1e-6 && ay1 <= B.y + 1e-6;
  };
  const topoSort = (os: Obj[]): Obj[] => {
    const out: Obj[] = [];
    const st = new Map<Obj, number>();
    const visit = (o: Obj): void => {
      if (st.get(o) === 2) return;
      if (st.get(o) === 1) return;
      st.set(o, 1);
      for (const p of os) if (p !== o && behind(p, o)) visit(p);
      st.set(o, 2);
      out.push(o);
    };
    for (const o of os) visit(o);
    return out;
  };
  return {
    controls,
    draw(g: G, w: number, h: number, t: number) {
      reset(g);
      const f = frame(g, w, h);
      vbg(g, f, '#2a2350', '#141030');
      const N = 7;
      // 바닥
      for (let y = 0; y < N; y++)
        for (let x = 0; x < N; x++) {
          const road = y === 2 || y === 3;
          const col = road ? ((x + y) % 2 ? '#8b8fa8' : '#7f839c') : (x + y) % 2 ? '#9fe08a' : '#8fd47a';
          g.beginPath();
          const a = sp(x, y, 0);
          const b = sp(x + 1, y, 0);
          const c = sp(x + 1, y + 1, 0);
          const d = sp(x, y + 1, 0);
          g.moveTo(a[0], a[1]);
          g.lineTo(b[0], b[1]);
          g.lineTo(c[0], c[1]);
          g.lineTo(d[0], d[1]);
          g.closePath();
          g.fillStyle = col;
          g.fill();
        }
      const ph = (t * 0.22) % 2;
      bus.x = (ph < 1 ? smooth(ph) : smooth(2 - ph)) * 6;
      const all = [...statics, bus];
      const useTopo = auto ? Math.floor(t / 3) % 2 === 0 : topo;
      const naive = [...all].sort((a, b) => a.x + a.y - (b.x + b.y));
      const order = useTopo ? topoSort(all) : naive;
      // 틀린 곳 세기
      let bad = 0;
      const idx = new Map(naive.map((o, i) => [o, i] as [Obj, number]));
      for (const a of all)
        for (const b of all) if (a !== b && behind(a, b) && idx.get(a)! > idx.get(b)!) bad++;
      for (let i = 0; i < order.length; i++) {
        const o = order[i]!;
        drawObj(g, o);
        if (nums) {
          const p = sp(o.x + o.w / 2, o.y + o.d / 2, o.h + 0.3);
          g.fillStyle = '#1b1530';
          g.beginPath();
          g.arc(p[0], p[1], 6, 0, TAU);
          g.fill();
          txt(g, String(i + 1), p[0], p[1] + 0.5, 7, '#fff', 'center', 800);
        }
      }
      const okCol = useTopo ? '#8bffb0' : '#ff8a9a';
      pill(g, useTopo ? '위상 정렬: 「뒤에 있는 것 먼저」 규칙으로 줄 세움' : `칸 번호(x+y) 순서 → 잘못 겹친 쌍 ${bad}`, 140, 13, 8, 'rgba(0,0,0,.4)', okCol);
      g.restore();
    },
  };
}
```

### i310 견본 항목 — `src/demos/demos2dLook.ts:3793`
```ts
  i310: { kind: '2d', caption: '여러 칸 물체를 칸 번호 합으로 줄 세우면 버스가 울타리 위로 뚫고 나옴 ↔ 위상 정렬은 바름 (3초마다 비교)', make: mkI310 }
```

## 관련 기술
- 먼저 알면 좋은 기술: [스프라이트 쌓기 (sprite stacking)](https://ai-techstudio.web.app/ai/t/i308.md) `i308`
- 다음에 해 볼 기술: [2.5D 시차 깊이 (층층 무대)](https://ai-techstudio.web.app/ai/t/i309.md) `i309`