Unity A*寻路算法实战：从原理到代码实现与优化

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 Cost）：G值与H值之和。开放列表中F值最小的节点，就是下一步要扩展的节点。

整个算法的循环逻辑可以浓缩成五步：

1. 把起点放进开放列表（Open List）。
2. 从开放列表里取出F值最小的节点，称为当前节点。
3. 如果当前节点就是终点，回溯路径，结束。
4. 遍历当前节点的所有相邻节点：
   • 不可通行的节点直接跳过。
   • 如果相邻节点在开放列表或关闭列表（Closed List）中，且这次算出来的G值不比已有G值小，则跳过。
   • 否则更新该节点的父节点、G值和F值，放进开放列表。
5. 把当前节点移入关闭列表，回到第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 List<Node> GetNeighbours(Node node) { List<Node> neighbours = new List<Node>(); 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 = GetComponent<Grid>(); } public List<Node> FindPath(Vector3 startWorldPos, Vector3 endWorldPos) { Node startNode = grid.NodeFromWorldPoint(startWorldPos); Node endNode = grid.NodeFromWorldPoint(endWorldPos); Heap<Node> openSet = new Heap<Node>(grid.MaxSize); HashSet<Node> closedSet = new HashSet<Node>(); 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 List<Node> RetracePath(Node startNode, Node endNode) { List<Node> path = new List<Node>(); 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); } }

这里我特意用了Heap<Node>而不是List<Node>来存储开放列表。为什么？因为开放列表最频繁的操作是“取出F值最小的节点”和“更新已有节点的F值后重新排序”。用List实现，每次取最小值都要遍历整个列表，O(n)的复杂度；而二叉堆的取最小值和插入操作都是O(log n)。地图有10000个格子时，List版本每帧要遍历上万次，堆版本只需要十几次比较。这个性能差距在移动端尤其明显。

堆的实现不是本文重点，但可以给个思路：用数组存储完全二叉树，索引i的父节点是(i-1)/2，子节点是2i+1和2i+2。节点需要实现IComparable<Node>接口，比较F值。我用的这个Heap<T>类大约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.5

weight = 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 Search（JPS）的核心思路。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，但后面又因为新的更短路径回退了旧的gCost，parent没有同步回退”。建议在更新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，足足改了三版方案，才让寻路框架足够通用。所以如果你现在正在为寻路效果挠头，不要幻想一步到位，先用最简版本跑通循环，再逐层加需求。算法本身是死的，游戏是活的，能灵活组合这些基础模块，比背下来任何一段代码都有用。