# AI 꾸러미 — A* 길찾기 (열린 · 닫힌 칸 보기) — A* pathfinding (f = g + h)
> 열린 칸(노랑)과 닫힌 칸(파랑)이 퍼지는 모습을 한 걸음씩 보여, A* · 다익스트라 · 탐욕 탐색이 길을 찾는 방식을 나란히 비교한다.  
> 견본: https://ai-techstudio.web.app/#t/i264

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

## 주문서

### 만들어 줘: A* 길찾기 (열린 · 닫힌 칸 보기) — A* pathfinding (f = g + h)

#### 1. 목표
미로 · 벽이 있는 격자 판에 A* 길찾기를 넣고 다익스트라 · 탐욕과 나란히 비교해 줘 — 열린 칸 · 닫힌 칸이 한 걸음씩 퍼지고, 끝나면 길과 길이 · 살펴본 칸 수가 보이게. 분위기는 어두운 바탕 형광 색.

#### 2. 핵심 기술 용어
- **A* pathfinding (f = g + h)** — 온 거리 + 남은 거리 어림이 가장 작은 칸부터
- **Dijkstra's algorithm** — 온 거리만 보고 둥글게 다 퍼지기
- **Greedy best-first search** — 남은 거리 어림만 보고 달려가기
- **Octile distance heuristic · binary heap** — 8방향 어림 거리 · 우선순위 큐

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

#### 4. 조건
- 열린 칸은 이진 힙(우선순위 큐)으로 — 배열을 매번 정렬하지 않기
- 대각선 이동은 양옆 칸 중 하나라도 벽이면 막기 (모서리 끼어 지나가기 금지), 대각선 비용 √2
- 어림은 옥타일 거리, A* 열쇠는 g + h·1.0001 (같은 값일 때 목표 쪽을 먼저)
- 이미 닫힌 칸이 힙에서 다시 나오면 건너뛰기
- 셋 나란히 비교에서는 같은 문제 · 같은 속도로

#### 5. 완성 기준 (이게 보이면 성공)
- A* 는 목표 쪽으로 좁게, 다익스트라는 둥글게 넓게, 탐욕은 목표로 곧장 가다 벽에 막혀 돌아가는 모습이 보인다
- 끝나면 분홍 길이 그려지고 「길이 ○○」와 살펴본 칸 수가 알고리즘마다 보인다
- A* 와 다익스트라 길이는 같고, 탐욕은 같거나 더 길다
- 「새 문제」로 미로가 바뀌어도 끊김 없이 돈다

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

## 원리
- 모든 탐색은 「열린 칸」 우선순위 큐에서 값이 가장 작은 칸을 꺼내 닫고, 그 이웃을 열린 칸에 넣는다.
- 값이 다익스트라는 g(온 거리), 탐욕은 h(남은 거리 어림), A* 는 f = g + h. 그래서 A* 는 목표 쪽으로 뾰족하게, 다익스트라는 둥글게 퍼진다.
- 8방향 격자의 어림은 옥타일 거리: h = max(dx, dy) + (√2 − 1)·min(dx, dy) — 실제보다 크지 않아 A* 가 최단 길을 보장한다.
- 탐욕은 처음 열린 칸을 다시 고치지 않아 빠르지만, 컵 모양 벽에 걸려 먼 길로 돌아갈 수 있다.
- 견본은 탐색을 한 번에 끝까지 돌려 칸마다 「몇 번째에 열렸나 · 닫혔나」를 적어 두고, 화면은 그 번호까지만 칠해 한 걸음씩 보인다.

