C#开发WPF/Silverlight动画及游戏系列教程(Game Course)：(七)传说中的A*寻径算法

核心提示： 关于地图引擎方面的处理涉及到两个方面的知识： 1）地图的实现（包括地图的切割、合成、呈现方式等） 2）地图物件的实现（包括地图中实现寻路、遮罩、传送点等） 为了让大家能更加有兴趣深入后面的知识，我选择先从地图寻路开始讲解吧： 目前游戏中的寻路最经典的莫过于A*(A Star)寻路了，C#开发WPF/Silverlig

关于地图引擎方面的处理涉及到两个方面的知识：

1）地图的实现（包括地图的切割、合成、呈现方式等）

2）地图物件的实现（包括地图中实现寻路、遮罩、传送点等）

为了让大家能更加有兴趣深入后面的知识，我选择先从地图寻路开始讲解吧：

目前游戏中的寻路最经典的莫过于A*(A Star)寻路了，它是一种寻路思维的合集，那么基于它产生的算法则又有多种，例如曼哈顿启发式算法、对角线取径算法、欧几里德几何算法、最大取值算法等等，不同的算法产生的效果不同：如计算出路径需要的总时间，得到的路径长短优劣等，并且参数的不同也将导致结果的大异。我借助国外一位牛人的A*寻径工具(有兴趣的朋友可以在http://www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527/中找到相关资源)，分别通过对各种路径使用各种A*算法来寻径，最终通过花费时间和路径的优美性进行了横向与纵向的比较评分，得出速度最快的算法：曼哈顿启发式算法。它在所有的包括就算九曲十八弯的复杂路径计算中均能表现极其优异的速率，下图为测试的部分截图：

图片看不清楚？请点击这里查看原图（大图）。

图中棕色格子代表障碍物，起点位于左上角，终点在中间的红色边框格子，蓝色格子代表找到的路径。从图中右下角可以看到，就算如此复杂的充满分支的迷宫中仍可以在3毫秒中找到最佳路径，这是极其优异的。那么很多朋友看到这可能会感觉如此复杂的程序，哪是一般人能写出来的？其实说难还是有一些难度的，但是幸运的是，我们的同胞已经将一篇入门文章翻译出来了，我看了一下很不错，该翻译文章地址如下（看该文章请有耐心不长不短，但是看完以后将有非常大的收获！）：http://data.gameres.com/message.asp?TopicID=25439，那么我们该如何通过C#代码来实现曼哈顿A*呢？我抛砖引玉简单原理描述一下：从起点开始发散式的寻找周围8个点，通过各种条件筛选出最优的那个点，然后将此点再作为起点继续循环以上过程，最后我们得到的所有起点集合即为最终路径。是不是觉得不太难了？呵呵，那么大家动手写写吧！(大家完全可以参考我给大家的那位外国牛人写的程序，里面有源码，通过参考源码，相信大家花些时间完全可以轻易的实现自己的A*)