# AI 꾸러미 — 페인트 통 (영역 채우기) — Flood fill (BFS)
> 누른 픽셀과 이어진 같은 색 칸을 너비 우선으로 찾아 채우고, 찾은 순서대로 조금씩 칠해 물결처럼 퍼지게 하는 페인트 통 도구.  
> 견본: https://ai-techstudio.web.app/#t/i314

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

## 주문서

### 만들어 줘: 페인트 통 (영역 채우기) — Flood fill (BFS)

#### 1. 목표
색칠하기 그림에 페인트 통 채우기를 넣어 줘 — 누른 곳과 이어진 같은 색 칸을 찾아 물결처럼 채우고, 선 가장자리까지 빈틈없이. 분위기는 손그림 선 색칠 공책.

#### 2. 핵심 기술 용어
- **Flood fill (BFS)** — 영역 채우기 — 이웃으로 번지며 찾기
- **4-connectivity** — 위 · 아래 · 왼쪽 · 오른쪽만 이웃으로
- **Line-art alpha threshold** — 선 알파가 문턱 넘으면 벽으로
- **ImageData Uint32Array** — 픽셀을 32비트 정수 배열로

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

#### 4. 조건
- 방문 · 큐 배열은 미리 한 번 만들어 재사용 (누를 때마다 new 하지 않기)
- 선 판단은 선 겹의 알파로 — 칠한 색 겹과 선 겹을 따로 들기
- 벽에 닿은 가장자리 픽셀도 마지막에 함께 칠하기 (흰 테 막기)
- 이미 같은 색이면 바로 끝내기
- 선을 새로 그으면 알파 배열을 다시 읽기

#### 5. 완성 기준 (이게 보이면 성공)
- 닫힌 영역을 누르면 누른 곳부터 물결처럼 색이 퍼져 영역만 꽉 찬다
- 선 가장자리에 흰 테가 남지 않는다
- 끌어서 선을 새로 그으면 그 선도 벽이 되어 영역이 나뉜다

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

## 원리
- 선 그림 겹의 알파만 따로 배열(la)에 담아 둔다. 알파 > 100 이면 벽.
- 누른 픽셀의 지금 색을 기억하고, 큐에 넣고 시작. 큐에서 하나 꺼내 위 · 아래 · 왼쪽 · 오른쪽 이웃 중 「방문 안 함 · 벽 아님 · 같은 색」만 다시 넣는다.
- 벽에 닿은 이웃은 따로 모아 두었다가 다 채운 뒤에 함께 칠한다 — 선의 흐린 가장자리(안티앨리어싱) 아래 흰 테가 안 남는다.
- 큐에 들어간 순서 = 누른 곳에서 가까운 순서. 그 순서대로 프레임마다 일정 개수씩 칠하면 물결처럼 퍼진다 (약 0.55초).

## 핵심 코드 — 너비 우선 채우기 (가장자리 포함 · 순서 기록)
(발췌: demos/demosDrawTools.ts paintBucket() fillAt() 을 정리)
```ts
// la: 선 겹 알파(Uint8Array), col32: 칠한 색 겹 픽셀(Uint32Array), PW × PH
function fillAt(x: number, y: number, c32: number, la: Uint8Array, col32: Uint32Array,
                PW: number, PH: number, visited: Uint8Array, queue: Int32Array) {
  const N = PW * PH, s = y * PW + x;
  if (la[s] > 100) return null;                 // 선 위를 눌렀다
  const seed = col32[s];
  if (seed === c32) return null;                // 이미 같은 색
  visited.fill(0);
  let head = 0, tail = 0;
  queue[tail++] = s; visited[s] = 1;
  const edges: number[] = [];
  while (head < tail) {
    const i = queue[head++], ix = i % PW;
    const nb = [ix > 0 ? i - 1 : -1, ix < PW - 1 ? i + 1 : -1, i - PW, i + PW]; // 4 이웃
    for (const j of nb) {
      if (j < 0 || j >= N || visited[j]) continue;
      visited[j] = 1;
      if (la[j] > 100) { edges.push(j); continue; } // 벽 — 가장자리로 기억
      if (col32[j] !== seed) continue;
      queue[tail++] = j;
    }
  }
  return { order: queue.slice(0, tail), edges }; // order 를 앞에서부터 조금씩 칠하면 물결
}
// 칠하기: 프레임마다 speed × dt 개씩 col32[order[k]] = c32, 끝나면 edges 도 칠하고 putImageData
```

