通過沒有障礙的迷宮路徑搜尋
假設我們有以下 4 乘 4 格：
讓我們假設這是一個迷宮。但是，沒有牆壁/障礙物。我們只有一個起點（綠色方塊）和一個終點（紅色方塊）。我們還假設為了從綠色變為紅色，我們不能對角移動。所以，從綠色方塊開始，讓我們看看我們可以移動到哪個方塊，然後用藍色突出顯示它們：
為了選擇移動到下一個方格，我們需要考慮 2 個啟發式：
g值 - 這個節點離綠色方塊有多遠。h值 - 這是該節點離紅色方塊的距離。f值 - 這是g值和h值的總和。這是告訴我們要移動到哪個節點的最終數字。
為了計算這些啟發式演算法，我們將使用這個公式：distance = abs(from.x - to.x) + abs(from.y - to.y)
這被稱為 曼哈頓距離 公式。
讓我們計算綠色方塊左邊的藍色方塊的 g 值：abs(3 - 2) + abs(2 - 2) = 1
大！ 我們得到了價值：1。現在，讓我們嘗試計算 h 值：abs(2 - 0) + abs(2 - 0) = 4
完善。現在，讓我們得到 f 值：1 + 4 = 5
因此，該節點的最終值為 5。
讓我們對所有其他藍色方塊做同樣的事情。每個正方形中心的大數字是 f 值，而左上角的數字是 g 值，右上角的數字是 h 值：
我們計算了所有藍色節點的 g，h 和 f 值。現在，我們選哪個？
無論哪個具有最低的 f 值。
但是，在這種情況下，我們有 2 個具有相同 f 值的節點，5。我們如何在它們之間進行選擇？
簡單地說，要麼隨機選擇一個，要麼設定優先順序。我通常喜歡這樣的優先順序：“右>上>下>左”
其中一個 f 值為 5 的節點將我們帶入向下方向，另一個帶我們向左。由於 Down 的優先順序高於 Left，因此我們選擇了 Down 的方塊。
我現在標記我們計算啟發式的節點，但沒有移動到橙色，我們選擇的節點為青色：
好的，現在讓我們為青色節點周圍的節點計算相同的啟發式：
同樣，我們選擇從青色節點向下的節點，因為所有選項都具有相同的 f 值：
讓我們計算青色節點唯一的鄰居的啟發式：
好吧，因為我們將遵循我們一直遵循的相同模式：
再一次，讓我們計算節點鄰居的啟發式：
我們搬到那裡：
最後，我們可以看到我們旁邊有一個勝利的廣場，所以我們搬到那裡，我們就完成了。