# AI 꾸러미 — 포아송 원판 흩뿌리기 — Poisson disk sampling (Bridson)
> 이미 놓인 점 둘레 고리(r ~ 2r)에서만 새 점을 던져 서로 최소 거리를 지키게 해서, 나무 · 바위가 뭉치지도 비지도 않고 고르게 흩어진다.  
> 견본: https://ai-techstudio.web.app/#t/i254

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

## 주문서

### 만들어 줘: 포아송 원판 흩뿌리기 — Poisson disk sampling (Bridson)

#### 1. 목표
숲의 나무 배치를 포아송 원판 흩뿌리기로 배치해 줘 — 서로 최소 거리를 지키며 고르게, 그냥 무작위와 나란히 비교할 수 있게. 그림은 위에서 내려다본 귀여운 숲.

#### 2. 핵심 기술 용어
- **Poisson disk sampling (Bridson)** — 포아송 원판 흩뿌리기 — 서로 r 이상 떨어진 무작위 점
- **Active list** — 아직 둘레에 점을 더 놓을 수 있는 점 목록
- **Background grid (cell = r/√2)** — 칸 하나에 점 하나 — 가까운 점만 빠르게 확인
- **Blue noise distribution** — 고르게 퍼진 무작위 (뭉침 없음)

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

#### 4. 조건
- 격자 칸 크기는 반드시 r/√2 이하 — 그래야 칸 하나에 점 하나만 들어간다
- 가장자리에 여백(0.02)을 둬 나무가 판 밖으로 잘리지 않게
- 그냥 무작위와 같은 수의 점으로 나란히 비교 — 너무 가까운 짝을 빨간 선으로
- 3D 로 쓰면 점 수천 개를 하나씩 메시로 만들지 말고 InstancedMesh 로

#### 5. 완성 기준 (이게 보이면 성공)
- 왼쪽 그냥 무작위는 빨간 선(너무 가까운 짝)이 여기저기, 오른쪽 포아송 원판은 하나도 없다
- 만드는 중에 활성 점(노랑) · 지금 고리 · 던져 본 점(성공 초록 · 실패 빨강)이 보인다
- 「최소 거리」를 줄이면 나무가 빽빽해지고 늘리면 듬성해지지만 늘 고르다
- 같은 시드면 같은 숲이 나온다

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

## 원리
- 그냥 무작위는 우연히 뭉치는 곳과 텅 빈 곳이 생긴다. 포아송 원판은 「어떤 두 점도 r 보다 가깝지 않게」를 지킨다.
- 첫 점을 놓고 활성 목록에 넣는다. 활성 점 하나를 골라 둘레 r ~ 2r 고리 안에 최대 18번 던져 본다.
- 던진 자리가 다른 점과 모두 r 이상 떨어져 있으면 놓고 활성 목록에 더한다. 18번 다 실패하면 그 활성 점을 뺀다.
- 확인을 빠르게 하려고 한 칸 = r/√2 인 격자를 둔다 — 칸 하나에 점이 많아야 하나라, 둘레 5 × 5 칸만 보면 된다.
- 활성 목록이 비면 끝 — 판이 고르게 꽉 찬다.

## 핵심 코드 — 브리드슨 포아송 원판 (끝까지 한 번에)
(발췌: demos/demosMapA.ts i254 step · far · add 를 한 번에 도는 꼴로)
```ts
function poisson(AW: number, AH: number, rad: number, rng: () => number, k = 18) {
  const cs = rad / Math.SQRT2;                         // 칸 하나에 점 하나
  const gw = Math.ceil(AW / cs), gh = Math.ceil(AH / cs);
  const grid = new Int32Array(gw * gh).fill(-1);
  const pts: { x: number; y: number }[] = [];
  const active: number[] = [];
  const add = (x: number, y: number) => {
    pts.push({ x, y });
    active.push(pts.length - 1);
    grid[Math.floor(y / cs) * gw + Math.floor(x / cs)] = pts.length - 1;
  };
  const far = (x: number, y: number) => {
    const gx = Math.floor(x / cs), gy = Math.floor(y / cs);
    for (let j = gy - 2; j <= gy + 2; j++)
      for (let i = gx - 2; i <= gx + 2; i++) {
        if (i < 0 || j < 0 || i >= gw || j >= gh) continue;
        const q = grid[j * gw + i];
        if (q >= 0 && Math.hypot(pts[q].x - x, pts[q].y - y) < rad) return false;
      }
    return true;
  };
  add(AW * (0.3 + rng() * 0.4), AH * (0.3 + rng() * 0.4));
  while (active.length) {
    const ai = Math.floor(rng() * active.length);
    const p = pts[active[ai]];
    let placed = false;
    for (let t = 0; t < k; t++) {
      const a = rng() * Math.PI * 2, d = rad * (1 + rng());   // r ~ 2r 고리
      const x = p.x + Math.cos(a) * d, y = p.y + Math.sin(a) * d;
      if (x > 0.02 && y > 0.02 && x < AW - 0.02 && y < AH - 0.02 && far(x, y)) { add(x, y); placed = true; break; }
    }
    if (!placed) active.splice(ai, 1);                 // 둘레가 꽉 찼다
  }
  return pts;
}
```

