本文是 AStar寻路1-实现基本功能 的性能优化篇。
性能分析方法
为了查看代码的 profiler，本文使用 Unity 实现图形化，借助 VS 的 C# 性能测试工具，通过热点函数来定位瓶颈并制定优化策略。
经过 VS 性能测试工具分析，上篇的热点函数集中在排序相关操作和估值函数上。
A* 路径精度
A* 寻路所得的路径，在大多数情况下并非最短路径，但一定接近最短路径。只有每次的估计值恰好等于真实最短路径的代价，才能得到严格意义上的最短路径。
原因在于 A* 采用贪心策略，估值本身存在误差，且某节点的 f 值一旦确定就不再更新，直到寻路结束。因此，估值函数的精度与效率对整个算法影响极大。
常见估值方法
- 曼哈顿距离法：目标点与当前点的水平距离与垂直距离之和，计算开销最小。
- 直线距离法：两点之间的欧氏距离，因涉及开方运算，CPU 代价较大，但得到的路径更平滑，开销约为曼哈顿的 2 倍。
- 综合法：结合了以上两种方法的特点，如下图所示，从 A 点到 B 点的示意：
空间优化
搜索过程中，由于事先不确定是否存在可达路径，需要保存完整的节点信息。最坏情况下（无路径），空间占用等于节点总数。对于需要反复寻路的场景，复用 Node 对象可以避免频繁 new 的开销，是一个值得关注的优化点。
open 表排序优化
从时间开销来看，每次向 open 表插入节点时都需要保持列表有序。一种有效的优化方案是使用二叉堆来维护 open 表的有序性。
通过数组实现二叉堆，可以快速索引节点在堆中的位置，从而高效完成插入操作。二叉堆的详细原理此处不再展开。