在上一篇《地下酒馆:顾客的状态与行为》里,顾客点完菜后已经有了自己的座位,接下来就该走去桌边了。
出发点和目标点之间可能还隔着几张桌子,这条路具体是怎么算出来的?
地下酒馆 Demo 里的 NPC 使用 Unity 的导航系统。
为了说清楚它用到的 A* 算法,我先把酒馆简化成一张方格图,从最简单的广度优先搜索说起。
# 地图的表示
假设顾客站在 B3,要去 H3,每一步只能向上、下、左、右走一格,家具占用的格子不能进入。
同一张图上还标了三个拥挤的格子 D3、E3、F3,后面会用到。这里的拥挤代价是为了比较算法加的,游戏里没有给这段过道单独计费。

对搜索算法来说,每个能站人的格子都是一个节点,可以直接迈过去的两个格子之间彼此相接。
如果每一步都算 1,从 B3 向右走到 H3 只需 6 步,这已经是最短的。现在把规则稍微改一下:进入普通格的花费为 1,进入拥挤格的花费为 4。直走的步数没有变,但代价却成了 15。而绕到下一排虽然多走两步,但反而可能更划算。
那么怎么把上述示例应用到真实的游戏场景中呢?
在 Unity 的导航网格中,用的是另一种类似的表示方法来划分地图。
简单来说,我们把可行走的地面分成多个凸多边形,相邻多边形之间可以通行,这样每个多边形就相当于上面示意中的格子。
因为多边形有大有小,走过的距离也不同,所以这里要把距离算进代价。Unity 会在多边形上放置用于搜索的节点,节点之间的通行代价按 “距离 × 所经区域的代价系数” 计算。
因此,我们使用图来抽象 Unity 的导航网格:每个多边形对应一个搜索节点,节点之间的边表示可以通行,边上的权重记录这段路的代价。
# 寻路算法
为了更直观地展示搜索过程,下面仍用前面的方格图来说明这几种算法。
先用 BFS 找到步数最少的路线,再用 Dijkstra 处理每一步代价不同的情况,最后让 A* 根据终点的位置来决定优先往哪个方向搜索。
# BFS 与最少步数
广度优先搜索(BFS)的思路是按步数从起点逐层向外找,先检查一步能到的位置,再检查两步、三步的位置。这样先找到的就是步数最少的路线。
当每一步的代价都相同时,最少步数也就对应最低代价。实现这个搜索顺序,只需要一个先进先出的队列。
先把 B3 放进队列。取出 B3,按右、下、左、上的顺序检查邻居,把第一次见到的 C3、B4、A3、B2 依次放到队尾,并记下它们都是从 B3 来的。
下一次取出 C3,刚发现的 D3 和 C4 也要排到队尾。因此,离起点一步的几个格子一定会比它们先得到处理。

第一次发现一个格子时,就已经知道了到这里的最少步数。同一格之后再被别的邻居发现,可以直接跳过。
每格只要记住第一次从哪里来,最后从 H3 沿着它的前驱一路往回找,再把顺序倒过来,就能得到整条路线。
图中的三次搜索都在终点出队时停止,起点和终点也计入取出的格数。BFS 取出了 28 格,得到的路线是从 B3 直走到 H3。
如果只计步数,这个答案没有问题。可是这条路正好穿过三格拥挤的过道。要让顾客考虑绕路,就要把每一步实际付出的代价算进去。
# Dijkstra 与累计代价
当每一步的代价不同时,Dijkstra 会把沿途的花费加起来,每次优先检查累计代价最低的位置。这样便宜的绕路就有机会先于昂贵的近路被找到。
具体来说,它给每个已发现的格子记一个数 g ,表示目前找到的从起点到这里的最低代价。待检查的格子放进优先队列,每次先取 g 最小的一个。图上优先级相同时,仍按入队先后处理。
以 C3 为例,从 B3 向右一步到这里, g = 1 。再向右进 D3 是拥挤过道,累计代价变成 5;向下进 C4 则只要 2。
因此,即使先看到了 D3,C4 也会排在它前面。每次检查邻居时,都把 “到当前格的代价 + 迈进邻格的代价” 与邻格原有的记录比较。如果新路线更便宜,就把它的代价和前驱一起更新。第一次发现邻格时,还不能像 BFS 那样把走法定下来。

