寻路算法:BFS、Dijkstra、A*、JPS、NavMesh 与流场

2664 字
13 分钟
寻路算法: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#

原理#

  1. 烘焙:根据场景的几何体和角色的参数(半径、高度、可攀爬的坡度和台阶高度),计算出可行走区域,并划分成凸多边形。
  2. 搜索:以多边形为节点,用 A* 找到一串相连的多边形(走廊)。
  3. 拉直路径:走廊中有无数条路径,用拐角算法(Funnel Algorithm,也叫拉绳算法)找出紧贴拐角的最短路径,就像把一根绳子在走廊里拉紧。

多边形的数量远少于网格的格子数,所以搜索很快;拉直后的路径也很自然,没有网格路径的锯齿。

Unity 中的 NavMesh#

组件作用
NavMeshSurface烘焙导航网格,支持运行时重新烘焙(AI Navigation 包)
NavMeshAgent让角色沿路径移动,处理转向、加速、局部避障
NavMeshObstacle动态障碍物。勾选 Carve 后会在导航网格上”挖洞”,路径会绕开它
NavMeshLink / Off Mesh Link连接不相邻的区域:跳跃、爬梯子、传送门

全局寻路与局部避障:A* 规划出的是一条静态路径;多个单位同时移动时,还需要局部避障(比如 RVO 算法),让它们在行进中互相让开,不会挤在一起或者穿过彼此。NavMeshAgent 内置了避障功能。

六、流场寻路#

RTS 游戏中,几百个单位要去同一个目标。每个单位各自跑一次 A*,开销是单位数量的倍数。

流场(Flow Field):

  1. 从目标出发,对整张地图做一次 Dijkstra,得到每个格子到目标的代价(积分场);
  2. 每个格子计算一个方向,指向周围代价最低的邻居(向量场);
  3. 所有单位只需要查询自己所在格子的方向,沿着它走。

一次计算,所有单位共享。单位越多越划算,而且天然适合大群单位流动的表现。代价是每个目标都要对整张地图计算一次,目标很多且分散时不划算。

七、优化#

问题做法
地图很大,单次寻路慢分层寻路(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* 在多边形之间寻路得到走廊,再用拐角算法拉直成最短路径。

大量单位寻路怎么优化? 去同一目标的用流场,一次计算共享;分帧处理寻路请求、放到后台线程;使用分层寻路;配合局部避障。

网格寻路的路径有锯齿怎么办? 路径平滑:检查能否直线到达更远的路径点,跳过中间不必要的拐点。

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

寻路算法:BFS、Dijkstra、A*、JPS、NavMesh 与流场
https://xslab.cloud/posts/algorithms/pathfinding/
作者
LuxFire
发布于
2026-10-14
许可协议
CC BY-NC-SA 4.0
相关文章 智能推荐
1
游戏中的随机:随机数生成器、权重随机、洗牌、伪随机分布与均匀采样
游戏算法 Unity 与 .NET 随机数生成器的区别、种子与可复现;权重随机的三种实现(线性、二分、别名法);Fisher-Yates 洗牌及其常见错误;洗牌袋;Dota 式的伪随机分布;在圆内、球面上均匀取点;正态分布与噪声;以及随机相关的服务器权威问题。
2
游戏 AI 决策:状态机、分层状态机、行为树、效用 AI 与 GOAP
游戏算法 游戏 AI 要解决什么问题;有限状态机的实现与状态爆炸;分层状态机;行为树的节点类型、执行状态、Tick 机制、黑板与中断,以及一个最小实现;效用 AI 的打分机制;GOAP 的目标、动作与规划;各种方案的对比与选择。
3
曲线与缓动:贝塞尔、Catmull-Rom、弧长参数化与缓动函数
游戏算法 游戏中曲线的用途;二次与三次贝塞尔曲线的公式、性质与德卡斯特里奥算法;经过所有点的 Catmull-Rom 样条与向心参数化;曲线上匀速运动的弧长参数化;沿曲线运动时的朝向;常用缓动函数与 AnimationCurve;以及 Unity Splines。
4
定时器的实现:从逐帧计时到最小堆与时间轮
游戏算法 游戏中定时器的需求;逐帧计时、协程、统一管理器三种基础做法的问题;用最小堆管理大量定时器;时间轮的原理、轮数计算与分层时间轮;时间源(缩放时间、真实时间、服务器时间)的选择;暂停、取消与回调中的注意事项。
5
空间划分:网格、四叉树、八叉树、BVH 与 AOI
游戏算法 为什么需要空间划分;均匀网格与空间哈希、四叉树与八叉树、BVH、KD 树、排序扫描的原理、复杂度和适用场景;四叉树的完整实现与动态物体的处理;在碰撞检测、范围查询、最近邻查找中的应用;以及 MMO 中的 AOI(九宫格与十字链表)。
随机文章 随机推荐
Profile Image of the Author
LuxFire
Hello, I'm LuxFire.
公告
欢迎来到我的博客!这是一则示例公告。
音乐
封面

音乐

暂未播放

0:00 0:00
暂无歌词
分类
标签
站点统计
文章
60
分类
6
标签
164
总字数
171,869
运行时长
0 天
最后活动
0 天前

文章目录