梦里千寻

这两天对智能寻路算法比较感兴趣

去搜了搜,都说A星算法是最完美的…那好吧..我就研究研究A星….

个人理解A星算法的核心思想就是评估当前点附近可以移动的点到终点的移动代价
然后选择代价更低的点作为当前点

如此循环,直到到达终点或者没有可移动的点

理解A星算法的时候是没有问题的,但是如何建立数据结构和地图模型却耗费了我不少时间
最后选择的方法是创建一个了一个包含父坐标,G/H/F值的结构体,然后用这个结构体创建了一个和地图大小等同的二维数组
这样的好处就是每个坐标的坐标位置也是它在数组中的位置,这样就方便很多…

在建立数据结构之前最好把算法吃透,这样才能保证数据结构的合理性…

像我上面的方法其实也有不合理的地方..每次寻找开放列表的时候要逐个判断一番
包括还没有进入开放列表的点,它也会进行最少一次判断,明显浪费了很多时间

现在特别大的地图还是很慢,正在研究如何使用二叉堆,据说提速效果很明显
如果将1000*1000的地图寻路速度保持在100MS以内,应该就可以满足应用要求了

放几张图…

另外附上源码……

注意,左键选择起点,右键选择终点

点我下载