只要每条边的代价都非负,队首格子被取出时,就不会再有一条尚未检查的路线能把它的代价降得更低。所以终点要等到出队时才算找到最优解。
这次顾客从 C3 转到 C4,沿第四行走到 H4,再向上到 H3。全程 8 步,累计代价也是 8,比直走的 15 低。
Dijkstra 在这张图里一共取出了 33 格。左侧那些离座位越来越远、但从入口走过去很便宜的位置,它也检查了。既然已经知道座位在右边,能不能先看看更接近座位的位置?
# A* 与剩余距离的估计
A* 在累计代价之外,还会考虑候选位置离终点有多远,让搜索优先沿着预计总花费较低的方向展开。这个对剩余代价的估计叫作启发函数。
它保留了 Dijkstra 的实际代价 g ,又加上一个 h ,估计从当前格到终点至少还要花多少代价。每次从优先队列取出的,是 f = g + h 最小的格子。
记录走过的路线、发现更便宜的走法时更新前驱,这些做法和 Dijkstra 一样。
这张地图只允许四方向移动,每一步的最低代价是 1。于是可以暂时忽略桌椅和拥挤过道,用横向格数差加上纵向格数差来估计 h ,即曼哈顿距离。
例如,从 C3 到 H3 至少还要横走 5 格, h = 5 。从 B4 到 H3 至少横走 6 格、竖走 1 格, h = 7 。两处从起点走过去都只花 1,A* 就会先取 f = 6 的 C3。到了 C3,昂贵的 D3 得到的是 g = 5、h = 4、f = 9 ,从下面绕行的 C4 则是 g = 2、h = 6、f = 8 ,这次先走下面更划算。

这个估计可以偏低。桌子挡路时实际要多走几步,但忽略障碍算出的距离依然是下限。并且在这张图上,相邻两格的 h 最多相差 1,迈过去至少也要花 1,因此沿一条路线继续走, f 不会变小。采用这个估计,终点出队时仍能得到最低代价的路线。
如果把 h 全设为 0,队列又只按 g 排,A* 就退回了 Dijkstra;反过来,若把代价估得过高,真正便宜的绕路可能一直排在队尾,先取出的终点就未必是最优解了。
这组图里,A* 和 Dijkstra 都找到了代价为 8 的同一条路,A* 只取出了 13 格。同代价时先取哪一格会影响这个数字,也可能改变最后选中的等价路线。这里更值得比较的是两图中搜索展开的方向。
# Unity 的导航网格
回到酒馆场景。烘焙导航网格( NavMesh )时,Unity 根据场景几何和角色的尺寸等设置,算出 NPC 能走的地面。相邻的导航多边形构成了前面说的图。
项目调用 NavMeshAgent.SetDestination 指定目标后,Unity 用 A* 在起点与终点所在的多边形之间搜索,得到一串连通的多边形,也就是角色可以经过的通道。
详见:Unity 导航系统原理。

