A*算法求解最短路径[代码下载][讨论]

问关于A*算法的问题，目的可能是写一个搜索最短路径的程序。这个在鼠标控制精灵运动的游戏中（不算智冠公司出的那些用鼠标充当键盘方向键的弱智RPG）大量使用，尤其是即时战略类的。但是我个人认为A*算法只适合处理静态路径求解，对即时战略游戏中大量对象堵塞过道时，疏通交通很难实现（也不是不能实现，这需要一个相当好的估价函数，且不能一次搜索路径）。
　　我奇怪的是，A*算法应该是算法课的基础知识了，任何一个系统学习过算法的人都应该了解，本不应该我在这里乱写一通，大家随意翻本将计算机算法的书，就应该看的到。（讲AI的书了更是少不了）不过既然许多朋友问起，在各个讨论组，BBS等地方也屡次见人提到，特花一下午时间完成本文和附带的程序，满足我们广大爱好者的求知欲，专业人士免看，以免班门弄斧。不过如有错误一定指出哟。
　　在介绍A*算法前，先提一下广度优先搜索，广度优先搜索就是每次将当前状态可能发展的策略逐层展开，比如一个地图中，对象允许向四个方向移动。那么，就将地点处，对象向上下左右各移动一步，将四个状态都保存在内存中，然后再从这四个出发点向各自的四个方向再移动一步...（当然这里可以剔除不合理的移动方法。比如不准向回移动）实际上，整个搜索好似一个圆形向外展开，直到到达目的地，很明显这样求解一定能找到最优解，但节点展开的数量是和距离成级数增加的。
　　而A*算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数评估每次的的决策的价值，决定先尝试哪一种方案。这样可以极大的优化普通的广度优先搜索。一般来说，从出发点（A）到目的地（B）的最短距离是固定的，我们可以写一个函数judge()估计A到B的最短距离，如果程序已经尝试着从出发点（A）沿着某条路线移动到了C点，那么我们认为这个方案的AB间的估计距离为A到C实际已经行走了的距离H加上用judge()估计出的C到B的距离。如此，无论我们的程序搜索展开到哪一步，都会算出一个评估值，每一次决策后，将评估值和等待处理的方案一起排序，然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步，一直循环到对象移动到目的地，或所有方案都尝试过却没有找到一条通向目的地的路径则结束（通常在游戏里还要设置超时控制的代码，当内存消耗过大或用时过久就退出搜索）。
　　完了？没有。怎么写这个算法中的估价函数非常的重要，如何保证一定能找到最短路径呢？充要条件是，你的估价函数算出的两点间的距离必须小于等于实际距离。这个可以从数学上严格证明，有兴趣可以自己去查阅相关资料。如果你的估价函数不满足这点，就只能叫做A算法，并不能保证最后的结果是最优的，但它可能速度非常的快。但无疑，满足那个条件的A*算法中，估计值越接近真实值的估价函数就做的越好，下面给出的程序，我只使用了一个相当简单的估价函数：求出两点中，若无障碍物的情况下的最短路径。如果您想写出快速的寻路算法，请自己寻找好的估价函数吧。
　　下面附的程序我已经花时间注释过了，并且调试通过。
代码：
<a href="attachment/2003111412412225546.rar">2003111412412225546.rar</a>

好,谢谢

顶

以下是引用mycug在2003-12-29 17:50:39的发言：
你测试过这个算法吗

附的程序我已经花时间注释过了，并且调试通过。

呵呵,不知道好不好啊.

xie

下载学习看看~

<P>学习一下。</P><img src="images/post/smile/dvbbs/em02.gif" />

<img src="images/post/smile/dvbbs/em01.gif" /><img src="images/post/smile/dvbbs/em02.gif" /><img src="images/post/smile/dvbbs/em04.gif" />