## 흔한 실수 · 확인 목록
- [ ] **선 아래 흐린 가장자리에 흰 테가 남는다** — 벽에 닿은 이웃 픽셀을 모아 두었다가 다 채운 뒤 같은 색으로 칠한다.
- [ ] **재귀로 채우면 큰 영역에서 콜 스택이 넘친다** — 큐(Int32Array)로 너비 우선 — 재귀 없음.
- [ ] **칠한 색 겹과 선 겹을 한 장에 두면 색이 선을 덮어 벽이 사라진다** — 선 겹을 따로 들고 벽 판단은 그 알파로만.
- [ ] **RGBA 색을 32비트로 만들 때 순서가 뒤집힌다** — 리틀 엔디안이라 (A << 24) | (B << 16) | (G << 8) | R. 견본 toC32 처럼 한 곳에서 바꾼다.

## 완성 기준 체크리스트
- [ ] 닫힌 영역을 누르면 누른 곳부터 물결처럼 색이 퍼져 영역만 꽉 찬다
- [ ] 선 가장자리에 흰 테가 남지 않는다
- [ ] 끌어서 선을 새로 그으면 그 선도 벽이 되어 영역이 나뉜다

## 이 기술 정보
- id: `i314` · 분류: 2D · 화면 › 그리기 도구 · 2D · 난이도 쉬움 · 폰 부담 가벼움 (폰 OK) — 종이 크기 픽셀만큼 방문 배열 · 큐(Int32Array) 를 한 번 만들어 돌려 쓴다. 한 번 채우기는 영역 픽셀 수만큼.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i314
- 쓰면 좋을 때: 색칠 공책 · 그림 색칠 놀이 / 「이 영역은 몇 칸?」 넓이 세기
- 쓰지 말 때: 아주 큰 그림(수백만 픽셀)에서 한 번에 — 큐가 커진다. 줄 단위 채우기(scanline fill)가 메모리를 덜 쓴다 / 선에 틈이 많은 손그림 — 틈으로 밖까지 샌다. 선을 굵게 하거나 닫힌 영역만 쓰기

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### paintBucket — `src/demos/demosDrawTools.ts:1166`
```ts
function paintBucket(env: Env): Tool {
  const R = env.R;
  const lines = mkLayer(R, true);
  const colorL = mkLayer(R, true);
  const PW = lines.c.width;
  const PH = lines.c.height;
  const N = PW * PH;
  const colorImg = colorL.g.createImageData(PW, PH);
  const col32 = new Uint32Array(colorImg.data.buffer);
  let la = new Uint8Array(N);
  const visited = new Uint8Array(N);
  const queue = new Int32Array(N);
  const PALETTE = ['#e8564a', '#ffd166', '#9c6b43', '#7cc6f2', '#ffb627', '#58b368', '#8a5a3b', '#a6d785', '#cfeaff', '#f7a1c4', '#b18cf0'];
  let pi = 0;
  let anims: { order: Int32Array; n: number; done: number; edges: number[]; c32: number; speed: number }[] = [];
  let ripples: { p: P; t: number; c: string }[] = [];
  let downP: P | null = null;
  let path: P[] = [];
  let moved = false;
  let dirty = false;
  const toC32 = (hex: string): number => {
    const v = parseInt(hex.slice(1), 16);
    return ((255 << 24) | ((v & 255) << 16) | (((v >> 8) & 255) << 8) | ((v >> 16) & 255)) >>> 0;
  };
  function wob(pts: P[], close: boolean, seed: number): void {
    const g = lines.g;
    const q = shaky(pts, 0.7, seed);
    smoothPath(g, q, close);
    g.stroke();
  }
  function art(): void {
    clearLayer(lines);
    const g = lines.g;
    g.strokeStyle = '#2b2b33';
    g.lineWidth = 2.4;
    g.strokeRect(22, 24, 356, 204);
    const rect = (x0: number, y0: number, x1: number, y1: number, s: number): void => {
      wob(resampleStep([pt(x0, y0), pt(x1, y0), pt(x1, y1), pt(x0, y1), pt(x0, y0)], 6), false, s);
    };
    // 땅
    g.beginPath();
    g.moveTo(22, 206);
    g.quadraticCurveTo(46, 200, 72, 205);
    g.stroke();
    g.beginPath();
    g.moveTo(168, 205);
    g.quadraticCurveTo(270, 190, 378, 203);
    g.stroke();
    // 집
    rect(72, 122, 168, 205, 3);
    wob(resampleStep([pt(60, 123), pt(120, 72), pt(180, 123), pt(60, 123)], 6), false, 4);
    rect(104, 160, 130, 205, 5);
    rect(140, 134, 162, 156, 6);
    g.beginPath();
    g.moveTo(151, 134);
    g.lineTo(151, 156);
    g.moveTo(140, 145);
    g.lineTo(162, 145);
    g.stroke();
    rect(80, 136, 97, 153, 7);
    // 해
    wob(arcPts(322, 64, 22, 22, 0, 360, 36), true, 8);
    for (let i = 0; i < 9; i++) {
      const a = (i / 9) * Math.PI * 2 + 0.3;
      g.beginPath();
      g.moveTo(322 + Math.cos(a) * 29, 64 + Math.sin(a) * 29);
      g.lineTo(322 + Math.cos(a) * 37, 64 + Math.sin(a) * 37);
      g.stroke();
    }
    // 나무
    const crown: P[] = [];
    for (let i = 0; i <= 60; i++) {
      const a = (i / 60) * Math.PI * 2;
      const rr = 30 + 4 * Math.abs(Math.sin(a * 3.5));
      crown.push(pt(253 + Math.cos(a) * rr * 1.05, 118 + Math.sin(a) * rr));
    }
    smoothPath(g, crown, true);
    g.stroke();
    g.beginPath();
    g.moveTo(246, 146);
    g.lineTo(245, 200);
    g.moveTo(261, 146);
    g.lineTo(262, 199);
    g.stroke();
    // 구름
    const cloud: P[] = [];
    for (let i = 0; i <= 50; i++) {
      const a = (i / 50) * Math.PI * 2;
      const rr = 1 + 0.18 * Math.abs(Math.sin(a * 2.5));
      cloud.push(pt(190 + Math.cos(a) * 34 * rr, 52 + Math.sin(a) * 15 * rr));
    }
    smoothPath(g, cloud, true);
    g.stroke();
    // 새
    g.lineWidth = 1.8;
    for (const [bx, by] of [
      [60, 60],
      [84, 48],
    ] as [number, number][]) {
      g.beginPath();
      g.moveTo(bx - 7, by - 3);
      g.quadraticCurveTo(bx - 3, by - 5, bx, by);
      g.quadraticCurveTo(bx + 3, by - 5, bx + 7, by - 3);
      g.stroke();
    }
    refreshLines();
  }
  function refreshLines(): void {
    const d = lines.g.getImageData(0, 0, PW, PH).data;
    if (la.length !== N) la = new Uint8Array(N);
    for (let i = 0; i < N; i++) la[i] = d[i * 4 + 3]!;
  }
  function fillAt(p: P, hex: string): void {
    const x = Math.floor(p.x * R);
    const y = Math.floor(p.y * R);
    if (x < 0 || y < 0 || x >= PW || y >= PH) return;
    const s = y * PW + x;
    if (la[s]! > 100) return;
    const c32 = toC32(hex);
    const seed = col32[s]!;
    if (seed === c32) return;
    visited.fill(0);
    let head = 0;
    let tail = 0;
    queue[tail++] = s;
    visited[s] = 1;
    const edges: number[] = [];
    while (head < tail) {
      const i = queue[head++]!;
      const ix = i % PW;
      const nb = [ix > 0 ? i - 1 : -1, ix < PW - 1 ? i + 1 : -1, i - PW, i + PW];
      for (const j of nb) {
        if (j < 0 || j >= N || visited[j]) continue;
        visited[j] = 1;
        if (la[j]! > 100) {
          edges.push(j);
          continue;
        }
        if (col32[j] !== seed) continue;
        queue[tail++] = j;
      }
    }
    // 바깥(종이 밖)으로 새면 무시
    const order = queue.slice(0, tail);
    anims.push({ order, n: tail, done: 0, edges, c32, speed: Math.max(tail / 0.55, 30000) });
    ripples.push({ p, t: 0, c: hex });
  }
  return {
    rings: true,
    cursor: () => (moved ? 'pencil' : 'bucket'),
    color: () => PALETTE[pi % PALETTE.length]!,
    begin(p) {
      downP = p;
      path = [p];
      moved = false;
    },
    drag(p) {
      if (!downP) return;
      path.push(p);
      if (!moved && dist(p, downP) > 4) moved = true;
      if (moved) {
        const g = lines.g;
        g.strokeStyle = '#2b2b33';
        g.lineWidth = 2.2;
        const a = path[path.length - 2]!;
        g.beginPath();
        g.moveTo(a.x, a.y);
        g.lineTo(p.x, p.y);
        g.stroke();
        dirty = true;
      }
    },
    end() {
      if (!downP) return;
      if (moved) {
        if (dirty) refreshLines();
        dirty = false;
      } else {
        fillAt(downP, PALETTE[pi % PALETTE.length]!);
        pi++;
      }
      downP = null;
      moved = false;
    },
    step(dt) {
      let changed = false;
      for (const a of anims) {
        const to = Math.min(a.n, Math.floor(a.done + a.speed * dt));
        for (let k = Math.floor(a.done); k < to; k++) col32[a.order[k]!] = a.c32;
        a.done = to;
        if (a.done >= a.n) for (const e of a.edges) col32[e] = a.c32;
        changed = true;
      }
      anims = anims.filter((a) => a.done < a.n);
      if (changed) colorL.g.putImageData(colorImg, 0, 0);
      for (const rp of ripples) rp.t += dt;
      ripples = ripples.filter((q) => q.t < 0.7);
    },
    clear() {
      col32.fill(0);
      colorL.g.putImageData(colorImg, 0, 0);
      anims = [];
      ripples = [];
      pi = 0;
      art();
    },
    draw(g) {
      g.drawImage(colorL.c, 0, 0, W, H);
      g.drawImage(lines.c, 0, 0, W, H);
      for (const rp of ripples) {
        const u = rp.t / 0.7;
        g.strokeStyle = rp.c;
        g.globalAlpha = (1 - u) * 0.9;
        g.lineWidth = 2.2 * (1 - u) + 0.4;
        g.beginPath();
        g.arc(rp.p.x, rp.p.y, 4 + u * 22, 0, Math.PI * 2);
        g.stroke();
      }
      g.globalAlpha = 1;
      // 물감 접시
      const cur = PALETTE[pi % PALETTE.length]!;
      g.fillStyle = 'rgba(255,255,255,0.9)';
      rrect(g, 330, 210, 44, 14, 7);
      g.fill();
      for (let i = 0; i < 4; i++) {
        g.fillStyle = PALETTE[(pi + i) % PALETTE.length]!;
        g.beginPath();
        g.arc(338 + i * 9.5, 217, i ? 3 : 4.4, 0, Math.PI * 2);
        g.fill();
      }
      g.strokeStyle = cur;
      g.lineWidth = 0.8;
    },
    script() {
      const order: [number, number, number][] = [
        [118, 108, 0],
        [88, 180, 1],
        [116, 186, 2],
        [145, 139, 3],
        [157, 150, 3],
        [88, 145, 3],
        [322, 64, 4],
        [253, 112, 5],
        [253, 180, 6],
        [200, 222, 7],
        [50, 100, 8],
      ];
      const acts: Act[] = [WAIT(0.3)];
      for (const [x, y, c] of order) acts.push(DO(() => (pi = c)), TAP(x, y), WAIT(0.3));
      acts.push(WAIT(1.6));
      return acts;
    },
    controls: [{ type: 'button', label: '색 바꾸기', on: () => pi++ }],
  };
}
```

### i314 견본 항목 — `src/demos/demosDrawTools.ts:3436`
```ts
  i314: dom('페인트 통 — 누른 곳과 이어진 같은 색 칸을 물결처럼 채움 (끌면 연필로 선 긋기)', (e) => paintBucket(e))
```

## 관련 기술
- 먼저 알면 좋은 기술: [부드러운 붓 선 (곡선 보정 · 압력)](https://ai-techstudio.web.app/ai/t/i312.md) `i312`
- 다음에 해 볼 기술: [되돌리기 · 다시 하기 (명령 기록)](https://ai-techstudio.web.app/ai/t/i317.md) `i317`