【译】寻找最快的途径——A*寻路算法

　　在计算机科学中最常见的问题之一就是找到从出发点到目标的最短途径。有许多算法致力于解决这个问题，其中最流行的就是我们所知道的A*算法。

　　A*算法基本上由一个互相联系的网络构成。每个网络上的节点都知道它相邻的节点，并且知道它到它们的距离。没有要求规定路径一定是对称的，所以如果一个路径加入了，没有路径到其他节点，那么算法就会给这个节点建立一个模型，但是不包括反向路径。

　　A*算法的关键叫做the Heuristic（启发式）。如果 heuristic 大于最小值，那么它就会发现一个更慢的路径，但是如果 heuristic 太低，A*算法就会花费更多的时间来运行。一个普通的算法应该包括两点之间的物理路径。举个例子如果你的节点是基于网格式的系统，你正打算从点（2，0）到点（5，0），你的 heuristic 可能就是3。

　　A*算法工作原理是：从最开始的节点开始，识别其周围节点和到每个周围节点的距离。每个节点通过启发式来估算它到目标网格的距离。这些方格被放置在排序缓冲区，以距离排序。下一个测试的节点就是到网格终点最近的节点。起始处的方格被加到一系列已经被测试过的方格中，它们不会被更新。程序继续运行，每个节点逐步找到到起始节点的最短路径，然后按它自己的路线到达最终节点。最后，当最终节点被选中时，最短的路径就已经确定了。每个节点都知道路径来时的节点，后续可以在后面计算出来。维基百科上有一个形象的图来说明这一点。（gif见附件）

　　　

　　我用C#实现了这个算法，我已经将其发布到GitHub，大家可以随意下载，或是在您的程序中使用它，如果你想的话甚至可以改进我的算法。实现它的关键就是实现TilePathfinder 接口。每一个节点，或是在我的例子中中，方格，要提供周围的一系列方格和heuristic函数。