A *尋路，計算G成本

Question

我在理解如何持續計算實施A *尋道的正確G成本方面存在一些困難。據我瞭解，這是從起始節點轉移到當前節點的成本，但我不完全理解的是如何找到用於增加G成本的值。我見過使用像10和14這樣的數字的例子，但是這些是任意的，它取決於實現嗎？

當我開發2D遊戲時，似乎我幾乎不得不爲G代價找到一個「甜蜜點」（我應該注意的是，它似乎接近正在使用的地磚的寬度）節點）之前，我一直找到最短的路徑。

任何有關此事的澄清將是偉大的。

Answer 1

您可以定義它們。當你「走了一步」時，添加到G的數量是你如何告訴算法你真的喜歡什麼樣的路徑（H只是一個可容許的近似值，可以對一堆G增量進行求和，這有助於它更快地找到你想要的東西）。使用10和14是1和sqrt（2）的近似值，有點類似於如果有歐幾里得距離會發生什麼，但是在每一步都被約束到摩爾鄰域，有時這稱爲「對角距離」或「可視距離「（儘管更準確地說，該術語是用於使用準確的sqrt（2））。因此，這種選擇並不完全是從哪裏來的。

但是你的，選擇不同的成本，使得A *喜歡，如果你做的對角成本一樣的「直」的成本（或「不喜歡」）某些路徑，例如，它真的會像對角線移動一樣，它不一定避免來回曲折（只要曲折走向正確，這將是自由的，例如路徑/\的長度將與--的長度相同）。使用高對角線成本（> 2）將使其找到大部分看起來像您使用馮諾依曼鄰域的路徑，除了在「緊急情況」中它仍然能夠沿對角線移動。在1到2之間，差別不那麼明顯，但有時會出現在障礙物周圍。因此，使用低於sqrt（2）的對角線成本傾向於製造不必要的曲折形式的「奇怪」路徑，使用高於sqrt（2）的對角線成本傾向於使不能採用對角捷徑的「啞」路徑。但是你可能會想要這樣做，特別是如果它符合「實際成本」（如果有的話），比如單位或類似的步行時間。然後，在我自己的一場比賽中，我有意使對角線成本高於基於步行時間的對角線成本，以使路徑看起來更自然（否則它太曲折了）。

黃色的 「探索」。由於實現細節，底層路徑繞對角線成本10（它從NW開始順時針添加節點，並且使用穩定的插入到open而不是像堆這樣聰明的東西，因此具有等於F的節點是打結的，其上得到添加第一）。