A*初探 （三） 開放列表最佳拍檔--Binary Heap
摘要: 對于開放列表的維護方案來說，前面我說的，都是一些小花樣了，在一些很小的地圖上用他們并沒有什么太大的問題，但是如果地圖很大，需要搜尋的格子很多，那么開放列表里的元素必然會很多，那么我們是否可以用另外一種思維來考慮一下開放列表的維護工作？
其實我們每次從開放列表里面取值，每次只需要取里面所有元素的最小值就行了，而前面所說的兩種方案都有自己的優點，第一種不需要對開放列表做排序，但每次找起最小值來實在消耗很大，第2種在找最小值的時候只需取第一個元素就行，而麻煩在于需要一直維持開放列表里面所有元素的有序排列，那么我們是不是可以把這兩種方法的優點都結合起來呢
閱讀全文
posted @
2008-03-11 11:48 火夜風舞 閱讀(3155) |
評論 (0) 編輯
A*初探 （二） 針對開放列表的優化
摘要: 大家都知道，對于A*算法，圍繞著開放列表的操作是很多的，開始的時候需要把當前處理點的周圍8個點里，除了障礙點，已在開放列表里和關閉列表的點以外的其他點，計算G,F值以后都放進開放列表里，如果已經在開啟列表里的，還得對它進行一次G值的重檢測，從開放列表里每次要找出新的F值最低的點作為當前要處理的點，并且要把他從開放列表里面刪除，所以，對于開放列表的操作的速度，是影響A*尋路速度的第一個關卡
閱讀全文
posted @
2008-03-10 15:49 火夜風舞 閱讀(1773) |
評論 (4) 編輯
A*初探 （一）
摘要: 很早以前就在Gameres上學習過了A*的原理，但那時候也僅僅是看了遍原理，稍微了理解了下，當時雖然感覺A*并不復雜，但還是有幾個關鍵點沒能弄得清楚，比如更小G值的重新計算，趁著這幾天工作清閑，正好把最原始的A*算法給寫了一便
閱讀全文
posted @
2008-03-06 23:13 火夜風舞 閱讀(775) |
評論 (4) 編輯