A*初探 （三） 开放列表最佳拍档--Binary Heap
摘要: 对于开放列表的维护方案来说，前面我说的，都是一些小花样了，在一些很小的地图上用他们并没有什么太大的问题，但是如果地图很大，需要搜寻的格子很多，那么开放列表里的元素必然会很多，那么我们是否可以用另外一种思维来考虑一下开放列表的维护工作？
其实我们每次从开放列表里面取值，每次只需要取里面所有元素的最小值就行了，而前面所说的两种方案都有自己的优点，第一种不需要对开放列表做排序，但每次找起最小值来实在消耗很大，第2种在找最小值的时候只需取第一个元素就行，而麻烦在于需要一直维持开放列表里面所有元素的有序排列，那么我们是不是可以把这两种方法的优点都结合起来呢
阅读全文
posted @
2008-03-11 11:48 火夜风舞 阅读(3126) |
评论 (0) 编辑
A*初探 （二） 针对开放列表的优化
摘要: 大家都知道，对于A*算法，围绕着开放列表的操作是很多的，开始的时候需要把当前处理点的周围8个点里，除了障碍点，已在开放列表里和关闭列表的点以外的其他点，计算G,F值以后都放进开放列表里，如果已经在开启列表里的，还得对它进行一次G值的重检测，从开放列表里每次要找出新的F值最低的点作为当前要处理的点，并且要把他从开放列表里面删除，所以，对于开放列表的操作的速度，是影响A*寻路速度的第一个关卡
阅读全文
posted @
2008-03-10 15:49 火夜风舞 阅读(1738) |
评论 (4) 编辑
A*初探 （一）
摘要: 很早以前就在Gameres上学习过了A*的原理，但那时候也仅仅是看了遍原理，稍微了理解了下，当时虽然感觉A*并不复杂，但还是有几个关键点没能弄得清楚，比如更小G值的重新计算，趁着这几天工作清闲，正好把最原始的A*算法给写了一便
阅读全文
posted @
2008-03-06 23:13 火夜风舞 阅读(758) |
评论 (4) 编辑