# AI 꾸러미 — 내비 메시 (다각형 길찾기) — Navigation mesh (navmesh)
> 걸을 수 있는 땅을 들로네 삼각형으로 나누고, 삼각형 줄을 A* 로 찾은 뒤 깔때기 알고리즘으로 당겨 모서리를 스치는 곧은 길을 만든다.  
> 견본: https://ai-techstudio.web.app/#t/i267

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

## 주문서

### 만들어 줘: 내비 메시 (다각형 길찾기) — Navigation mesh (navmesh)

#### 1. 목표
장애물이 있는 방에 내비 메시 길찾기를 넣어 줘 — 땅이 삼각형으로 나뉘고, 삼각형 줄(파랑) → 꼬불꼬불한 중심 길 → 깔때기로 당긴 곧은 길(노랑) 순서로 보이게. 분위기는 어두운 바탕 반투명 삼각형.

#### 2. 핵심 기술 용어
- **Navigation mesh (navmesh)** — 걸을 수 있는 땅을 다각형으로 나눈 지도
- **Delaunay triangulation (Bowyer–Watson)** — 외접원 안에 다른 점이 없는 삼각형 나누기
- **Funnel algorithm (string pulling)** — 삼각형 줄 안에서 실을 당기듯 곧은 길 만들기
- **Portal edges** — 이웃 삼각형 사이 공유 모서리 (지나는 문)

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

#### 4. 조건
- 삼각분할 점에 아주 작은 흔들림(±0.01)을 줘 같은 선 위 점들로 인한 퇴화 삼각형을 피하기
- 장애물 안 삼각형 거르기: 무게중심과 각 모서리 가운데 근처 점까지 장애물 안인지 확인 (얇은 삼각형이 장애물을 가로지르지 않게)
- 문(portal)의 왼쪽 · 오른쪽 방향을 일관되게 — 앞 삼각형 중심 기준 외적 부호로 정하고, 길이 땅 밖으로 나가면 방향을 뒤집어 다시
- 삼각형 보기 · 깔때기 켬/끔(중심 길과 비교)을 바꿀 수 있게

#### 5. 완성 기준 (이게 보이면 성공)
- 방이 반투명 삼각형으로 덮이고 장애물 자리는 비어 있다
- 파란 삼각형 줄 위에 꼬불꼬불한 중심 길과 노란 곧은 길이 함께 보이고, 곧은 길이 더 짧다
- 곧은 길은 장애물 모서리에서만 꺾이고 장애물을 뚫지 않는다
- 「새 방」 · 「새 문제」를 여러 번 눌러도 길이 늘 땅 안에 있다

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

## 원리
- 방 테두리(12 간격)와 장애물 테두리(6.5 간격)를 따라 점을 찍고 들로네 삼각분할을 한다 (커다란 삼각형에서 시작해 점을 하나씩 넣는 Bowyer–Watson).
- 무게중심이 장애물 안에 있는 삼각형은 버리면 남은 삼각형들이 걸을 수 있는 땅이 된다.
- 두 삼각형이 공유하는 모서리 = 지나는 문(portal). 삼각형 무게중심을 점으로, 문을 선으로 A* 를 돌리면 삼각형 줄이 나온다.
- 무게중심끼리 이으면 꼬불꼬불하다. 깔때기 알고리즘은 출발점(꼭짓점)에서 문의 왼쪽 · 오른쪽 끝으로 깔때기를 좁혀 가다, 두 줄이 엇갈리면 그 모서리를 새 꼭짓점으로 삼는다.
- 결과는 장애물 모서리만 스치며 꺾이는 가장 짧은 길이다.