## 흔한 실수 · 확인 목록
- [ ] **격자 칸을 r 로 잡으면 가까운 점을 놓친다** — 칸 대각선이 r 이 되도록 r/√2 로 잡아야 칸 하나에 점이 많아야 하나 — 그래서 둘레 ±2 칸만 보면 된다.
- [ ] **모든 점과 거리를 재면 점이 많을 때 아주 느리다** — 격자에서 둘레 5 × 5 칸만 확인한다 (n² → 거의 n).
- [ ] **그냥 무작위에 「너무 가까우면 다시 뽑기」만 하면 끝에 가서 무한히 돈다** — 빈자리가 거의 없을 때 끝을 모른다. 활성 목록 방식은 고리 18번 실패로 끝이 정해진다.
- [ ] **나무가 판 가장자리에서 반쯤 잘린다** — 점은 여백(0.02) 안쪽에만 놓고, 그릴 때는 y 순으로 정렬해 앞 나무가 뒤 나무를 덮게 한다.

## 완성 기준 체크리스트
- [ ] 왼쪽 그냥 무작위는 빨간 선(너무 가까운 짝)이 여기저기, 오른쪽 포아송 원판은 하나도 없다
- [ ] 만드는 중에 활성 점(노랑) · 지금 고리 · 던져 본 점(성공 초록 · 실패 빨강)이 보인다
- [ ] 「최소 거리」를 줄이면 나무가 빽빽해지고 늘리면 듬성해지지만 늘 고르다
- [ ] 같은 시드면 같은 숲이 나온다

