C++新霖花园
3D园丁
posts - 7,comments - 14,trackbacks - 0
   很早以前就在Gameres上学习过了A*的原理,但那时候也仅仅是看了遍原理,稍微了理解了下,当时虽然感觉A*并不复杂,但还是有几个关键点没能弄得清楚,比如更小G值的重新计算,趁着这几天工作清闲,正好把最原始的A*算法给写了一便

   写A*原理的代码,自然最好得有一个直观的演示,A*走的是方格阵,GDI 的Setpixel函数正好可以满足我画方格的要求,利用最基本的VC8创建的一个小小的窗口,然后利用Setpixel在上面画障碍画寻找出来的路线,倒也是很合适

   创建的绘制区大小为400 * 400,也就是说一共有160000个象素点,其实仅仅演示初级的A*根本不需要这么大的区域,但是为了以后的优化代码能够显示出速度上的差异,我便故意用了这么大的绘制区

   基本的思想也相当简单,利用一个vector管理这160000个象素,也就是利用一维数组模拟二维数组的道理,然后单个vector元素里保存如下:win32的POINT结构变量一个,用来存储绘制的点位置信息,枚举类型一个,用来表示当前的结构处于什么状态,指向本身结构的指针一个,用于指向父象素,整型index值,保存当前结构在16000个象素点的下标,G,H,F3个整型,(这3个整型用来干什么,我想知道A*的都一眼就看出了)

   具体怎么写的我也不多说了,相信大家不会比我陌生,大概花了2天多一点的上班时间(断断续续写的,期间还要处理其他工作上的事情),终于把最基本的A*算法给完成,利用最后找出来的路线点,能成功在客户区绘制出绕过障碍的A-B之间的最短路径了
 
  最基本的东西算是完成了,但是这也只是最基本的第一步,最重要的一点是什么呢?当然是优化,A*搜索对于非常多的方格的时候,时间上的消耗是非常大的,所以算法就这一个,而针对这个算法而产生的优化算法,网上真是数不胜数了,所以下面要做的一步重要工作,就是优化算法,提高搜索速度了,我事先准备好的160000个象素点,终于能够派上他的用场了

从点POINT(2,2)搜寻到POINT(398,398)



如果对A*寻路基础算法原理不清楚并且有兴趣的朋友,可以去gameres上看一下这篇文章
http://data.gameres.com/message.asp?TopicID=25439
posted on 2008-03-06 23:13 火夜风舞 阅读(757) 评论(4)  编辑 收藏 引用

FeedBack:
# re: A*初探 (一)
2008-05-27 09:01 | 陈海波
我是大四的毕业生,现在需要你的编好的东西交毕业设计.麻烦帮忙. 谢谢!  回复  更多评论
  
# re: A*初探 (一)
2008-05-27 09:02 | 陈海波
我的QQ:253115755
邮箱:anhuichenhaibo@sina.com 着急,谢谢了  回复  更多评论
  
# re: A*初探 (一)
2008-05-27 11:20 | aa
本专业没学好,连语文也没学好,悲哀啊。
应该风格一直,这样说:
“我是大四的毕业生,现在需要你的编好的东西交毕业设计,着急,限你2天内发到anhuichenhaibo@sina.com,请从速!”  回复  更多评论
  
# re: A*初探 (一)
2008-06-22 00:53 | 火夜风舞
晕,如果真的想要 到是可以给你去交毕业设计,这也不是什么很牛X的东西,只不过我到今天才看见这个,想必联系你也没什么用了 呵呵  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理