# Introduction to the A* Algorithm（笔记）

Source: Amit Patel / Red Blob Games, 2014（多轮更新至 2023）。
URL: https://www.redblobgames.com/pathfinding/a-star/introduction.html
延伸：http://theory.stanford.edu/~amitp/GameProgramming/

## 图搜索家族

| 算法 | 特点 |
|---|---|
| BFS | 等代价探索 |
| Dijkstra / UCS | 计入移动代价 |
| Greedy Best-First | 只靠启发，快但不保证最短 |
| A* | `f = g + h`：已走路成本 + 启发估计 |

## 要点

- 输入是**图**（节点+边），不是关卡美术；输出是图上的路径，如何落地由游戏定。
- 启发式不**高估**真实距离时，A* 保证最优路径（可采纳启发）。
- `h` 变小 → 接近 Dijkstra；`h` 变大 → 接近 Greedy。
- 性能首要：减少图节点；网格易用但节点多。
- A* **不**自带：协作移动、动态障碍、编队、转向半径、物体尺寸、路径平滑等。

## 选型

- 到所有点 / 多点：BFS 或 Dijkstra。
- 到单点：通常 A*。