实战避坑：在Unity里用A*做2D网格寻路，我踩过的性能坑和优化方案都在这了
Unity中A*算法性能优化的实战指南
当你在Unity项目中实现了一个基础A寻路系统后，随着游戏单位数量增加或地图规模扩大，性能问题往往会突然出现。帧率下降、卡顿现象频发，这些问题在移动端或需要大量单位同时寻路的RTS、塔防类游戏中尤为明显。本文将分享我在多个商业项目中积累的A性能优化经验，从数据结构选择到并行计算，提供一套完整的解决方案。
1. 核心数据结构优化：OpenList与CloseList的高效管理
大多数A*教程示例中使用简单的List来管理OpenList和CloseList，这在小型地图中尚可接受，但在实际项目中会成为性能瓶颈。当OpenList包含数千个节点时，每次查找F值最小的节点都会导致严重的性能问题。
1.1 优先队列(PriorityQueue)的引入
使用优先队列替代List可以大幅提升性能。C#中可以通过自定义堆结构实现：
public class PriorityQueue<T> where T : IComparable<T> { private List<T> data = new List<T>(); public void Enqueue(T item) { data.Add(item); int childIndex = data.Count - 1; while (childIndex > 0) { int parentIndex = (childIndex - 1) / 2; if (data[childIndex].CompareTo(data[parentIndex]) >= 0) break; T tmp = data[childIndex]; data[childIndex] = data[parentIndex]; data[parentIndex] = tmp; childIndex = parentIndex; } } public T Dequeue() { int lastIndex = data.Count - 1; T frontItem = data[0]; data[0] = data[lastIndex]; data.RemoveAt(lastIndex); --lastIndex; int parentIndex = 0; while (true) { int childIndex = parentIndex * 2 + 1; if (childIndex > lastIndex) break; int rightChild = childIndex + 1; if (rightChild <= lastIndex && data[rightChild].CompareTo(data[childIndex]) < 0) childIndex = rightChild; if (data[parentIndex].CompareTo(data[childIndex]) <= 0) break; T tmp = data[parentIndex]; data[parentIndex] = data[childIndex]; data[childIndex] = tmp; parentIndex = childIndex; } return frontItem; } }1.2 CloseList的替代方案
传统CloseList实现方式存在的问题：
- List.Contains()操作时间复杂度为O(n)
- 频繁的内存分配和释放
优化方案：
// 使用二维数组代替List private bool[,] closedNodes; // 初始化 closedNodes = new bool[mapWidth, mapHeight]; // 检查节点是否在CloseList中 bool isClosed = closedNodes[x, y]; // 添加节点到CloseList closedNodes[x, y] = true;2. 启发函数的选择与性能影响
启发函数h(n)的选择不仅影响路径质量，还直接影响算法性能。以下是三种常见启发函数的对比：
| 启发函数类型 | 计算公式 | 适用场景 | 性能影响 |
|---|---|---|---|
| 曼哈顿距离 | h = | dx | + |
| 对角线距离 | h = max( | dx | , |
| 欧几里得距离 | h = √(dx² + dy²) | 任意方向移动 | 计算成本高，路径最平滑 |
实际项目中，我推荐使用对角线距离作为默认选择：
// 对角线距离实现 private float Heuristic(int x1, int y1, int x2, int y2) { int dx = Mathf.Abs(x1 - x2); int dy = Mathf.Abs(y1 - y2); return Mathf.Max(dx, dy) + (Mathf.Sqrt(2) - 1) * Mathf.Min(dx, dy); }提示：在移动端设备上，避免在启发函数中使用平方根运算，可以用近似值替代。
3. 利用Unity Job System进行并行计算
当需要同时计算多个单位的路径时，传统的单线程A*会成为性能瓶颈。Unity的Job System可以完美解决这个问题。
3.1 并行A*的基本结构
// 定义Job结构 public struct AStarJob : IJob { public int startX, startY; public int targetX, targetY; public NativeArray<bool> walkableMap; public NativeArray<int> pathResult; public int mapWidth; public void Execute() { // 在这里实现A*算法 // 结果存储在pathResult中 } } // 调用Job public void FindPathParallel(int startX, int startY, int targetX, int targetY) { var job = new AStarJob { startX = startX, startY = startY, targetX = targetX, targetY = targetY, walkableMap = new NativeArray<bool>(mapData, Allocator.TempJob), pathResult = new NativeArray<int>(maxPathLength, Allocator.TempJob), mapWidth = mapWidth }; JobHandle handle = job.Schedule(); handle.Complete(); // 处理结果 int[] path = job.pathResult.ToArray(); // 释放NativeArray job.walkableMap.Dispose(); job.pathResult.Dispose(); }3.2 性能优化技巧
- 使用Burst Compiler加速计算
- 合理设置Job的batch size
- 避免在Job中分配托管内存
4. 动态障碍物处理策略
游戏中经常会有动态变化的障碍物，完全重新计算路径成本过高。以下是几种实用策略：
4.1 局部重规划(Local Repair)
当单位遇到新出现的障碍物时：
- 记录当前位置到目标点的直线距离
- 如果距离小于阈值，尝试绕开障碍物
- 否则，触发完整A*重新计算
public bool TryLocalRepair(Vector2 currentPos, Vector2 obstaclePos, float repairRadius) { // 简单的绕障算法示例 Vector2 toTarget = targetPos - currentPos; Vector2 toObstacle = obstaclePos - currentPos; if (toObstacle.magnitude < repairRadius) { Vector2 bypassDir = Vector2.Perpendicular(toObstacle.normalized); // 尝试两个方向的绕行 if (!Physics2D.Raycast(currentPos, bypassDir, repairRadius, obstacleMask)) { currentPath = GenerateBypassPath(currentPos, bypassDir); return true; } else if (!Physics2D.Raycast(currentPos, -bypassDir, repairRadius, obstacleMask)) { currentPath = GenerateBypassPath(currentPos, -bypassDir); return true; } } return false; }4.2 分层路径规划(Hierarchical Pathfinding)
对于大地图：
- 将地图划分为多个区域(Region)
- 先计算区域间的路径
- 再计算区域内的详细路径
public List<Vector2> FindHierarchicalPath(Vector2 start, Vector2 end) { // 第一层：区域路径 Region startRegion = GetRegion(start); Region endRegion = GetRegion(end); List<Region> regionPath = FindRegionPath(startRegion, endRegion); // 第二层：详细路径 List<Vector2> detailedPath = new List<Vector2>(); Vector2 current = start; foreach (Region region in regionPath) { Vector2 entrance = GetRegionEntrance(region, current); List<Vector2> segment = FindDetailedPath(current, entrance); detailedPath.AddRange(segment); current = entrance; } detailedPath.AddRange(FindDetailedPath(current, end)); return detailedPath; }5. 内存优化与对象池
频繁的路径计算会导致大量内存分配，合理使用对象池可以显著减少GC压力。
5.1 节点对象池实现
public class NodePool { private Stack<PathNode> pool = new Stack<PathNode>(); public PathNode GetNode(int x, int y, float g, float h, PathNode parent) { if (pool.Count > 0) { PathNode node = pool.Pop(); node.Reinitialize(x, y, g, h, parent); return node; } return new PathNode(x, y, g, h, parent); } public void ReturnNode(PathNode node) { pool.Push(node); } } // 使用方式 PathNode node = nodePool.GetNode(x, y, gCost, hCost, parentNode); // 使用完毕后 nodePool.ReturnNode(node);5.2 路径缓存策略
对于静态环境中的常用路径，可以实现简单的缓存机制：
public class PathCache { private Dictionary<(int, int, int, int), List<Vector2>> cache = new Dictionary<(int, int, int, int), List<Vector2>>(); private const int MaxCacheSize = 1000; public bool TryGetPath(int startX, int startY, int endX, int endY, out List<Vector2> path) { return cache.TryGetValue((startX, startY, endX, endY), out path); } public void CachePath(int startX, int startY, int endX, int endY, List<Vector2> path) { if (cache.Count >= MaxCacheSize) { // 简单的LRU缓存淘汰策略 var firstKey = cache.Keys.First(); cache.Remove(firstKey); } cache[(startX, startY, endX, endY)] = new List<Vector2>(path); } }在实现RTS游戏的大规模单位移动时，这些优化手段帮助我们将寻路性能提升了5-8倍。特别是在移动设备上，合理的数据结构选择和内存管理往往比算法本身的优化带来更大的性能提升。