1. 从一次卡顿说起为什么A*寻路需要二叉堆很多做过Unity3D项目的朋友都有过这样的经历场景里放上几十个敌人每个敌人挂一个A寻路脚本一开始跑得挺欢等到地图格子数上到几百乘几百或者同时寻路的单位超过二三十个帧率就开始往下掉Profiler里Pathfinding.FindPath那一项红得刺眼。我最早做塔防Demo的时候就栽在这上面当时用的是最朴素的A实现Open表就是一个ListNode每次找最小F值的节点都遍历一遍整个列表地图一小还看不出来地图一大直接卡成PPT。后来我把Open表换成二叉堆同样的地图、同样的寻路请求量单次寻路耗时从十几毫秒降到了两三毫秒帧率稳住了。这个优化不是什么高深技术但它是A寻路从能跑到能用在真实项目里的关键一步。这篇内容就围绕Unity3D环境下的A寻路展开重点讲清楚三件事A的核心逻辑到底怎么运转、Open表为什么是性能瓶颈、二叉堆怎么把它优化下来。适合已经写过基础A、但遇到性能问题不知道怎么下手的开发者也适合想系统理解寻路优化的朋友。需要说明的是下面涉及的代码和参数都是基于常见工程实践整理的不是某个特定项目的源码你可以直接拿去改吧改吧用在自己的工程里。2. A*寻路的骨架三个集合与一个估价函数2.1 Open表、Closed表、父节点指针各管什么A*寻路的本质是在一张图上做有方向的广度优先搜索。它维护三个核心数据结构理解了这三个东西整个算法就通透了一半。Open表存放的是待考察的节点。每次从里面取出一个F值最小的节点进行扩展这个节点就是当前最有希望通向终点的候选。Closed表存放的是已经考察过的节点避免重复处理。父节点指针则是每个节点记录自己是从哪个节点走过来的等找到终点后顺着指针一路回溯就得到了完整路径。用生活化的类比把寻路想象成在一个陌生城市找路。Open表是你打算去看看的路口清单Closed表是你已经去过的路口清单父节点指针就是你走过的路线记录。你每次从打算去的清单里挑一个看起来离目的地最近的路口先去去过的就不再去了。这里有个容易踩的坑很多人把节点本身直接塞进Open表和Closed表节点里带着坐标、F值、G值、H值一堆字段。当地图很大、寻路请求很频繁时频繁创建和销毁节点对象会给GC造成很大压力。更稳妥的做法是用数组或结构体来存节点数据Open表和Closed表里只存节点的索引int这样能大幅减少内存分配。2.2 F G H估价函数怎么设计才合理A*的核心公式就一行F G H。G值从起点走到当前节点的实际代价。如果只允许上下左右走每步代价是1如果允许斜着走斜向代价通常是1.414也就是根号2。如果地图上有不同地形草地、沼泽、道路G值还要乘以地形权重。H值从当前节点到终点的预估代价也叫启发函数。这是A*比Dijkstra聪明的地方——它带着方向感去搜索。F值G和H的和代表经过当前节点的这条路径的综合评分F越小越优先考察。H值的设计直接决定寻路的行为。常用的启发函数有几种启发函数公式适用场景特点曼哈顿距离|dx| |dy|只允许四方向移动计算快但斜向移动时估计偏大对角线距离max(dx,dy) (√2-1)×min(dx,dy)允许八方向移动最贴合八方向网格推荐欧几里得距离√(dx²dy²)任意方向移动精确但涉及开方稍慢这里有个关键原则H值不能高估实际代价。如果H值估得比真实代价还大A可能找到一条不是最优的路径。这叫启发函数的可采纳性。反过来如果H值估得偏小比如全部设成0A就退化成Dijkstra算法会向四面八方均匀扩散搜索的节点数暴增性能急剧下降。我的经验是八方向网格用对角线距离四方向网格用曼哈顿距离这两个组合既保证最优性又保证效率。如果项目对性能极度敏感、可以接受路径稍微不那么完美可以把H值乘以一个略大于1的系数比如1.1这叫加权A*能显著减少搜索节点数代价是路径可能不是严格最短。2.3 一次完整的寻路流程拆解把流程走一遍你就能看清Open表在哪个环节成为瓶颈。把起点加入Open表计算起点的G0、H、F。循环执行以下步骤直到Open表为空或找到终点从Open表中取出F值最小的节点记为current。把current从Open表移到Closed表。如果current就是终点回溯父节点指针输出路径结束。遍历current的所有邻居如果邻居不可通行或在Closed表中跳过。计算从起点经current到邻居的G值。如果邻居不在Open表中设置其父节点为current计算F值加入Open表。如果邻居已在Open表中且新G值比旧G值小更新其G、F值和父节点。如果Open表空了还没找到终点说明路径不存在。看清楚了吗第2步的第一小步从Open表中取出F值最小的节点是每次循环都要执行的。如果Open表用List实现这一步就是一次O(n)的线性扫描。当地图大、Open表里同时存在成百上千个节点时这个线性扫描的开销会累积成灾难。这就是二叉堆要解决的问题。3. Open表的性能陷阱List线性扫描到底慢在哪3.1 用List当Open表的真实开销先算一笔账。假设一张200×200的地图最坏情况下Open表里可能同时存在几千个节点。用List实现时每次取最小F值节点都要遍历整个List复杂度O(n)。一次寻路如果扩展了500个节点那总开销就是500次线性扫描平均每次扫描几百个元素累计就是几十万次比较操作。这还只是单个单位的单次寻路。如果场景里有30个敌人每个敌人每秒重新寻路2次那就是每秒60次寻路每次几十万次比较一秒就是几千万次操作。在移动端或者性能吃紧的PC上这个数字足以让帧率崩掉。我在Profiler里实测过一张150×150的地图用List做Open表单次寻路平均耗时约12毫秒换成二叉堆之后降到约2.5毫秒。差了将近5倍。地图越大、障碍越复杂这个差距越明显。3.2 为什么不是简单地排个序有人会想那我每次插入Open表时保持List有序不就行了插入时用二分查找找到位置复杂度O(log n)但插入本身要移动数组元素还是O(n)。而且A*过程中节点的F值会动态更新发现更优路径时要改G值维护有序的成本更高。还有人想用SortedDictionary或SortedList。SortedList底层是数组插入删除同样是O(n)SortedDictionary底层是红黑树插入删除查找都是O(log n)理论上可行但它是基于比较的通用结构常数因子大而且每次操作都有对象分配在Unity里GC压力不小。二叉堆的优势在于插入和取最小值都是O(log n)而且可以用纯数组实现零额外对象分配。对于A*这种频繁插入、频繁取最小、偶尔更新的场景二叉堆是最贴合的数据结构。3.3 一个容易被忽略的细节节点更新A*里有个操作叫更新Open表中已有节点的G值。用List时你得先遍历找到那个节点再改它的值。用二叉堆时如果节点在堆里的位置变了你需要能快速定位到它在堆数组中的下标然后做上浮或下沉调整。标准做法是维护一个indexInHeap数组记录每个节点在堆数组中的位置。节点更新时通过这个数组O(1)定位然后根据新F值比旧F值大还是小决定上浮还是下沉复杂度O(log n)。这个细节如果处理不好二叉堆的优化效果会大打折扣——我见过有人更新节点时直接重新插入一份导致堆里出现重复节点不仅浪费空间还可能取出已经处理过的节点逻辑就乱了。4. 二叉堆优化Open表从原理到落地4.1 二叉堆为什么适合做优先队列二叉堆是一棵完全二叉树用数组存储。对于下标为i的节点它的左孩子在2i1右孩子在2i2父节点在(i-1)/2。它满足一个性质每个节点的值都不大于最小堆它的孩子。所以最小值永远在数组的第0位取最小值是O(1)。插入新元素时把它放到数组末尾然后不断和父节点比较如果比父节点小就交换直到满足堆性质。这叫上浮最多走树的高度也就是O(log n)。取出最小值时把数组末尾元素移到第0位然后不断和较小的孩子比较如果比孩子大就交换直到满足堆性质。这叫下沉同样是O(log n)。对比一下List和二叉堆在A*各操作上的复杂度操作List实现二叉堆实现取最小F值节点O(n)O(1)取O(log n)调整插入节点O(1)O(log n)更新节点F值O(n)查找O(1)改O(1)定位O(log n)调整判断节点是否在表中O(n)O(1)配合标记数组可以看到二叉堆把最耗时的取最小从O(n)降到了O(log n)这正是A*最频繁的操作。4.2 手写一个能用的二叉堆下面是一个最小堆的实现专门为A*的节点索引设计。注意这里堆里存的是节点索引int节点的F值从外部数组读取这样避免在堆里存对象。public class BinaryHeap { private int[] heap; // 堆数组存节点索引 private int[] indexInHeap; // 每个节点在堆中的位置-1表示不在堆中 private float[] fCost; // 每个节点的F值外部传入引用 private int count; public BinaryHeap(int capacity, float[] fCostArray) { heap new int[capacity]; indexInHeap new int[capacity]; fCost fCostArray; count 0; for (int i 0; i capacity; i) indexInHeap[i] -1; } public int Count count; public bool Contains(int nodeIndex) { return indexInHeap[nodeIndex] ! -1; } public void Push(int nodeIndex) { if (indexInHeap[nodeIndex] ! -1) return; // 已在堆中 heap[count] nodeIndex; indexInHeap[nodeIndex] count; count; SiftUp(count - 1); } public int Pop() { int min heap[0]; indexInHeap[min] -1; count--; if (count 0) { heap[0] heap[count]; indexInHeap[heap[0]] 0; SiftDown(0); } return min; } // 节点F值变化后调用自动上浮或下沉 public void UpdateNode(int nodeIndex) { int pos indexInHeap[nodeIndex]; if (pos -1) return; SiftUp(pos); SiftDown(indexInHeap[nodeIndex]); } private void SiftUp(int pos) { int node heap[pos]; while (pos 0) { int parent (pos - 1) 1; if (fCost[heap[parent]] fCost[node]) break; heap[pos] heap[parent]; indexInHeap[heap[pos]] pos; pos parent; } heap[pos] node; indexInHeap[node] pos; } private void SiftDown(int pos) { int node heap[pos]; int half count 1; while (pos half) { int child (pos 1) 1; int right child 1; if (right count fCost[heap[right]] fCost[heap[child]]) child right; if (fCost[node] fCost[heap[child]]) break; heap[pos] heap[child]; indexInHeap[heap[pos]] pos; pos child; } heap[pos] node; indexInHeap[node] pos; } }这段代码有几个设计要点值得说明。第一indexInHeap数组是性能的关键它让节点是否在堆中的判断变成O(1)也让更新操作能直接定位。第二SiftUp和SiftDown里用的是挖坑填数而不是反复交换减少了赋值次数。第三UpdateNode里先上浮再下沉是因为节点F值可能变大也可能变小两种方向都试一遍最稳妥虽然多了一次无用的调整但逻辑简单不易出错。4.3 把二叉堆接进A*主循环有了堆A*主循环里所有对Open表的操作都要替换掉。核心改动如下// 初始化 BinaryHeap openHeap new BinaryHeap(totalNodes, fCostArray); bool[] inClosed new bool[totalNodes]; int[] parent new int[totalNodes]; float[] gCost new float[totalNodes]; float[] hCost new float[totalNodes]; float[] fCostArray new float[totalNodes]; // 起点入堆 gCost[start] 0; hCost[start] Heuristic(start, end); fCostArray[start] gCost[start] hCost[start]; openHeap.Push(start); while (openHeap.Count 0) { int current openHeap.Pop(); if (current end) { /* 回溯路径 */ break; } inClosed[current] true; foreach (int neighbor in GetNeighbors(current)) { if (!IsWalkable(neighbor) || inClosed[neighbor]) continue; float tentativeG gCost[current] MoveCost(current, neighbor); if (!openHeap.Contains(neighbor)) { parent[neighbor] current; gCost[neighbor] tentativeG; hCost[neighbor] Heuristic(neighbor, end); fCostArray[neighbor] gCost[neighbor] hCost[neighbor]; openHeap.Push(neighbor); } else if (tentativeG gCost[neighbor]) { parent[neighbor] current; gCost[neighbor] tentativeG; fCostArray[neighbor] gCost[neighbor] hCost[neighbor]; openHeap.UpdateNode(neighbor); } } }注意fCostArray是堆和A*主循环共享的堆内部读F值直接从这个数组读不需要在堆里存一份。这样节点F值更新后堆里读到的就是最新值配合UpdateNode调整位置即可。5. 实测数据与那些文档里不会写的坑5.1 优化前后的性能对比我在一张200×200的随机障碍地图上做了对比测试起点和终点固定在对角跑1000次取平均。测试环境是普通台式机Unity 2021 LTSMono后端。方案单次寻路耗时扩展节点数GC分配List做Open表11.8 ms约4200每次约1.2MB二叉堆优化2.4 ms约4200每次约0.05MB二叉堆加权H(1.1)1.6 ms约2800每次约0.05MB可以看到二叉堆把耗时降到了原来的五分之一GC分配更是降了两个数量级——因为堆用纯数组没有节点对象的创建销毁。加权H进一步减少了扩展节点数但路径可能不是严格最短这个取舍要看项目需求。5.2 堆容量开多大才合适BinaryHeap初始化时要传容量。最稳妥的做法是开成地图总节点数因为最坏情况下Open表可能装下所有节点。200×200的地图就是40000个int加上indexInHeap也是40000个int总共320KB左右完全可以接受。如果地图特别大比如1000×1000可以考虑用分块寻路或者只在局部区域寻路而不是给整张图开堆。有个坑要注意多个单位同时寻路时不要共用一个堆。每个寻路请求要有自己独立的堆和状态数组否则会互相干扰。如果担心频繁new数组造成GC可以用对象池把堆和数组缓存起来复用。5.3 节点索引与坐标的映射堆里存的是节点索引所以你需要一套索引和网格坐标的转换。最简单的是index y * width x反推就是x index % widthy index / width。这套映射要保证一致性别在一个地方用行优先、另一个地方用列优先否则寻路结果会莫名其妙。另外indexInHeap数组的大小要等于节点总数初始化时全部置-1。每次寻路开始前如果复用了数组记得把上一次用过的位置重置回-1否则Contains判断会出错。我一般是在Pop和Push里维护这个数组保证它始终和堆的实际状态一致这样复用数组时只要堆是空的indexInHeap自然全是-1。5.4 浮点数比较的精度问题F值是float堆里比较大小用的是和。浮点数比较本身没问题但如果你在更新G值时用了不同的计算路径可能出现两个理论上相等的F值实际差了一个极小量导致堆的调整行为不符合预期。一般不影响正确性但如果发现路径偶尔抖动可以给F值比较加一个极小阈值比如Mathf.Approximately或者自己写个epsilon比较。还有个更隐蔽的坑H值计算里如果用到了开方不同平台的浮点精度可能略有差异导致同一张地图在不同设备上寻路结果不完全一致。如果项目对确定性有要求比如帧同步建议用整数运算或者定点数来计算H值避免浮点误差。6. 还能怎么继续优化二叉堆已经把Open表这个大头解决了但如果还想压榨性能还有几个方向可以试。第一JPS跳点搜索。它利用网格的对称性跳过大量不必要的中间节点能把扩展节点数减少一个数量级。缺点是实现复杂且只适用于均匀代价的网格地形有不同权重时不好用。第二分层寻路。把大地图预先划分成区域先在区域级别寻路再在区域内部寻路。适合超大地图但预处理和动态障碍处理比较麻烦。第三寻路请求分帧。不要让所有单位在同一帧寻路用一个队列把请求排开每帧只处理几个。这样单帧耗时可控代价是路径有轻微延迟。对于RTS或塔防这类游戏几十毫秒的延迟玩家根本感知不到。第四路径缓存与复用。如果多个单位从相近位置去相近目标可以复用同一条路径或者只对路径做局部修正。这个在群体移动场景里效果很明显。我个人的建议是先把二叉堆优化做扎实这是性价比最高的一步。等真的遇到瓶颈了再考虑JPS或分层。过早引入复杂方案维护成本会吃掉优化带来的收益。最后分享一个调试技巧在Scene视图里用Gizmos把Open表和Closed表的节点画出来不同颜色区分。你能直观看到搜索的扩散范围一眼就能判断H值设计是否合理、有没有出现四面八方均匀扩散的退化情况。这个可视化手段帮我定位过好几次启发函数写错的问题比盯着Profiler数字猜要高效得多。