1. 项目概述从“撞墙”到“绕路”的AI进化在游戏开发里给NPC非玩家角色设计移动逻辑是每个开发者都会遇到的经典难题。最早期的游戏NPC要么是沿着固定路线巡逻像个设定好程序的机器人要么就是直线冲向玩家遇到障碍物就“砰砰”撞墙显得非常愚蠢。这种体验显然会破坏游戏的沉浸感。后来开发者们开始使用导航网格NavMesh这确实是个强大的解决方案尤其对于复杂的三维地形。但NavMesh也有它的局限它更像是一个“预烘焙”的解决方案对于动态变化的场景比如玩家可以随时搭建或摧毁的墙壁或者需要高度定制化寻路逻辑比如不同单位有不同的地形通过成本的场景就显得有些力不从心。这时候A寻路算法就闪亮登场了。它不依赖于预先生成的导航数据而是一种实时计算的、基于网格的寻路算法。你可以把它想象成一个非常聪明的“探路者”它知道自己的起点NPC当前位置和终点比如玩家位置也有一张标记了哪里能走可行走区域、哪里是墙障碍物的“地图”通常是二维网格。A算法的核心任务就是在这张地图上找出一条从起点到终点的最短、最合理的路径。它之所以在游戏开发中经久不衰就是因为其完美的平衡性——在绝大多数情况下它都能高效地找到最优路径同时计算开销又在可接受范围内。这次我们就来在Unity里亲手实现一个基于A*算法的NPC智能寻路系统并探讨如何让它更智能、更高效。2. A*算法核心原理拆解它为什么比瞎找聪明要理解A*我们可以先看看更“笨”的算法。比如广度优先搜索BFS它会像水波纹一样从起点向四周均匀扩散直到碰到终点。这一定能找到最短路径但搜索范围太大效率很低。深度优先搜索DFS则可能一条路走到黑撞了南墙才回头运气不好会浪费大量时间。A*算法的聪明之处在于它结合了两种信息来指导搜索方向从起点到当前点的实际代价G值以及从当前点到终点的预估代价H值。G值 (实际代价)这是从起点走到当前网格已经花费的“成本”。通常我们假设从一个网格走到其上下左右相邻的网格成本为10走到斜对角相邻的网格因为距离略长成本可以设为14约等于10的√2倍。这个值在寻路过程中是累加计算的非常准确。H值 (预估代价/启发值)这是当前网格到终点的“估算成本”。既然是估算就需要一个启发函数。最常用的是“曼哈顿距离”只允许上下左右移动时和“对角线距离”或“欧几里得距离”。在标准网格中我们常用曼哈顿距离H |当前点.x - 终点.x| * 10 |当前点.y - 终点.y| * 10。这个值代表了“理想情况下”还需要多少成本它引导算法优先向终点方向探索。F值 (总代价)这是A*做决策的核心依据F G H。算法在每一步中都会从所有待考察的网格中选择F值最小的那个作为下一步要走的点。这就像你在一片森林里找路G值告诉你已经走了多远累了H值告诉你离目的地大概还有多远希望你总会倾向于选择那个“既走得不太累又离目标近”的方向。两个关键列表开放列表 (Open List)存放所有已发现但尚未评估的网格。初始时只有起点。关闭列表 (Closed List)存放所有已评估完毕的网格即已作为路径点被考虑过。算法流程简述将起点加入开放列表。循环直到开放列表为空或找到终点 a. 从开放列表中找出F值最小的网格设为当前网格。 b. 将当前网格移到关闭列表。 c. 遍历当前网格的所有相邻网格通常是8个方向 - 如果是障碍物或已在关闭列表忽略。 - 如果不在开放列表将其加入并计算G、H、F值同时记录它的“父节点”为当前网格。 - 如果已在开放列表检查经由当前网格到达它是否会产生更小的G值即发现了一条更优路径。如果是则更新它的G值和F值并将其父节点改为当前网格。如果循环结束是因为找到了终点则从终点开始逆向追踪每个网格的父节点直到起点这条链就是找到的路径。如果开放列表空了都没找到终点则说明路径不存在。注意启发函数H值的选择至关重要。它必须满足“可采纳性”即永远不能高估实际代价。曼哈顿距离在允许对角线移动时是会高估的因为实际直线距离更短这时使用对角线距离切比雪夫距离或欧几里得距离更合适。高估的启发函数可能导致找不到最短路径但有时能更快地找到一条可行路径。3. Unity中的A*寻路系统设计与实现在Unity中实现A*我们需要构建几个核心组件一个用于表示网格和障碍物的地图系统一个执行A*算法的寻路管理器以及一个使用路径进行移动的NPC控制器。3.1 网格地图系统的构建我们首先需要将游戏世界离散化为一个二维网格。这里的关键是确定网格的大小和原点。// GridManager.cs 部分核心代码 public class GridManager : MonoBehaviour { public Vector2 gridWorldSize; // 网格覆盖的世界坐标范围长宽 public float nodeRadius; // 每个网格节点的半径决定网格间距 public LayerMask unwalkableMask; // 用于检测障碍物的图层 private Node[,] grid; // 核心的二维网格数组 private float nodeDiameter; private int gridSizeX, gridSizeY; void Start() { nodeDiameter nodeRadius * 2; // 计算网格在X和Y方向上有多少个节点 gridSizeX Mathf.RoundToInt(gridWorldSize.x / nodeDiameter); gridSizeY Mathf.RoundToInt(gridWorldSize.y / nodeDiameter); CreateGrid(); } 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, unwalkableMask)); grid[x, y] new Node(walkable, 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; // 注意Unity中Z轴对应二维的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]; } // ... 其他辅助方法如获取邻居节点、可视化网格等 } // Node.cs 节点数据类 public class Node { public bool walkable; // 是否可行走 public Vector3 worldPosition; // 世界坐标 public int gridX, gridY; // 网格坐标 public int gCost; // 从起点到本节点的代价 public int hCost; // 从本节点到终点的预估代价 public int fCost { get { return gCost hCost; } } // 总代价 public Node parent; // 路径回溯用的父节点 public Node(bool _walkable, Vector3 _worldPos, int _gridX, int _gridY) { walkable _walkable; worldPosition _worldPos; gridX _gridX; gridY _gridY; } }实操心得网格大小选择nodeRadius是关键参数。值越小网格越密寻路精度越高但节点数量呈平方增长会显著增加计算量。对于大多数角色移动网格大小设置为角色碰撞体半径的1.5到2倍是一个不错的起点既能保证不会卡进狭缝又不会太耗性能。障碍物检测Physics.CheckSphere是一种简单有效的方法。但对于复杂形状的静态障碍物更高效的做法是在初始化时CreateGrid使用Physics.OverlapBox一次性检测所有节点并将结果缓存起来。对于动态障碍物则需要有机制能动态更新相关节点的walkable状态。坐标转换注意Unity世界坐标X, Y, Z与二维网格坐标X, Y的对应关系。通常我们将游戏世界的XZ平面映射为网格的XY平面worldPosition.z对应网格的y坐标。3.2 A*算法核心类的实现接下来是实现算法逻辑的Pathfinding类。为了提高性能我们使用Heap堆数据结构来优化开放列表。因为每一步都需要从开放列表中取出F值最小的节点使用堆最小堆可以将这个操作的时间复杂度从O(n)降低到O(log n)。// Pathfinding.cs public class Pathfinding : MonoBehaviour { private GridManager grid; // 引用网格管理器 void Awake() { grid GetComponentGridManager(); } public void FindPath(Vector3 startPos, Vector3 targetPos) { Node startNode grid.NodeFromWorldPoint(startPos); Node targetNode grid.NodeFromWorldPoint(targetPos); // 使用Heap优化的开放列表和普通的关闭列表这里用HashSet提升查找效率 HeapNode openSet new HeapNode(grid.MaxSize); HashSetNode closedSet new HashSetNode(); openSet.Add(startNode); while (openSet.Count 0) { Node currentNode openSet.RemoveFirst(); // 取出F值最小的节点 closedSet.Add(currentNode); // 如果找到终点 if (currentNode targetNode) { RetracePath(startNode, targetNode); return; } // 遍历当前节点的所有邻居 foreach (Node neighbour in grid.GetNeighbours(currentNode)) { if (!neighbour.walkable || closedSet.Contains(neighbour)) { continue; } // 计算从当前节点到邻居节点的新G值 // 这里假设直线成本10对角线成本14 int newMovementCostToNeighbour currentNode.gCost GetDistance(currentNode, neighbour); if (newMovementCostToNeighbour neighbour.gCost || !openSet.Contains(neighbour)) { neighbour.gCost newMovementCostToNeighbour; neighbour.hCost GetDistance(neighbour, targetNode); neighbour.parent currentNode; if (!openSet.Contains(neighbour)) { openSet.Add(neighbour); } else { openSet.UpdateItem(neighbour); // 如果G值更新需要在堆中重新排序 } } } } // 如果循环结束仍未返回说明没有找到路径 } // 回溯生成路径从终点到起点然后反转 void RetracePath(Node startNode, Node endNode) { ListNode path new ListNode(); Node currentNode endNode; while (currentNode ! startNode) { path.Add(currentNode); currentNode currentNode.parent; } path.Reverse(); // 将路径传递给请求者如NPC控制器 // OnPathFound(path); } // 计算两个节点间的距离成本启发函数 int GetDistance(Node nodeA, Node nodeB) { int dstX Mathf.Abs(nodeA.gridX - nodeB.gridX); int dstY Mathf.Abs(nodeA.gridY - nodeB.gridY); // 对角线移动成本14直线移动成本10 if (dstX dstY) { return 14 * dstY 10 * (dstX - dstY); } else { return 14 * dstX 10 * (dstY - dstX); } } } // Heap.cs 最小堆实现关键优化 public class HeapT where T : IHeapItemT { T[] items; int currentItemCount; public Heap(int maxHeapSize) { items new T[maxHeapSize]; } public void Add(T item) { item.HeapIndex currentItemCount; items[currentItemCount] item; SortUp(item); currentItemCount; } public T RemoveFirst() { T firstItem items[0]; currentItemCount--; items[0] items[currentItemCount]; items[0].HeapIndex 0; SortDown(items[0]); return firstItem; } // ... 省略 SortUp, SortDown, Swap, CompareTo 等堆排序核心方法 } public interface IHeapItemT : IComparableT { int HeapIndex { get; set; } }注意事项堆的实现自己实现一个最小堆是性能优化的关键一步。确保IHeapItem接口包含HeapIndex属性用于在交换元素时快速更新索引。CompareTo方法应比较节点的fCost如果相同则比较hCost确保排序稳定。路径平滑A*算法在网格上找到的路径通常是“锯齿状”的折线。直接让NPC按此路径移动会显得生硬。一种简单的优化是路径点简化从起点开始依次检查每个路径点如果从当前点到下下个点之间没有障碍物用射线检测则可以跳过中间的点。更高级的可以使用贝塞尔曲线或样条曲线进行平滑。异步寻路FindPath是一个计算密集型函数如果在主线程中为多个NPC同时计算复杂路径会导致游戏卡顿。务必将其放入协程Coroutine或使用C#的ThreadPool/Task在后台线程中计算计算完成后再将结果回调给主线程更新NPC路径。3.3 NPC控制与移动逻辑寻路算法返回的是一系列世界坐标点Node.worldPosition。NPC控制器需要根据这些点来移动。// NPCMovement.cs public class NPCMovement : MonoBehaviour { public float speed 5f; public float turnSpeed 5f; public float stoppingDistance 0.1f; private ListVector3 path; private int targetIndex; private bool hasPath false; // 由Pathfinding回调 public void OnPathFound(ListNode newPath) { if (newPath ! null newPath.Count 0) { // 将Node列表转换为Vector3列表并可选地进行路径平滑 path SimplifyPath(newPath); targetIndex 0; hasPath true; StopCoroutine(FollowPath); StartCoroutine(FollowPath); } else { // 未找到路径的处理 Debug.Log(No path found!); hasPath false; } } IEnumerator FollowPath() { if (path null || path.Count 0) yield break; Vector3 currentWaypoint path[0]; while (hasPath) { // 检查是否到达当前路径点 if (Vector3.Distance(transform.position, currentWaypoint) stoppingDistance) { targetIndex; if (targetIndex path.Count) { // 到达终点 hasPath false; yield break; } currentWaypoint path[targetIndex]; } // 计算移动方向和旋转 Vector3 direction (currentWaypoint - transform.position).normalized; // 移动 transform.Translate(direction * speed * Time.deltaTime, Space.World); // 平滑转向可选 if (direction ! Vector3.zero) { Quaternion lookRotation Quaternion.LookRotation(direction); transform.rotation Quaternion.Slerp(transform.rotation, lookRotation, Time.deltaTime * turnSpeed); } yield return null; // 等待下一帧 } } // 简单的路径点简化射线检测 ListVector3 SimplifyPath(ListNode path) { ListVector3 waypoints new ListVector3(); if (path.Count 2) { waypoints.Add(path[0].worldPosition); return waypoints; } Vector2 oldDirection Vector2.zero; for (int i 1; i path.Count; i) { // 将世界坐标的XZ平面转换为Vector2进行方向比较 Vector2 newDirection new Vector2(path[i].worldPosition.x - path[i-1].worldPosition.x, path[i].worldPosition.z - path[i-1].worldPosition.z); newDirection.Normalize(); // 如果方向发生变化则将上一个点加入路径点 if (newDirection ! oldDirection) { waypoints.Add(path[i-1].worldPosition); } oldDirection newDirection; } // 加入终点 waypoints.Add(path[path.Count - 1].worldPosition); return waypoints; } }实操心得停止距离stoppingDistance不宜设为0否则NPC可能会在目标点附近来回振荡。设置为一个略大于0的值如0.1或角色半径的一半可以让移动更稳定。移动与旋转分离上面的例子将移动和旋转耦合在同一个协程里。对于更复杂的动画控制如使用Animator最好将移动逻辑更新位置和旋转逻辑分开或者使用Unity的NavMeshAgent那样的方式只提供目标点由另一个更专业的移动控制器来处理具体移动和动画融合。路径动态更新如果目标是移动的如玩家你需要定期例如每秒或当目标移动超过一定距离时重新请求寻路。但要注意频率过于频繁的寻路请求是性能杀手。4. 性能优化与高级技巧一个基础的A*实现可以工作但在大型地图或大量NPC的场景下性能可能成为瓶颈。以下是几个关键的优化方向。4.1 数据结构与算法优化我们已经使用了堆来优化开放列表。除此之外使用更高效的关闭列表HashSetNode的查找效率是O(1)比ListNode的O(n)好得多。避免频繁的GC分配在FindPath循环中避免在循环体内new列表或数组。可以复用节点对象池。GetNeighbours方法可以预计算所有邻居的偏移量并直接返回网格引用而不是创建新的列表。分帧寻路如果一帧内有大量寻路请求可以将它们分散到多帧中执行避免单帧卡顿。可以维护一个寻路请求队列每帧只处理其中几个。4.2 权重与地形系统基础的A*只区分“可走”与“不可走”。更真实的游戏世界会有不同地形草地走得慢公路走得快沼泽非常慢。我们可以为Node类增加一个movementPenalty移动惩罚字段。public class Node { // ... 原有字段 public int movementPenalty; // 移动代价加成例如草地5公路0沼泽20 } // 在Pathfinding计算G值时加入惩罚 int newMovementCostToNeighbour currentNode.gCost GetDistance(currentNode, neighbour) neighbour.movementPenalty;这样算法会自动偏好移动代价低的路径即使它们看起来更长。4.3 分层寻路与局部避障对于超大地图一次性计算整个地图的路径是不现实的。可以采用分层寻路高层图将地图划分为大的区域簇区域间用关键点如门口、桥梁连接。先在高层的抽象图上寻路找到需要经过哪些区域。底层图在NPC进入每个区域时再使用标准的A*进行精细寻路。对于动态的小型障碍物如其他移动的NPCA频繁重算不划算。可以在A计算出的全局路径基础上结合局部避障算法如RVO (Reciprocal Velocity Obstacles)相互速度障碍法常用于人群模拟能让多个NPC自然地相互避让。势场法 (Potential Fields)将目标点设为引力场障碍物设为斥力场NPC沿着合力方向移动。计算简单适合处理大量简单单位的避障。4.4 与Unity生态的整合虽然我们自己实现了A*但有时也需要与其他系统配合与NavMesh混合使用对于静态环境用NavMesh生成大致路径对于动态障碍或需要特殊成本计算的区域切换到A*进行局部重规划。使用ECS/DOTS如果NPC数量极多成千上万可以考虑使用Unity的ECS架构和Job System来并行化A*寻路计算这将带来巨大的性能提升但实现复杂度也更高。5. 常见问题与调试技巧实录在实际开发中你肯定会遇到各种奇怪的问题。下面是我踩过的一些坑和解决方法。问题1NPC卡在角落或障碍物边缘。原因网格大小 (nodeRadius) 设置得与NPC碰撞体大小太接近或者障碍物检测 (CheckSphere) 的半径太小导致可行走网格与障碍物网格之间没有足够的“缓冲地带”。解决确保nodeRadius大于NPC碰撞体的半径。在检测障碍物时可以使用略大于nodeRadius的值进行检测或者在生成网格后对障碍物节点进行“膨胀”处理——将障碍物周围一圈的节点也标记为不可行走。问题2寻路结果不是最短路径或者路径很奇怪地绕远。原因最常见的原因是启发函数H值计算有误或者邻居节点的获取逻辑有问题比如不允许对角线移动但距离计算却按对角线算。也可能是开放列表中节点排序时F值相同时的处理逻辑不对。调试可视化网格和路径在GridManager中编写OnDrawGizmos代码用不同颜色绘制可行走/不可行走节点、开放列表、关闭列表以及最终路径。这是最直观的调试手段。检查启发函数确保你使用的距离估算方式曼哈顿、对角线、欧几里得与允许的移动方式匹配。单步调试对于一条出错的路径可以打印出算法每一步选择的节点及其F、G、H值看决策过程哪里出了问题。问题3大量NPC同时寻路导致游戏帧率下降。原因A*计算在主线程进行阻塞了游戏循环。解决强制异步将所有FindPath调用放入线程池或使用Task.Run。注意Unity的API如Transform.position,Physics.CheckSphere不是线程安全的必须在主线程进行世界坐标到网格坐标的转换 (NodeFromWorldPoint) 和障碍物检测。一种模式是主线程准备寻路请求数据起点、终点、网格数据快照→ 丢给后台线程计算 → 后台线程返回节点索引序列 → 主线程根据索引重建路径世界坐标。限制频率为每个NPC设置寻路冷却时间比如每秒最多重新寻路2次。简化网格在满足游戏需求的前提下使用尽可能大的网格节点。使用路径共享如果多个NPC要去同一个目标点可以只计算一次路径然后让它们共享这条路径或路径的大部分。问题4NPC移动时抖动或走“之”字形。原因路径点过于密集且NPC的移动和旋转速度不匹配或者每帧移动距离过大导致“过冲”然后又折返。解决路径平滑如前所述使用路径点简化或曲线平滑。改进移动控制器使用Vector3.MoveTowards或Vector3.SmoothDamp来实现更平滑的移动插值。对于旋转使用Quaternion.RotateTowards或Quaternion.Slerp。预测移动不要简单地向当前路径点移动可以向前看几个路径点计算一个更平滑的前进方向。问题5动态障碍物更新后NPC不会重新规划路径。原因网格数据是静态的初始化后没有监听场景中障碍物的变化。解决为动态障碍物注册让动态障碍物在启用/禁用或移动时通知GridManager更新其覆盖的网格节点的walkable状态。局部网格更新不需要更新整个网格只需计算动态障碍物影响到的局部区域其碰撞体范围加上NPC半径的缓冲区域的节点。路径失效与重算当NPC检测到其当前路径上的某个节点变为不可行走时立即停止移动并请求一次新的寻路。实现一个健壮、高效的A*寻路系统是游戏AI开发的一块重要基石。它不仅能用于NPC移动还能应用于塔防游戏中敌人的行进路线规划、策略游戏中单位的战术移动甚至解谜游戏中方块推拉的步骤计算。理解其原理掌握其优化技巧并学会根据具体游戏需求进行定制和扩展这将让你在解决各类路径规划问题时游刃有余。
Unity游戏开发：A*寻路算法原理与高效NPC智能移动实现
1. 项目概述从“撞墙”到“绕路”的AI进化在游戏开发里给NPC非玩家角色设计移动逻辑是每个开发者都会遇到的经典难题。最早期的游戏NPC要么是沿着固定路线巡逻像个设定好程序的机器人要么就是直线冲向玩家遇到障碍物就“砰砰”撞墙显得非常愚蠢。这种体验显然会破坏游戏的沉浸感。后来开发者们开始使用导航网格NavMesh这确实是个强大的解决方案尤其对于复杂的三维地形。但NavMesh也有它的局限它更像是一个“预烘焙”的解决方案对于动态变化的场景比如玩家可以随时搭建或摧毁的墙壁或者需要高度定制化寻路逻辑比如不同单位有不同的地形通过成本的场景就显得有些力不从心。这时候A寻路算法就闪亮登场了。它不依赖于预先生成的导航数据而是一种实时计算的、基于网格的寻路算法。你可以把它想象成一个非常聪明的“探路者”它知道自己的起点NPC当前位置和终点比如玩家位置也有一张标记了哪里能走可行走区域、哪里是墙障碍物的“地图”通常是二维网格。A算法的核心任务就是在这张地图上找出一条从起点到终点的最短、最合理的路径。它之所以在游戏开发中经久不衰就是因为其完美的平衡性——在绝大多数情况下它都能高效地找到最优路径同时计算开销又在可接受范围内。这次我们就来在Unity里亲手实现一个基于A*算法的NPC智能寻路系统并探讨如何让它更智能、更高效。2. A*算法核心原理拆解它为什么比瞎找聪明要理解A*我们可以先看看更“笨”的算法。比如广度优先搜索BFS它会像水波纹一样从起点向四周均匀扩散直到碰到终点。这一定能找到最短路径但搜索范围太大效率很低。深度优先搜索DFS则可能一条路走到黑撞了南墙才回头运气不好会浪费大量时间。A*算法的聪明之处在于它结合了两种信息来指导搜索方向从起点到当前点的实际代价G值以及从当前点到终点的预估代价H值。G值 (实际代价)这是从起点走到当前网格已经花费的“成本”。通常我们假设从一个网格走到其上下左右相邻的网格成本为10走到斜对角相邻的网格因为距离略长成本可以设为14约等于10的√2倍。这个值在寻路过程中是累加计算的非常准确。H值 (预估代价/启发值)这是当前网格到终点的“估算成本”。既然是估算就需要一个启发函数。最常用的是“曼哈顿距离”只允许上下左右移动时和“对角线距离”或“欧几里得距离”。在标准网格中我们常用曼哈顿距离H |当前点.x - 终点.x| * 10 |当前点.y - 终点.y| * 10。这个值代表了“理想情况下”还需要多少成本它引导算法优先向终点方向探索。F值 (总代价)这是A*做决策的核心依据F G H。算法在每一步中都会从所有待考察的网格中选择F值最小的那个作为下一步要走的点。这就像你在一片森林里找路G值告诉你已经走了多远累了H值告诉你离目的地大概还有多远希望你总会倾向于选择那个“既走得不太累又离目标近”的方向。两个关键列表开放列表 (Open List)存放所有已发现但尚未评估的网格。初始时只有起点。关闭列表 (Closed List)存放所有已评估完毕的网格即已作为路径点被考虑过。算法流程简述将起点加入开放列表。循环直到开放列表为空或找到终点 a. 从开放列表中找出F值最小的网格设为当前网格。 b. 将当前网格移到关闭列表。 c. 遍历当前网格的所有相邻网格通常是8个方向 - 如果是障碍物或已在关闭列表忽略。 - 如果不在开放列表将其加入并计算G、H、F值同时记录它的“父节点”为当前网格。 - 如果已在开放列表检查经由当前网格到达它是否会产生更小的G值即发现了一条更优路径。如果是则更新它的G值和F值并将其父节点改为当前网格。如果循环结束是因为找到了终点则从终点开始逆向追踪每个网格的父节点直到起点这条链就是找到的路径。如果开放列表空了都没找到终点则说明路径不存在。注意启发函数H值的选择至关重要。它必须满足“可采纳性”即永远不能高估实际代价。曼哈顿距离在允许对角线移动时是会高估的因为实际直线距离更短这时使用对角线距离切比雪夫距离或欧几里得距离更合适。高估的启发函数可能导致找不到最短路径但有时能更快地找到一条可行路径。3. Unity中的A*寻路系统设计与实现在Unity中实现A*我们需要构建几个核心组件一个用于表示网格和障碍物的地图系统一个执行A*算法的寻路管理器以及一个使用路径进行移动的NPC控制器。3.1 网格地图系统的构建我们首先需要将游戏世界离散化为一个二维网格。这里的关键是确定网格的大小和原点。// GridManager.cs 部分核心代码 public class GridManager : MonoBehaviour { public Vector2 gridWorldSize; // 网格覆盖的世界坐标范围长宽 public float nodeRadius; // 每个网格节点的半径决定网格间距 public LayerMask unwalkableMask; // 用于检测障碍物的图层 private Node[,] grid; // 核心的二维网格数组 private float nodeDiameter; private int gridSizeX, gridSizeY; void Start() { nodeDiameter nodeRadius * 2; // 计算网格在X和Y方向上有多少个节点 gridSizeX Mathf.RoundToInt(gridWorldSize.x / nodeDiameter); gridSizeY Mathf.RoundToInt(gridWorldSize.y / nodeDiameter); CreateGrid(); } 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, unwalkableMask)); grid[x, y] new Node(walkable, 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; // 注意Unity中Z轴对应二维的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]; } // ... 其他辅助方法如获取邻居节点、可视化网格等 } // Node.cs 节点数据类 public class Node { public bool walkable; // 是否可行走 public Vector3 worldPosition; // 世界坐标 public int gridX, gridY; // 网格坐标 public int gCost; // 从起点到本节点的代价 public int hCost; // 从本节点到终点的预估代价 public int fCost { get { return gCost hCost; } } // 总代价 public Node parent; // 路径回溯用的父节点 public Node(bool _walkable, Vector3 _worldPos, int _gridX, int _gridY) { walkable _walkable; worldPosition _worldPos; gridX _gridX; gridY _gridY; } }实操心得网格大小选择nodeRadius是关键参数。值越小网格越密寻路精度越高但节点数量呈平方增长会显著增加计算量。对于大多数角色移动网格大小设置为角色碰撞体半径的1.5到2倍是一个不错的起点既能保证不会卡进狭缝又不会太耗性能。障碍物检测Physics.CheckSphere是一种简单有效的方法。但对于复杂形状的静态障碍物更高效的做法是在初始化时CreateGrid使用Physics.OverlapBox一次性检测所有节点并将结果缓存起来。对于动态障碍物则需要有机制能动态更新相关节点的walkable状态。坐标转换注意Unity世界坐标X, Y, Z与二维网格坐标X, Y的对应关系。通常我们将游戏世界的XZ平面映射为网格的XY平面worldPosition.z对应网格的y坐标。3.2 A*算法核心类的实现接下来是实现算法逻辑的Pathfinding类。为了提高性能我们使用Heap堆数据结构来优化开放列表。因为每一步都需要从开放列表中取出F值最小的节点使用堆最小堆可以将这个操作的时间复杂度从O(n)降低到O(log n)。// Pathfinding.cs public class Pathfinding : MonoBehaviour { private GridManager grid; // 引用网格管理器 void Awake() { grid GetComponentGridManager(); } public void FindPath(Vector3 startPos, Vector3 targetPos) { Node startNode grid.NodeFromWorldPoint(startPos); Node targetNode grid.NodeFromWorldPoint(targetPos); // 使用Heap优化的开放列表和普通的关闭列表这里用HashSet提升查找效率 HeapNode openSet new HeapNode(grid.MaxSize); HashSetNode closedSet new HashSetNode(); openSet.Add(startNode); while (openSet.Count 0) { Node currentNode openSet.RemoveFirst(); // 取出F值最小的节点 closedSet.Add(currentNode); // 如果找到终点 if (currentNode targetNode) { RetracePath(startNode, targetNode); return; } // 遍历当前节点的所有邻居 foreach (Node neighbour in grid.GetNeighbours(currentNode)) { if (!neighbour.walkable || closedSet.Contains(neighbour)) { continue; } // 计算从当前节点到邻居节点的新G值 // 这里假设直线成本10对角线成本14 int newMovementCostToNeighbour currentNode.gCost GetDistance(currentNode, neighbour); if (newMovementCostToNeighbour neighbour.gCost || !openSet.Contains(neighbour)) { neighbour.gCost newMovementCostToNeighbour; neighbour.hCost GetDistance(neighbour, targetNode); neighbour.parent currentNode; if (!openSet.Contains(neighbour)) { openSet.Add(neighbour); } else { openSet.UpdateItem(neighbour); // 如果G值更新需要在堆中重新排序 } } } } // 如果循环结束仍未返回说明没有找到路径 } // 回溯生成路径从终点到起点然后反转 void RetracePath(Node startNode, Node endNode) { ListNode path new ListNode(); Node currentNode endNode; while (currentNode ! startNode) { path.Add(currentNode); currentNode currentNode.parent; } path.Reverse(); // 将路径传递给请求者如NPC控制器 // OnPathFound(path); } // 计算两个节点间的距离成本启发函数 int GetDistance(Node nodeA, Node nodeB) { int dstX Mathf.Abs(nodeA.gridX - nodeB.gridX); int dstY Mathf.Abs(nodeA.gridY - nodeB.gridY); // 对角线移动成本14直线移动成本10 if (dstX dstY) { return 14 * dstY 10 * (dstX - dstY); } else { return 14 * dstX 10 * (dstY - dstX); } } } // Heap.cs 最小堆实现关键优化 public class HeapT where T : IHeapItemT { T[] items; int currentItemCount; public Heap(int maxHeapSize) { items new T[maxHeapSize]; } public void Add(T item) { item.HeapIndex currentItemCount; items[currentItemCount] item; SortUp(item); currentItemCount; } public T RemoveFirst() { T firstItem items[0]; currentItemCount--; items[0] items[currentItemCount]; items[0].HeapIndex 0; SortDown(items[0]); return firstItem; } // ... 省略 SortUp, SortDown, Swap, CompareTo 等堆排序核心方法 } public interface IHeapItemT : IComparableT { int HeapIndex { get; set; } }注意事项堆的实现自己实现一个最小堆是性能优化的关键一步。确保IHeapItem接口包含HeapIndex属性用于在交换元素时快速更新索引。CompareTo方法应比较节点的fCost如果相同则比较hCost确保排序稳定。路径平滑A*算法在网格上找到的路径通常是“锯齿状”的折线。直接让NPC按此路径移动会显得生硬。一种简单的优化是路径点简化从起点开始依次检查每个路径点如果从当前点到下下个点之间没有障碍物用射线检测则可以跳过中间的点。更高级的可以使用贝塞尔曲线或样条曲线进行平滑。异步寻路FindPath是一个计算密集型函数如果在主线程中为多个NPC同时计算复杂路径会导致游戏卡顿。务必将其放入协程Coroutine或使用C#的ThreadPool/Task在后台线程中计算计算完成后再将结果回调给主线程更新NPC路径。3.3 NPC控制与移动逻辑寻路算法返回的是一系列世界坐标点Node.worldPosition。NPC控制器需要根据这些点来移动。// NPCMovement.cs public class NPCMovement : MonoBehaviour { public float speed 5f; public float turnSpeed 5f; public float stoppingDistance 0.1f; private ListVector3 path; private int targetIndex; private bool hasPath false; // 由Pathfinding回调 public void OnPathFound(ListNode newPath) { if (newPath ! null newPath.Count 0) { // 将Node列表转换为Vector3列表并可选地进行路径平滑 path SimplifyPath(newPath); targetIndex 0; hasPath true; StopCoroutine(FollowPath); StartCoroutine(FollowPath); } else { // 未找到路径的处理 Debug.Log(No path found!); hasPath false; } } IEnumerator FollowPath() { if (path null || path.Count 0) yield break; Vector3 currentWaypoint path[0]; while (hasPath) { // 检查是否到达当前路径点 if (Vector3.Distance(transform.position, currentWaypoint) stoppingDistance) { targetIndex; if (targetIndex path.Count) { // 到达终点 hasPath false; yield break; } currentWaypoint path[targetIndex]; } // 计算移动方向和旋转 Vector3 direction (currentWaypoint - transform.position).normalized; // 移动 transform.Translate(direction * speed * Time.deltaTime, Space.World); // 平滑转向可选 if (direction ! Vector3.zero) { Quaternion lookRotation Quaternion.LookRotation(direction); transform.rotation Quaternion.Slerp(transform.rotation, lookRotation, Time.deltaTime * turnSpeed); } yield return null; // 等待下一帧 } } // 简单的路径点简化射线检测 ListVector3 SimplifyPath(ListNode path) { ListVector3 waypoints new ListVector3(); if (path.Count 2) { waypoints.Add(path[0].worldPosition); return waypoints; } Vector2 oldDirection Vector2.zero; for (int i 1; i path.Count; i) { // 将世界坐标的XZ平面转换为Vector2进行方向比较 Vector2 newDirection new Vector2(path[i].worldPosition.x - path[i-1].worldPosition.x, path[i].worldPosition.z - path[i-1].worldPosition.z); newDirection.Normalize(); // 如果方向发生变化则将上一个点加入路径点 if (newDirection ! oldDirection) { waypoints.Add(path[i-1].worldPosition); } oldDirection newDirection; } // 加入终点 waypoints.Add(path[path.Count - 1].worldPosition); return waypoints; } }实操心得停止距离stoppingDistance不宜设为0否则NPC可能会在目标点附近来回振荡。设置为一个略大于0的值如0.1或角色半径的一半可以让移动更稳定。移动与旋转分离上面的例子将移动和旋转耦合在同一个协程里。对于更复杂的动画控制如使用Animator最好将移动逻辑更新位置和旋转逻辑分开或者使用Unity的NavMeshAgent那样的方式只提供目标点由另一个更专业的移动控制器来处理具体移动和动画融合。路径动态更新如果目标是移动的如玩家你需要定期例如每秒或当目标移动超过一定距离时重新请求寻路。但要注意频率过于频繁的寻路请求是性能杀手。4. 性能优化与高级技巧一个基础的A*实现可以工作但在大型地图或大量NPC的场景下性能可能成为瓶颈。以下是几个关键的优化方向。4.1 数据结构与算法优化我们已经使用了堆来优化开放列表。除此之外使用更高效的关闭列表HashSetNode的查找效率是O(1)比ListNode的O(n)好得多。避免频繁的GC分配在FindPath循环中避免在循环体内new列表或数组。可以复用节点对象池。GetNeighbours方法可以预计算所有邻居的偏移量并直接返回网格引用而不是创建新的列表。分帧寻路如果一帧内有大量寻路请求可以将它们分散到多帧中执行避免单帧卡顿。可以维护一个寻路请求队列每帧只处理其中几个。4.2 权重与地形系统基础的A*只区分“可走”与“不可走”。更真实的游戏世界会有不同地形草地走得慢公路走得快沼泽非常慢。我们可以为Node类增加一个movementPenalty移动惩罚字段。public class Node { // ... 原有字段 public int movementPenalty; // 移动代价加成例如草地5公路0沼泽20 } // 在Pathfinding计算G值时加入惩罚 int newMovementCostToNeighbour currentNode.gCost GetDistance(currentNode, neighbour) neighbour.movementPenalty;这样算法会自动偏好移动代价低的路径即使它们看起来更长。4.3 分层寻路与局部避障对于超大地图一次性计算整个地图的路径是不现实的。可以采用分层寻路高层图将地图划分为大的区域簇区域间用关键点如门口、桥梁连接。先在高层的抽象图上寻路找到需要经过哪些区域。底层图在NPC进入每个区域时再使用标准的A*进行精细寻路。对于动态的小型障碍物如其他移动的NPCA频繁重算不划算。可以在A计算出的全局路径基础上结合局部避障算法如RVO (Reciprocal Velocity Obstacles)相互速度障碍法常用于人群模拟能让多个NPC自然地相互避让。势场法 (Potential Fields)将目标点设为引力场障碍物设为斥力场NPC沿着合力方向移动。计算简单适合处理大量简单单位的避障。4.4 与Unity生态的整合虽然我们自己实现了A*但有时也需要与其他系统配合与NavMesh混合使用对于静态环境用NavMesh生成大致路径对于动态障碍或需要特殊成本计算的区域切换到A*进行局部重规划。使用ECS/DOTS如果NPC数量极多成千上万可以考虑使用Unity的ECS架构和Job System来并行化A*寻路计算这将带来巨大的性能提升但实现复杂度也更高。5. 常见问题与调试技巧实录在实际开发中你肯定会遇到各种奇怪的问题。下面是我踩过的一些坑和解决方法。问题1NPC卡在角落或障碍物边缘。原因网格大小 (nodeRadius) 设置得与NPC碰撞体大小太接近或者障碍物检测 (CheckSphere) 的半径太小导致可行走网格与障碍物网格之间没有足够的“缓冲地带”。解决确保nodeRadius大于NPC碰撞体的半径。在检测障碍物时可以使用略大于nodeRadius的值进行检测或者在生成网格后对障碍物节点进行“膨胀”处理——将障碍物周围一圈的节点也标记为不可行走。问题2寻路结果不是最短路径或者路径很奇怪地绕远。原因最常见的原因是启发函数H值计算有误或者邻居节点的获取逻辑有问题比如不允许对角线移动但距离计算却按对角线算。也可能是开放列表中节点排序时F值相同时的处理逻辑不对。调试可视化网格和路径在GridManager中编写OnDrawGizmos代码用不同颜色绘制可行走/不可行走节点、开放列表、关闭列表以及最终路径。这是最直观的调试手段。检查启发函数确保你使用的距离估算方式曼哈顿、对角线、欧几里得与允许的移动方式匹配。单步调试对于一条出错的路径可以打印出算法每一步选择的节点及其F、G、H值看决策过程哪里出了问题。问题3大量NPC同时寻路导致游戏帧率下降。原因A*计算在主线程进行阻塞了游戏循环。解决强制异步将所有FindPath调用放入线程池或使用Task.Run。注意Unity的API如Transform.position,Physics.CheckSphere不是线程安全的必须在主线程进行世界坐标到网格坐标的转换 (NodeFromWorldPoint) 和障碍物检测。一种模式是主线程准备寻路请求数据起点、终点、网格数据快照→ 丢给后台线程计算 → 后台线程返回节点索引序列 → 主线程根据索引重建路径世界坐标。限制频率为每个NPC设置寻路冷却时间比如每秒最多重新寻路2次。简化网格在满足游戏需求的前提下使用尽可能大的网格节点。使用路径共享如果多个NPC要去同一个目标点可以只计算一次路径然后让它们共享这条路径或路径的大部分。问题4NPC移动时抖动或走“之”字形。原因路径点过于密集且NPC的移动和旋转速度不匹配或者每帧移动距离过大导致“过冲”然后又折返。解决路径平滑如前所述使用路径点简化或曲线平滑。改进移动控制器使用Vector3.MoveTowards或Vector3.SmoothDamp来实现更平滑的移动插值。对于旋转使用Quaternion.RotateTowards或Quaternion.Slerp。预测移动不要简单地向当前路径点移动可以向前看几个路径点计算一个更平滑的前进方向。问题5动态障碍物更新后NPC不会重新规划路径。原因网格数据是静态的初始化后没有监听场景中障碍物的变化。解决为动态障碍物注册让动态障碍物在启用/禁用或移动时通知GridManager更新其覆盖的网格节点的walkable状态。局部网格更新不需要更新整个网格只需计算动态障碍物影响到的局部区域其碰撞体范围加上NPC半径的缓冲区域的节点。路径失效与重算当NPC检测到其当前路径上的某个节点变为不可行走时立即停止移动并请求一次新的寻路。实现一个健壮、高效的A*寻路系统是游戏AI开发的一块重要基石。它不仅能用于NPC移动还能应用于塔防游戏中敌人的行进路线规划、策略游戏中单位的战术移动甚至解谜游戏中方块推拉的步骤计算。理解其原理掌握其优化技巧并学会根据具体游戏需求进行定制和扩展这将让你在解决各类路径规划问题时游刃有余。
