[求助] A*寻路的优化(2010-10-01更新)

dbshy

高中时学的数据结构 N年过去了忘的差不多了
外行人提出几点看法：
我觉得A star最主要提高效率还是在于估价函数
最差的估价函数就会变成BFS ，不过在RM中没啥压力的 = =
另外这个要具体情况具体分析  
当然用二叉堆可以提高效率，对于RM来说就不重要了

我用站上的A star来做RTS  感觉还行
扯淡完毕 闪人

等待各位编程高手给出优化

猫哥哥

优化的方式几乎已经都被你想到了。

如果是要求特别高，在设计地图的时候就要考虑到尽量不要有死路，或者封闭的盲点。还可以考虑在地图数据里预设能被优先搜索到的主路径，然后只需求出对象到主路径和终点到主路径的路线，与主路径中的部分合成，减少搜索。
如果是多个对象同时寻同一个目的地（像星际争霸里的一队兵前往某个地点），可以采取跟随策略，减少搜索。

另外，H值*10的地方，把10改成大一些的数，在比较开阔的地图里也能加快速度。不过加得太大了，生成的路径形状可能会笔直到没有美感……

zhong

A *算法之前有花过一天时间去看过,我所知道的优化方法上面大概都被你罗列出来了,不过不知道那个切大格的具体实现方式和思路是怎么样的?貌似还可以对地图中一些不可能寻到路的区域(例如围墙围着的建筑之类的)做一些特殊处理,让程序不去傻傻的寻路,也是一种优化方法吧.好像通用性的A*算法可以优化空间也不是太大了,除了你说的那些,当然这只是个人浅见,我觉得要进一步优化的话,就要结合具体的地图设计和游戏的具体需求了.至于估值函数一直也是我比较好奇的东西,除了曼哈顿方法之外,在商业游戏的应用领域是怎么处理这个的...我个人比较不成熟的想法是 1.运用统计学的方法对游戏地图进行预处理,然后来算出一个大概的估值函数. 2.对于一些地图环境差异较大,采用各自合适的估值函数.  另: 楼上猫哥也是本人偶像之一,还有楼主也是:lol...

summer92

- -偷懒吗？有现成工具？