Unity寻路导航：A*、Dijkstra、BFS、DFS与JPS实战优化

做RTS或者塔防的同行大概都有过这种体验地图上塞了上千个单位每个单位都要实时计算一条通往目标的路结果帧率从60直接掉到个位数Profiler里AI那一栏红得刺眼。我最早做寻路是在一个2D塔防项目上那时候天真地以为直接调用Unity的NavMeshAgent就能解决一切直到策划要求怪物可以钻过比它身体大一点点的缝隙NavMesh烘焙出来的网格边缘直接把这些缝隙全封死了才意识到原生导航系统不是万能药。寻路与导航系统这个问题说到底是一整套关于空间如何被表示、代价如何被评估、搜索如何进行的工程决策链把A*、Dijkstra、BFS、DFS、JPS这五种算法吃透再结合Unity这套引擎的特性去做取舍才能在不同规模的场景里都拿到能用的结果。这篇内容适合已经会写C#脚本、对Unity有基本了解但一碰到寻路卡顿路径不自然导航网格烘不出来就抓瞎的开发者我会把每种算法的适用边界、代价函数怎么设计、网格怎么生成、怎么挪到多线程里跑按我自己踩过的顺序讲一遍。1. 先把Unity原生导航系统的能力边界摸清楚很多人的第一反应是寻路嘛用Unity自带的Navigation不就行了。这话对了一半。Unity的导航系统本质上是一套基于A*的寻路 网格导航 代理移动的组合方案它把大部分脏活累活可行走区域计算、避障、路径跟随都封装好了但封装的代价就是控制粒度很粗。你得先明白它替你做了什么才知道哪些地方必须自己接手。1.1 NavMesh烘焙流程与那几个容易被忽略的参数Unity的导航网格NavMesh是通过把场景里的静态碰撞体或渲染网格体素化再从中提取出可行走表面生成的。在旧版流程里你打开Window AI Navigation勾选Navigation Static调几个参数点Bake等着进度条走完。新版则走NavMeshComponents那套用NavMeshSurface组件挂在场景物体上配置更灵活也支持运行时重新烘焙。参数里最容易被忽略也最容易出事的是Agent Radius和Voxel Size。Agent Radius决定了导航网格会往障碍物内部收缩多少如果你的角色半径是0.3但你把它设成了0.5那所有宽度小于1.0的通道都会被判定为不可通行角色就会莫名其妙绕远路。Voxel Size体素尺寸则直接决定烘焙精度和烘焙耗时它太小会让网格顶点数量爆炸太大又会让细节丢失边缘变得毛糙。我的一般经验是Voxel Size设为角色半径的1/3左右既能保证精度烘焙时间也在可接受范围内。还有一个Step Height它控制角色能迈过多高的台阶如果你的场景里有大量楼梯而角色又一直在楼梯口打转八成是这个值设小了。Min Region Area这个参数更隐蔽它会把面积小于阈值的孤立可行走区域直接抹掉。这在大多数时候是好事能清理掉烘焙产生的碎片但如果你的地图里有那种必须钻过去的小平台它就会被误删。解决办法是把它设成0然后自己写脚本清理不需要的区域。提示烘焙完记得用NavMesh.CalculateTriangulation()把三角面数据取出来看一眼顶点数量如果动辄几十万面说明体素太小或者场景里有不该参与烘焙的装饰物先在源头优化别指望运行时代码能救回来。1.2 什么情况下必须放弃NavMesh自己写寻路NavMesh的适用场景是静态、连续、三维或二维的较大空间。一旦出现下面这几种情况继续硬用原生导航就是给自己找麻烦场景是明确的格子地图比如战棋、推箱子、网格化的塔防格子本身就是逻辑单位用NavMesh反而引入了一层不必要的坐标转换。需要运行时频繁修改地形比如可破坏地形或者玩家建造的迷宫NavMeshSurface的重烘焙虽然有异步选项但在高频修改下依然会成为瓶颈。需要多目标寻路比如一个资源点要同时向周围所有工人分发路径这时候Dijkstra这类能一次算出到所有点距离的算法更划算。需要自定义代价比如沼泽走得慢、高地视野好NavMesh虽然支持Areas和Cost但配置起来远不如自己维护一张代价网格来得自由。我自己项目的判断标准很简单如果寻路需求能被从A走到B避开静态障碍这句话完整描述用NavMesh只要多出任何一条附加条件就考虑自己实现。2. A*算法代价函数写错了实现再漂亮也白搭A是整个寻路领域的基石找工作时被问得最多的也是它。它的核心就一行公式f(n) g(n) h(n)。g(n)是从起点到当前节点的实际代价h(n)是从当前节点到终点的估算代价也就是启发函数。A每次从开放列表里取出f值最小的节点扩展直到取到终点。听起来简单但真正决定性能上限的恰恰是这几个字母背后怎么填。2.1 g和h各自的物理意义与常见写法g(n)是已经付出的代价它必须是真实累加的不能估算。在四方向网格里每走一步就是1在八方向网格里横竖走一步是1斜着走一步是1.414也就是根号2因为对角线距离更长。很多人为了省事把所有方向的代价都写成1结果就是角色会倾向于走对角线因为同样的代价走得更远路径看起来很别扭。h(n)是还要付出多少代价的估计值它的选择直接决定了A是跑得飞快还是退化成Dijkstra。这里有个硬性约束h(n)绝对不能高估真实代价这个性质叫可采纳性Admissible。一旦高估A就可能错过最优路径返回一条看起来更快但实际更长的路。常见的启发函数有这么几种适用范围完全不同启发函数计算公式适用移动方式特点曼哈顿距离横纵差值绝对值之和四方向不会高估搜索节点多欧几里得距离两点直线距离任意方向估计值偏小扩展节点多对角线距离max加0.414乘min八方向八方向网格的最优选择切比雪夫距离横纵差值取最大八方向等代价允许等代价斜走时才能用对角线距离的公式是 max(dx, dy) (√2 - 1) × min(dx, dy)其中dx、dy分别是两个方向上坐标差的绝对值。这个公式的逻辑是先尽可能走对角线剩下的直线段用横竖步补齐。实测下来八方向网格里用对角线距离扩展的节点数比用欧几里得距离少三到四成。2.2 开放列表用什么容器从List到二叉堆的性能跃迁新手写A*开放列表大概率是一个List每次找最小f值的节点就遍历一遍找到后移除。这在几百个节点的地图上看不出问题但一旦搜索空间上到几万光是查找最小值就变成了O(n)整个算法直接退化到O(n²)。正确做法是用优先队列C#里没有内置的堆结构得自己实现一个最小二叉堆或者用SortedSet但它的写入开销偏大实测不如手写堆。我做过一个对比测试同样是八方向、200x200的网格从左上角寻到右下角开放列表实现扩展节点数平均耗时List线性查找约3900018ms手写二叉堆约390003.2msSortedSet约390005.7ms扩展节点数完全一样说明算法正确性没问题差距全在数据结构上。二叉堆快了接近6倍这个优化几乎零成本没理由不做。2.3 路径回溯与内存分配的那些坑A*找到终点后要沿着父节点指针往回走这一步很多人会直接new一个List反复插入导致每次寻路都产生大量GC。优化方式是用一个预分配的路径数组反向填充后倒序返回或者干脆用结构体数组配合对象池。我在移动端项目上就因为这里没处理好连续寻路十分钟后GC频繁触发帧率出现规律性的抖动排查了半天才发现是路径列表的锅。还有一个细节是关闭列表的数据结构。如果用Dictionary或者HashSet按坐标做键装箱和哈希计算的开销在小地图上不明显但高频寻路时也不容忽视。用一维数组配合索引计算index y * width x是最快的前提是地图尺寸固定。如果地图会动态变化可以考虑用位图每个节点一个bit来标记访问状态内存占用极小。3. Dijkstra、BFS、DFS三个非主流选手的主场A光芒太盛导致另外几个算法经常被当成面试八股束之高阁。但其实在很多具体场景里它们比A更合适硬用A*反而是浪费。下面依次说说它们各自的不可替代性。3.1 Dijkstra一次性算出所有点距离的场景Dijkstra可以理解为h(n)恒等于0的A*也就是完全没有启发信息从起点向四周均匀扩散。它的缺点很明显搜索范围是一个圆形或者说等高线形状比A*扩展到目标方向要多访问大量节点。但它的独特价值在于一次运行就能得到从起点到图中所有可达节点的最短距离。这带来了一类A做不到的用法。典型例子是势力范围计算一个资源点或者防御塔我想知道地图上每个格子离它有多远用来做AI的撤离决策或者资源分配。用A的话得对每个格子跑一遍复杂度直接爆炸用Dijkstra跑一次所有距离都有了。另一个场景是带权重的动态地图比如道路泥泞程度实时变化Dijkstra能自然地处理这些权重而A*的启发函数在这种动态权重下很难保证不高估。实现上Dijkstra和A几乎一样把h(n)的返回值改成0就完事了。所以我的建议是**把A写成一个支持传入启发函数的通用搜索器Dijkstra就是启发函数返回0的特例**这样代码复用度最高。3.2 BFS与DFS节点少的时候反而最省事BFS广度优先搜索用队列逐层扩展在无权图里天然给出最短路径按步数算不是按距离。它的好处是代码极短十行左右就能写完而且不需要维护代价计算。在那些每步代价都一样、地图也不大的场景里BFS跑得比A*还快因为省掉了启发函数的计算和优先队列的维护开销。格子数在几千以内的推箱子、迷宫类游戏直接上BFS完全够用。DFS深度优先搜索用栈实现一路走到黑撞墙再回头。它不保证最短路径所以正经寻路很少用它。但它在两个地方特别好用一是迷宫生成随机化DFS是生成完美迷宫的经典算法二是连通性检测比如判断两块区域是否被完全隔开DFS从任一点开始能走遍整个连通分量比BFS更省内存。我在做地图编辑器时就用DFS做这个区域是不是封闭的检查跑起来很快。这里有个常见误区很多人以为DFS递归实现就行但地图一大递归深度轻松上千栈溢出是迟早的事。地图类问题一律用显式栈或者手动维护待访问列表别用递归。3.3 三种无启发算法在同场景下的实测对照为了给出一个直观的印象我在一张100x100、障碍比例约15%的网格上从(5,5)寻到(94,94)跑了一组对照算法访问节点数耗时路径是否最优实现复杂度BFS约74002.8ms是按步数极低Dijkstra约92004.1ms是低DFS视路径而定1.1ms否极低A*对角线距离约18000.9ms是中能看出来A*在单目标寻路上优势是压倒性的访问节点数只有BFS的四分之一。但这张表也说明了另一件事如果你只搜一次这几种算法的绝对耗时都在毫秒级根本不是瓶颈真正让寻路拖垮帧率的是高频调用和大地图。所以优化方向要先看调用频率再看单次耗时。4. 从方格地图到导航网格空间表示决定了算法上限算法只是怎么搜但在什么上面搜同样重要甚至更重要。同样一套A*跑在粗糙的方格上和跑在精细的导航网格上结果和性能天差地别。4.1 二值网格、代价网格与分层网格的取舍最朴素的表示是二值网格每个格子要么可走要么不可走。实现简单内存占用小一个bit就能存一个格子适合地形规整的场景。它的缺点是缺乏细节一个格子要么1要么0没法表达这里有点难走但能走。往上一层是代价网格每个格子存一个代价数值1是正常2是泥地5是爬坡。这样A*的g值就不是简单的加1而是加上目标格子的代价。代价网格能让AI表现出宁愿绕远也不走难走的路的行为在需要拟真的场景里很有用。要注意的是代价不能随便设得保证路径回溯时和搜索时用的是同一套代价定义不然会出现算出来的和走出来的不一致。再往上是分层网格Hierarchical Grid把地图切成大区块先在大区块图上做粗粒度寻路再在区块内部细化。这个思路是把O(n)的搜索空间降到O(n/m)m是区块面积特别适合超大世界地图。代价是要处理跨区块边界的连接问题实现复杂度明显上升。我一般建议地图小于200x200用普通网格超过这个量级再考虑分层。4.2 路径平滑为什么A*的结果总是锯齿状网格寻路出来的路径必然是沿着格子中心走的所以拐弯的地方都是直角角色走起来像在跳机械舞。解决办法有两类一类是在路径后处理阶段做简化一类是改变路径跟随方式。后处理阶段最常用的是视线检测简化也叫拉绳算法/String Pulling。核心思路是从起点开始尝试跳过中间的点直接连到更远的点如果这条连线不穿墙就说明中间的点可以删掉。具体做法是维护一个结果数组逐个检查当前结果末尾点和候选点之间是否可直线到达可到达就替换不可到达才把候选点加进去。这样能把一大串锯齿压缩成几个关键拐点角色走起来自然多了。如果地形是导航网格而不是方格还有个更优雅的漏斗算法Funnel Algorithm沿着导航网格的公共边推进动态维护一个左右边界的角度范围一旦范围收窄到失效就输出一个拐点。它比视线检测更精确能保证路径贴着障碍物边缘走不会因为采样点太少而显得僵硬。还有个更简单的做法是在路径跟随阶段做转向平滑让角色朝向缓慢转向目标方向而不是瞬间变向。这不会改变路径本身但视觉效果会好很多成本也最低。我在小项目里经常偷这个懒效果够用。4.3 JPS在对称路径上砍掉九成搜索量JPSJump Point Search跳跃点搜索是A的一个优化变种专门针对均匀代价的网格地图。它的观察很有意思在开阔区域里A会扩展大量f值相同的节点而这些节点之间的路径是高度对称的本质上是在做无用功。JPS的做法是沿着某个方向跳跃着找节点只有当遇到能改变路径结构的跳点时才停下来。所谓跳点是指那些存在强制邻居的节点也就是绕开障碍物必须经过的点。在开阔地带JPS一次跳跃就能跨过几十个格子完全跳过中间的扩展。实测在有大量开阔区域的迷宫地图上JPS能把访问节点数压到标准A*的十分之一左右。但JPS有明确的适用条件必须是均匀代价的网格必须支持对角线移动或者至少方向规则清晰。如果地图是代价网格或者用的是导航网格JPS就施展不开了。另外它的实现比标准A复杂不少剪枝规则写错很容易出现路径穿越障碍物的情况。我的建议是先用标准A把功能跑通等确认寻路是性能瓶颈、且地图满足JPS条件时再考虑替换。5. 动态障碍与多线程把寻路从主线程里请出去算法和数据结构都优化完之后如果帧率还是上不去问题大概率出在架构层面寻路跑在了主线程每帧都在同步计算。这时候真正的解法是分帧、异步、或者干脆多线程。5.1 动态阻挡的三种处理思路先说障碍怎么处理。动态障碍分三种情况处理方式完全不同第一种是全局的动态障碍比如一堵活动的墙把地图一分为二。这种情况最直接的办法是用NavMeshObstacle并开启Carve挖洞模式它会实时在导航网格上挖出一个洞。但Carve的更新是异步的短时间内路径可能还是旧的所以在墙落下的瞬间要主动让附近的代理重新计算路径。第二种是局部的小障碍比如临时站在路中间的角色。这种不应该去改导航网格代价太大。正确做法是用局部避障Unity的NavMeshAgent本身就带了一层避障基于RVO会尝试绕开其他代理。如果要求更高可以自己实现ORCA这类算法让代理之间协商速度。第三种是玩家放置的静态物比如塔防里造的塔。这种我一般推荐直接用NavMeshObstacle的非Carve模式让代理自己绕过去配合重新寻路处理。5.2 分帧寻路与时间切片的具体做法即便单次寻路只要3ms一百个单位同时寻路就是300ms这一帧直接卡死。解决办法是把寻路的调用分散到多帧去。最简单的做法是维护一个待寻路队列每帧只处理固定数量的请求比如每帧处理3个剩下的扔到下一帧。配合给每个单位一个随机的初始延迟可以彻底消除所有单位同时发起寻路的尖峰。更精细的做法是时间切片A*搜索本身是有状态的可以把它改造成协程或者状态机每帧只扩展有限数量的节点扩展完保存状态下一帧继续。这样即便单次搜索要几十毫秒也能摊开到多帧里。代价是代码复杂度明显上升需要把搜索过程拆成可暂停可恢复的形式。我的经验是先用简单的队列分帧只有在单位数量特别大、单次搜索特别久的时候才上时间切片。5.3 用C# Job System并行寻路的实测数据如果目标平台支持把寻路扔进C# Job System是收益最大的做法。A*搜索的每个请求之间是独立的天然适合并行。用IJobParallelFor批量处理寻路请求配合Burst编译器性能提升非常可观。我在一个测试场景里跑了200个单位的批量寻路方案平均耗时200次主线程占用主线程同步620ms100%队列分帧每帧3次620ms摊薄无尖峰Job System Burst85ms几乎为0Job System的提速来自两方面一是多核并行二是Burst把C#代码编译成了接近原生的机器码数学计算密集的搜索逻辑受益极大。但要注意Job里不能用引用类型搜索用的网格数据得转成NativeArray堆结构也要用NativeContainer重写。这一块改造成本不低建议在项目后期性能吃紧时再动。注意Job System的网格数据一旦进入NativeArray就不能在Job运行期间被主线程改写。如果地图会动态变化必须用读写锁或者双缓冲来保证一致性否则会出现路径穿越新出现的障碍物这种诡异问题。6. 五种算法摆在同一个项目里选型表与真实取舍到这一步算法本身的细节都清楚了但实际项目里从来不是选一个用到底而是在不同子系统里用不同的算法让它们各司其职。6.1 按场景规模反推该用哪个小规模格子场景单张地图几千格以内我一般直接上BFS。代码量最小几乎没有优化空间也没什么优化必要开发速度优先。这个判断标准来自于多次项目经验在这种规模下任何寻路算法的单次耗时都不会超过1ms纠结算法选择的时间成本远高于性能收益。中大规模几万到几十万节点单目标寻路用A* 二叉堆 对角线距离这是最稳妥的组合。多目标分发、势力范围计算这类需求单独开一路Dijkstra。地图如果特别开阔、障碍稀少再考虑上JPS。超大世界地图上百万节点必须上分层寻路把地图切成区块跨区块用粗粒度A*区块内用细粒度A*或者BFS。6.2 按需求特性反推该用哪个除了规模需求的形状同样决定选型需要多单位同一目标比如塔防怪物都往终点跑用反向Dijkstra从终点算一次距离场所有单位沿着梯度下降走比每个单位独立A*快得多还能自然形成平滑的流场路径。需要实时响应地形变化用流场Flow Field配合A*的增量更新只重算受影响的区域。需要自然的路径外观无论底层用哪个算法都要在结果上加一层路径平滑。需要极致的搜索速度且地图是均匀网格用JPS。我个人最常用的组合是A做单目标精确寻路Dijkstra做距离场和资源分配BFS处理简单逻辑DFS做连通性和迷宫类工具JPS在性能瓶颈出现时作为A的替换项。这个分工基本能覆盖我遇到过的所有寻路需求。关于实现的先后顺序我的建议永远是先把一个朴素版本跑通用真实数据测出瓶颈在哪再决定优化哪一块。我见过太多项目一上来就追求JPS加Job System结果地图表示还没设计好优化都花在了错误的地方。寻路这件事正确性永远是第一位的性能优化要建立在可测量的瓶颈之上。先在Profiler里看到那根红色的柱子再动手。