## 핵심 코드 — 하나의 틀로 A* · 다익스트라 · 탐욕 (열쇠만 다르다)
(발췌: demos/demosMapB.ts gridSearch · eachNb 를 정리 (Heap 은 같은 파일의 이진 힙))
```ts
const DX = [1, -1, 0, 0, 1, 1, -1, -1], DY = [0, 0, 1, -1, 1, -1, 1, -1];
const DL = [1, 1, 1, 1, Math.SQRT2, Math.SQRT2, Math.SQRT2, Math.SQRT2];
function eachNb(cols: number, rows: number, block: (i: number) => boolean, i: number, fn: (j: number, len: number) => void) {
  const x = i % cols, y = (i / cols) | 0;
  for (let d = 0; d < 8; d++) {
    const nx = x + DX[d], ny = y + DY[d];
    if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue;
    const j = ny * cols + nx;
    if (block(j)) continue;
    if (d >= 4 && (block(y * cols + nx) || block(ny * cols + x))) continue; // 모서리 끼어 지나가기 금지
    fn(j, DL[d]);
  }
}
// algo: 0 = A*, 1 = 다익스트라, 2 = 탐욕
function gridSearch(cols: number, rows: number, wall: Uint8Array, s: number, goal: number, algo: number) {
  const N = cols * rows, gs = new Float32Array(N).fill(Infinity), par = new Int32Array(N).fill(-1);
  const closedAt = new Int32Array(N).fill(-1), openedAt = new Int32Array(N).fill(-1); // 몇 번째 걸음에 열렸나 · 닫혔나 → 화면은 이 번호까지만 칠한다
  const gx = goal % cols, gy = (goal / cols) | 0;
  const H = (i: number) => { const dx = Math.abs((i % cols) - gx), dy = Math.abs(((i / cols) | 0) - gy); return Math.max(dx, dy) + (Math.SQRT2 - 1) * Math.min(dx, dy); };
  const key = (i: number) => (algo === 0 ? gs[i] + H(i) * 1.0001 : algo === 1 ? gs[i] : H(i));
  const heap = new Heap();
  gs[s] = 0; openedAt[s] = 0; heap.push(key(s), s);
  let step = 0;
  while (heap.size) {
    const i = heap.pop();
    if (closedAt[i] >= 0) continue;
    closedAt[i] = ++step;
    if (i === goal) break;
    eachNb(cols, rows, (j) => wall[j] === 1, i, (j, len) => {
      if (closedAt[j] >= 0) return;
      const ng = gs[i] + len;
      if (algo === 2 ? openedAt[j] < 0 : ng < gs[j] - 1e-6) { // 탐욕은 처음 연 값을 고치지 않는다
        gs[j] = ng; par[j] = i;
        if (openedAt[j] < 0) openedAt[j] = step;
        heap.push(key(j), j);
      }
    });
  }
  const path: number[] = [];
  if (closedAt[goal] >= 0) for (let c = goal; c >= 0; c = par[c]) path.unshift(c);
  return { closedAt, openedAt, steps: step, path, cost: gs[goal] };
}
```

## 흔한 실수 · 확인 목록
- [ ] **어림값을 실제보다 크게 잡으면 A* 가 최단이 아닌 길을 낸다** — 8방향이면 옥타일 거리, 4방향이면 맨해튼 거리처럼 실제를 넘지 않는 어림을 쓴다.
- [ ] **대각선으로 벽 모서리 사이를 빠져나간다** — 대각선은 양옆 두 칸이 모두 열려 있을 때만 허락한다.
- [ ] **열린 칸을 배열에 넣고 매번 정렬하면 큰 판에서 느려진다** — 이진 힙에 넣고, 값이 바뀌면 새로 넣은 뒤 이미 닫힌 칸은 꺼낼 때 건너뛴다.
- [ ] **같은 f 값이 많으면 A* 가 다익스트라처럼 넓게 퍼진다** — h 에 1.0001 처럼 아주 조금 더 무게를 주면 목표 쪽 칸을 먼저 꺼낸다.

## 완성 기준 체크리스트
- [ ] A* 는 목표 쪽으로 좁게, 다익스트라는 둥글게 넓게, 탐욕은 목표로 곧장 가다 벽에 막혀 돌아가는 모습이 보인다
- [ ] 끝나면 분홍 길이 그려지고 「길이 ○○」와 살펴본 칸 수가 알고리즘마다 보인다
- [ ] A* 와 다익스트라 길이는 같고, 탐욕은 같거나 더 길다
- [ ] 「새 문제」로 미로가 바뀌어도 끊김 없이 돈다

