注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

眼睛想旅行

技术就是我的生命与信仰!

 
 
 

日志

 
 
关于我

精通C,C++,python,Erlang。并熟悉各种其他编程语言,用cocos2dx游戏引擎作过几个项目。会MySQL增删改查,了解OpenGL渲染原理。懂单片机,能设计数字电路系统,会画电路图和设计电路板。喜欢了解最新前沿技术,并持续关注和学习新技术。

网易考拉推荐

如何快速进行A* 寻路  

2014-10-21 20:41:55|  分类: C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
下班了,没有事情作,之前一个人作游戏的时候,因为压力很大,所以特别喜欢写博客,但自从上班之后,再写博客的动力几乎就没有了。这就是为什么,原来在手机游戏这一块有很多的高手,现在都不怎么在网上活动了的原因。
    今天来说一下我们作游戏时最常用的一种游戏地图中绕过障碍物的自动寻路算法吧。这个其实之前已经有很多的高人写过了,我只是把他们的文章进行了一下整理和总结罢了。
    今天的这个文章的基本思路是这样的,我会先介绍一下什么是A* 寻路,然后会说到A*寻路中为了提高寻路速度的最好排序算法--二叉堆排序。再接着会聊一下C++中的STL库中使用std::vector的二叉堆对一个结构体数据进行排序。因为STL中的排序用到的是STL中的比较用的是仿函数,所以要对结构体或者对象根据属性值来排序列就必须要对比较操作符">"或者"<"进行重载。
    好了,先说A*寻路,我就懒得写了,大家参考一下这个博文吧:http://blog.csdn.net/lufy_legend/article/details/5733733
    A*寻路的大体思路是,从起始点开始,一点一点的将要寻找的可能节点加入寻路开放数组中,而这个开放数组就要用到我们说的二叉堆排序。当然,也可以用快速排序。这样我们可以每一次都取出花费最少的节点,再最后,将找到的关闭节点,反向回来,就可以得到我们的A*寻路路径了。
    真的是懒得复制了,大家还是看别人讲的一个有关二叉堆排序列的博文吧:
   这个博文真的写的非常好。简单明了。我也就不多说了。
   然后就是关于使用STL中的二叉堆排序方法的四个函数了。参考下这个博文:
make_heap():建立二叉堆。
push_heap(): 给二叉堆中添加数据。
pop_heap():   删除二叉堆顶数据。
sort_heap():      排序列二叉堆。
大家参考一下,文作者也讲的很明白,只是关于比较操作符的重载写的太少了:
关于C++中的操作符重载,大家可以参考下下边的这个博客:
总的来说,A*寻路也就这样了。没有什么新的东西了。写一个模块可以终身受用了。这两天在弄一个关于六边形的瓦片地图的A*寻路,有很多的坐标变换,还是要下一翻功夫的。这可能就是为什么使用六边形的瓦片地图编辑器会比较少的原因吧。等下次我来分享一下六边形坐标变换上想的一些算法吧。
  评论这张
 
阅读(337)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017