A *尋找快速技工

Question

如果我有一個可以在四個方向上移動的2D環境，但除了這些方向之外，我還可以沿着一個方向衝向一個方向，直到我撞到牆上，我將如何計算可接受的啓發式爲了這？無論是移動還是短跑，每個人的G成本都是1，所以衝刺和步行的權重是平等的。我應該甚至使用A *嗎？如果在某些情況下，多次衝刺會使您到達目的地的速度比移動速度快，即使在衝刺之後您離目的地更遠的地方，什麼樣的尋路能夠計算最佳路徑？

Answer 1

啓發式：啓發式可接受，如果它永遠不會高估達到目標的成本。既然你使用了四個基本方向，那麼一個可接受的啓發式就是從開始到目的地之間的曼哈頓距離（L1-Norm），稱之爲dist。然後將dist除以單個破折號中的圖塊數量。你不會高估使用這種啓發式方法。

計算最佳路徑：您可以使用A-Star來計算最佳路徑，前提是您使用可接受的啓發式。關鍵是你的node.getNeighbors()方法返回與當前節點相鄰的鄰居，即返回（N），（S）outh，（E）ast和（W）est，以及那些可以從一個破折號開始的鄰居當前節點（即dashDist-N/S/E/W）。該方法可能是這個樣子：

public List<Node> getNeighbors(){ 
    List<Node> neighbors = new LinkedList<Node>(); 
    neighbors.addAll(this.getAdjacentNeighbors()); 
    neighbors.addAll(this.getDashableNeighbors()); 
    return neighbors; 
} 

private List<Node> getAdjacentNeighbors(){ 
    //implement code to get the adjacent neighbors 
} 

private List<Node> getDashableNeighbors(){ 
    //implement code to get the neighbors 1-dash away 
} 

另一個考慮：我認爲破折號發生在一條直線上......在這種情況下，我建議尋找到JumpPointSearch algorithm。它利用世界上的對稱性來減少開放集合中的節點數量。