## 이 기술 정보
- id: `i264` · 분류: 지도 · 길찾기 › 길찾기 · 이동 · 2D · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 30×18 = 540칸, 힙으로 꺼내기 한 번 log n. 한 번 탐색은 1ms 도 안 걸린다 — 보여 주기 위해 일부러 초당 110걸음으로 나눠 그린다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i264
- 쓰면 좋을 때: 격자 판에서 두 칸 사이 가장 짧은 길이 필요할 때 / 탐색 알고리즘의 차이를 눈으로 보여 줄 때 / 캐릭터가 벽을 돌아 목표로 걸어가야 할 때
- 쓰지 말 때: 유닛 수백이 같은 목표로 갈 때 — 대신 흐름장(i265) / 칸이 아닌 넓은 땅 — 대신 내비 메시(i267) / 칸마다 비용이 다른 지도를 한 출발점에서 모두 재야 할 때 — 대신 다익스트라 비용 지도(i266)

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### gridSearch — `src/demos/demosMapB.ts:305`
```ts
function gridSearch(cols: number, rows: number, wall: Uint8Array, s: number, goal: number, algo: number): Run {
  const N = cols * rows;
  const gs = new Float32Array(N).fill(Infinity);
  const par = new Int32Array(N).fill(-1);
  const closedAt = new Int32Array(N).fill(-1);
  const openedAt = new Int32Array(N).fill(-1);
  const gx = goal % cols;
  const gy = (goal / cols) | 0;
  const H = (i: number): number => {
    const dx = Math.abs((i % cols) - gx);
    const dy = Math.abs(((i / cols) | 0) - gy);
    return Math.max(dx, dy) + (SQ2 - 1) * Math.min(dx, dy);
  };
  const key = (i: number): number => (algo === 0 ? gs[i]! + H(i) * 1.0001 : algo === 1 ? gs[i]! : H(i));
  const heap = new Heap();
  gs[s] = 0;
  openedAt[s] = 0;
  heap.push(key(s), s);
  let step = 0;
  const blocked = (j: number): boolean => wall[j] === 1;
  while (heap.size) {
    const i = heap.pop();
    if (closedAt[i]! >= 0) continue;
    step++;
    closedAt[i] = step;
    if (i === goal) break;
    eachNb(cols, rows, blocked, i, (j, len) => {
      if (closedAt[j]! >= 0) return;
      const ng = gs[i]! + len;
      if (algo === 2 ? openedAt[j]! < 0 : ng < gs[j]! - 1e-6) {
        gs[j] = ng;
        par[j] = i;
        if (openedAt[j]! < 0) openedAt[j] = step;
        heap.push(key(j), j);
      }
    });
  }
  const path: number[] = [];
  if (closedAt[goal]! >= 0) for (let c = goal; c >= 0; c = par[c]!) path.unshift(c);
  return { closedAt, openedAt, steps: step, path, cost: gs[goal]! };
}
```

