# AI 꾸러미 — 다익스트라 비용 지도 (지형 비용) — Dijkstra's algorithm with terrain cost (weighted grid)
> 길 1 · 풀 2 · 모래 3 · 늪 5 처럼 칸마다 비용이 다른 지도에 다익스트라를 돌려, 같은 시간 선(등시선)이 지형 따라 퍼지는 모습을 그린다.  
> 견본: https://ai-techstudio.web.app/#t/i266

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

## 주문서

### 만들어 줘: 다익스트라 비용 지도 (지형 비용) — Dijkstra's algorithm with terrain cost (weighted grid)

#### 1. 목표
길 · 풀 · 모래 · 늪이 있는 지도에 지형 비용 다익스트라를 넣어 줘 — 출발점에서 같은 시간 선이 길을 따라 길쭉하게, 늪에서는 촘촘하게 퍼지고, 끝나면 가장 빠른 길이 그려지게. 분위기는 지도 색 + 색 띠.

#### 2. 핵심 기술 용어
- **Dijkstra's algorithm with terrain cost (weighted grid)** — 칸 비용이 다른 격자의 최단 거리
- **Isochrone map** — 같은 시간에 닿는 곳을 이은 선
- **Cost map / travel time map** — 칸마다 걸리는 시간 지도

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

#### 4. 조건
- 칸 사이 비용은 두 칸 비용의 평균 × 이동 길이 (한쪽 칸 비용만 쓰면 방향에 따라 값이 달라진다)
- 물 같은 못 가는 칸은 Infinity 로, 대각선은 모서리 끼어 지나가기 금지
- 시간 T 를 0 에서 최대값까지 늘리며 색 띠 · 등시선이 퍼지는 모습 보이기
- 「지형 비용 끄기(모두 1)」로 둥글게 퍼지는 것과 비교

#### 5. 완성 기준 (이게 보이면 성공)
- 등시선이 길을 따라 길쭉하게 뻗고, 늪 · 모래에서는 촘촘하다
- 지형 비용을 끄면 등시선이 거의 둥근 팔각형이 된다
- 퍼짐이 끝나면 출발점에서 도착점까지 가장 빠른 길이 그어지는데, 곧은 길보다 길(갈색)을 타고 돌아간다
- 「새 지도」 · 「새 출발점」으로 바로 바뀐다

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

## 원리
- 칸마다 지나는 비용(길 1 · 풀 2 · 모래 3 · 늪 5 · 물 ∞)을 둔다.
- 두 칸 사이 비용 = (두 칸 비용의 평균) × 이동 길이(곧게 1 · 대각선 √2).
- 출발점에서 다익스트라를 끝까지 돌리면 모든 칸의 「가장 빠른 시간」이 나온다.
- 그 값이 시간 T 이하인 칸만 칠하고, 일정 간격의 값마다 마칭 스퀘어로 선을 그으면 등시선 — 길 위에서는 멀리, 늪에서는 조금만 퍼진다.
- 도착점에서 시간이 가장 작게 줄어드는 이웃을 따라 거꾸로 걸으면 가장 빠른 길이 나온다.

## 핵심 코드 — 비용 지도 다익스트라 + 가장 빠른 길 되짚기
(발췌: demos/demosMapB.ts dijkstra · i266 newProblem 을 정리)
```ts
const COST = [1, 2, 3, 5, Infinity]; // 길 · 풀 · 모래 · 늪 · 물
const cost = new Float32Array(C * R);
for (let i = 0; i < C * R; i++) cost[i] = flat && terr[i] !== 4 ? 1 : COST[terr[i]];

function dijkstra(cols: number, rows: number, cost: Float32Array, src: number): Float32Array {
  const dist = new Float32Array(cols * rows).fill(Infinity);
  const heap = new Heap();
  dist[src] = 0; heap.push(0, src);
  const blocked = (j: number) => !isFinite(cost[j]);
  while (heap.size) {
    const i = heap.pop(), di = dist[i];
    eachNb(cols, rows, blocked, i, (j, len) => {
      const nd = di + ((cost[i] + cost[j]) / 2) * len; // 두 칸 평균 × 길이(1 또는 √2)
      if (nd < dist[j] - 1e-6) { dist[j] = nd; heap.push(nd, j); }
    });
  }
  return dist;
}
// 가장 빠른 길: 도착점에서 시간이 가장 작은 이웃으로 거꾸로
const dist = dijkstra(C, R, cost, src);
const path: number[] = [];
for (let c = dst; c !== src; ) {
  path.unshift(c);
  let bj = -1, bd = dist[c];
  eachNb(C, R, (j) => !isFinite(cost[j]), c, (j) => { if (dist[j] < bd) { bd = dist[j]; bj = j; } });
  if (bj < 0) break;
  c = bj;
}
path.unshift(src);
// 그리기: dist ≤ T 인 칸만 색 띠, band 간격마다 마칭 스퀘어로 등시선 (T 는 시간에 따라 0 → 최대)
```

