这是一个演示寻径算法的程序平台,目前可演示寻径算法包括A*,A**,水波算法(水波算法和优化水波算法原理一样,只是数据结构不同而已),和双向水波算法。 \N
\N程序使用说明:
1,可以在"选择地图"菜单选择预设的地图。
2,如果想自己设定地图以供算法演示也可以按下"制作地图菜单"后,根据自己的需要制作地图(当你在地图上左键点击鼠标会修改点中的一格地图,当你单击然后拖曳鼠标就会一次改变4格地图,方便制作。)。
3,如需要改变搜索的始末点,请点击"设置起点和终点"菜单项(按键后第一次点击确定起点,用绿色小方块表示,第二次点击确定终点,用黄色小方块表示)。
4,如果制作好的地图有研究价值可以按下"保存制作的地图"菜单,那么地图就会以数组的形式被保存到执行文件同一目录下的一个名叫SaveMap的txt文件里面。如果你要重新对该地图进行操作,只要选择"读取保存的地图"菜单的子菜单项就可以了。
5,地图准备好,始末点准备好之后,就可以从"选择算法"菜单项的子菜单中选择算法进行搜索了,搜索结束后默认会以一条蓝色的线表示搜索到的路径。同时用信息框显示出搜索时间。(以毫秒为单位,包括创建对象所用的时间)
6,搜索结束后可以从"显示方式"菜单栏的子菜单中选择显示方式,包括"只显示搜索过的路径","显示搜索过的节点",和"用渐变色显示搜索过的节点"(同一色阶表示到起点的路程相同)。
7,演示功能,另外为了更好地研究搜索路径的过程,我添加了演示功能,当你选择好地图后选择"算法演示"菜单项的子菜单-选择将要演示的算法,那么程序就会以彩色一步一步地描绘该算法目前搜索过的点(同上面一样,以红橙黄绿青蓝紫的顺序来表示到起点距离的长度,同一色阶的点到起点的距离相等)。这功能使到更直接地了解算法(比如水波你会看到搜索的点就像水波那样扩散开去;如果用A*你会直观地观察到它总是先搜索最可能是最短路径的那些点(估值最高的点)),不过就要你等代一些时间(一旦开始演示就不能中途停止...)。
(另注:A*算法演示的时候所显示的彩色不表示它到起点的距离,而是表示估值大小。另外目前所有算法所找到的路径都是最短路径。)
\N 开发这个平台的目的是更好地研究寻径算法(我觉得这方面的源代码比较缺乏,使到我们对寻径算法的深入研究受阻,我记得当初我研究A*算法的时候,四处找源代码,结果还是找不到一些注释结构清晰的源代码,这使我只能从某些文献中文字上去了解A*算法,所以这个平台上的A*算法完全是我自己按照A*的思想编写出来的,由于数据结构用得不好,使得速度有很大的限制,希望有朋友能提供更好的实现方法。)。当然寻径算法远不止这些,将要添加上去的算法是遗传算法,对寻径算法感兴趣的朋友也可以把自己的算法给我让我添加上去以做比较研究(哪怕是已有的算法,因为实现方法不同,数据结构不同,运行效果可能会出现很大的差异)对于本软件的bug和一些不完善的地方也欢迎批评指出,欢迎大家一起学习交流!
另外,这是一个公开源代码的软件,希望使用者尊重作者劳动成果(水波算法原创,A**由天地之灵原创),如果需要用到里面的代码请与作者商议,只有形成这样的共识后,才能让更多的高手公开自己的代码,让大家共同研究共同进步。
作者:华南理工 张颖鹏
联系方式:
QQ: 382839044
\N
来源:http://bbs.gameres.com/showforum.asp?forumid=1