## 핵심 코드 — 깔때기 알고리즘 (문 목록 → 곧은 길)
(발췌: demos/demosMapB.ts funnel · i267 newProblem 을 정리)
```ts
type V2 = [number, number];
const tri2 = (a: V2, b: V2, c: V2) => (c[0] - a[0]) * (b[1] - a[1]) - (b[0] - a[0]) * (c[1] - a[1]);
const eq = (a: V2, b: V2) => Math.abs(a[0] - b[0]) < 1e-9 && Math.abs(a[1] - b[1]) < 1e-9;
function funnel(start: V2, end: V2, portals: [V2, V2][]): V2[] {
  const P: [V2, V2][] = [[start, start], ...portals, [end, end]];
  const path: V2[] = [start];
  let apex = start, left = start, right = start, ai = 0, li = 0, ri = 0;
  for (let i = 1; i < P.length; i++) {
    const [L, Rr] = P[i];
    if (tri2(apex, right, Rr) <= 0) {                       // 오른쪽 줄을 좁힐 수 있나
      if (eq(apex, right) || tri2(apex, left, Rr) > 0) { right = Rr; ri = i; }
      else { path.push(left); apex = left; ai = li; left = right = apex; li = ri = ai; i = ai; continue; } // 엇갈림 → 왼쪽 끝이 새 꼭짓점
    }
    if (tri2(apex, left, L) >= 0) {                          // 왼쪽 줄을 좁힐 수 있나
      if (eq(apex, left) || tri2(apex, right, L) < 0) { left = L; li = i; }
      else { path.push(right); apex = right; ai = ri; left = right = apex; li = ri = ai; i = ai; continue; }
    }
  }
  if (!eq(path[path.length - 1], end)) path.push(end);
  return path;
}
// 삼각형 줄 → 문 목록 (앞 삼각형 중심 기준으로 왼쪽 · 오른쪽 정하기)
const raw: [V2, V2][] = [];
for (let i = 0; i + 1 < corridor.length; i++) {
  const e = M.nb[corridor[i]].find((n) => n.o === corridor[i + 1])!;
  const p = M.P[e.u], q = M.P[e.v], c = M.cen[corridor[i]];
  raw.push(tri2(c, p, q) > 0 ? [p, q] : [q, p]);
}
let straight = funnel(start, goal, raw);
if (!valid(straight)) straight = funnel(start, goal, raw.map(([p, q]) => [q, p])); // 방향이 반대였으면 뒤집어 다시
```

## 흔한 실수 · 확인 목록
- [ ] **문의 왼쪽 · 오른쪽을 섞으면 깔때기 길이 장애물을 뚫는다** — 모든 문을 같은 규칙(앞 삼각형 기준 외적 부호)으로 정하고, 길 위 점이 메시 밖이면 방향을 뒤집어 다시 돌린다.
- [ ] **삼각형 중심끼리 이은 길을 그대로 쓰면 캐릭터가 지그재그로 걷는다** — 삼각형 줄은 「어디를 지날지」만 정하고, 실제 길은 깔때기로 당긴다.
- [ ] **장애물 모서리를 가로지르는 얇은 삼각형이 남는다** — 무게중심만이 아니라 모서리 가운데 근처 점도 장애물 안인지 검사해 거른다.
- [ ] **점들이 한 줄로 놓이면 들로네가 깨진 삼각형을 만든다** — 점에 아주 작은 흔들림을 더하고, 외접원 분모가 0 에 가까우면 반지름 무한대로 둔다.

## 완성 기준 체크리스트
- [ ] 방이 반투명 삼각형으로 덮이고 장애물 자리는 비어 있다
- [ ] 파란 삼각형 줄 위에 꼬불꼬불한 중심 길과 노란 곧은 길이 함께 보이고, 곧은 길이 더 짧다
- [ ] 곧은 길은 장애물 모서리에서만 꺾이고 장애물을 뚫지 않는다
- [ ] 「새 방」 · 「새 문제」를 여러 번 눌러도 길이 늘 땅 안에 있다

## 이 기술 정보
- id: `i267` · 분류: 지도 · 길찾기 › 길찾기 · 이동 · 2D · 난이도 어려움 · 폰 부담 보통 (폰 주의) — 들로네는 점 n 개마다 모든 삼각형을 훑어 n² 정도 — 점 수백 개면 수 ms 라 방이 바뀔 때만 짓는다. 길찾기 · 깔때기는 삼각형 줄 길이만큼이라 가볍다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i267
- 쓰면 좋을 때: 넓은 열린 땅에서 캐릭터가 자연스럽게 걸어야 할 때 / 칸 격자로는 길이 지그재그로 보일 때 / 3D 게임 바닥 (같은 원리를 3D 바닥 다각형에)
- 쓰지 말 때: 칸 판 퍼즐 — 대신 A*(i264) / 같은 목표로 가는 유닛 수백 — 대신 흐름장(i265) / 장애물이 계속 움직이는 판 — 메시를 매번 다시 지어야 한다

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### locateTri — `src/demos/demosMapB.ts:1524`
```ts
function locateTri(M: NavMesh, p: V2): number {
  for (let i = 0; i < M.T.length; i++) {
    const [a, b, c] = M.T[i]!;
    if (inTri(p, M.P[a]!, M.P[b]!, M.P[c]!, 0)) return i;
  }
  return -1;
}
```

