# AI 꾸러미 — 미로 생성 (깊이 우선 · 크루스칼 · 윌슨) — Maze generation (spanning tree)
> 같은 크기 판을 깊이 우선 · 크루스칼 · 윌슨 세 알고리즘으로 파 내려가, 긴 복도 미로와 짧은 갈래 미로가 어떻게 다른지 나란히 보여 준다.  
> 견본: https://ai-techstudio.web.app/#t/i250

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

## 주문서

### 만들어 줘: 미로 생성 (깊이 우선 · 크루스칼 · 윌슨) — Maze generation (spanning tree)

#### 1. 목표
미로 찾기 게임 판을 미로 생성 알고리즘으로 만들어 줘 — 깊이 우선 · 크루스칼 · 윌슨 중에서 고를 수 있게. 보이는 모습은 파 내려가는 과정이 보이는 설명.

#### 2. 핵심 기술 용어
- **Maze generation (spanning tree)** — 미로 만들기 = 칸을 잇는 나무 하나 만들기
- **Recursive backtracker (DFS)** — 깊이 우선 — 막히면 되돌아가며 파기
- **Randomized Kruskal's algorithm · union-find** — 벽을 무작위로 허물되 이미 이어진 칸끼리는 안 허묾
- **Wilson's algorithm (loop-erased random walk)** — 고리를 지우는 무작위 걷기 — 모든 미로가 똑같은 확률

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

#### 4. 조건
- 칸마다 뚫린 쪽을 비트로 (1 오른쪽 · 2 아래 · 4 왼쪽 · 8 위) — 벽을 허물면 양쪽 칸 모두에 표시
- 세 알고리즘은 같은 칸 · 이웃 함수를 쓰고 「한 걸음」 함수만 다르게
- 시드 있는 난수로 — 같은 시드면 같은 미로
- 다 지으면 너비 우선 거리로 정답 길을 찾고, 막다른 길 수를 보여 준다

#### 5. 완성 기준 (이게 보이면 성공)
- 세 판이 동시에 파이고, 깊이 우선은 머리(노란 점) · 크루스칼은 덩어리 색 · 윌슨은 분홍 걷기 줄이 보인다
- 다 지으면 출발점에서 거리 색이 번지고 흰 정답 길이 그려진다
- 판 아래 「막다른 길 · 길이」 숫자로 깊이 우선이 막다른 길이 가장 적다는 것이 보인다
- 「미로 크기」를 바꾸면 세 판이 같은 크기로 다시 지어진다

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

## 원리
- 미로는 칸들을 고리 없이 모두 잇는 나무다 — 어느 두 칸 사이에도 길이 딱 하나.
- 깊이 우선: 스택 맨 위 칸에서 안 가 본 이웃으로 파고, 갈 곳이 없으면 스택에서 빼며 되돌아간다 → 길고 구불구불한 복도, 갈래가 적다.
- 크루스칼: 모든 벽을 섞어 하나씩 보며, 양쪽 칸이 아직 다른 덩어리일 때만 허문다(합집합-찾기) → 짧은 막다른 길이 많다.
- 윌슨: 미로 밖 칸에서 미로에 닿을 때까지 무작위로 걷고, 걷다 만든 고리는 지운 뒤 그 길을 파 넣는다 → 치우침 없는 고른 미로.
- 다 지으면 출발점에서 너비 우선으로 거리를 재 색칠하고, 벽이 셋인 칸(막다른 길) 수와 정답 길이를 센다.

## 핵심 코드 — 깊이 우선 · 크루스칼 · 윌슨 (끝까지 한 번에)
(발췌: demos/demosMapA.ts i250 carve · stepDfs · stepKruskal · stepWilson 을 한 번에 도는 꼴로)
```ts
const C = 10, R = 14;
const bit = (a: number, b: number): [number, number] =>
  b - a === 1 ? [1, 4] : b - a === -1 ? [4, 1] : b - a === C ? [2, 8] : [8, 2];
const nbrs = (i: number) => {
  const x = i % C, y = (i / C) | 0, o: number[] = [];
  if (x > 0) o.push(i - 1); if (x < C - 1) o.push(i + 1);
  if (y > 0) o.push(i - C); if (y < R - 1) o.push(i + C);
  return o;
};
function carve(pass: Uint8Array, a: number, b: number) {
  const [ba, bb] = bit(a, b); pass[a] |= ba; pass[b] |= bb;     // 양쪽 칸 모두 뚫림 표시
}
function dfs(rnd: () => number): Uint8Array {
  const pass = new Uint8Array(C * R), seen = new Uint8Array(C * R), st = [0];
  seen[0] = 1;
  while (st.length) {
    const c = st[st.length - 1];
    const opts = nbrs(c).filter((n) => !seen[n]);
    if (!opts.length) { st.pop(); continue; }                  // 막히면 되돌아가기
    const n = opts[Math.floor(rnd() * opts.length)];
    carve(pass, c, n); seen[n] = 1; st.push(n);
  }
  return pass;
}
function kruskal(rnd: () => number): Uint8Array {
  const pass = new Uint8Array(C * R), par = Int32Array.from({ length: C * R }, (_, i) => i);
  const find = (i: number) => { while (par[i] !== i) { par[i] = par[par[i]]; i = par[i]; } return i; };
  const edges: [number, number][] = [];
  for (let i = 0; i < C * R; i++) { if (i % C < C - 1) edges.push([i, i + 1]); if (i + C < C * R) edges.push([i, i + C]); }
  for (let i = edges.length - 1; i > 0; i--) { const j = Math.floor(rnd() * (i + 1)); [edges[i], edges[j]] = [edges[j], edges[i]]; }
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) { par[ra] = rb; carve(pass, a, b); }        // 다른 덩어리일 때만 허문다
  }
  return pass;
}
function wilson(rnd: () => number): Uint8Array {
  const pass = new Uint8Array(C * R), inM = new Uint8Array(C * R);
  inM[Math.floor(rnd() * C * R)] = 1;
  for (;;) {
    const rest = [...inM.keys()].filter((i) => !inM[i]);
    if (!rest.length) return pass;
    const walk = [rest[Math.floor(rnd() * rest.length)]];
    while (!inM[walk[walk.length - 1]]) {
      const ns = nbrs(walk[walk.length - 1]), n = ns[Math.floor(rnd() * ns.length)];
      const at = walk.indexOf(n);
      if (at >= 0) walk.length = at + 1; else walk.push(n);    // 고리는 지운다
    }
    for (let k = 0; k < walk.length - 1; k++) { carve(pass, walk[k], walk[k + 1]); inM[walk[k]] = 1; }
  }
}
```

## 흔한 실수 · 확인 목록
- [ ] **한쪽 칸에만 뚫림을 적으면 길찾기 · 그리기가 어긋난다** — 벽 하나를 허물 때 두 칸 모두에 반대 방향 비트를 함께 적는다 (bit 함수가 짝을 돌려준다).
- [ ] **깊이 우선을 재귀 함수로 짜면 큰 미로에서 스택이 넘친다** — 배열 스택으로 돌린다 — 견본도 st 배열을 쓴다.
- [ ] **윌슨은 처음 몇 걸음이 아주 오래 걸린다** — 미로가 한 칸뿐일 때 거기 닿기까지 오래 걷는다. 화면용이면 한 프레임에 여러 걸음(견본 4걸음)을 돌린다.
- [ ] **난이도를 크기로만 바꾸면 깊이 우선 미로는 큰 판도 쉽게 느껴진다** — 갈래가 적어 한 길만 따라가면 되기 때문 — 어렵게 하려면 크루스칼 · 윌슨처럼 갈래가 많은 쪽을 쓴다.

## 완성 기준 체크리스트
- [ ] 세 판이 동시에 파이고, 깊이 우선은 머리(노란 점) · 크루스칼은 덩어리 색 · 윌슨은 분홍 걷기 줄이 보인다
- [ ] 다 지으면 출발점에서 거리 색이 번지고 흰 정답 길이 그려진다
- [ ] 판 아래 「막다른 길 · 길이」 숫자로 깊이 우선이 막다른 길이 가장 적다는 것이 보인다
- [ ] 「미로 크기」를 바꾸면 세 판이 같은 크기로 다시 지어진다