## 흔한 실수 · 확인 목록
- [ ] **들어가는 칸 비용만 더하면 늪에서 나올 때와 들어갈 때 값이 다르다** — 두 칸 비용의 평균 × 이동 길이로 잰다.
- [ ] **힙에 같은 칸이 여러 번 들어가 오래된 값으로 다시 퍼진다** — 꺼낸 거리가 지금 거리보다 크면 건너뛰거나, 더 작아질 때만 넣는다 (nd < dist[j]).
- [ ] **칸 경계로 등시선을 그리면 계단이 거칠다** — 칸 가운데 값으로 마칭 스퀘어(i259)를 돌려 매끈한 선을 뽑는다.

## 완성 기준 체크리스트
- [ ] 등시선이 길을 따라 길쭉하게 뻗고, 늪 · 모래에서는 촘촘하다
- [ ] 지형 비용을 끄면 등시선이 거의 둥근 팔각형이 된다
- [ ] 퍼짐이 끝나면 출발점에서 도착점까지 가장 빠른 길이 그어지는데, 곧은 길보다 길(갈색)을 타고 돌아간다
- [ ] 「새 지도」 · 「새 출발점」으로 바로 바뀐다

## 이 기술 정보
- id: `i266` · 분류: 지도 · 길찾기 › 길찾기 · 이동 · 2D · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 40×25 = 1,000칸 다익스트라 한 번(문제가 바뀔 때만). 등시선은 격자 위 마칭 스퀘어라 프레임마다 그려도 가볍다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i266
- 쓰면 좋을 때: 지형마다 이동 속도가 다를 때 / 「여기서 3분 안에 갈 수 있는 곳」 범위를 보여 줄 때 / 전략 게임 이동 범위 · 시간 비교
- 쓰지 말 때: 출발 · 도착이 정해진 길 하나만 필요할 때 — 대신 A*(i264, 더 적게 살펴봄) / 비용이 모두 같은 판 — 너비 우선 탐색이면 충분

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### clamp01 — `src/demos/demosMapB.ts:18`
```ts
const clamp01 = (x: number): number => clamp(x, 0, 1);
```

