沒有對角線移動

我目前正在試圖實現在C++中使用A * A *尋路：http://www.policyalmanac.org/games/aStarTutorial.htm 沒有對角線移動

不過，對於第一個版本，我決定不包括對角線移動。

在C點的總結部分，在那裏它循環檢查當前點的鄰居：

for each neighbour of the current square (above, below, left, right) 
    if neighbour on closed list or not walkable { 
     continue 
    } 

    if neighbour not in open list { 
     add to open list 
     set parent of neighbour to current square 
     update F, G, H values 
    } else if neighbour is on open list { 
     check to see if this path to that square is better, 
     using G cost as the measure. A lower G cost means that this is a better path. 
     If so, change the parent of the square to the current square, 
     and recalculate the G and F scores of the square. 
    }

如果我只允許4方向的運動，我仍然需要檢查G值，看是否該廣場的路徑更好？例如，從起點開始，起點的所有4個鄰居將具有相同的g。

來源

2016-12-05 PrimateJunkie

如果我沒有記錯，所有的直接鄰居都有相同的g成本，但是如果你的目標位於你所在位置的西北斜向，那麼從西或北鄰居開始的路徑的g成本將低於g成本如果你是從東方或南方鄰居開始的話。 – mrogers

@NicoSchertler那麼我應該檢查具有最低g成本的鄰居嗎？然後將該平方的父元素設置爲當前平方並重新更新值？ – PrimateJunkie

A *算法的步驟不會根據集合中的項目數量（當前單元格的鄰居）而改變。你甚至可以在地圖上有鄰居清除的蟲洞/傳送器（除了相鄰的單元格外），A *仍然可以工作。 –

檢查較低G成本的重點是爲該方塊設置一條新路徑，前提是找到更好的路徑。您最初可能會找到從A到C的路徑，但稍後搜索時，您會發現到C的鄰居的不同路徑。如果C不在封閉列表中，則新路徑C的G成本可能會低於第一個，所以你想用更好的G（因此F）值來更新C.

來源

2016-12-05 19:16:20 aah

這是我陷入困境的地方。因此，在查看每個鄰居時，我應該檢查一下，看看該鄰居是否具有比該節點的父節點+鄰居與父節點之間的距離更低的g成本？@aah – PrimateJunkie

如果一個鄰居在打開的列表中，但沒有關閉的列表，這意味着它有一個以前的父母。因此，您正在計算基於新父母的G成本，並將其與舊父母的G成本進行比較，並使用兩者中的較小者。您不會將父母的G成本與鄰居進行比較。 – aah

@PrimateJunkie爲了說明，將鄰居相對於舊父代的G代價與鄰居相對於新父代的G代價進行比較。因此，如果相鄰方塊之間的權重爲W（*，*），並且舊父項爲P1，新項爲P2，則比較G（P1）+ W（P1，C）與G（P2）+ W P2，C），其中C是鄰居平方。 – aah

我們來分析一下情況。基本點是圖中的每個邊都具有相同的權重。

假設您目前在頂點c並且分析了鄰居n。那麼鄰居n的更新距離將是distance(c) + w，其中w是統一的邊緣長度。現在的問題是如果n可以有比通過不同的路徑更大的距離。

假設以前的父母p爲n這將導致更長的路徑。那麼，n的距離是distance(p) + w。爲了該表達式比從c更新的成本較大，下面需要持有：

distance(p) + w > distance(c) + w 
distance(p) > distance(c)

所以p將不得不遠離開始比c。如果你使用Dijkstra算法，這是不可能的，因爲這意味着p將在c之後被修復。但是你使用A *並用啓發式確定順序。因此，以下兩個條件需要保留：

distance(p) > distance(c) 
distance(p) + heuristic(p) <= distance(c) + heuristic(c) 
<=> heuristic(p) <= heuristic(c) - (distance(p) - distance(c))

所以它歸結爲您的啓發式。廣泛使用的曼哈頓距離啓發式允許這樣做。所以如果你使用這種啓發式，你必須檢查一個更低的成本。如果你的啓發式不允許上述條件（例如Dijkstra案例中的恆定啓發式），那麼你就不會。

來源

2016-12-05 19:28:33

沒有對角線移動

回答

相關問題