瞭解Astar算法實現

Question

從這個鏈接：http://www.policyalmanac.org/games/aStarTutorial.htm

如果相鄰的廣場已經開放列表中，選中這條道路是否 到廣場是一個更好的。換句話說，如果我們使用當前的方塊 到達那裏，如果該方塊的G分數較低，請查看 。否則，不要做任何事情。

實施例：

父（已經遍歷）：o
分支：A，B，C

父（工作）：甲
分行：B，d

打開清單包含A，B，C和現在D.

現在，上面引用中的大膽陳述是比較哪條路徑，路徑A到B？ 即 A的比較到B & & Ò到B OR A的 比較到B & & A至d

請澄清。

Answer 1

基本A *是：

While we're not close enough to the/a destination 
    Take the point that we have now, with the lowest expected total cost (so known cost up to this point plus estimated remaining cost). 
    Calculate cost for all surrounding locations & add them back to the priority queue with their expected total cost. 

return route that we followed to the closest point 

在正式A *的術語，G-比分是到那裏的成本。 H分數是從那裏到你想去的地方的估算值。

極端情況是，如果你的H分總是高估;新的分數（估計值+新的成本）將總是低於先前的平方的估計值+成本，因此您將直接到達目標。如果你的H分總是低估（或者是0或者其他），你總是會選擇離你的出發點更近的方格，因爲他們到目前爲止成本更低，所以你基本上會從那個位置進行填充。

您可以從理論的角度或從實際的角度使用A *。從理論上講，你可能永遠不會高估任何鏈接的成本。這意味着您將始終找到最有效的路線，但需要更長時間才能找到它，因爲您將擴展更多節點。

從實際的角度來看，使用它可以允許稍微不允許的啓發式（可以稍微高估）。你發現的路線很可能會稍微不理想，但對於遊戲使用來說不應該太糟糕。雖然計算速度更快，因爲你不再擴展一切。我所做的一個（緩慢的）實現花了6分鐘在1k * 1k的地圖上進行，並且使用了常規的觸發距離啓發式算法，但是隻有幾秒鐘的時間增加了3次。這些路線並沒有太大的差別。使啓發式時間5使得路線基本上仍然更快，但無法如此。

WRT你的直接問題： 這是你評估的第二個平方。你有從O到A，B，C規劃的道路（每條路線的給定成本G）。現在，假設從O到A到B的高速公路，而不是從O到B的土路。這意味着通過A的速度更快。擴展時，它會查看所有周圍的正方形，並將開銷列表的成本+啓發式添加到已打開的列表中。如果它在那裏，它會看到新的路線是否更快（降低到達那個方格），只有這樣，它才能取代它。

因此，在您的示例中，它將O> A-> D添加到列表中，然後檢查O> A-> B是否比O-> B更快。

- 補遺

打開清單：2/A（通過O），5/B（通過O），7/C（通過O）

封閉列表：0/O（原點/通過無）

拿A，因爲它是目前爲止成本最低的。然後，A的每個鄰居計算到達那裏的成本。

• 如果已經有一個條目，並且成本比我們目前知道的要低，請替換條目。
• 如果沒有當前條目，請添加它。

在A上工作，成本爲2到B，3到D的道路。通過A前往B，成本爲4，當前入口爲5，因此我們將其替換。 D不在那裏，所以我們添加它。

打開清單：4/B（通過A），5/d（通過A），7/C（通過O）

封閉列表：0/O（原點/通過任何操作），2/A （通過O）

所以我們比較了A到B對O2至B.

Answer 2

那麼，如果我們是在節點A的工作，我們正在考慮它的鄰居。假設我們現在正在考慮B節點（它在openList中）。

給出的定義告訴我們比較B的G值（當工作節點爲O時，它首次添加到打開列表時的先前計算值）和從開始（O）到達A的成本總和從A到達B的費用。