浅谈A*算法的一个C#实现

当然，主要参考的算法文档是“http://www.vckbase.com/document/viewdoc/?id=1422”不过这里并没有给出实际的源代码。而搜了一下A*算法的代码，大都是ActionScript的源码。毕竟用Flash做一个Demo会方便很多。不过既然都打开了VisualStudio，那么就用写一个C#实现吧。

A*算法最主要的是对路径的评分函数。而实际应用时，这个函数的设计会产生不同的结果。从上面的文档中我们可以很容易地了解到评分F的公式：

F = H + G

当然根据文中提到的简便方法，我们可以对H和G的计算写出下面的代码。

PathNode这个类实现了IComparable接口，目的是为了对PathNode列表进行排序。还记得上面提到的文章中的一句话吗“寻找开启列表中F值最低的格子。我们称它为当前格。”没错，这就是为这个条件做的准备。对于寻找F值最低的“格子”，把开启列表一排序就OK了。

在实现实际的算法时，还需要准备3个容器对象：

没写什么注释，但思路就是上文中的“A*方法总结”。在此就不重新粘贴一遍了。在此需要多铝骄涞氖牵乇樟斜碛昧艘桓Dictionary，其实关闭列表的目的就是查找下一个点是否在关闭列表当中，用Dictionary的ContainsKey方法比较容易，毕竟在Hashtable中找个Key总比在List中找个元素要快。

为了简化C#实现算法，这里只是遍历了当前点的上下左右4个相邻点。上文中介绍的是遍历8个点的情况，不过这也不是很复杂，只不过麻烦点在于G这个方法，需要判断一下是不是斜向走的。另外对4个相邻点的遍历，方法来源于之前看的一段AS代码，它用了一个偏移量数组来保存8个偏移量。而这里只是保存了4个偏移量。在实际的算法中，循环一下偏移量数组就很方便了（之前见过一个代码并没有用这个方法，而是复制了8短类似的函数调用代码，逻辑上就不如这个看的清晰）。delta数组如下：

另一个C#实现过程中需要注意的地方是如果4个偏移后的新点包含在开启列表中，那么应该是对开启列表中对应的PathNode的G值进行更新。如果是重新new一个新的PathNode，然后再加入开启列表，那么算法就会出现问题，有可能会陷入无限循环。