A*搜索算法（补充）

在之前的文章A*搜索算法(Java实现)中，本人给大家介绍了A*搜索算法的算法流程以及附送了了一份本人用Java代码实现的A*搜索算法，今天，我们就从应用方面谈一谈A*搜索的一些应用场景以及对于之前的算法如何进行改良；

1.利用A*搜索算法进行道路规划:作为最典型的启发式搜索的典型算法，我们可以通过预估算走到路径的改路径将会花费的成本，每走一步都是一个取局部最优的过程(贪心思想)，当我们寻找到了一条从起点到终点的路径时，这条路径可能不是全局最优的解决方案，但是这个解决方案在某些应用场景上也是可以接受的，例如在针对寻找一条从A地到B地的一条路径，如果我们将路径长度作为代价成本的话，至少从路程来看，我们显然是最短的那条路径，即使这条路径可能不是最经济的。

搜索路径

在进行道路规划是，我们可以针对最重要的因素S进行A*搜索，确保在S方面取得最优的解决方案。

2. 平滑路径:A* 自动给你花费最小的，最短的路径，但它不会自动给你最平滑的路径。看看我们的例子所找到的路径。

图2

如图二所示，在这条路径上，第一步在起点的右下方，如果第一步在起点的正下方是不是路径会更平滑呢？

       有几个方法解决这个问题。在你计算路径时，你可以惩罚那些改变方向的方格，把它的 G 值增加一个额外的开销。另一种选择是，你可以遍历你生成的路径，查找那些用相邻的方格替代会使路径更平滑的地方。

3.关于路径代价F中的H部分，我们在计算这个值是可以考虑将障碍物，如果这条路径存在障碍物，可以将此路径的代价提高。

4.  预先处理你的地图，指出哪些区域是不可到达的。这些区域称为“孤岛”。实际上，他们可以是岛屿，或者是被墙壁等包围而不可到达的任意区域。 A* 的下限是，你告诉他搜寻通往哪些区域的路径时，他会搜索整个地图，直到所有可以抵达的方格都通过 open list 或 close list 得到了处理。这会浪费大量的 CPU 时间。这可以通过预先设定不可到达的区域来解决。在某种数组中记录这些信息，在寻路前检查它。

5.非方形搜索区域：在我们的例子中，我们使用都是 2D 的方形的区域。你可以使用不规则的区域。想想冒险游戏中的那些国家，你可以设计一个像那样的寻路关卡。你需要建立一张表格来保存国家相邻关系，以及从一个国家移动到另一个国家的 G 值。你还需要一个方法了估算 H 值。其他的都可以向上面的例子一样处理。当你向 open list 添加新项时，不是使用相邻的方格，而是查看表里相邻的国家。