【正文】 Help(Help, 39。) 。 13 for(SubMenusubMenu : ()){ if(()==this){ (subMenu)。 subMenus = (subMenus)。 } } 他有三個主菜單組成使用， getSubMenus()方法得到下層的菜單。 clearPath()清理路徑 clearMap()清理障礙物，起原理同上個函數(shù) 按鈕代碼 存在三個 按鈕 JButtonstartButton = new JButton(Start)。 JButtondrawButton = new JButton(ClearMap)。 ()。 i 。 j drawData[i].length。 14 } } rebuildAstarMap()。 這里計算的算法結(jié)束的當(dāng)前的時間減去開始記錄下的時間 updateCostTimeMillis(() start)。 public ListAStarNode find() { init()。 while(!isEnd() amp。 !isFind()){ current = getMinFNodeFromOpenList()。 isFind = true。 for(AStarNode neighbor : getNeighbor(current)){ if(neighbor==null || isInCloseMap(neighbor) || isCanNotGo(current, neighbor)) continue。 AStarNodenodeFromOpenList = getNodeFromOpenList(neighbor)。 基于 A*算法的路徑尋找 isBetter = tg() ? false : true。 } if(isBetter){ (current, target)。 } 上述算法一開始將圖初始化，并且判定時候已經(jīng)找到路徑或者已經(jīng)到達(dá)了終點，如果不是則開 始尋找，尋找最初，將判斷，這個節(jié)點是否有相鄰的節(jié)點，相鄰的節(jié)點時候已經(jīng)搜索到，相鄰節(jié)點是否在已有路徑中。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。 基于 A*算法的路徑尋找 do{ (0, current)。 }while(current!=null)。并且這樣的設(shè)計也易于路徑的保存，方便了試驗相互之間的比較。 floatminF = (index).getF()。 for(int i=1。 i++){ AStarNodeaStarNode = (i)。 index = i。 在上面的介紹中其實已經(jīng)可以看出在這個算法中起到最重要的作用其實是節(jié)點及其周邊環(huán)境。 節(jié)點判斷函數(shù)及屬性函數(shù)的設(shè)計 實現(xiàn)的路徑總體的策略（即以上的代碼） 則是實現(xiàn)路勁上每一個點的判斷和下一個節(jié)點選擇的事宜。 = heuristicCostEstimate(this, target)。 } 此函數(shù)的作用就是判斷這個子節(jié)點是否能稱為最優(yōu)路徑的下一個節(jié)點的函數(shù)。 對角的平方差來計算他的值，值越小就意味著他離他的父節(jié)點就越近。 基于 A*算法的路徑尋找 intoffsety = 。 if(offsetX==0 amp。offsety==1) distinct = G_1。amp。 elseif(offsetX==1 amp。offsety==0) distinct = G_3。 privatefinalstaticintG_2 = 14。 privatefinalstaticintG_4 = 14。 一個方塊各個角上的值都是最大的，邊上的值則比他小一點。amp。 這個就相當(dāng)于（ 0， 1）的坐標(biāo) thrownewAStarPositionException(Unvalid relation between current node(+this+) and fater node(+father+))。 } 為了保證不會出現(xiàn)局部最優(yōu)的情況，他將調(diào)用下一函數(shù)再次計算是否存在一個更好的節(jié)點： publicvoidreCalculatorGAndH(AStarNode father, AStarNode target) { = distinctG(father)。 = g+h。 } 以上就是程序一個基本的算法的實現(xiàn)。 18當(dāng)點擊各個按鈕將會觸發(fā)各個函數(shù)。 Swing 是 JAVA基礎(chǔ)類 的一部分。 SWING 提供許多比 AWT 更好的屏幕顯示元素。 它們是 JFC 的一部分。這意味著你可以在任意平臺上使用 JAVA 支持的任意面板。 仿真實驗 及結(jié)果比較 g(n)的改變對結(jié)果的變化 基于 A*算法的路徑尋找 圖 第一次 運行的路徑圖 這是任意畫出的障礙物，灰色顯示的就是路徑中的障礙物。 在他一開始的時候他明顯是以對角線的方式進行著搜索，這是因為在 AStarNode。 privatefinalstaticintG_2 = 14。 privatefinalstaticintG_4 = 14。 privatefinalstaticintG_6 = 14。 privatefinalstaticintG_8 = 14。 因為我認(rèn)為起點和終點在對角線上那么他們之間的連線就應(yīng)該是最 短，因此對于一個存在的節(jié)點來說他對角線上的估價值的價值將會更高 基于 A*算法的路徑尋找 圖 改變了終點和 g(n)的結(jié)果 大部分我們改變 終點的位置之后，我們發(fā)現(xiàn)由于終點去了左下方一次一開始和結(jié)束的路徑變成了直線，這是在估價值沒有變的情況下的。但是可以看見 圖 局部效果 從這個位置開始路徑又變成了斜線。 基于 A*算法的路徑尋找 圖 改變重點位置后的路徑圖 圖 估價值改變后的路徑圖 以上兩張圖是為了比較估價值對尋找路徑所產(chǎn)生的影響。 基于 A*算法的路徑尋找 圖 A 采用的估價值形式為 privatefinalstaticintG_1 = 14。 privatefinalstaticintG_3 = 14。 privatefinalstaticintG_5 = 14。 privatefinalstaticintG_7 = 14。 privatestaticfinalintG_0 = 14。 有上面兩張圖可以看見他們選擇出來的路徑是一致的，這說明了路徑的選擇是依賴于障礙物的位置 ，他不依賴于估價值的大小。因此，可以得出一個結(jié)論估價值的設(shè)置將會對算法效率產(chǎn)生很大的影響。 privatefinalstaticintG_2 = 11。 基于 A*算法的路徑尋找 privatefinalstaticintG_4 = 11。 privatefinalstaticintG_6 = 11。 privatefinalstaticintG_8 = 11。 發(fā)現(xiàn)路徑?jīng)]有改變但是時間變成了 29 秒。 圖 估價值不變的位置變換后的結(jié)果 在估價值不變的情況下 對于同一張障礙物圖來說變換終點位置對算法的時間產(chǎn)生了變化幾乎發(fā)了一倍，這也同樣證明了他的智能性，不是機械的查找。 24更加證明了選出路徑只依賴于障礙物。 （ 2） 估價值對算法的效率產(chǎn)生一定的影響，從結(jié)果來看數(shù)值越大消耗的時間將會越大。這和算法的原理相符合。 曼哈頓距離依賴座標(biāo)系統(tǒng)的轉(zhuǎn)度，而非系統(tǒng)在座標(biāo)軸上的平移或映射。因此這種圓其實就是旋轉(zhuǎn)了 45 度的正方形。對一個半徑為 r 的圓來說，這個正方形的圓每邊長 √2r 。圓 的半徑 r對基于 A*算法的路徑尋找 切比雪夫距離（ L∞ 空間）的二維平面來說，也是一個對座標(biāo)軸來說邊長為 2r的正方形，因此二維切比雪夫距離可視為等同于旋轉(zhuǎn)且放大過的二維曼哈頓距離。 下面將會對估價函數(shù)最重要的 h(n)進行比較，此處的 h為 : return (( ) + ( ))*G_0。 當(dāng)采用同一個障礙物地圖時： 圖 基于曼哈頓距離的路徑圖 路徑產(chǎn)生一定的變化 ： 圖 局部效果圖 在轉(zhuǎn)角的附近節(jié)點更加曲折，而不是一開始貼邊繞過，在最后也是一條曲線而不是一開始的直線，這說明這個估價函數(shù)更加喜歡曲線的方式繞過尋求路徑。 26 . 圖 修改 后的 曼哈頓距離的路徑圖 這次得出的路徑更加的曲折不過更加接近于最好的路徑，但是他的耗時接近了 50秒，這有可能是因為他是對數(shù)計算因此耗時更高。 基于 A*算法的路徑尋找 圖 改變精度后的路徑圖 果然隨著精度的提高他的路徑更加 的圓潤了并且少了不必要的曲線，并且結(jié)束時是對角線，而不是以前的折線，更加節(jié)省了路徑。 （ 2） 基于 對角線距離 的改進 . 這個方法可以平衡 h（ n）和 g(n)之間的關(guān)系 ，可以 更加 充分的考慮到點之間關(guān)系。 xDistance=( )。 if (xDistanceyDistance) { float h。 return h*G_0。 h = 14*xDistance + 10*(yDistancexDistance)。 他會根據(jù)不同方向來調(diào)整 下 一個節(jié)點的位置。 28基于 對角線 的判斷方法更加適合這一情況。 return (float) (G_0*(()^2+()^2))。 29 （ 4） 基于 Breaking ties 的微調(diào)方案 在某些情況下，我們不希望算法的步數(shù)不超過某一個特定的值。 float dy1=()。 float dy2=39。 float h = 0。 return h。 基于 A*算法的路徑尋找 6 結(jié)束語 總結(jié) 從第五章的試驗可以看出 G（ n）函數(shù)將會根據(jù)障礙物的位置和父節(jié)點的位置調(diào)整他的子節(jié)點的位置， G(N)函數(shù)的定義將會影響到算法的效率，越是復(fù)雜的數(shù)據(jù)上的定義就會耗費跟多時間。并且在編程的過程中，這一個函數(shù) 的 數(shù)據(jù)類型也影響了 產(chǎn)生的路徑 的精度，在調(diào)整為 FLOAT 浮點數(shù)字后路徑看上去更加的圓潤了，但是同時也將耗時提高了上去。兩者相互的制約和選擇產(chǎn)生了最后的路徑。而且當(dāng)我們對于路徑提出更多要求的的時候，對于 h(n)就需要進行一定的改變，例如步數(shù)等等。在編寫過程也遇到很多問題，通過網(wǎng)上查找解決辦法，這也是一種很好的經(jīng)驗，這一實驗的操作下來還是比較順利的，并且在指導(dǎo)老師史小紅的指導(dǎo)下對論文結(jié)構(gòu)和寫法進行了改進，并且對算法也有了更深入的認(rèn)識。因此有可能被分配到不同的內(nèi)核上進行了處理。試圖將影響降到最低。 由于本人的能力值有限，這次試驗只是實驗 A*算法對其他的算法并沒有深入，希望以后有機會可以繼續(xù)研究，希望可以諒解。 31 3D Game RealTime Strategy with Depth DirectionA*Algorithm for MultiLayer,2020 [3] Hongxian Zhang,Research and Application for Combination between Copied Map and A* Algorithm in 2D Game,2020 [4] Alex Kring, Alex J. Champandard, and Nick Samarin, DHPA* and SHPA*: Efficient HierarchicalPathfinding in Dynamic and StaticGame Worlds,2020 [5] Gee ,ALGORITHMS IN A NUTSHELL,東南大學(xué)出版社， 2020 [6] Patrick Lester， Heuristics and A* Pathfinding， ， 2004 基于 A*算法的路徑尋找 發(fā)表學(xué)術(shù)論文情況 基于 A*算法的路徑尋找 致 謝 在這個最后大學(xué)時光，首先感謝我的指導(dǎo)老師史小宏老師，沒有你的督促和批評指正。感謝老師對我題目和論文各個地方的指導(dǎo)與幫助。不知道以后還有沒有機會在這樣的聊天和吃飯。感謝網(wǎng)上無私奉獻(xiàn)的人民，沒有你們的幫助，編程中遇到的很多問題也無法 圓滿的解決。感謝你們讓我知道了自己的渺小，指引了我的