### i264 견본 항목 — `src/demos/demosMapB.ts:649`
```ts
  i264: {
    kind: '2d',
    caption: 'A* 는 목표 쪽으로 뾰족하게, 다익스트라는 둥글게 다 퍼지고, 탐욕은 빠르지만 컵 벽에 걸려 돌아가요 (노랑 = 열린 칸 · 파랑 = 닫힌 칸)',
    make() {
      const COLS = 30;
      const ROWS = 18;
      let seed = 1;
      let M = makeMaze(COLS, ROWS, seed);
      let runs = [0, 1, 2].map((a) => gridSearch(COLS, ROWS, M.wall, M.s, M.g, a));
      let algo = 0;
      let compare = false;
      let speed = 1;
      let phaseT = 0;
      const done = [-1, -1, -1];
      const layer = new Layer();
      const RATE = 110;
      const newMap = (): void => {
        seed++;
        M = makeMaze(COLS, ROWS, seed);
        runs = [0, 1, 2].map((a) => gridSearch(COLS, ROWS, M.wall, M.s, M.g, a));
        phaseT = 0;
        algo = 0;
        done.fill(-1);
      };
      const chips = (g: G, w: number, y: number, u: number, live: number[]): void => {
        let x = w - 6 * u;
        for (let a = 2; a >= 0; a--) {
          const v = live[a]!;
          const s = v < 0 ? `${ALGO_NAME[a]} —` : `${ALGO_NAME[a]} ${v}칸`;
          const on = compare || a === algo;
          const pw = pill(g, s, x, y, 7.5 * u, on ? ALGO_COL[a]! : 'rgba(255,255,255,0.1)', on ? '#0b1020' : 'rgba(255,255,255,0.75)', 'right');
          x -= pw + 4 * u;
        }
      };
      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, '#141b2e', '#0b1020');
          const headH = 22 * u;
          if (!compare) {
            const run = runs[algo]!;
            const S = phaseT * RATE;
            const tDone = run.steps / RATE;
            const pathK = (phaseT - tDone) / 0.8;
            if (phaseT > tDone) done[algo] = run.steps;
            if (phaseT > tDone + 0.8 + 1.4) {
              algo++;
              phaseT = 0;
              if (algo > 2) newMap();
            }
            const fit = fitGrid(COLS, ROWS, 7 * u, headH + 3 * u, w - 14 * u, h - headH - 9 * u);
            const L = layer.get(`1|${M.id}|${w}|${h}|${dpr}`, w, h, dpr, (lg) => paintTiles(lg, fit, COLS, ROWS, M.wall, '#222c46', '#26314d', '#4a5578', '#2a3150'));
            g.drawImage(L, 0, 0, w, h);
            drawSearch(g, fit, M, run, S, pathK, t);
            const live = done.slice();
            if (live[algo]! < 0) live[algo] = Math.min(run.steps, Math.floor(S));
            chips(g, w, headH / 2 + 1 * u, u, live);
            txt(g, ALGO_NAME[algo]!, 8 * u, headH / 2 + 1.5 * u, 13 * u, ALGO_COL[algo]!, 'left', 900);
            if (pathK > 1) {
              const L2 = run.path.length > 1 ? `길이 ${run.cost.toFixed(1)}` : '';
              pill(g, L2, w / 2, h - 12 * u, 8 * u, 'rgba(255,79,139,0.92)');
            }
          } else {
            const S = phaseT * RATE;
            const maxSteps = Math.max(...runs.map((r) => r.steps));
            if (phaseT > maxSteps / RATE + 0.8 + 1.8) newMap();
            const vert = h > w * 0.9;
            const pw = vert ? w : w / 3;
            const ph = vert ? (h - headH) / 3 : h - headH;
            const fits: Fit[] = [];
            for (let a = 0; a < 3; a++) {
              const px = vert ? 0 : a * pw;
              const py = headH + (vert ? a * ph : 0);
              fits.push(fitGrid(COLS, ROWS, px + 4 * u, py + 12 * u, pw - 8 * u, ph - 16 * u));
            }
            const L = layer.get(`3|${M.id}|${w}|${h}|${dpr}`, w, h, dpr, (lg) => {
              for (const f of fits) paintTiles(lg, f, COLS, ROWS, M.wall, '#222c46', '#26314d', '#4a5578', '#2a3150');
            });
            g.drawImage(L, 0, 0, w, h);
            const live = [0, 0, 0];
            for (let a = 0; a < 3; a++) {
              const run = runs[a]!;
              const f = fits[a]!;
              drawSearch(g, f, M, run, S, (phaseT - run.steps / RATE) / 0.8, t);
              live[a] = Math.min(run.steps, Math.floor(S));
              txt(g, ALGO_NAME[a]!, f.ox, f.oy - 6 * u, 10 * u, ALGO_COL[a]!, 'left', 900);
              if (S >= run.steps) txt(g, `길이 ${run.cost.toFixed(1)}`, f.ox + COLS * f.s, f.oy - 6 * u, 8.5 * u, '#ff8fb3', 'right', 800);
            }
            txt(g, '같은 문제 · 같은 속도', 8 * u, headH / 2 + 1.5 * u, 10 * u, '#cfd8ff', 'left', 800);
            chips(g, w, headH / 2 + 1 * u, u, live);
          }
        },
        controls: [
          { type: 'toggle', label: '셋 나란히 비교', value: false, on: (v) => ((compare = v), (phaseT = 0), (algo = 0), done.fill(-1)) },
          { type: 'range', label: '속도', min: 0.3, max: 3, step: 0.1, value: 1, on: (v) => (speed = v) },
          { type: 'button', label: '새 문제', on: newMap },
          { type: 'button', label: '다음 알고리즘', on: () => ((algo = (algo + 1) % 3), (phaseT = 0)) },
        ] as Control[],
      };
    },
  }
```

## 관련 기술
- 먼저 알면 좋은 기술: [미로 생성 (깊이 우선 · 크루스칼 · 윌슨)](https://ai-techstudio.web.app/ai/t/i250.md) `i250`
- 다음에 해 볼 기술: [흐름장 (많은 유닛 한꺼번에)](https://ai-techstudio.web.app/ai/t/i265.md) `i265` · [다익스트라 비용 지도 (지형 비용)](https://ai-techstudio.web.app/ai/t/i266.md) `i266` · [내비 메시 (다각형 길찾기)](https://ai-techstudio.web.app/ai/t/i267.md) `i267`
- 참고 문서: [Red Blob Games — Introduction to the A* Algorithm](https://www.redblobgames.com/pathfinding/a-star/introduction.html) · [Godot 문서 — AStarGrid2D](https://docs.godotengine.org/en/stable/classes/class_astargrid2d.html)