1. A*寻路算法Unity游戏开发绕不开的必修课做游戏开发这些年我面试过不少Unity候选人几乎每次都会聊到寻路。有人张口就是NavMesh Agent但一追问A的原理就含糊其辞。这其实很可惜——Unity内置的NavMesh确实好用但在回合制战棋、塔防、俯视角RTS、体素地图这些场景里A依然是更灵活、更可控的方案。尤其在需要精细控制移动路径、动态计算绕障或者实现自定义角色AI时手写A*几乎是绕不开的基本功。本文要拆的就是A*寻路算法在Unity引擎中的完整落地过程。从算法本身的数学原理开始到网格数据结构的搭建、核心循环的C#实现、启发式函数的选型再到动态地图更新、多点寻路优化和与NavMesh的选型对比。篇幅比较长但每段都会尽量说透“为什么这么做”而不是只丢给你一份能跑通的代码。适合已经有Unity基础、正在做战斗AI或地图系统的开发者也适合准备跳槽想系统补一补算法底子的朋友。先说个最朴素的认知寻路问题本质上是一张带权图上的最短路径搜索。A之所以比Dijkstra快是因为它知道“终点大概在哪个方向”并利用这个信息优先扩展更可能到达目标的节点。这个“方向感”就是启发式函数也是A的灵魂所在。1.1 为什么是A*而不是BFS或Dijkstra很多入门教程喜欢把广度优先搜索BFS、Dijkstra和A*放在一起讲但实际项目里选型逻辑其实非常简单BFS适合所有边权都为1的等代价地图比如传统迷宫。它一层层向外扩散虽然保证找到最短路径但搜索范围是一个圆形效率偏低。Dijkstra适合边权不同的地图它会优先处理代价最小的节点但完全不关心目标位置。一个100x100的网格Dijkstra可能把大半个地图都扩展完才找到终点。A*在Dijkstra的基础上加了一个“对剩余路径的估算值”也就是启发式函数h(n)。它让搜索变成有方向性的朝着终点收敛而不是漫无目的地扩散。我用一个生活类比帮助理解你要从北京西站去首都机场Dijkstra的做法是“不管终点在哪先把所有能走的道路按距离排序一条条走遍”A*则是一边走一边看导航发现方向偏了立刻调整优先选择“当前已走距离 估计剩余距离”最小的路线。这个“估计剩余距离”就是启发式函数。在Unity的开发场景里A几乎总是优于Dijkstra因为游戏地图普遍较大而玩家和敌人的移动目标是明确的。唯一需要警惕的是如果启发式函数估算过高A会退化成贪心算法可能找不到最短路径估算过低又会退化成Dijkstra失去加速效果。这个平衡点我们稍后在启发式函数章节详细讨论。1.2 算法核心概念节点、代价与启发式函数A*的术语不多但每个都必须吃透节点Node搜索图的基本单位。在网格地图里通常是一个格子或一个路点存放坐标、通行状态和邻接关系。G值G Cost从起点到当前节点的实际累计代价。每走一步累加移动代价比如直线移动代价为1斜向移动为1.4精确点是√2。H值H Cost当前节点到终点的估算代价。注意是“估算”不是实际路径。常用的估算方式有曼哈顿距离、对角线距离和欧几里得距离。F值F CostG值与H值之和。开放列表中F值最小的节点就是下一步要扩展的节点。整个算法的循环逻辑可以浓缩成五步把起点放进开放列表Open List。从开放列表里取出F值最小的节点称为当前节点。如果当前节点就是终点回溯路径结束。遍历当前节点的所有相邻节点不可通行的节点直接跳过。如果相邻节点在开放列表或关闭列表Closed List中且这次算出来的G值不比已有G值小则跳过。否则更新该节点的父节点、G值和F值放进开放列表。把当前节点移入关闭列表回到第2步。如果开放列表为空说明没有可达路径。这套逻辑看起来不复杂但落地到Unity里绝大多数Bug都出在“相邻节点的遍历方式”“G值更新的判定条件”和“路径回溯的边界处理”这三处。下一章我会用完整的C#代码逐一说明。2. 从零搭建一个可用的A*框架核心代码实现理论知识说得再热闹不如直接看代码。这里我提供一套我在实际项目里打磨过的A*实现核心数据结构基于二维网格但稍加改动就能扩展到六边形地图或路点图。为了不喧宾夺主我把代码拆成三段地图网格、节点定义、寻路主逻辑。2.1 地图网格数据结构的建立Unity里最直观的网格表示法是用一个二维数组存每个格子的通行状态。真实项目里还会存移动代价、高度差、所属区域等信息。下面是个精简版public enum NodeType { Walkable, Obstacle, SlowZone, Start, End } public class Grid : MonoBehaviour { public Vector2 gridWorldSize; public float nodeRadius; public Node[,] grid; public bool displayGridGizmos; private float nodeDiameter; private int gridSizeX, gridSizeY; private void Awake() { nodeDiameter nodeRadius * 2; gridSizeX Mathf.RoundToInt(gridWorldSize.x / nodeDiameter); gridSizeY Mathf.RoundToInt(gridWorldSize.y / nodeDiameter); CreateGrid(); } private void CreateGrid() { grid new Node[gridSizeX, gridSizeY]; Vector3 worldBottomLeft transform.position - Vector3.right * gridWorldSize.x / 2 - Vector3.forward * gridWorldSize.y / 2; for (int x 0; x gridSizeX; x) { for (int y 0; y gridSizeY; y) { Vector3 worldPoint worldBottomLeft Vector3.right * (x * nodeDiameter nodeRadius) Vector3.forward * (y * nodeDiameter nodeRadius); bool walkable !Physics.CheckSphere(worldPoint, nodeRadius, obstacleMask); NodeType nodeType walkable ? NodeType.Walkable : NodeType.Obstacle; grid[x, y] new Node(nodeType, worldPoint, x, y); } } } public Node NodeFromWorldPoint(Vector3 worldPosition) { float percentX (worldPosition.x gridWorldSize.x / 2) / gridWorldSize.x; float percentY (worldPosition.z gridWorldSize.y / 2) / gridWorldSize.y; percentX Mathf.Clamp01(percentX); percentY Mathf.Clamp01(percentY); int x Mathf.RoundToInt((gridSizeX - 1) * percentX); int y Mathf.RoundToInt((gridSizeY - 1) * percentY); return grid[x, y]; } public ListNode GetNeighbours(Node node) { ListNode neighbours new ListNode(); for (int x -1; x 1; x) { for (int y -1; y 1; y) { if (x 0 y 0) continue; int checkX node.gridX x; int checkY node.gridY y; if (checkX 0 checkX gridSizeX checkY 0 checkY gridSizeY) { neighbours.Add(grid[checkX, checkY]); } } } return neighbours; } }Node类也很简单public class Node { public NodeType nodeType; public Vector3 worldPosition; public int gridX, gridY; public int gCost; public int hCost; public Node parent; public Node(NodeType type, Vector3 worldPos, int x, int y) { nodeType type; worldPosition worldPos; gridX x; gridY y; } public int FCost gCost hCost; }这个网格有几个设计细节值得说明用Physics.CheckSphere而不是Physics.BoxCast是因为球形检测在格子中心点判断是否可通行时最稳定不会因为角色碰撞体的边角问题产生毛刺判定。当然如果地图里全是墙体BoxCast也够用但Sphere基本没有方向性问题。nodeRadius和gridWorldSize的关系决定了地图里能划分出多少个格子。nodeRadius越小格子越密路径越精细但计算量指数上升。经验值是让格子半径等于角色半径的一半左右既能看到平滑的走位又不会卡在狭窄通道里。Awake里创建网格而不是Start是为了保证其他脚本在Start里调用寻路时网格已经就绪。这是我踩过的一个时序坑后面还会细说。2.2 A*核心循环的实现细节核心寻路方法public class Pathfinding : MonoBehaviour { private Grid grid; private void Awake() { grid GetComponentGrid(); } public ListNode FindPath(Vector3 startWorldPos, Vector3 endWorldPos) { Node startNode grid.NodeFromWorldPoint(startWorldPos); Node endNode grid.NodeFromWorldPoint(endWorldPos); HeapNode openSet new HeapNode(grid.MaxSize); HashSetNode closedSet new HashSetNode(); openSet.Add(startNode); while (openSet.Count 0) { Node currentNode openSet.RemoveFirst(); closedSet.Add(currentNode); if (currentNode endNode) { return RetracePath(startNode, endNode); } foreach (Node neighbour in grid.GetNeighbours(currentNode)) { if (!neighbour.IsWalkable || closedSet.Contains(neighbour)) { continue; } int newMovementCostToNeighbour currentNode.gCost GetDistance(currentNode, neighbour); if (newMovementCostToNeighbour neighbour.gCost || !openSet.Contains(neighbour)) { neighbour.gCost newMovementCostToNeighbour; neighbour.hCost GetDistance(neighbour, endNode); neighbour.parent currentNode; if (!openSet.Contains(neighbour)) { openSet.Add(neighbour); } else { openSet.UpdateItem(neighbour); } } } } return null; // 开放列表为空没有可达路径 } private ListNode RetracePath(Node startNode, Node endNode) { ListNode path new ListNode(); Node currentNode endNode; while (currentNode ! startNode) { path.Add(currentNode); currentNode currentNode.parent; } path.Reverse(); return path; } private int GetDistance(Node a, Node b) { int dstX Mathf.Abs(a.gridX - b.gridX); int dstY Mathf.Abs(a.gridY - b.gridY); if (dstX dstY) { return 14 * dstY 10 * (dstX - dstY); } return 14 * dstX 10 * (dstY - dstX); } }这里我特意用了HeapNode而不是ListNode来存储开放列表。为什么因为开放列表最频繁的操作是“取出F值最小的节点”和“更新已有节点的F值后重新排序”。用List实现每次取最小值都要遍历整个列表O(n)的复杂度而二叉堆的取最小值和插入操作都是O(log n)。地图有10000个格子时List版本每帧要遍历上万次堆版本只需要十几次比较。这个性能差距在移动端尤其明显。堆的实现不是本文重点但可以给个思路用数组存储完全二叉树索引i的父节点是(i-1)/2子节点是2i1和2i2。节点需要实现IComparableNode接口比较F值。我用的这个HeapT类大约60行比List版本性能高出一个数量级。另一个关键设计是GetDistance里的代价设定直线移动10斜向移动14。这个比例不是随拍的14是√2×10的整数近似。整数运算比浮点运算快得多而且在小范围内不会有可感知的精度误差。如果你要做带“地形高度差”的寻路把高度差产生的额外代价加进G值即可不影响这个基础架构。2.3 启发式函数的选择与调优启发式函数h(n)的选择直接决定A*的行为表现。三种常见选择曼哈顿距离h |dx| |dy|适合只能四方向移动的地图。对角线距离h max(dx, dy) (√2-1)×min(dx, dy)适合八方向移动。我上面的代码用的就是这个的整数近似版。欧几里得距离h √(dx² dy²)适合任意方向移动但在网格图上通常效果不好因为估算值过低搜索范围偏大。调优的核心原则只有一条h(n)的估算值不能超过真实距离否则A*会丢失最优解。这句话值得反复强调。我见过有人为了追求搜索速度把曼哈顿距离乘以2结果角色绕远路、路径歪歪扭扭排查了半天才发现是启发函数的问题。如果你想在“最优解”和“搜索速度”之间做权衡可以引入权重因子neighbour.hCost weight * GetDistance(neighbour, endNode); // weight建议范围1.0~1.5weight 1.0是严格最优weight 1.2左右路径几乎看不出区别但搜索速度提升20%到30%weight超过2.0路径会明显变差甚至出现“撞墙后原地打转”的诡异行为。这个技巧在大型开放世界里非常实用。3. Unity中的实战落地技巧代码能跑通了接下来才是真正的考验怎么把它放进游戏里不卡顿、不抖动、不出诡异Bug。这一章我总结几个高频场景的落地经验和教训。3.1 用Tilemap还是自定义网格坐标转换与碰撞检测做2D游戏时很多人纠结用Unity Tilemap还是上一章的自定义Grid。我的建议是纯2D平面、格子逻辑简单的游戏比如战棋、消消乐直接用Tilemap把瓦片碰撞体作为A*的障碍物数据源。需要八方向移动、动态障碍、多层高度的游戏用自定义Grid更灵活。如果是Tilemap方案坐标转换是重点。Tilemap的坐标是基于Cell的而移动对象的世界坐标是浮点Vector3。转换逻辑Vector3Int cellPos tilemap.WorldToCell(worldPosition); bool isWalkable tilemap.HasTile(cellPos) false; // 注意有瓦片不代表不可走取决于你的瓦片配置这里有个坑Unity Tilemap默认会把“空白区域”视为无瓦片但游戏里空白区域可能是可走也可能是不可走比如悬崖。所以别直接把HasTile的结果当通行状态建议用TileBase的colliderType二次判断或者维护一张自定义的可通行标记字典。碰撞检测方面2D项目记得用Physics2D.OverlapCircle而不是Physics.CheckSphere两者在3D和2D体系下是独立的物理系统用混了会得到完全错误的结果——我第一次迁移2D项目时就栽在这里。3.2 多单位寻路路径复用与拥挤处理角色一多寻路系统最容易爆的瓶颈是每个单位每帧都请求寻路路径计算结果堆积CPU直接拉满。实战中三个优化手段非常有效路径缓存目标不变、起点变化不大的情况下复用上次路径。比如跟着玩家跑的宠物不需要每帧重新寻路每0.5秒试一次“当前路径是否还能走通”能走就继续用。路径平滑A*算出来的是格子级路径直接给角色走会出现明显折线。我常用的平滑方案是“视线剪枝”从路径第一点开始尝试直接连接更远的点如果中间没有碰撞体就跳过中间的点。这个过程反复执行最后路径会变成一条非常顺滑的折线。蛇形位移避免拥挤多个单位同时走同一条路时如果不加处理会互相推挤甚至完全卡死。Waypoint偏移法很管用——给每个单位分配一个横向偏移量沿路径方向平移几个像素视觉上看起来就像一支小队在大摇大摆地行军。3.3 动态障碍物与运行时地图更新游戏里最常见的动态障碍物就是门、陷阱、可破坏墙体。处理方式分两级第一级障碍物状态变化时直接更新对应格子的通行状态public void UpdateNodeWalkable(Vector3 worldPos, bool walkable) { Node node grid.NodeFromWorldPoint(worldPos); if (node ! null) { node.nodeType walkable ? NodeType.Walkable : NodeType.Obstacle; } }这个方法很便宜但会带来一个新问题已经在寻路中的单位不会自动响应变化它们可能走到一半发现路径被堵死了。所以第二级是“路径失效检测”单位沿路径移动时每帧检查前方一个格子是否突然变成障碍物如果是立即重新寻路。这个检测成本极低一个Physics.Raycast就搞定。如果你在做一个怪物波次防守游戏敌人数量很多且频繁触发重新寻路建议把“重新寻路”做成协程加一个最小间隔时间比如0.2秒防止同一时刻大量单位同时发起寻路造成CPU峰值。4. 性能优化与高级应用当寻路遇到大世界和复杂AI基础版本能跑通后你会发现真正麻烦的是大规模地图。100x100的网格还算友好但到了500x500甚至1000x1000经典A*就力不从心了。这一章写几个我个人推荐的高级优化方向。4.1 大规模地图的性能瓶颈与优化策略先算一笔账500x500网格就是25万个节点。一次寻路平均扩展2万个节点每节点遍历8个邻居就是16万次邻居迭代。如果每秒有20个单位同时寻路每秒就是320万次迭代。这个量级在PC上还算能撑但在移动端直接卡成PPT。应对手段从粗到细有这么几个缩小搜索图把多个格子合并成一个大区块区块内部视为统一代价。这就是Jump Point SearchJPS的核心思路。JPS能跳过大量“同质化”的格子在开阔地图上最高能提速一个数量级。分层寻路先在大区块级别规划一条粗路径再到具体区块内规划精路径。类似导航仪先规划“城市—城市”的高速路线再规划“收费站—目的地”的街道路线。Unity里做大地图AOI兴趣区域管理时这套思路非常常用。缓存增量更新地图不大但单位多时把“起点—终点”对作为key缓存寻路结果。当地图变化时只清除受影响区域的缓存条目而不是全部清空。移动端的经验值单个单位的寻路耗时不要超过1毫秒一个单位每秒重新寻路不超过2次。一旦超过这个阈值先想想有没有办法砍掉多余的寻路请求再来讨论算法本身的优化。4.2 分层寻路Hierarchical Pathfinding的思路简化分层寻路听起来高大上实现起来其实不复杂。我给你一个最小可用方案把整个地图划分成若干区域Region每个区域大小为8x8或16x16个格子。每个区域内部预先计算“入口点”到“出口点”的路径入口和出口就是区域边界的可通行格子。寻路时先在图层面用A*搜索从当前区域到目标区域的“区域路径”再在区域内部细化。这样做的好处是图层面搜索只涉及几十个区域节点速度极快。缺点是目前的地图结构需要手动或半自动地划分区域动态障碍物的处理也比较麻烦。我的建议是如果你的地图超过256x256且单位很多分层方案值得花时间做否则JPS和路径缓存完全够用。4.3 与Unity内置NavMesh的选型对比这是个老生常谈但始终不过时的话题。给一个我个人的选型表维度A*自定义网格Unity NavMesh动态障碍物容易控制格子状态直接更新需要额外用NavMeshObstacle且避障行为较难精细调特殊地形支持高度差、多层地图、门禁开关烘焙后修改麻烦动态区域要重新烘焙路径确定性可控方便做逻辑判定依赖系统内部实现调试困难开发成本需要自己写网格生成和寻路逻辑几乎零成本拖组件即用性能组件化后优化空间大官方引擎级优化多单位时也有不错表现我的习惯是原型阶段用NavMesh快速出效果正式做战斗地图和特殊玩法时换成A*自定义网格。比如塔防里的路线规划、战棋里的攻击范围预览、开放世界里的NPC巡逻这些需求NavMesh要么做不到要么做起来很别扭。另外NavMesh的移动逻辑对网络同步不友好如果你想做帧同步对战A*方案几乎是唯一选择——因为它的结果是确定性的而NavMesh的高度依赖物理引擎不同设备跑出来的结果可能不同。5. 常见问题排查与调试技巧实录最后这部分我把这些年做Unity寻路踩过的坑整理成一个速查手册。每一个都是真实发生过的问题希望你能少走弯路。5.1 路径抖动、死循环与开销异常症状一角色走到终点附近后反复横跳十有八九是路径平滑和到期判定冲突。比如路径最后一个点与终点距离小于停止半径时角色应该停下来但你的移动逻辑还在朝最后一个路径点移动导致来回切换。解决方案很简单到达路径末端后直接检测与终点的距离小于阈值就打断移动清空路径。症状二寻路偶尔死循环游戏卡死发生在开放列表为空时没做返回处理或者某个节点的parent指向了自己。我排查这个Bug时打印了所有节点的gCost发现某个节点的父节点在循环里被反复指向自己。根因是“更新gCost时先修改了parent但后面又因为新的更短路径回退了旧的gCostparent没有同步回退”。建议在更新gCost时把“修改parent”的操作放在“确认这是最短路径”之后而不是之前。症状三性能突然暴涨每帧都调用FindPath排查时加一句日志打印FindPath的调用方和时间。我发现80%的“性能暴涨”不是算法慢而是某些逻辑每帧都在发起重新寻路。常见原因动态障碍物的失效检测写得过于激进把“前方有障碍”误判为“路径失效”。正确做法是只有“障碍物确实挡住了当前路径”时才触发重新寻路而不是角色稍一停顿就重新跑一遍A*。5.2 可视化调试与Gizmos应用Unity的Gizmos是调试寻路的神器没有之一。我几乎每个寻路项目都会在Grid脚本里加这样一段代码private void OnDrawGizmos() { if (grid null || !displayGridGizmos) return; foreach (Node n in grid) { Gizmos.color n.nodeType switch { NodeType.Obstacle Color.red, NodeType.SlowZone Color.yellow, NodeType.Start Color.green, NodeType.End Color.blue, _ Color.white }; Gizmos.DrawWireCube(n.worldPosition, Vector3.one * (nodeDiameter - 0.1f)); } }这样你就能在Scene视图里直观看到每个格子的状态。调试路径本身时我习惯把路径节点用连线方式绘制出来同时用不同颜色区分“原始路径”和“平滑后路径”一眼就能看出平滑算法是否正常工作。另外在路径计算的关键分支处加Debug.DrawLine把openSet里F值最小的节点到终点的预估路径画出来就能看到A*的搜索过程是如何一步步收敛到终点的。这个方法在验证启发式函数权重时格外好用。5.3 已踩过的坑与实用建议确保起点和终点不在障碍物内A*寻路的第一步是NodeFromWorldPoint如果传入的坐标在墙里会直接返回一个不可通行的节点作为起点后续全乱套。在战斗技能系统里我遇到过技能释放点离墙太近导致寻路返回null的情况正确处理方式是先做射线检测把起点修正到最近的可通行点。多线程不是银弹C#的ThreadPool可以把寻路计算扔到后台线程但Unity API比如Physics、Transform不能后台调用。所以在后台线程只做纯数据计算用Grid的副本和Node数组算完再在主线程更新单位的移动目标。这套方案的坑在于网格数据同步我后来的做法是干脆不用多线程优先减少寻路请求次数。地图尺寸是二的幂这不是硬性要求但如果你的格子数量是2的N次方某些位运算优化就能用上比如取模、整除都可以用位操作代替。对超大网格来说这个细节能让寻路循环快5%左右积少成多。注意Unity物理系统和网格更新的时序Awake里创建网格但物理系统在Awake阶段可能还没完全初始化Physics.CheckSphere的结果可能不准。更稳妥的做法是在网格脚本的Start里创建网格再给寻路管理器一个“网格已就绪”的事件其他脚本收到事件后再发起寻路请求。最后聊一个个人体会A*寻路算法写一次不难难的是在复杂玩法里让它表现稳定。我做战棋游戏时为了处理飞行单位、瞬移技能、地形Buff足足改了三版方案才让寻路框架足够通用。所以如果你现在正在为寻路效果挠头不要幻想一步到位先用最简版本跑通循环再逐层加需求。算法本身是死的游戏是活的能灵活组合这些基础模块比背下来任何一段代码都有用。