### i267 견본 항목 — `src/demos/demosMapB.ts:1823`
```ts
  i267: {
    kind: '2d',
    caption: '걸을 수 있는 땅을 삼각형으로 → 삼각형 줄(파랑) → 꼬불꼬불 중심 길 대신 깔때기로 당긴 곧은 길(노랑)',
    make() {
      let seed = 2;
      let M = buildNav(seed);
      let speed = 1;
      let showMesh = true;
      let useFunnel = true;
      let phaseT = 0;
      let prob = 0;
      let start: V2 = [0, 0];
      let goal: V2 = [0, 0];
      let corridor: number[] = [];
      let portals: [V2, V2][] = [];
      let zig: V2[] = [];
      let straight: V2[] = [];
      const layer = new Layer();
      const freeAt = (p: V2): boolean => locateTri(M, p) >= 0 && M.obs.every((o) => !inPoly(p, o));
      const meshHas = (p: V2): boolean => {
        for (const [a, b, c] of M.T) if (inTri(p, M.P[a]!, M.P[b]!, M.P[c]!, 1e-3)) return true;
        return false;
      };
      const valid = (path: V2[]): boolean => {
        for (let i = 1; i < path.length; i++)
          for (let k = 1; k < 16; k++) {
            const a = path[i - 1]!;
            const b = path[i]!;
            if (!meshHas([lerp(a[0], b[0], k / 16), lerp(a[1], b[1], k / 16)])) return false;
          }
        return true;
      };
      const newProblem = (): void => {
        prob++;
        const r = rng(seed * 1000 + prob);
        for (let tries = 0; tries < 200; tries++) {
          const a: V2 = [4 + r() * 30, 4 + r() * (M.H - 8)];
          const b: V2 = [M.W - 34 + r() * 30, 4 + r() * (M.H - 8)];
          if (r() < 0.5) {
            a[0] = M.W - a[0];
            b[0] = M.W - b[0];
          }
          if (!freeAt(a) || !freeAt(b)) continue;
          const ta = locateTri(M, a);
          const tb = locateTri(M, b);
          const cor = triCorridor(M, ta, tb);
          if (cor.length < 3) continue;
          start = a;
          goal = b;
          corridor = cor;
          break;
        }
        const raw: [V2, V2][] = [];
        for (let i = 0; i + 1 < corridor.length; i++) {
          const e = M.nb[corridor[i]!]!.find((n) => n.o === corridor[i + 1])!;
          const p = M.P[e.u]!;
          const q = M.P[e.v]!;
          const c = M.cen[corridor[i]!]!;
          raw.push(tri2(c, p, q) > 0 ? [p, q] : [q, p]);
        }
        portals = raw;
        straight = funnel(start, goal, raw);
        if (!valid(straight)) {
          portals = raw.map(([p, q]) => [q, p]);
          straight = funnel(start, goal, portals);
        }
        zig = [start, ...corridor.slice(1, -1).map((i) => M.cen[i]!), goal];
        phaseT = 0;
      };
      newProblem();
      const TRI_COL = ['#7fd3ff', '#a7f3d0', '#c4b5fd', '#fde68a', '#fbcfe8'];
      return {
        draw(g, w, h, t, dt) {
          reset(g);
          const u = scaleOf(w, h);
          const dpr = dprOf(g);
          phaseT += Math.min(dt, 0.1) * speed;
          bgGrad(g, w, h, '#1c2234', '#0e1220');
          const pad = 8 * u;
          const headH = 16 * u;
          const k = Math.min((w - pad * 2) / M.W, (h - headH - pad * 1.3) / M.H);
          const ox = (w - M.W * k) / 2;
          const oy = headH + (h - headH - pad * 0.5 - M.H * k) / 2;
          const S = (p: V2): V2 => [ox + p[0] * k, oy + p[1] * k];
          const L = layer.get(`${seed}|${w}|${h}|${dpr}|${showMesh}`, w, h, dpr, (lg) => {
            rr(lg, ox - 4 * u, oy - 4 * u, M.W * k + 8 * u, M.H * k + 8 * u, 6 * u);
            lg.fillStyle = '#3a3346';
            lg.fill();
            lg.fillStyle = '#2a3142';
            lg.fillRect(ox, oy, M.W * k, M.H * k);
            // 바닥 돌 판
            const tile = 10 * k;
            lg.save();
            lg.beginPath();
            lg.rect(ox, oy, M.W * k, M.H * k);
            lg.clip();
            for (let y = 0; y < M.H * k; y += tile)
              for (let x = 0; x < M.W * k; x += tile) {
                lg.fillStyle = `rgba(255,255,255,${0.02 + 0.03 * hash2(x | 0, y | 0, 4)})`;
                lg.fillRect(ox + x + 0.5, oy + y + 0.5, tile - 1, tile - 1);
              }
            lg.restore();
            if (showMesh) {
              M.T.forEach(([a, b, c], i) => {
                const pa = S(M.P[a]!);
                const pb = S(M.P[b]!);
                const pc = S(M.P[c]!);
                lg.beginPath();
                lg.moveTo(pa[0], pa[1]);
                lg.lineTo(pb[0], pb[1]);
                lg.lineTo(pc[0], pc[1]);
                lg.closePath();
                lg.globalAlpha = 0.09;
                lg.fillStyle = TRI_COL[i % TRI_COL.length]!;
                lg.fill();
                lg.globalAlpha = 1;
                lg.strokeStyle = 'rgba(140,220,255,0.33)';
                lg.lineWidth = Math.max(0.6, 0.7 * u);
                lg.stroke();
              });
            }
            // 장애물: 그림자 → 옆면 → 윗면
            for (const o of M.obs) {
              const sp = o.map(S);
              const poly = (dx: number, dy: number): void => {
                lg.beginPath();
                sp.forEach(([x, y], i) => (i ? lg.lineTo(x + dx, y + dy) : lg.moveTo(x + dx, y + dy)));
                lg.closePath();
              };
              poly(3 * u, 4 * u);
              lg.fillStyle = 'rgba(0,0,0,0.45)';
              lg.fill();
              poly(0, 0);
              lg.fillStyle = '#5b4636';
              lg.fill();
              poly(0, -3 * u);
              const gr = lg.createLinearGradient(sp[0]![0], sp[0]![1] - 20 * u, sp[2]![0], sp[2]![1]);
              gr.addColorStop(0, '#c9a27a');
              gr.addColorStop(1, '#8d6a4c');
              lg.fillStyle = gr;
              lg.fill();
              lg.strokeStyle = 'rgba(60,40,25,0.6)';
              lg.lineWidth = 1 * u;
              lg.stroke();
              // 나무 판 줄
              lg.save();
              lg.clip();
              lg.strokeStyle = 'rgba(80,55,35,0.35)';
              for (let q = -40; q < 40; q += 4) {
                lg.beginPath();
                lg.moveTo(sp[0]![0] + q * u * 1.5, sp[0]![1] - 30 * u);
                lg.lineTo(sp[0]![0] + q * u * 1.5 + 30 * u, sp[0]![1] + 30 * u);
                lg.stroke();
              }
              lg.restore();
            }
          });
          g.drawImage(L, 0, 0, w, h);
          // 단계: 삼각형 줄 → 중심 길 → 문(포털) → 곧은 길 → 걷기
          const tA = 1.1;
          const tB = tA + 0.7;
          const tC = tB + 0.9;
          const walkLen = polyLen(useFunnel ? straight : zig);
          const tD = tC + Math.min(3, walkLen / 45);
          if (phaseT > tD + 0.9) newProblem();
          const nCor = Math.min(corridor.length, Math.floor((phaseT / tA) * corridor.length) + 1);
          for (let i = 0; i < nCor; i++) {
            const [a, b, c] = M.T[corridor[i]!]!;
            const pa = S(M.P[a]!);
            const pb = S(M.P[b]!);
            const pc = S(M.P[c]!);
            g.beginPath();
            g.moveTo(pa[0], pa[1]);
            g.lineTo(pb[0], pb[1]);
            g.lineTo(pc[0], pc[1]);
            g.closePath();
            const fresh = i === nCor - 1 && phaseT < tA;
            g.fillStyle = fresh ? 'rgba(160,230,255,0.75)' : 'rgba(80,170,255,0.32)';
            g.fill();
            g.strokeStyle = 'rgba(150,215,255,0.8)';
            g.lineWidth = 0.8 * u;
            g.stroke();
          }
          // 중심 길 (지그재그)
          if (phaseT > tA) {
            g.setLineDash([3 * u, 3 * u]);
            g.strokeStyle = 'rgba(255,255,255,0.75)';
            g.lineWidth = 1.3 * u;
            strokePathPart(g, zig.map(S), (phaseT - tA) / (tB - tA));
            g.setLineDash([]);
            g.fillStyle = 'rgba(255,255,255,0.8)';
            for (const p of zig.slice(1, -1)) {
              const q = S(p);
              g.beginPath();
              g.arc(q[0], q[1], 1.6 * u, 0, TAU);
              g.fill();
            }
          }
          // 포털과 깔때기 곧은 길
          if (phaseT > tB && useFunnel) {
            const pk = clamp01((phaseT - tB) / (tC - tB));
            const nP = Math.floor(pk * portals.length);
            g.lineCap = 'round';
            for (let i = 0; i < Math.min(portals.length, nP + 1); i++) {
              const [l, r] = portals[i]!;
              const a = S(l);
              const b = S(r);
              g.strokeStyle = 'rgba(255,214,102,0.45)';
              g.lineWidth = 2 * u;
              g.beginPath();
              g.moveTo(a[0], a[1]);
              g.lineTo(b[0], b[1]);
              g.stroke();
            }
            glowStroke(g, straight.map(S), pk, '#ffd166', 2.4 * u);
            for (const p of straight.slice(1, -1)) {
              const q = S(p);
              g.fillStyle = '#fff';
              g.beginPath();
              g.arc(q[0], q[1], 2.4 * u, 0, TAU);
              g.fill();
            }
          }
          // 걷는 캐릭터
          const path = useFunnel ? straight : zig;
          const wk = clamp01((phaseT - tC) / (tD - tC));
          const [pos, ang] = alongPoly(path, ease(wk) * polyLen(path));
          const sp = S(start);
          const gp = S(goal);
          drawFlag(g, sp[0], sp[1] + 2 * u, 13 * u, '#3ddc84');
          drawPin(g, gp[0], gp[1] + 2 * u, 13 * u, '#ff4f6b', t);
          const hp = S(pos);
          drawHero(g, hp[0], hp[1], 11 * u, ang, '#ffd166');
          txt(g, '내비 메시', 8 * u, headH / 2 + 1 * u, 10.5 * u, '#9fe0ff', 'left', 900);
          const step = phaseT < tA ? '① 삼각형 줄 찾기' : phaseT < tB ? '② 중심을 이은 길' : phaseT < tC ? (useFunnel ? '③ 깔때기로 당기기' : '③ 중심 길 그대로') : '④ 걷기';
          pill(g, `${step} · 삼각형 ${M.T.length}개`, w - 7 * u, headH / 2 + 1 * u, 7.5 * u, 'rgba(255,255,255,0.12)', '#e8ecff', 'right');
          if (phaseT > tC) {
            const a = polyLen(zig);
            const b = polyLen(straight);
            pill(g, `중심 길 ${a.toFixed(0)} → 곧은 길 ${b.toFixed(0)}`, w / 2, h - 9 * u, 7.5 * u, 'rgba(255,190,60,0.92)', '#2a1a00');
          }
        },
        controls: [
          { type: 'toggle', label: '삼각형 보기', value: true, on: (v) => (showMesh = v) },
          { type: 'toggle', label: '깔때기로 곧게 (끄면 중심 길)', value: true, on: (v) => ((useFunnel = v), (phaseT = 0)) },
          { type: 'range', label: '속도', min: 0.3, max: 3, step: 0.1, value: 1, on: (v) => (speed = v) },
          { type: 'button', label: '새 문제', on: newProblem },
          { type: 'button', label: '새 방', on: () => ((seed++), (M = buildNav(seed)), newProblem()) },
        ] as Control[],
      };
    },
  }
```

## 관련 기술
- 먼저 알면 좋은 기술: [A* 길찾기 (열린 · 닫힌 칸 보기)](https://ai-techstudio.web.app/ai/t/i264.md) `i264` · [보로노이 지역 · 나라 나누기](https://ai-techstudio.web.app/ai/t/i246.md) `i246`
- 다음에 해 볼 기술: [시야 · 가림 (그림자 던지기 FOV)](https://ai-techstudio.web.app/ai/t/i268.md) `i268`
- 참고 문서: [Wikipedia — Bowyer–Watson algorithm](https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm)