Unity A*寻路算法实战：从原理到动态避障与性能优化

1. 先从需求说起A*寻路真的过时了吗做 Unity 游戏也快十年了每年都有新框架新方案冒出来但寻路这块只要项目里需要“在地图上有逻辑地移动”A* 寻路算法依然是绕不开的基石。很多朋友一听到 A* 就觉得是“大学算法课作业”觉得现在有 NavMesh、有现成插件就直接拖进去用没必要自己啃原理。但我在实际项目里碰到的情况恰恰相反路径是跑通了一遇到动态障碍、超大地图、多单位并发立刻露馅。这时候回头补 A* 的基础知识往往才是真正解决问题的起点。这一章的内容就是把 A* 寻路算法在 Unity 引擎里的实现细节和高级用法摊开来讲。我会从最核心的估价函数讲起一直写到网格建模、动态避障、路径平滑、性能优化最后附上我这几轮项目里踩过的坑。适合正在写 RTS、塔防、MOBA、俯视角 RPG以及任何需要自研寻路逻辑的开发者参考如果你只是用小场景做 Demo直接拖 NavMesh 就行但如果你想搞懂“为什么有时候明明有路却找不到路”这篇内容就是给你准备的。1.1 你会在什么场景下想起A*先说说哪些项目让我真正决定“必须自己写 A*而不是全靠 NavMesh”。NavMesh 烘焙出来的是连续凸多边形区域优点是路径很自然、寻路性能极高但也有三个让我头疼的问题。第一动态障碍。NavMesh 是离线烘焙的运行时加了一堵墙或者一个临时掩体不做局部动态烘焙AI 就直接穿模走过去。虽然可以用 NavMeshModifierVolume 做动态阻挡但很多情况下 A* 配合格子权重修改要灵活得多。第二非标准地形。比如 2D 游戏里的 Tilemap 地图、体素风格的地形本身就可以抽象成离散格子用 A* 天然吻合。第三路径行为控制。有些玩法需要在同一网格上做不同权重的区域比如沼泽减速、沙漠加速、安全区禁入NavMesh 对这类“成本场”的支持远不如 A* 来得直接。当然我并不是说 A* 全面优于 NavMesh后面我会专门用一节来对比选型这里只是说明有些需求A* 才是正解。1.2 这一章能帮你解决什么我见过太多群友在问为什么我的 AI 会绕远路为什么单位寻路时一卡一卡的为什么动态障碍一放进去路径就不更新了这些问题其实都能追溯到 A* 的某个细节上。这篇文章会带你把三条线走通原理线A* 的估价函数、启发式选择、二叉堆优化搞懂每一步的数学意义和工程意义实现线从 Node、Grid 到 AStar 核心循环的 Unity 代码落地拿到就能改能跑实战线动态障碍刷新、路径平滑、多单位优化、常见 Bug 排查技巧全部来自真实项目踩坑记录。看完之后你至少能做到两件事一是能在 Unity 里手写一个可用的 A* 网格寻路二是能看懂成熟寻路插件如 Aron Granberg 的 A* Pathfinding Project的核心设计不再是一装就完、一出问题就懵。2. A*原理拆解不背公式也能写出正确的寻路2.1 F G H三个数字背后的导航逻辑A* 的核心只有一句话在每一步扩展时选择总代价 F 最小的节点继续搜索。F 等于 G 加 HG 是从起点走到当前节点的实际代价H 是从当前节点到终点不考虑障碍的预估代价。我当年刚学时也觉得这就一个公式背下来不就行了真去写代码才明白G 和 H 的定义方式直接决定了寻路结果的“性格”。G 是实际代价意味着每走一步都要根据地图上的真实情况累加。比如普通格子走一步代价是 1沼泽是 3那你从起点到某个节点的 G 就应该是路径上一路加出来的真实开销。H 是预估代价它允许甚至鼓励“低估”只要 H 不超过实际最小代价A* 就一定能找到最优解。这两者合在一起A* 就兼得了 Dijkstra 的完备性和贪心搜索的速度。这里有个很关键的设计直觉A* 并不是一次性“看穿”整条路径而是一圈一圈地从起点向外扩散搜索只是扩散的优先级由 H 引导方向朝着终点倾斜。就像一个徒步者手里有张不完全准确的地图知道终点大体在哪个方向所以他每到一个路口都优先朝终点方向试探实在走不通再绕回来。这就是 A* 比广度优先省时间的根本原因。2.2 启发式函数怎么选曼哈顿、欧几里得还是对角线H 的计算方式业内一般叫启发式函数。不同网格模型要配不同的启发式选错了轻则寻路变慢重则路径变得很奇葩。如果你的地图允许四方向移动上下左右最常用的是曼哈顿距离H |dx| |dy|。这个函数计算快只需要两次取绝对值和一次加法而且和四方向移动的实际最短距离很匹配。如果地图允许八方向移动还带斜向曼哈顿距离会明显高估斜向路径的开销导致算法更倾向于找直角折线而不是直线斜穿这时候要用对角距离H max(|dx|, |dy|) (√2 - 1) * min(|dx|, |dy|)。如果你用欧几里得距离 H √(dx² dy²)结果一般也不错但因为有平方根运算每扩展一个节点都要多算一次开销在大地图上差值很可观。我在项目里常用的做法是网格允许八方向移动就固定用对角距离然后配合二叉堆排序。如果你在做一个允许单位自由移动的平滑场景建议直接考虑 NavMesh 而不必纠结 H 的选型因为 A* 的离散网格表达天然适合格子类玩法。2.3 二叉堆开放列表的隐形加速器原理讲完了多数教程就会给一个“从开放列表里选 F 最小的节点”的伪代码。这一步说起来轻巧做起来很容易翻车如果用一个普通 List 来存开放列表每次取最小值都要 O(n) 的线性扫描地图稍微大一点几千个节点一扩展帧率瞬间崩掉。解决思路是用二叉堆Binary Heap或者优先队列来维护开放列表。插入和弹出最小值都是 O(log n)比线性扫描快了整整一个数量级。Unity 自带的 C# 里没有直接暴露 PriorityQueue老版本没有新版本在 .NET 6 里才有所以我一般直接用数组自己写一个最小堆或者用现成的第三方优先队列库。堆顶永远是最小 F 值的节点每次弹出堆顶作为当前扩展节点即可。实现二叉堆的细节不算复杂但有几个坑一是堆的键值要同时比较 FF 相等时建议再比 H或者按 G避免频繁抖动二是更新节点代价时需要支持“上浮”操作否则找不到正确的堆位置三是容量要预分配避免频繁扩容。我封装过一个简化版本后面章节会附上核心代码。3. 手写Unity网格寻路从地图到路径的完整链路3.1 网格建模把连续世界切成可搜索的格子A* 要跑起来第一步就是把地图抽象成离散的节点集合。我在 Unity 里最常用的方案是基于 Grid 的格子地图以左下角为原点用 gridSizeX、gridSizeY 定义格子数量每个格子的世界尺寸由 cellSize 决定。这样一张 20×20 的地图在 0.5 米粒度的方格下只是 40×40 1600 个节点搜索起来非常快但在做开放大世界时就别这么干地图几千平米、粒度又细节点数会爆炸后面我会讲这种场景的解决方案。建模时要额外处理两件事一是阻挡检测二是权重层。阻挡检测我常用 Physics.CheckSphere以格子中心为球心半径为 cellSize 的一半检测是否碰到障碍物层。这里有个经验值碰撞体半径不要恰好等于格子的一半否则贴着墙边的单位会把相邻可行格子都判成阻挡实测里调到 0.45 倍左右会稳定很多。权重层则是一张和 grid 同尺寸的权重数组默认 1可以在地图编辑器里手工标记或运行时动态写入。沼泽、泥地就写 3道路写 0.5A* 在计算 G 值时用这些权重乘上步进代价AI 就会自动绕开沼泽、优先走道路。3.2 三个核心类Node、Grid、AStar为了让代码结构清晰我习惯把寻路拆成三个类。Node 类负责单个格子的数据世界坐标、格子坐标、是否可行走、加权代价 G、预估代价 H、父节点引用以及一个用于堆操作的唯一索引。这个类在实现二叉堆时要承担“记录自己在堆中位置”的责任否则更新代价时找不到节点这是很多初写堆优化的人会漏掉的一环。Grid 类负责地图的静态数据网格尺寸、格子大小、阻挡数组、权重数组并且提供两个最常用的转换函数WorldToGrid世界坐标转格子坐标和 GridToWorld格子坐标转世界坐标。这两个函数看着简单但世界坐标到格子坐标要处理原点偏移和取整方向容易出 bug建议写单元测试覆盖。AStar 类负责实际搜索接收起点和终点内部维护二叉堆和关闭列表把寻路结果以世界坐标列表的形式返回。这三个类解耦之后你已经可以在一个测试场景里把 A* 跑通了后续如果想把寻路逻辑改成多线程、改成 Burst 指令集也只需要替换 AStar 类的内部实现事件、单位、动画相关代码不用动。3.3 开闭表与回溯标准A*循环的Unity实现这是整个寻路引擎最核心的一段循环我直接贴一段我在项目里用过的核心逻辑为了篇幅做了简化但保留了关键细节using System.Collections.Generic; using UnityEngine; public class AStarPathfinding : MonoBehaviour { private Grid grid; public ListVector3 FindPath(Vector3 startWorld, Vector3 endWorld) { Node startNode grid.WorldToNode(startWorld); Node targetNode grid.WorldToNode(endWorld); HeapNode openSet new HeapNode(); HashSetNode closedSet new HashSetNode(); openSet.Add(startNode); while (openSet.Count 0) { Node current openSet.RemoveFirst(); closedSet.Add(current); if (current targetNode) { return RetracePath(startNode, targetNode); } foreach (Node neighbor in grid.GetNeighbors(current)) { if (!neighbor.walkable || closedSet.Contains(neighbor)) continue; // 这里的成本计算是重点 // 用权重区分地形沼泽、高地都体现在这行乘法上 float stepCost (neighbor.worldPosition - current.worldPosition).magnitude; float newCostToNeighbor current.gCost stepCost * neighbor.weight; if (newCostToNeighbor neighbor.gCost || !openSet.Contains(neighbor)) { neighbor.gCost newCostToNeighbor; neighbor.hCost GetHeuristic(neighbor, targetNode); neighbor.parent current; if (!openSet.Contains(neighbor)) { openSet.Add(neighbor); } else { openSet.UpdateItem(neighbor); } } } } return null; // 无路可达 } private ListVector3 RetracePath(Node start, Node end) { ListVector3 path new ListVector3(); Node current end; while (current ! start) { path.Add(current.worldPosition); current current.parent; } path.Reverse(); return path; } private float GetHeuristic(Node a, Node b) { // 八方向地图常用对角距离 float dx Mathf.Abs(a.gridX - b.gridX); float dy Mathf.Abs(a.gridY - b.gridY); return Mathf.Max(dx, dy) (Mathf.Sqrt(2f) - 1f) * Mathf.Min(dx, dy); } }这段代码里藏着几个容易出错的细节。第一newCostToNeighbor 的计算必须基于 current 的 gCost 而不是邻居原来的值否则路径回溯会乱。第二当邻居已经在开放列表里时更新 gCost 后一定要调用 UpdateItem 触发堆的上浮不然后续取最小值时会拿到一个过期 F 值。第三RetracePath 出来的是格子世界坐标数组直接用会让单位走折线还需要路径平滑处理一下。这套代码我已经在多个项目里跑过稳定性足够新手照着搭环境、放两个障碍物测试就能直观感受到 A* 的搜索能力。4. 高级应用实践动态避障、路径平滑与性能优化4.1 动态障碍物如何优雅地影响寻路静态障碍跑通了游戏里真正麻烦的是动态障碍。敌人、建造中的防御塔、被摧毁的桥梁都会在游戏进行中改变地图通行状态。如果寻路时再重新烘焙整张网格那成本太高了我在项目里的做法是“运行时局部刷新”。具体流程是这样的每个动态障碍物在 Enable 时向 Grid 发送一个占位请求Grid 根据它的 AABB 范围把覆盖到的所有格子写入 walkable false并让这些格子对附近单位触发路径重算障碍物位移或 Disable 时再恢复。为了保证局部刷新不影响全局正确性我额外维护了一个“障碍源引用计数”字典同一个格子可能同时被墙和箱子占住只有计数归零时才恢复可通行。这个细节很多人会忽略结果就是墙拆了、箱子也被移走格子还是不可走单位傻站在原地。路径重算也不是全局重跑。如果目标点还可达只是在碰撞点附近局部阻塞我一般只对受影响的单位做一次“局部重新寻路”取当前单位前方一小段路径的终点作为新起点重新跑一小段 A*拼回原路径。这样既避免了全图重算的卡顿又保证了动态环境下 AI 不会一头撞上刚出现的新墙。实测下来单位数量在 200 上下时帧率影响可以忽略。4.2 路径平滑让AI走直线而不是走折线格子寻路有一个必然的副作用路径是由格子中心点连成的折线。如果直接把这条路径发给单位你会看到 AI 在拐弯处一步一顿非常机械根本不像“智能角色”。所以路径拿到手之后还要做一次平滑处理。最简单的平滑是“视线检查”从路径起点开始依次检查当前点与后续节点的连线是否与障碍物碰撞如果无碰撞就跳过中间所有节点直到最后一个可直视的点把路径拉直。这个逻辑在 2D 格子地图上写起来很快性能也好。如果你的地图是 3D 起伏地形单纯的视线检查就不够用了我会在路径点之间做二次贝塞尔或 Catmull-Rom 样条插值让单位沿曲线移动但要额外控制插值速度避免拐弯时出现“漂移感”。这里有个我在移动端项目里反复调整的参数路径平滑后的转向速度。插值太激进单位会看起来像“甩尾漂移”太保守又会原地转圈。我的经验值是普通步兵的转向角速度设在每秒 360° 到 540° 之间重甲单位可以更低一些这样既有辨识度又不会有违和感。具体数值要根据角色动画再微调。4.3 大规模单位的性能优化思路当单位数量超过几百个时A* 的性能压力主要来自三处每帧多次寻路、开放列表排序、重复的网格访问。我的优化思路是分层处理的。第一层寻路请求合并。不需要每个单位每帧都去寻路。单位状态机里维护一个“寻路冷却时间”默认 0.5 秒只有当目标点变化、当前路径失效或者冷却结束时才发起新寻路。大批单位同时收到移动指令时还可以把请求放进队列每帧最多处理 N 条分帧完成避免单帧卡顿。第二层空间复用。如果一群单位的目标点相同比如玩家框选 50 个兵攻击同一个敌人只需要算一次 A* 路径然后让每个单位沿着这条路径做局部偏移而不是重复搜索 50 遍。第三层数据局部性。把 Grid 的底层数据从 class 数组改成 struct 数组利用连续内存提高缓存命中率再激进一点可以用 Unity 的 Job System 把寻路逻辑批处理到工作线程上甚至配合 Burst 编译器进一步提速。我自己的项目里用 Job System 重构后同屏 600 个单位同时寻路主线程耗时从 12ms 降到 2ms 左右效果立竿见影。需要提醒的是Job System 版本的 A* 调试难度会显著上升因为不能在 Job 里直接用 Unity 的调试绘制 API。我的习惯是先保留一个单线程版本用于开发调试上线前再切换到 Job 版本并用一段自动化测试保证两个版本结果一致。5. 常见问题排查与工具选型实录5.1 我踩过的三个坑先来三个真实项目里印象深刻的 Bug。第一个是“路径绕远路”。场景表现是明明两点之间有一条直路AI 非要绕一大圈。排查后发现问题出在启发式函数我在地图上允许了斜向移动却在 H 里用了曼哈顿距离导致 A* 高估了斜向路径的总代价优先选择直角路径。换成对角距离函数后问题立即消失。这个坑特别容易踩因为地图上只要有斜向通行曼哈顿距离就不严谨。第二个是“格子权重没重置”。我的地图编辑器允许策划手绘权重但每次重新读图时忘了把旧的权重数组清空结果一张新地图上残留上一张地图的沼泽区域AI 反复绕路。后来我在 Grid 初始化时强制全部重置并在编辑器模式下显示权重叠加图才彻底根治这个问题。第三个是“动态障碍物卡死单位”。单位面前突然立起一堵墙按我的设计它会立刻重新寻路但新路径依然穿过墙因为墙的占位格子被“引用计数”保护着但重新寻路时单位已经站在计数为 1 的格子上被自己卡住了。解决方式是给单位本身一个“当前所在格子不参与寻路阻挡”的豁免标记只对 NPC 障碍生效。这类问题单纯看代码很难发现最好在网格可视化模式下把单位占位和障碍占位用不同颜色画出来一眼就能看出异常。5.2 NavMesh与Grid A*怎么选很多时候读者会纠结项目里到底用 Unity 自带 NavMesh 还是手写 Grid A*或者用第三方 A* 插件。这个问题要看项目类型。维度NavMeshGrid A*A* Pathfinding Project 插件烘焙方式离线烘焙运行时构建运行时构建支持分层网格动态障碍较弱需要额外 Surfaces 重建灵活局部刷新支持 Dynamic Grid 更新路径自然度高连续折线更自然低需额外平滑平滑功能内置性能高静态场景优势大中节点多时需优化高度优化含多线程学习成本最低需要懂算法中等功能多需读文档适用场景3D 开放世界、室内场景2D Tilemap、RTS、塔防复杂寻路需求、大规模单位我的个人选择标准是3D 场景、地图静态、单位量少直接用 NavMesh2D 地图基于 Tilemap、有区域权重差异、需要频繁更新障碍用自写 Grid A*单位规模大、地图又复杂那直接上成熟插件把精力省下来给玩法。插件本身也是读 A* 源码的好素材它的文档和源码质量都比较高适合进阶学习。5.3 排查工具与调试技巧最后说说调试。没有工具辅助A* 的 bug 真的能让人看到怀疑人生。我建议在开发阶段一定打开一套网格可视化工具。最简单的方式是用 Unity 的 OnDrawGizmos 把每个格子的状态画出来可行走格子画浅色障碍格子画深色当前开放列表里的节点画蓝色关闭列表画灰色最终路径用连线标出来。这一套可视化不到一百行代码但排查效率提升几十倍。另一个会救命的工具是路径断点日志。当寻路返回 null 时打印起点和目标点的格子坐标、可通行状态、地图边界信息。我遇到过很多次“终点根本不在网格范围内”的乌龙没有日志根本没法定位。还有个小技巧把寻路结果缓存起来每次新寻路前先和缓存路径对比能快速发现路径跳变的问题比如动态障碍刷新导致某个区域权重异常这个对比很容易暴露。最后分享一点个人体会写 A* 这些年最大的感触是算法本身并不难难的是把它放到一个真实的项目里和各种系统纠缠在一起后依然保持稳定和高效。前面讲的 FGH 和二叉堆可能一个下午就能写出来但动态障碍的引用计数、路径平滑的转向速度、多单位寻路的请求合并这些都是在一次次被策划、被测试、被线上问题“教育”之后才一点点完善的。如果你正在为 AI 寻路头疼我建议不要急着装插件先拿起纸笔画一张 6×6 的格子地图手推一遍 A* 的完整流程。把这一步做扎实了再去动代码、读插件源码你会发现自己看任何寻路方案都像在看一张摊开的地图哪里转弯、哪里减速一目了然。