A* 寻路

朝着目标搜索

交互演示

交互演示 · 移动指针或点击画面，观察变化

A* 在网格中搜索时，总会优先扩展“已付出的代价加上到终点的估计剩余距离”最小的格子。估计值引导搜索朝目标推进，因此在这个迷宫中，它比盲目搜索少扩展约 40% 的格子。只要估计值从不高估实际剩余代价，返回的路径仍然是最短路径。

适用场景

当单位需要在由可通行位置组成的图中寻找路线时，可以使用 A*。图负责描述哪里可以通行，独立的移动控制器则负责沿求得的路线移动。

实现示例

不依赖特定引擎的伪代码。请根据你使用的引擎调整函数和坐标约定。

open.push(start, priority = 0)
while open is not empty:
  current = open.popLowest()
  if current == goal: return reconstructPath(current)
  for next in neighbors(current):
    relaxEdge(current, next, cost + heuristic(next, goal))

常见错误

要获得通常的最短路径保证，启发函数不能高估剩余代价。它应与允许的移动方式相匹配；如果单位无法通过某个缝隙，还要禁止沿对角线切过那个拐角。

延伸阅读

Red Blob Games：A* 入门 ↗

内容原作 Nicolas Zullo · 中文整理与交互改编