这张图仍沿用前面几个示例中的家具布局,把座位移到了 H1,方便看清拐角。浅色块是一条可通过的多边形通道,折线是角色可以沿它行走的一条路线。
当然,此图只是一个平面示意图,实际场景中烘焙出来的多边形边界会有所不同。
角色没有必要走到每个多边形的中心。
眼前一段通道是直的,就直接走向下一个能看见的拐角。
行走过程中迎面来了另一位顾客,局部避让还可以临时调整移动方向。这样两人错身而过后,仍能继续沿原来的通道往桌边走。
# 酒馆里的两个寻路问题
# 菜单前的站位
轮到结伴的顾客点单时,游戏会在菜单前排出一道浅弧,给每位组员找一个站位。
这里容易漏掉一步: NavMesh.SamplePosition 能在期望位置附近找到网格上的点,却没有检查这位顾客从队列里能不能走过去。
两块地面即使隔得很近,也可能被桌椅或一段断开的网格隔开。
因此,这里还要从这位顾客的实际位置再算一次路径。
CalculatePath 在只能到达半途的情况下也可能返回 true ,还得检查状态是否为 PathComplete 。
最后再和已经选好的站位比一下距离,免得两位顾客挤在同一个位置。
下面摘录了 ServiceOrderQueue.TryBeginGroup 中检查一位组员站位的部分代码。 desired 是给这位组员预先算好的位置, positions 里保存着已经选好的站位。
if (!NavMesh.SamplePosition(desired, out var hit, .65f, NavMesh.AllAreas)) return; | |
var path = new NavMeshPath(); | |
if (!NavMesh.CalculatePath(members[i].transform.position, hit.position, | |
NavMesh.AllAreas, path) | |
|| path.status != NavMeshPathStatus.PathComplete | |
|| positions.Exists(p => Vector3.Distance(p, hit.position) < .7f)) return; | |
positions.Add(hit.position); |
# 移动与到达判定
假设这样的一种场景:顾客正沿着桌边走,导航组件已经算出了下一步的位置,但角色的碰撞体可能碰到桌角,实际只走了这一步的一部分。那么下一次移动就需要从角色实际站到的位置继续计算。
即角色真正走起来,还要经过一次碰撞处理。
NpcNavigator 先取出导航组件计划移动到的位置,让 CharacterController 执行这一步,再把实际站到的位置写回去:
var step = agent.nextPosition - transform.position; | |
step.y = -2f * Time.deltaTime; | |
body.Move(step); | |
agent.nextPosition = transform.position; |
走到桌边时,先看顾客和椅旁站位的水平距离,已经在允许范围内就直接停下。还要继续走的话,才让导航组件朝站位移动,并通过 HasArrived 检查这次移动有没有结束。
这里要等路径计算完毕、确认路径完整,再看两个距离:沿路径还剩多远,以及角色现在站的位置和导航终点在地面上实际相距多远。即使导航显示只剩最后一点距离,角色还被障碍挡在远处,也不会被这一步误判为已经到达。
# UE5 中的点击移动
在另一个 UE5 项目里做点击移动时,我也遇到过这样一个问题:
用 Simple Move to Location 把点击位置交给导航后,角色总是在离实际点击位置还差一点的地方停下。
排查主要通过 Print String 进行。
先获取本次点击后实际传给导航节点的目标坐标,等角色停止移动,再通过 GetActorLocation 获取角色的实际坐标。
把两个坐标相减,接到 Vector Length XY 上就能算出水平距离,再用 Print String 打印,最后得到的数据约等于 50,即偏差的距离大致为 50。
(这里比较的是 XY 平面上的距离。因为角色的 Actor 原点通常在胶囊体中间,点击目标却在地面上,如果直接算三维距离,就会把这段高度差也算进去。且我们实际关注的也只是这个水平距离)
因为偏差距离差不多为 50,我由此联想到角色的胶囊体半径。
于是我接着打印 GetScaledCapsuleRadius 返回的胶囊体缩放后半径,也同样得到 50,二者几乎相等。
我认为,问题出在我使用的导航函数 Simple Move to Location 。
这个函数的到达判定中,把角色胶囊体半径也算入到达范围,所以才会出现 “角色中心还没走到点击位置就停下” 的情况。
我希望它能更接近点击的位置,但 Simple Move to Location 节点只提供 Controller 和 Goal 两个输入,无法直接调整这些到达参数。
于是我改用了 AI MoveTo ,把点击输入与实际移动拆开处理:
点击得到目标位置后,将它交给控制角色的 AIController ,由它实际执行移动。
(原先这两步都是在 PlayerController 中处理的)
而改用 AI MoveTo 之后,就能直接调整 Acceptance Radius 和 Stop on Overlap 。
前者设置允许提前停止的距离,后者如果开启,同样会把角色的半径加入到达判定范围。
因此,我把 Acceptance Radius 设为较小的非负值,并关闭 Stop on Overlap 。
这样一来,角色就能在更接近点击位置的地方停下,问题解决。






