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*。