2.8　用A*找到最优路径

A*算法可能是路径查找中最常用的技术了，因为它容易实现、效率高，而且还有优化的余地。所以有一些算法把它作为基础并非巧合。另外，A*与迪杰斯特拉算法具有同根性，所以你会发现它们实现上的相似之处。

准备工作

就像迪杰斯特拉算法，本节也使用GPWiki中的二叉堆实现。同样，理解它们代表什么以及它们的原理很重要。最后，我们进入启发式搜索，这意味着我们需要理解什么是启发式以及它的用处是什么。

简单来说，就本节的目的而言，启发式算法是一个用于计算两个顶点之间近似成本的函数，以便于比较其他结果并选择最小成本的结果。

我们需要对Graph类做一个小的修改：

1. 将成员变量定义为delegate：

2. 实现欧几里得距离的函数，作为默认的启发式算法：

3. 实现曼哈顿距离的函数，作为另一个启发式算法。它将帮助我们比较使用不同启发式算法的结果：

操作步骤

虽然本节定义了一个函数，但是请注意代码中的注释，以便更好地理解代码逻辑：

1. 定义GetPathAstar函数及其成员变量：

2. 将源节点添加到堆（作为优先队列）中并赋一个无限大的距离值给除源节点之外的所有顶点：

3. 声明用于遍历图的循环：

4. 实现用于在必要时返回路径的条件逻辑：

5. 获取顶点的邻接点（某些书中也叫作前驱节点）：

6. 遍历邻接点，用于计算cost函数：

7. 如果有必要的话，扩大已经访问过的节点（frontier）列表并更新成本值：

运行原理

A*的原理与迪杰斯特拉算法很相似，但是，A*不是从所有可能的节点中选择出真正的最低成本的节点，而是基于一个给定的启发式算法选择出最优的节点，然后继续下去。在我们的示例中，默认的启发式算法仅仅基于两个顶点间的欧几里得距离，或者曼哈顿距离。

延伸阅读

鼓励你根据不同的游戏和上下文编写不同的启发式算法的函数，下面是一个示例：

在Graph类中定义启发式函数：

在这里最重要的事情是，我们开发的启发式算法既是可接受的，又是始终一致的。更多关于这些话题的深入原理请参考Russel和Norvig的著作：Artificial Intelligence: A Modern Approach。

你可能没有注意到，我们没有实现BuildPath方法，这是因为在2.5节中已经讨论过。

其他参考

请参考本章中的以下内容：

▪ 见2.7节

▪ 见2.5节

关于Delegates的更多信息，请参阅网站上的官方文档：

https://unity3d.com/learn/tutorials/modules/intermediate/scripting/delegates