当地图很⼤的时候，或者使⽤A星算法的寻路频率很⾼的时候，普通的A星算法就会消耗⼤量的CPU性能急剧下降，普通的A星性能还是不过关。接下来我们讲讲A星寻路在遇到性能瓶颈时的优化⽅案。 当距离很⼤，中间有很多障碍物时，A星的算法就会遇到瓶颈，不断加⼊的可⾏⾛点使得排序速度越来越慢，最后可能造成CPU阻塞⽆法动弹。
当寻路距离太⼤时怎么办？
其实路径不是⾮得实时计算出来才好，我们可以把⼀些常⽤的路径，在离线下算好放在数据⽂件中，游戏开启时放在内存⾥，当需要寻路到那个节点或者那个节点附近时，就可以取出来直接使⽤，⽽不再需要计算。 ⽐如 A到B 我们已经算法路径并存放在了内存⾥，当我们在A附近，要寻路到B附近时，就可以先寻路到A，再调出A到B的路径，再计算B 到⽬的的路径。
以这种⽅式来规避⼀些计算量特别⼤，或者计算频率特别⾼的寻路算法调⽤，在⼤型世界的RPG游戏⾥特别常⽤。
另⼀种⽅法为制作导航点的⽅式。什么是导航点呢？就是去⽬的地的必经的点位。
⽐如在⼀座城市⾥，有4个出⼝点，这个4个出⼝点就可以称为导航点，去⽬的地的路上肯定会经过这4个点的其中⼀个，我们在寻路时可以先寻到最近的⼀个出⼝的导航点，当到达导航点后，再次寻到⽬的地去的路径，有可能在这条路径上，还有⼀些导航点，继续寻最近的导航点，依次类推，直到没有导航点可寻时，则直接寻路到⽬的地。
⼆、A星的排序算法优化
每次插⼊open列表的点后，open就不再是有序的队列了，所以每次去拿最⼩值时都需要重新排序。排序的时间消耗随着队列长度的增⼤⽽增⼤，其实有很⼤⼀部分A星的性能消耗都在排序上。
那么是不是可以不排序，其实可以不排序，⽽使⽤到插⼊位置并插⼊的⽅法，让队列永远保持有序状态。
因为open队列在插⼊前是有序的，所以我们可以选⽤⼆分查算法来到插⼊的位置。
每次插⼊时都使⽤⼆分查算法查插⼊点，那么每次的插⼊复杂度为O(logN)，⽐快排⼀次的O(NlogN)要快很多。
三、优化排序判断依据的预测值计算⽅法自动化机械手臂
前⾯⽤图所举的例⼦中，都是以当前点p与终点e之间的距离来作为预测值，这种⽅法简单但也不科学，导致A星寻更好的点位时总是要绕很⼤的弯路。
我们可以改变⼀下这个策略，选⽤⼀个更科学的⽅法， F 预测值= G 当前最近步数 + H 预测当前点到终点的步数 的⽅法。
F 为预测值，G为起点s到当前点p的最近步数，H为当前点p到终点e的预测值，它们相加为F预测值。
其中G应该是已经计算好并放⼊节点中的值，该值就是计算过程中起点s到当前点的步数。我们可以把每步计算好的步数都放⼊节点中，以待需要计算时使⽤。
这个⽅法相当于，原来只关注当前点到终点的距离，变为关注起点s经过当前点p路径到终点e的距离，虽然还是贪婪的简单预测算法，但⽐起原来只关注当前点p与终点e的距离，更加科学化，能更快的到更好更近的点位。
为什么要改善这个预测值，改善预测值有什么意义呢？时钟显示器
筋膜仪其实预测值的计算⽅法代表了在寻路过程中的⾛法，如果预测值只关注在于终点距离最近的点上，那么在寻路过程中的选择点位的顺序就会偏向于与终点更近的点。⽽如果预测值计算公式，关注的是整个距离较近的点位上，那么在寻路过程中在选择点位上也就会偏向整条路径短的⽅向上去靠。
四、多次频繁A星寻路的优化
多次频繁寻路中，对A星算法中每个运算，每⾏代码的运算细节都会有⽐较重⼤的考验。
⽐如我们在查看⼀个节点是否为被取过的节点，即是否为Close，很多⼈都会在Close⾥取寻该节点是否存在，这个操作明显就没有考虑到性能的消耗，要在Close列表中节点，就相当于遍历⼀遍所有已经过的节点，Close⾥的节点越多，越浪费CPU，⽽且是不只⼀次浪费，每个循环都会浪费⼀次，性能消耗巨⼤。
因此我们通常的做法是把节点作为⼀个实例，在实例中添加IsClose的变量，来判断是否被取过，或者说是否Close。
但这种⽅法还是不够，因为IsClose变量是要初始化的，每次寻路都要将前⾯寻路过的痕迹抹去才能开始全新的寻路过程。
这就是⼜⼀个被很多⼈忽视的初始化的性能消耗，每次在A星寻路开始前，需要将IsClose的变量初始化为false，就需要遍历整个数据来初始化。
每次都要遍历整个数据的话，A星算法⽆论优化的多快都⽆济于事了，因为初始化的性能消耗就已经将A星的性能消耗完全盖掉了。如果初始化的性能消耗需要遍历整个数据，那么优化A星算法的意义何
细分驱动器
在。
其实可以⽤⼀个变量就能判断IsClose的⽅法，⽆需初始化。
我们可以在寻路类中设置⼀个属性变量FindIndex，或者专门为寻路服务的静态变量也可以，⽽每个寻路节点中也存有⼀个变量FindIndex，每次寻路前都对FindIndex++，在判断IsClose时，当节点中的FindIndex与寻路类中FindIndex⼀致时说明已经被当次寻路算法取出过，否则两者不⼀样，说明这个节点没有被取出过，当节点被取出时，节点⾥的FindIndex则设置为当前寻路类中的FindIndex值，以表明该节点已经被这次寻路算法取出过。
⽤⼀个变量和整数的⽐较就能知道IsClose的结果，省去了巨量的初始化操作。
在A星算法这种经常⽤频繁⽤的算法中，⼀个⼩⼩的性能消耗就能放⼤很多倍，特别注意调⽤的函数的复杂度，公式的复杂度，以及运算的优化，尽量做到能不调⽤函数的不调⽤函数，能简化公式的尽量简化公式，能⽤&|<>位运算符号代替加减乘除的尽量⽤位运算代替，节省A 星算法的性能开销。
我也看过所谓的B星算法过程，其实世上没有B星，所谓的B星其实就是我们A星的优化版本，⽽且互联⽹中所阐述的B星算法存在⼀定⼏率⽆法寻到路径的问题，即它只关注所谓的‘前⽅‘，⽽忽略了其实’后⽅‘也有路，如果只有后⽅有路时，B星就⽆法到路径。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议