## 이 기술 정보
- id: `i250` · 분류: 지도 · 길찾기 › 지도 생성 (절차) · 2D · 난이도 쉬움 · 폰 부담 가벼움 (폰 OK) — 10 × 14 칸 기준 걸음 수백 번. 윌슨은 처음에 미로가 작아 걷기가 길어서 한 프레임에 4걸음씩 돌린다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i250
- 쓰면 좋을 때: 미로 게임 판을 매번 새로 만들 때 (난이도 = 알고리즘 · 크기) / 그래프 · 나무 · 합집합-찾기를 눈으로 설명할 때
- 쓰지 말 때: 고리가 있어야 재미있는 판(여러 길) — 다 만든 뒤 벽 몇 개를 더 허물거나 동굴(i248)을 쓴다 / 방이 있는 던전 — BSP 방 + 복도(i247)

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### i250 견본 항목 — `src/demos/demosMapA.ts:1704`
```ts
  i250: {
    kind: '2d',
    caption: '같은 크기 미로를 깊이 우선 · 크루스칼 · 윌슨으로 — 다 지으면 출발점에서 거리 색: 긴 복도 vs 짧은 갈래',
    make() {
      let C = 10;
      let R = 14;
      let distOn = true;
      interface Mz {
        pass: Uint8Array;
        inM: Uint8Array;
        done: boolean;
        stack: number[];
        edges: [number, number][];
        par: Int32Array;
        walk: number[] | null;
        head: number;
        dist: Int32Array;
        maxD: number;
        dead: number;
        sol: number[];
      }
      let mz: Mz[] = [];
      let rnd = mulberry(1);
      let flood = 0;
      const BIT = (a: number, b: number): [number, number] => {
        const d = b - a;
        if (d === 1) return [1, 4];
        if (d === -1) return [4, 1];
        if (d === C) return [2, 8];
        return [8, 2];
      };
      const carve = (m: Mz, a: number, b: number): void => {
        const [ba, bb] = BIT(a, b);
        m.pass[a] = m.pass[a]! | ba;
        m.pass[b] = m.pass[b]! | bb;
      };
      const nbrs = (i: number): number[] => {
        const x = i % C;
        const y = (i / C) | 0;
        const o: number[] = [];
        if (x > 0) o.push(i - 1);
        if (x < C - 1) o.push(i + 1);
        if (y > 0) o.push(i - C);
        if (y < R - 1) o.push(i + C);
        return o;
      };
      const find = (p: Int32Array, i: number): number => {
        while (p[i] !== i) {
          p[i] = p[p[i]!]!;
          i = p[i]!;
        }
        return i;
      };
      const newMz = (): Mz => ({ pass: new Uint8Array(C * R), inM: new Uint8Array(C * R), done: false, stack: [], edges: [], par: new Int32Array(C * R), walk: null, head: -1, dist: new Int32Array(C * R).fill(-1), maxD: 1, dead: 0, sol: [] });
      const finish = (m: Mz): void => {
        m.done = true;
        const q = [0];
        m.dist[0] = 0;
        const from = new Int32Array(C * R).fill(-1);
        while (q.length) {
          const c = q.shift()!;
          for (const n of nbrs(c)) {
            if (m.dist[n]! >= 0) continue;
            if (!(m.pass[c]! & BIT(c, n)[0])) continue;
            m.dist[n] = m.dist[c]! + 1;
            from[n] = c;
            q.push(n);
          }
        }
        m.maxD = Math.max(1, ...Array.from(m.dist));
        m.dead = 0;
        for (let i = 0; i < C * R; i++) {
          const p = m.pass[i]!;
          if (p === 1 || p === 2 || p === 4 || p === 8) m.dead++;
        }
        m.sol = [];
        for (let c = C * R - 1; c >= 0; c = from[c]!) m.sol.push(c);
      };
      const stepDfs = (m: Mz): void => {
        if (!m.stack.length) return finish(m);
        const c = m.stack[m.stack.length - 1]!;
        const opts = nbrs(c).filter((n) => !m.inM[n]);
        if (!opts.length) {
          m.stack.pop();
          m.head = m.stack[m.stack.length - 1] ?? -1;
          return;
        }
        const n = opts[Math.floor(rnd() * opts.length)]!;
        carve(m, c, n);
        m.inM[n] = 1;
        m.stack.push(n);
        m.head = n;
      };
      const stepKruskal = (m: Mz): void => {
        while (m.edges.length) {
          const [a, b] = m.edges.pop()!;
          const ra = find(m.par, a);
          const rb = find(m.par, b);
          if (ra === rb) continue;
          m.par[ra] = rb;
          carve(m, a, b);
          m.inM[a] = 1;
          m.inM[b] = 1;
          m.head = b;
          return;
        }
        finish(m);
      };
      const stepWilson = (m: Mz): void => {
        if (!m.walk) {
          const rest: number[] = [];
          for (let i = 0; i < C * R; i++) if (!m.inM[i]) rest.push(i);
          if (!rest.length) return finish(m);
          m.walk = [rest[Math.floor(rnd() * rest.length)]!];
          return;
        }
        const c = m.walk[m.walk.length - 1]!;
        const ns = nbrs(c);
        const n = ns[Math.floor(rnd() * ns.length)]!;
        m.head = n;
        if (m.inM[n]) {
          m.walk.push(n);
          for (let k = 0; k < m.walk.length - 1; k++) {
            carve(m, m.walk[k]!, m.walk[k + 1]!);
            m.inM[m.walk[k]!] = 1;
          }
          m.walk = null;
          return;
        }
        const at = m.walk.indexOf(n);
        if (at >= 0) m.walk.length = at + 1;
        else m.walk.push(n);
      };
      const run = runner({
        rate: 75,
        hold: 2,
        start(seed) {
          rnd = mulberry(seed);
          mz = [newMz(), newMz(), newMz()];
          const d = mz[0]!;
          d.inM[0] = 1;
          d.stack = [0];
          const k = mz[1]!;
          k.inM.fill(1);
          for (let i = 0; i < C * R; i++) {
            k.par[i] = i;
            if (i % C < C - 1) k.edges.push([i, i + 1]);
            if (i + C < C * R) k.edges.push([i, i + C]);
          }
          for (let i = k.edges.length - 1; i > 0; i--) {
            const j = Math.floor(rnd() * (i + 1));
            const tmp = k.edges[i]!;
            k.edges[i] = k.edges[j]!;
            k.edges[j] = tmp;
          }
          mz[2]!.inM[Math.floor(rnd() * C * R)] = 1;
          flood = 0;
        },
        step() {
          const [a, b, c] = mz as [Mz, Mz, Mz];
          if (!a.done) stepDfs(a);
          if (!b.done) stepKruskal(b);
          if (!c.done) for (let k = 0; k < 4 && !c.done; k++) stepWilson(c);
          if (a.done && b.done && c.done) {
            flood += 1 / 70;
            return flood >= 1.25;
          }
          return false;
        },
      });
      run.restart();
      const NAMES = ['깊이 우선', '크루스칼', '윌슨'];
      const NOTE = ['긴 복도 · 갈래 적음', '짧은 갈래 많음', '고르게 무작위'];
      const distCol = (k: number): string => {
        const c = rampAt(
          [
            [0, [80, 220, 200]],
            [0.35, [90, 140, 255]],
            [0.7, [190, 100, 240]],
            [1, [255, 150, 80]],
          ],
          k,
        );
        return rgb(c);
      };
      return {
        draw(g, w, h, t, dt) {
          reset(g);
          run.tick(dt);
          const u = ui(scaleOf(w, h));
          g.fillStyle = '#0c111e';
          g.fillRect(0, 0, w, h);
          const pw = w / 3;
          const top = 20 * u;
          const bot = 16 * u;
          mz.forEach((m, p) => {
            const cs = Math.min((pw - 8 * u) / C, (h - top - bot) / R);
            const ox = p * pw + (pw - cs * C) / 2;
            const oy = top + (h - top - bot - cs * R) / 2;
            const wt = Math.max(1, cs * 0.24);
            rr(g, ox - wt, oy - wt, cs * C + wt, cs * R + wt, 3 * u);
            g.fillStyle = '#1a2236';
            g.fill();
            const walkSet = m.walk ? new Set(m.walk) : null;
            const stackSet = p === 0 && !m.done ? new Set(m.stack) : null;
            for (let i = 0; i < C * R; i++) {
              const inm = m.inM[i] || (walkSet?.has(i) ?? false);
              if (!inm) continue;
              const x = ox + (i % C) * cs;
              const y = oy + ((i / C) | 0) * cs;
              let col = '#dfe8f7';
              if (m.done && distOn && flood > 0) {
                const d = m.dist[i]! / m.maxD;
                col = d <= flood ? distCol(d) : '#dfe8f7';
              } else if (p === 1 && !m.done) {
                const r0 = find(m.par, i);
                col = `hsl(${(hash2(r0, 3) * 360) | 0},65%,72%)`;
              } else if (stackSet?.has(i)) col = '#8fe3c8';
              if (walkSet?.has(i) && !m.inM[i]) col = '#ff7eb6';
              g.fillStyle = col;
              const pa = m.pass[i]!;
              g.fillRect(x, y, cs - wt + ((pa & 1) ? wt : 0), cs - wt);
              if (pa & 2) g.fillRect(x, y, cs - wt, cs);
            }
            if (m.walk) {
              g.strokeStyle = '#ff4f9a';
              g.lineWidth = Math.max(1, cs * 0.28);
              g.lineJoin = 'round';
              g.beginPath();
              m.walk.forEach((c, k) => {
                const X = ox + (c % C) * cs + (cs - wt) / 2;
                const Y = oy + ((c / C) | 0) * cs + (cs - wt) / 2;
                if (k) g.lineTo(X, Y);
                else g.moveTo(X, Y);
              });
              g.stroke();
            }
            if (!m.done && m.head >= 0) {
              const X = ox + (m.head % C) * cs + (cs - wt) / 2;
              const Y = oy + ((m.head / C) | 0) * cs + (cs - wt) / 2;
              g.beginPath();
              g.arc(X, Y, cs * 0.45 + Math.sin(t * 14) * cs * 0.08, 0, TAU);
              g.fillStyle = p === 2 ? '#ff4f9a' : '#ffe14d';
              g.fill();
            }
            if (m.done && flood >= 1) {
              const k = clamp01((flood - 1) / 0.2);
              g.strokeStyle = `rgba(255,255,255,${k})`;
              g.lineWidth = Math.max(1, cs * 0.22);
              g.lineJoin = 'round';
              g.beginPath();
              m.sol.forEach((c, j) => {
                const X = ox + (c % C) * cs + (cs - wt) / 2;
                const Y = oy + ((c / C) | 0) * cs + (cs - wt) / 2;
                if (j) g.lineTo(X, Y);
                else g.moveTo(X, Y);
              });
              g.stroke();
            }
            txt(g, NAMES[p]!, p * pw + pw / 2, 10 * u, 9 * u, ['#ffe14d', '#9ad7ff', '#ff8cc0'][p]!, 'center', 800);
            const info = m.done ? `막다른 길 ${m.dead} · 길이 ${m.sol.length}` : NOTE[p]!;
            txt(g, info, p * pw + pw / 2, h - 8 * u, 7.5 * u, m.done ? '#fff' : '#8a97b4', 'center', 700);
          });
          g.fillStyle = 'rgba(255,255,255,0.07)';
          g.fillRect(pw, 4 * u, 1, h - 8 * u);
          g.fillRect(pw * 2, 4 * u, 1, h - 8 * u);
        },
        controls: [
          seedCtl(run),
          speedCtl(run),
          { type: 'toggle', label: '거리 색 · 정답 길', value: true, on: (v) => { distOn = v; } },
          { type: 'range', label: '미로 크기', min: 6, max: 22, step: 1, value: 10, on: (v) => { C = v; R = Math.round(v * 1.4); run.restart(run.seed); } },
        ],
      };
    },
  }
```

## 관련 기술
- 먼저 알면 좋은 기술: [방 + 복도 던전 (BSP)](https://ai-techstudio.web.app/ai/t/i247.md) `i247`
- 다음에 해 볼 기술: [A* 길찾기 (열린 · 닫힌 칸 보기)](https://ai-techstudio.web.app/ai/t/i264.md) `i264`
- 참고 문서: [Wikipedia — Maze generation algorithm](https://en.wikipedia.org/wiki/Maze_generation_algorithm)