寻路算法:BFS、Dijkstra、A*、JPS、NavMesh 与流场
一、寻路的建模
寻路的本质是在图上找最短路径。地图首先要转换成图:
| 表示方式 | 图的节点 | 特点 | 适合 |
|---|---|---|---|
| 网格 | 每个格子 | 简单直观,编辑方便;节点多,路径带锯齿 | 2D 游戏、策略游戏、休闲游戏 |
| 路点图 | 手动放置的关键点 | 节点少、搜索快;需要人工布置,覆盖不全 | 早期 3D 游戏、固定路线的 NPC |
| 导航网格(NavMesh) | 可行走区域划分出的凸多边形 | 节点少、能表示任意形状的可行走区域,路径自然 | 3D 游戏的主流 |
二、几种搜索算法
| 算法 | 每次扩展哪个节点 | 结果 | 特点 |
|---|---|---|---|
| BFS(广度优先) | 离起点步数最少的 | 每步代价相同时最短 | 不考虑代价不同的情况 |
| Dijkstra | 离起点实际代价最小的 | 一定最短 | 向四面八方均匀扩散,搜索了很多无关的方向 |
| 贪心最佳优先 | 离终点估计距离最小的 | 不一定最短 | 直奔目标,很快,但遇到障碍容易绕远路 |
| A* | f = g + h 最小的 | 在启发函数满足条件时一定最短 | 兼顾已走的代价和到终点的估计,既准又快 |
g:从起点到当前节点的实际代价;h:从当前节点到终点的估计代价(启发函数);f = g + h:经过这个节点的路径的总代价估计。
A* 可以看成 Dijkstra(只看 g)和贪心(只看 h)的结合。
三、A*
流程
1. 把起点放入 Open 表(待检查的节点,按 f 从小到大取出)2. 循环: a. 从 Open 表中取出 f 最小的节点 current b. 如果 current 是终点,沿着"父节点"回溯得到路径,结束 c. 把 current 放入 Closed 表(已确定最短代价的节点) d. 对 current 的每个邻居: 跳过不可走的、已在 Closed 表中的 新的 g = current.g + 两者之间的代价 如果邻居不在 Open 表中,或者新的 g 更小: 更新邻居的 g、f 和父节点,放入 Open 表3. Open 表空了还没到终点:说明不可达启发函数
| 启发函数 | 公式(dx、dy 为坐标差的绝对值) | 适合 |
|---|---|---|
| 曼哈顿距离 | dx + dy | 只能上下左右移动的网格 |
| 对角距离(Octile) | max(dx, dy) + (√2 - 1) × min(dx, dy) | 可以八方向移动的网格 |
| 欧几里得距离 | √(dx² + dy²) | 可以任意方向移动 |
可采纳性:启发函数不超过真实的剩余代价时,A* 一定能找到最短路径。
| h 的取值 | 结果 |
|---|---|
| h = 0 | 退化成 Dijkstra,结果最短但搜索范围大 |
| h ≤ 真实代价 | 结果最短,h 越接近真实代价,搜索越少 |
| h > 真实代价 | 不保证最短,但搜索更快 |
| h 远大于 g | 接近贪心,很快,路径可能很差 |
游戏中经常故意把 h 乘以一个略大于 1 的系数(加权 A*),用一点点路径质量换取明显更快的搜索。
实现
public static class AStar{ static readonly Vector2Int[] Dirs = { new(1, 0), new(-1, 0), new(0, 1), new(0, -1) };
public static List<Vector2Int> Find(bool[,] walkable, Vector2Int start, Vector2Int goal) { var open = new MinHeap<Vector2Int>(); var g = new Dictionary<Vector2Int, int> { [start] = 0 }; var parent = new Dictionary<Vector2Int, Vector2Int>(); var closed = new HashSet<Vector2Int>(); open.Push(start, H(start, goal));
while (open.Count > 0) { var cur = open.Pop(); if (!closed.Add(cur)) continue; // 同一个节点可能多次入堆,取出过的直接跳过 if (cur == goal) return BuildPath(parent, cur);
foreach (var d in Dirs) { var next = cur + d; if (!InBounds(walkable, next) || !walkable[next.x, next.y] || closed.Contains(next)) continue; int newG = g[cur] + 1; if (g.TryGetValue(next, out int oldG) && newG >= oldG) continue; g[next] = newG; parent[next] = cur; open.Push(next, newG + H(next, goal)); // 不去修改堆中已有的项,直接再放入一份 } } return null; // 不可达 }
static int H(Vector2Int a, Vector2Int b) => Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
static bool InBounds(bool[,] map, Vector2Int p) => p.x >= 0 && p.y >= 0 && p.x < map.GetLength(0) && p.y < map.GetLength(1);
static List<Vector2Int> BuildPath(Dictionary<Vector2Int, Vector2Int> parent, Vector2Int cur) { var path = new List<Vector2Int> { cur }; while (parent.TryGetValue(cur, out cur)) path.Add(cur); path.Reverse(); return path; }}
// 最小二叉堆。Unity 当前的 .NET 版本中没有 PriorityQueue,需要自己实现public class MinHeap<T>{ readonly List<(T item, int key)> _data = new(); public int Count => _data.Count;
public void Push(T item, int key) { _data.Add((item, key)); int i = _data.Count - 1; while (i > 0) { int p = (i - 1) / 2; if (_data[p].key <= _data[i].key) break; (_data[p], _data[i]) = (_data[i], _data[p]); i = p; } }
public T Pop() { T top = _data[0].item; int last = _data.Count - 1; _data[0] = _data[last]; _data.RemoveAt(last); int i = 0; while (true) { int l = i * 2 + 1, r = l + 1, m = i; if (l < _data.Count && _data[l].key < _data[m].key) m = l; if (r < _data.Count && _data[r].key < _data[m].key) m = r; if (m == i) break; (_data[m], _data[i]) = (_data[i], _data[m]); i = m; } return top; }}Open 表为什么用堆:每次都要取出 f 最小的节点。用列表每次都要遍历,是 O(n);用最小堆,取出和插入都是 O(log n)。
实现中的优化:示例中使用字典,便于理解。实际项目中,网格的节点可以用一维数组索引(y × 宽 + x)存储 g 值、父节点和状态,并在多次寻路之间复用这些数组,避免分配。
四、JPS:跳点搜索
在代价均匀的网格上,从 A 到 B 往往有很多条等长的路径(先右后上、先上后右……)。A* 会把这些等价的路径都探索一遍,浪费大量时间。
JPS(Jump Point Search)的思路是:沿着一个方向直接”跳”过去,中间的格子不放进 Open 表,直到遇到跳点才停下:
- 到达终点;
- 遇到”强迫邻居”:旁边有障碍物,使得某个邻居只能经过当前格子才能以最短路径到达。这里是路径可能需要拐弯的地方。
JPS 只把跳点加入 Open 表,扩展的节点数量远少于 A*,在开阔的地图上快很多倍,而且结果仍然是最短路径。
限制:只适用于每格代价相同的网格。地形有不同移动代价(比如沼泽减速)时不能直接使用。
五、NavMesh
原理
- 烘焙:根据场景的几何体和角色的参数(半径、高度、可攀爬的坡度和台阶高度),计算出可行走区域,并划分成凸多边形。
- 搜索:以多边形为节点,用 A* 找到一串相连的多边形(走廊)。
- 拉直路径:走廊中有无数条路径,用拐角算法(Funnel Algorithm,也叫拉绳算法)找出紧贴拐角的最短路径,就像把一根绳子在走廊里拉紧。
多边形的数量远少于网格的格子数,所以搜索很快;拉直后的路径也很自然,没有网格路径的锯齿。
Unity 中的 NavMesh
| 组件 | 作用 |
|---|---|
NavMeshSurface | 烘焙导航网格,支持运行时重新烘焙(AI Navigation 包) |
NavMeshAgent | 让角色沿路径移动,处理转向、加速、局部避障 |
NavMeshObstacle | 动态障碍物。勾选 Carve 后会在导航网格上”挖洞”,路径会绕开它 |
NavMeshLink / Off Mesh Link | 连接不相邻的区域:跳跃、爬梯子、传送门 |
全局寻路与局部避障:A* 规划出的是一条静态路径;多个单位同时移动时,还需要局部避障(比如 RVO 算法),让它们在行进中互相让开,不会挤在一起或者穿过彼此。NavMeshAgent 内置了避障功能。
六、流场寻路
RTS 游戏中,几百个单位要去同一个目标。每个单位各自跑一次 A*,开销是单位数量的倍数。
流场(Flow Field):
- 从目标出发,对整张地图做一次 Dijkstra,得到每个格子到目标的代价(积分场);
- 每个格子计算一个方向,指向周围代价最低的邻居(向量场);
- 所有单位只需要查询自己所在格子的方向,沿着它走。
一次计算,所有单位共享。单位越多越划算,而且天然适合大群单位流动的表现。代价是每个目标都要对整张地图计算一次,目标很多且分散时不划算。
七、优化
| 问题 | 做法 |
|---|---|
| 地图很大,单次寻路慢 | 分层寻路(HPA*):把地图分成区块,先在区块之间寻路,再在区块内部细化 |
| 很多单位同时寻路 | 分帧:寻路请求排队,每帧只处理一部分,或者每帧限制扩展的节点数;放到后台线程或 Job 中 |
| 重复的寻路 | 缓存常用的路径;多个单位去同一目标时使用流场 |
| 网格路径有锯齿 | 路径平滑:从起点开始,检查能否直线到达更远的路径点(视线检测),能则跳过中间的点 |
| 动态障碍物 | 路径被阻挡时只重新规划受影响的部分;或者只用局部避障绕开 |
| 目标不可达 | 限制最大搜索的节点数,超出后返回离目标最近的可达点,避免整张地图被搜一遍 |
常见追问
A 的原理是什么?*
每次从 Open 表中取出 f = g + h 最小的节点扩展,g 是起点到当前的实际代价,h 是到终点的估计代价,直到取出终点,再沿父节点回溯得到路径。
A 和 Dijkstra 有什么区别?* Dijkstra 只看 g,向四周均匀扩散;A* 加上启发函数 h,偏向终点方向搜索,在保证最短的前提下搜索得更少。
启发函数怎么选?有什么要求? 四方向用曼哈顿,八方向用对角距离,任意方向用欧几里得。h 不超过真实代价时结果一定最短;故意放大 h 可以更快,但不保证最短。
Open 表用什么数据结构? 最小堆(优先队列),取出和插入都是 O(log n)。
JPS 为什么快?有什么限制? 跳过对称的等价路径,沿方向直接跳到需要拐弯的跳点,只把跳点加入 Open 表,扩展的节点少很多。只适用于代价均匀的网格。
NavMesh 的原理是什么? 把可行走区域烘焙成凸多边形,用 A* 在多边形之间寻路得到走廊,再用拐角算法拉直成最短路径。
大量单位寻路怎么优化? 去同一目标的用流场,一次计算共享;分帧处理寻路请求、放到后台线程;使用分层寻路;配合局部避障。
网格寻路的路径有锯齿怎么办? 路径平滑:检查能否直线到达更远的路径点,跳过中间不必要的拐点。
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!