### i266 견본 항목 — `src/demos/demosMapB.ts:1014`
```ts
  i266: {
    kind: '2d',
    caption: '길 1 · 풀 2 · 모래 3 · 늪 5 — 같은 시간 선(등시선)이 길을 따라 길쭉하게, 늪에서는 촘촘하게 퍼져요',
    make() {
      const C = 40;
      const R = 25;
      const T_ROAD = 0;
      const T_GRASS = 1;
      const T_SAND = 2;
      const T_SWAMP = 3;
      const T_WATER = 4;
      const COST = [1, 2, 3, 5, Infinity];
      const TCOL = ['#a8784a', '#6fae58', '#ecd9a0', '#5f7a4a', '#2f6fa3'];
      let seed = 4;
      let terr = new Uint8Array(C * R);
      let src = 0;
      let dst = 0;
      let dist: Float32Array = new Float32Array(C * R);
      let path: number[] = [];
      let flat = false;
      let speed = 1;
      let phaseT = 0;
      let rounds = 0;
      const layer = new Layer();
      const small = mk(C, R);
      const sg = small.getContext('2d')!;
      const img = sg.createImageData(C, R);
      const buildTerrain = (): void => {
        terr = new Uint8Array(C * R);
        for (let y = 0; y < R; y++)
          for (let x = 0; x < C; x++) {
            const n = fbm(x * 0.09, y * 0.11, seed, 4);
            const m = fbm(x * 0.13 + 40, y * 0.13, seed + 5, 3);
            let k = T_GRASS;
            if (n < 0.34) k = T_WATER;
            else if (n < 0.41) k = T_SWAMP;
            else if (m > 0.6) k = T_SAND;
            terr[y * C + x] = k;
          }
        // 길 두 개 (가로 · 세로로 구불구불)
        const r = rng(seed * 7);
        for (let q = 0; q < 2; q++) {
          let x = q === 0 ? 0 : 6 + Math.floor(r() * (C - 12));
          let y = q === 0 ? 4 + Math.floor(r() * (R - 8)) : 0;
          for (let k = 0; k < 200; k++) {
            terr[y * C + x] = T_ROAD;
            if (q === 0) {
              x++;
              if (r() < 0.25) y = clamp(y + (r() < 0.5 ? -1 : 1), 1, R - 2);
              if (x >= C) break;
            } else {
              y++;
              if (r() < 0.25) x = clamp(x + (r() < 0.5 ? -1 : 1), 1, C - 2);
              if (y >= R) break;
            }
            terr[y * C + Math.min(C - 1, x)] = T_ROAD;
          }
        }
      };
      const costArr = (): Float32Array => {
        const c = new Float32Array(C * R);
        for (let i = 0; i < C * R; i++) c[i] = terr[i] === T_WATER ? Infinity : flat ? 1 : COST[terr[i]!]!;
        return c;
      };
      const newProblem = (): void => {
        const r = rng(seed * 131 + rounds * 7 + 1);
        const land = (): number => {
          for (;;) {
            const i = Math.floor(r() * C * R);
            if (terr[i] !== T_WATER) return i;
          }
        };
        const cost = costArr();
        for (let k = 0; k < 20; k++) {
          src = land();
          dist = dijkstra(C, R, cost, src);
          let n = 0;
          for (let i = 0; i < C * R; i++) if (isFinite(dist[i]!)) n++;
          if (n > C * R * 0.5) break;
        }
        let best = src;
        for (let k = 0; k < 40; k++) {
          const i = land();
          if (isFinite(dist[i]!) && dist[i]! > dist[best]! && r() < 0.6) best = i;
        }
        dst = best;
        path = [];
        for (let c = dst; c !== src; ) {
          path.unshift(c);
          let bj = -1;
          let bd = dist[c]!;
          eachNb(C, R, (j) => !isFinite(cost[j]!), c, (j) => {
            if (dist[j]! < bd) {
              bd = dist[j]!;
              bj = j;
            }
          });
          if (bj < 0) break;
          c = bj;
        }
        path.unshift(src);
        phaseT = 0;
      };
      buildTerrain();
      newProblem();
      const BAND: RGB[] = ['#fff2a8', '#ffc46b', '#ff8a5c', '#e2587a', '#a74f9e', '#6252a8', '#3b4a96'].map(hexRGB);
      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;
          let maxD = 1;
          for (let i = 0; i < C * R; i++) if (isFinite(dist[i]!) && dist[i]! > maxD) maxD = dist[i]!;
          const DUR = 3.4;
          const T = (phaseT / DUR) * maxD;
          if (phaseT > DUR + 2.6) {
            rounds++;
            if (rounds % 3 === 0) seed++, buildTerrain();
            newProblem();
          }
          bgGrad(g, w, h, '#1a2233', '#0d1320');
          const headH = 18 * u;
          const fit = fitGrid(C, R, 5 * u, headH, w - 10 * u, h - headH - 5 * u);
          const { s, ox, oy } = fit;
          const L = layer.get(`${seed}|${w}|${h}|${dpr}`, w, h, dpr, (lg) => {
            rr(lg, ox - 3, oy - 3, C * s + 6, R * s + 6, 5);
            lg.fillStyle = 'rgba(0,0,0,0.4)';
            lg.fill();
            for (let i = 0; i < C * R; i++) {
              const x = ox + (i % C) * s;
              const y = oy + ((i / C) | 0) * s;
              const k = terr[i]!;
              const c = hexRGB(TCOL[k]!);
              const v = 0.9 + 0.2 * hash2(i, 3, seed);
              lg.fillStyle = css([c[0] * v, c[1] * v, c[2] * v]);
              lg.fillRect(x, y, s + 0.5, s + 0.5);
            }
            // 무늬: 풀 포기 · 모래 점 · 늪 갈대 · 물결
            const r = rng(seed + 99);
            for (let i = 0; i < C * R; i++) {
              const x = ox + (i % C) * s;
              const y = oy + ((i / C) | 0) * s;
              const k = terr[i]!;
              if (k === T_GRASS && r() < 0.5) {
                lg.strokeStyle = 'rgba(30,80,30,0.5)';
                lg.lineWidth = Math.max(0.6, s * 0.08);
                const gx = x + s * (0.2 + r() * 0.6);
                const gy = y + s * (0.4 + r() * 0.4);
                lg.beginPath();
                lg.moveTo(gx - s * 0.12, gy - s * 0.2);
                lg.lineTo(gx, gy);
                lg.lineTo(gx + s * 0.12, gy - s * 0.22);
                lg.stroke();
              } else if (k === T_SAND) {
                lg.fillStyle = 'rgba(150,110,50,0.45)';
                for (let q = 0; q < 3; q++) lg.fillRect(x + r() * s, y + r() * s, Math.max(0.6, s * 0.08), Math.max(0.6, s * 0.08));
              } else if (k === T_SWAMP) {
                lg.strokeStyle = 'rgba(25,45,20,0.7)';
                lg.lineWidth = Math.max(0.6, s * 0.07);
                lg.beginPath();
                const gx = x + s * 0.5;
                lg.moveTo(gx, y + s * 0.85);
                lg.lineTo(gx - s * 0.1, y + s * 0.25);
                lg.moveTo(gx + s * 0.2, y + s * 0.85);
                lg.lineTo(gx + s * 0.25, y + s * 0.35);
                lg.stroke();
                lg.fillStyle = 'rgba(60,90,70,0.6)';
                lg.fillRect(x + s * 0.1, y + s * 0.7, s * 0.3, s * 0.12);
              } else if (k === T_WATER && r() < 0.3) {
                lg.strokeStyle = 'rgba(255,255,255,0.25)';
                lg.lineWidth = Math.max(0.6, s * 0.07);
                lg.beginPath();
                lg.arc(x + s * 0.5, y + s * 0.8, s * 0.3, Math.PI * 1.2, Math.PI * 1.8);
                lg.stroke();
              } else if (k === T_ROAD) {
                lg.fillStyle = 'rgba(120,80,40,0.35)';
                lg.fillRect(x + s * 0.47, y + s * 0.2, s * 0.06, s * 0.6);
              }
            }
          });
          g.drawImage(L, 0, 0, w, h);
          // 등시 띠 (작은 그림을 늘려서 부드럽게)
          const band = maxD / 9;
          const d8 = img.data;
          for (let i = 0; i < C * R; i++) {
            const d = dist[i]!;
            const o = i * 4;
            if (!isFinite(d) || d > T) {
              d8[o + 3] = 0;
              continue;
            }
            const b = Math.floor(d / band);
            const c = rampAt(BAND, b / 9);
            const alt = b % 2 ? 0.86 : 1;
            d8[o] = c[0] * alt;
            d8[o + 1] = c[1] * alt;
            d8[o + 2] = c[2] * alt;
            d8[o + 3] = 150;
          }
          sg.putImageData(img, 0, 0);
          g.imageSmoothingEnabled = true;
          g.drawImage(small, ox, oy, C * s, R * s);
          // 등시선 (칸 가운데 값으로 마칭 스퀘어)
          const val = (x: number, y: number): number => {
            const d = dist[y * C + x]!;
            return isFinite(d) ? d : 1e6;
          };
          const iso = (lv: number): void => {
            for (let y = 0; y < R - 1; y++)
              for (let x = 0; x < C - 1; x++) {
                const a = val(x, y);
                const b = val(x + 1, y);
                const c = val(x + 1, y + 1);
                const d = val(x, y + 1);
                const idx = (a < lv ? 1 : 0) | (b < lv ? 2 : 0) | (c < lv ? 4 : 0) | (d < lv ? 8 : 0);
                if (idx === 0 || idx === 15) continue;
                const X = ox + (x + 0.5) * s;
                const Y = oy + (y + 0.5) * s;
                const e = (p: number, q: number): number => clamp01((lv - p) / (q - p));
                const top: V2 = [X + e(a, b) * s, Y];
                const right: V2 = [X + s, Y + e(b, c) * s];
                const bot: V2 = [X + e(d, c) * s, Y + s];
                const left: V2 = [X, Y + e(a, d) * s];
                const seg = (p: V2, q: V2): void => {
                  g.moveTo(p[0], p[1]);
                  g.lineTo(q[0], q[1]);
                };
                switch (idx) {
                  case 1: case 14: seg(left, top); break;
                  case 2: case 13: seg(top, right); break;
                  case 3: case 12: seg(left, right); break;
                  case 4: case 11: seg(right, bot); break;
                  case 6: case 9: seg(top, bot); break;
                  case 7: case 8: seg(left, bot); break;
                  case 5: seg(left, top); seg(right, bot); break;
                  case 10: seg(top, right); seg(left, bot); break;
                }
              }
          };
          g.lineJoin = 'round';
          g.lineCap = 'round';
          g.beginPath();
          for (let lv = band; lv < T; lv += band) iso(lv);
          g.strokeStyle = 'rgba(255,255,255,0.75)';
          g.lineWidth = Math.max(0.8, s * 0.12);
          g.stroke();
          if (T < maxD) {
            g.beginPath();
            iso(T);
            g.strokeStyle = 'rgba(255,240,140,0.35)';
            g.lineWidth = Math.max(2, s * 0.6);
            g.stroke();
            g.strokeStyle = '#fff6b0';
            g.lineWidth = Math.max(1.2, s * 0.2);
            g.stroke();
          }
          // 가장 싼 길
          const pathK = (phaseT - DUR) / 0.9;
          if (pathK > 0) glowStroke(g, path.map((i) => cellC(fit, C, i)), pathK, '#ff3d7f', Math.max(1.4, s * 0.28));
          const sp = cellC(fit, C, src);
          g.fillStyle = '#fff';
          g.beginPath();
          g.arc(sp[0], sp[1], s * 0.7, 0, TAU);
          g.fill();
          g.fillStyle = '#ff3d7f';
          g.beginPath();
          g.arc(sp[0], sp[1], s * 0.42, 0, TAU);
          g.fill();
          const dp = cellC(fit, C, dst);
          drawFlag(g, dp[0], dp[1] + s * 0.4, s * 2, '#ff3d7f');
          // 머리 · 범례
          txt(g, flat ? '비용 모두 1' : '지형 비용', 7 * u, headH / 2 + 1 * u, 10.5 * u, '#fff2a8', 'left', 900);
          let lx = w - 6 * u;
          const items: [string, number][] = [['늪 5', 3], ['모래 3', 2], ['풀 2', 1], ['길 1', 0]];
          g.font = `800 ${7.5 * u}px ${F}`;
          for (const [s2, k] of items) {
            const tw = g.measureText(s2).width;
            txt(g, s2, lx, headH / 2 + 1 * u, 7.5 * u, '#e8ecf5', 'right', 800);
            lx -= tw + 4 * u;
            rr(g, lx - 7 * u, headH / 2 - 3 * u, 7 * u, 7 * u, 2 * u);
            g.fillStyle = TCOL[k]!;
            g.fill();
            lx -= 13 * u;
          }
          if (pathK > 1) pill(g, `걸린 시간 ${dist[dst]!.toFixed(0)}`, w / 2, h - 12 * u, 8 * u, 'rgba(255,61,127,0.92)');
          vignette(g, w, h, 0.25);
        },
        controls: [
          { type: 'toggle', label: '지형 비용 끄기 (모두 1)', value: false, on: (v) => ((flat = v), newProblem()) },
          { type: 'range', label: '속도', min: 0.3, max: 3, step: 0.1, value: 1, on: (v) => (speed = v) },
          { type: 'button', label: '새 출발점', on: () => (rounds++, newProblem()) },
          { type: 'button', label: '새 지도', on: () => (seed++, buildTerrain(), newProblem()) },
        ] as Control[],
      };
    },
  }
```

## 관련 기술
- 먼저 알면 좋은 기술: [A* 길찾기 (열린 · 닫힌 칸 보기)](https://ai-techstudio.web.app/ai/t/i264.md) `i264` · [마칭 스퀘어 (등고선 · 경계)](https://ai-techstudio.web.app/ai/t/i259.md) `i259`
- 다음에 해 볼 기술: [흐름장 (많은 유닛 한꺼번에)](https://ai-techstudio.web.app/ai/t/i265.md) `i265`
- 참고 문서: [Red Blob Games — Implementation of A* (Dijkstra with weights)](https://www.redblobgames.com/pathfinding/a-star/implementation.html)