## 이 기술 정보
- id: `i254` · 분류: 지도 · 길찾기 › 지도 생성 (절차) · 2D · 난이도 쉬움 · 폰 부담 가벼움 (폰 OK) — 점 하나 놓기에 둘레 25칸 확인 × 최대 18번. 수천 개도 한 번에 금방 — 3D 배치는 만든 뒤 인스턴싱으로 그린다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i254
- 쓰면 좋을 때: 나무 · 풀 · 바위 · 별처럼 많은 장식을 자연스럽게 흩뿌릴 때 / 「무작위인데 고르게」를 비교해 보여 줄 때
- 쓰지 말 때: 딱 정해진 줄 · 격자 배치가 필요할 때 — 그냥 격자 + 작은 흔들림이 더 쉽다 / 점 수를 정확히 정해야 할 때 — 포아송은 수가 r 에 따라 정해진다

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### i254 견본 항목 — `src/demos/demosMapA.ts:2657`
```ts
  i254: {
    kind: '2d',
    caption: '왼쪽 그냥 무작위는 뭉치고 비어요 — 오른쪽 포아송 원판: 활성 점 둘레 고리(r~2r)에서만 새 점, 서로 최소 거리를 지켜 고른 숲',
    make() {
      let rad = 0.075;
      let rings = true;
      interface Pt { x: number; y: number; born: number; c: number }
      let pts: Pt[] = [];
      let rnd: Pt[] = [];
      let active: number[] = [];
      let tries: { x: number; y: number; ok: boolean; t: number }[] = [];
      let cur = -1;
      let clock = 0;
      let rng = mulberry(1);
      let grid: Int32Array = new Int32Array(0);
      let gw = 0;
      let gh = 0;
      const AW = 1;
      const AH = 1.25;
      const run = runner({
        rate: 60,
        hold: 1.8,
        start(seed) {
          rng = mulberry(seed);
          pts = [];
          rnd = [];
          active = [];
          tries = [];
          const cs = rad / Math.SQRT2;
          gw = Math.ceil(AW / cs);
          gh = Math.ceil(AH / cs);
          grid = new Int32Array(gw * gh).fill(-1);
          add(AW * (0.3 + rng() * 0.4), AH * (0.3 + rng() * 0.4));
        },
        step() {
          // 활성 점 하나에서 k 번 던져 보기
          if (!active.length) return true;
          const ai = Math.floor(rng() * active.length);
          const p = pts[active[ai]!]!;
          cur = active[ai]!;
          let placed = false;
          for (let k = 0; k < 18; k++) {
            const a = rng() * TAU;
            const d = rad * (1 + rng());
            const x = p.x + Math.cos(a) * d;
            const y = p.y + Math.sin(a) * d;
            const ok = x > 0.02 && y > 0.02 && x < AW - 0.02 && y < AH - 0.02 && far(x, y);
            tries.push({ x, y, ok, t: clock });
            if (ok) {
              add(x, y);
              placed = true;
              break;
            }
          }
          if (!placed) active.splice(ai, 1);
          // 같은 수만큼 그냥 무작위
          while (rnd.length < pts.length) rnd.push({ x: 0.02 + rng() * (AW - 0.04), y: 0.02 + rng() * (AH - 0.04), born: clock, c: rng() });
          if (tries.length > 60) tries.splice(0, tries.length - 60);
          return false;
        },
      });
      const far = (x: number, y: number): boolean => {
        const cs = rad / Math.SQRT2;
        const gx = Math.floor(x / cs);
        const gy = Math.floor(y / cs);
        for (let j = gy - 2; j <= gy + 2; j++)
          for (let i = gx - 2; i <= gx + 2; i++) {
            if (i < 0 || j < 0 || i >= gw || j >= gh) continue;
            const q = grid[j * gw + i]!;
            if (q >= 0 && Math.hypot(pts[q]!.x - x, pts[q]!.y - y) < rad) return false;
          }
        return true;
      };
      const add = (x: number, y: number): void => {
        const cs = rad / Math.SQRT2;
        pts.push({ x, y, born: clock, c: rng() });
        const k = pts.length - 1;
        active.push(k);
        grid[Math.floor(y / cs) * gw + Math.floor(x / cs)] = k;
      };
      run.restart();
      const tree = (g: G, x: number, y: number, r: number, c: number, grow: number): void => {
        const rr2 = r * (grow < 1 ? ease(grow) * 1.15 : 1);
        if (rr2 <= 0.2) return;
        g.fillStyle = 'rgba(10,40,10,0.35)';
        g.beginPath();
        g.ellipse(x + rr2 * 0.25, y + rr2 * 0.35, rr2 * 1.02, rr2 * 0.8, 0, 0, TAU);
        g.fill();
        const base = mix([46, 120, 58], [92, 160, 70], c);
        g.fillStyle = rgb(base);
        g.beginPath();
        g.arc(x, y, rr2, 0, TAU);
        g.fill();
        g.fillStyle = rgb(mix(base, [255, 255, 200], 0.25));
        g.beginPath();
        g.arc(x - rr2 * 0.28, y - rr2 * 0.3, rr2 * 0.45, 0, TAU);
        g.fill();
      };
      return {
        draw(g, w, h, _t, dt) {
          reset(g);
          clock += dt;
          run.tick(dt);
          const u = ui(scaleOf(w, h));
          g.fillStyle = '#20301f';
          g.fillRect(0, 0, w, h);
          const top = 18 * u;
          const pw = Math.min((w - 18 * u) / 2, ((h - top - 6 * u) * AW) / AH);
          const ph = (pw * AH) / AW;
          const gap = (w - pw * 2) / 3;
          const panels: [number, Pt[], string, boolean][] = [
            [gap, rnd, '그냥 무작위', false],
            [gap * 2 + pw, pts, '포아송 원판', true],
          ];
          for (const [px, list, name, isP] of panels) {
            const py = top + (h - top - ph) / 2 - 2 * u;
            rr(g, px, py, pw, ph, 6 * u);
            const gr = g.createLinearGradient(0, py, 0, py + ph);
            gr.addColorStop(0, '#9ccf72');
            gr.addColorStop(1, '#79b356');
            g.fillStyle = gr;
            g.fill();
            g.save();
            rr(g, px, py, pw, ph, 6 * u);
            g.clip();
            const S = pw / AW;
            if (rings) {
              g.fillStyle = 'rgba(255,255,255,0.13)';
              for (const p of list) {
                g.beginPath();
                g.arc(px + p.x * S, py + p.y * S, (rad / 2) * S, 0, TAU);
                g.fill();
              }
              if (!isP) {
                // 너무 가까운 짝 = 빨간 선
                g.strokeStyle = 'rgba(230,40,40,0.85)';
                g.lineWidth = 1.4 * u;
                g.beginPath();
                for (let i = 0; i < list.length; i++)
                  for (let j = i + 1; j < list.length; j++) {
                    const a = list[i]!;
                    const b = list[j]!;
                    if (Math.hypot(a.x - b.x, a.y - b.y) < rad) {
                      g.moveTo(px + a.x * S, py + a.y * S);
                      g.lineTo(px + b.x * S, py + b.y * S);
                    }
                  }
                g.stroke();
              }
            }
            const sorted = [...list].sort((a, b) => a.y - b.y);
            for (const p of sorted) tree(g, px + p.x * S, py + p.y * S, rad * 0.42 * S, p.c, (clock - p.born) / 0.35);
            if (isP && !run.holding) {
              // 활성 점 · 고리 · 던져 본 점
              g.fillStyle = 'rgba(255,200,60,0.9)';
              for (const a of active) {
                const p = pts[a]!;
                g.beginPath();
                g.arc(px + p.x * S, py + p.y * S, 1.6 * u, 0, TAU);
                g.fill();
              }
              const c = pts[cur];
              if (c) {
                g.beginPath();
                g.arc(px + c.x * S, py + c.y * S, rad * 2 * S, 0, TAU);
                g.arc(px + c.x * S, py + c.y * S, rad * S, 0, TAU, true);
                g.fillStyle = 'rgba(255,230,90,0.22)';
                g.fill('evenodd');
                g.strokeStyle = 'rgba(255,230,90,0.9)';
                g.lineWidth = 1.2 * u;
                g.beginPath();
                g.arc(px + c.x * S, py + c.y * S, rad * S, 0, TAU);
                g.stroke();
              }
              for (const q of tries) {
                const k = 1 - (clock - q.t) / 0.5;
                if (k <= 0) continue;
                g.globalAlpha = k;
                g.fillStyle = q.ok ? '#7dff9a' : '#ff5a5a';
                g.beginPath();
                g.arc(px + q.x * S, py + q.y * S, 1.8 * u, 0, TAU);
                g.fill();
              }
              g.globalAlpha = 1;
            }
            g.restore();
            txt(g, name, px + pw / 2, 10 * u, 9 * u, isP ? '#ffe680' : '#e8e8e8', 'center', 800);
          }
          txt(g, `나무 ${pts.length}그루씩`, w / 2, h - 6 * u, 7 * u, 'rgba(255,255,255,0.6)', 'center', 700);
        },
        controls: [
          seedCtl(run),
          speedCtl(run),
          { type: 'range', label: '최소 거리', min: 0.05, max: 0.14, step: 0.005, value: 0.075, on: (v) => { rad = v; run.restart(run.seed); } },
          { type: 'toggle', label: '거리 원 · 너무 가까운 짝', value: true, on: (v) => { rings = v; } },
        ],
      };
    },
  }
```

## 관련 기술
- 먼저 알면 좋은 기술: [잡음 섬 지도 (높이 → 생물군)](https://ai-techstudio.web.app/ai/t/i245.md) `i245`
- 다음에 해 볼 기술: [파동 함수 붕괴 (WFC) 타일 맞춤](https://ai-techstudio.web.app/ai/t/i249.md) `i249`
- 참고 문서: [Bridson (2007) — Fast Poisson Disk Sampling in Arbitrary Dimensions](https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf)