寻路：A* 怎么少走冤枉路

算法只认识图

NPC 要从屋子这头走到那头。我们看到的是一张关卡：墙、门、柱子、楼梯。寻路算法看到的却只有一张图 (Graph)：一堆节点，和连接节点的边。

Red Blob Games 的 A* 教程特别强调这一点：边只表示「能从 A 到 B」，至于怎么迈步、要不要开门、走直线还是走曲线，算法一概不管。输入是图，输出是图上的一条路径，怎么把这条路径落到角色身上，是游戏自己的事。所以，图怎么建往往和算法选哪个一样重要。

图从哪来：格子、路点、导航网格

同一间带柱子的屋子，可以建成三种完全不同的图：

• 格子最容易实现，但节点非常多；
• 路点是手工或自动放的一组关键点，图很稀疏，但角色只能沿着连线走；
• 导航网格 (NavMesh) 把可行走区域建成一组多边形，节点常取多边形本身或者它们之间的公共边。节点少，路径又能在多边形内部任意取点。引擎一般从关卡的碰撞几何自动「烘焙」出导航网格。

一家人：BFS、Dijkstra、Greedy 和 A*

常见的寻路算法其实是同一个家族，区别在于「下一个先看哪个节点」：

选型很简单：要找到所有点或多个点的路，用 BFS 或 Dijkstra；只要到一个终点，通常用 A*。

f = g + h

A* 给每个节点算一个分数：

$$f(n) = g(n) + h(n)$$

• $g(n)$：从起点走到 $n$ 已经花掉的代价，是实打实算出来的；
• $h(n)$：从 $n$ 到终点还要花多少的估计，叫启发式 (Heuristic)。

每一步都展开 $f$ 最小的节点。只要 $h$ 从不高估真实的剩余距离（这样的启发式叫可采纳的 (Admissible)），A* 就保证找到最短路。

$h$ 的大小决定了 A* 像谁：$h$ 越小，越接近 Dijkstra——只看走过的路，向四面八方均匀扩张；$h$ 越大，越接近 Greedy——只看离终点多远，冲得快，但不再保证最短。

动手：A* 到底省掉了多少

下面是一片没有障碍的空地。黄点是起点，鼠标是终点，橙线是最短路。滑块 k 控制启发式有多准：$h = k \times$ 到终点的直线距离。k = 0 时完全不用启发，就是 Dijkstra；k = 1 时 $h$ 恰好等于真实距离。亮起来的格子，是在找到终点之前一定会被展开的格子。

空地上的 A*：启发式越准，展开越少收起代码

启发式有多准 k0.60

改一改格子更细h 估高了

也可以直接改右边的代码：停手约 0.3 秒会自动重新运行；改坏了点「还原代码」。

分层：先订走廊，再细化

开放世界里，直接在一张覆盖全图的细网格上跑 A*，节点太多。常见的做法是分层：高层是一张很稀疏的图（房间、地标、扇区），先在上面订出一条「走廊级」的路线；进到具体区域以后，再在那一块的导航网格或格子上细化。

也可以用一张稀疏的路点图做战略层，导航网格做战术层。思路都一样：先在很少的节点上决定大方向，再在局部把细节补上。

全局路线和局部挤让

A* 和导航网格回答的是「大致怎么走」：绕开墙、找到门、上对楼层。可是一群角色同时走时，彼此之间的即时挤让，它们管不了——那是下一课局部避障的事。《游戏引擎架构》把寻路列为角色 AI 最底层的能力之一，局部避障则是叠在它上面的另一层。

A* 不管的事

Red Blob 明确列出了 A* 不负责的东西，每一项都要靠额外的系统：

• 多个角色协作移动、互相让路；
• 会移动的障碍、运行时变化的地图；
• 危险区域的评估；
• 编队；
• 转弯半径、物体的尺寸；
• 路径平滑，以及动画。

另外，A* 也不只用在寻路上。前面 GOAP 那一课里的规划器，就是把同一个 A* 搬到「世界状态」组成的图上，用来搜行动序列。

在游戏里怎么用

取舍与常见的坑

小结与练习

• 寻路算法只认识图，格子、路点、导航网格是三种建图方式，节点越少越快；
• BFS、Dijkstra、Greedy、A* 是一家人，A* 用 $f = g + h$ 挑下一个节点；
• 启发式不高估，A* 就保证最短；越准，展开得越少；
• 大世界用分层：先在稀疏的图上订路线，再在局部细化；挤让交给局部避障。

练习：在画布的代码里加一面墙（比如一个矩形），让墙里的格子不参与。想一想：这时 $g$ 还能用直线距离吗？亮起来的区域应该往哪个方向长？