文章目錄

• 錯誤描述
• • 錯誤分析
  • 效率
• 找到的正確的代碼
• 個人維護的Astar倉庫

---

看懂本文的前提是了解清楚A星算法的原理

推薦這篇 A星算法詳解(個人認為最詳細,最通俗易懂的一個版本)

---

錯誤描述

項目里的尋路算法是主程(已經走了)從網上直接copy下來用的
簡單測試了下，以80*80的地圖為例，發現從(0,0)到((30,30)之間隨便找個起點，到終點(length-1,length-1)的路徑全都尋不到

排查到問題之后挺無語，百度搜到的Java實現的Astar算法都一模一樣，計算出的曼哈頓值都沒乘代價10就直接當做H使用，不止有很多路尋不到，并且還會產生大量(非常大量)多余的消耗 (斷點分析時發現有異常大量的結點被加入到closeList，地圖越大越多、消耗越大）。稍后會分析錯誤是如何產生的

2021.07.28 補充
通過查詢到的錯誤資料的時間推斷，大概率認為是各路"神仙"從這個github復制的代碼：倉庫鏈接
經過和作者溝通，確定了是有錯誤的。相關issues：issue#1、issue#3
我也創建了一個倉庫對該實現進行了bug修復、效率優化并進行以后的維護：倉庫鏈接

貼幾個無腦復制的錯誤示例，目的是讓大家找資料的時候不要拿來就用

錯誤分析

簡單舉個例子，當曼哈頓值不乘代價直接作為H值來用時，造成最直接的問題就是 會取到錯誤的最優點

假設在12*12的無障礙物地圖中，從(4,4)尋路到(11,11) (4,4)周圍的八個格子中，理論上最優點(F值最小的點)應該是(5,5) 而實際在這個錯誤的算法中最優點會變成(4,5) 因為曼哈頓值不乘10(DIRECT_VALUE橫豎移動代價)而直接作為H使用，是這樣的：(4,5)的G=10,H=13;(5,5)的G=14,H=12;明顯10+13 < 14+12 乘上DIRECT_VALUE再看：(4,5)的G=10,H=130;(5,5)的G=14,H=120;明顯10+130 > 14+120

在整個算法過程中，這會導致有非常多錯誤的最優點，產生大量沒用的分析計算，資源浪費非常嚴重，并且經常尋不到路

效率

下面對比一下錯誤代碼和進行修復之后的代碼(具體實現思路都一樣，進行了修復和效率優化)
差距非常懸殊 (再次吐槽無腦復制)

消耗大的是網上錯誤的代碼(曼哈頓值直接作為H使用)，不僅非常慢，還會有很多點尋不到

消耗小的是正確的代碼(曼哈頓值乘代價(10)作為H)

找到的正確的代碼

百度篩選截止到16年的博文，基本都是正確的實現
如 A*算法的java實現

個人維護的Astar倉庫

github：wushu037/java-astar
對原有實現進行了bug修復、效率優化，添加了尋路用例、路徑地圖打印

---

😁歡迎加入QQ群交流： [游戲-Web-開發技術棧 ??] ‘300567032’
點擊下方圖標一鍵加入！

---

總結

以上是生活随笔為你收集整理的Astar算法的Java实现 (其他很多都是错的，没有计入曼哈顿值的代价)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。