在二維數組中執行A *路徑查找

我正在製作2D瓦片地圖，現在我正在嘗試實施A *尋路。我正在關注the Wikipedia pseudocode for A*。在二維數組中執行A *路徑查找

除了在算法中做出的決定中出現一些奇怪的行爲之外，事情進展得很順利。

我迄今爲止代碼：

void Pathfinding(Point from, Point destination) { 

    goalNode = new Node(destination, 0, 0); 
    startNode = new Node(from, 0, ManhattanDistance(from, destination)); 

    open = new List<Node>();   //list of nodes 
    closed = new List<Node>(); 
    open.Add(startNode);    //Add starting point 

    while(open.Count > 0) { 

     node = getBestNode();     //Get node with lowest F value 
     if(node.position == goalNode.position) { 
      Debug.Log("Goal reached"); 
      getPath(node); 
      break; 
     } 
     removeNode(node, open); 
     closed.Add(node); 

     List<Node> neighbors = getNeighbors(node); 
     foreach(Node n in neighbors) { 
      float g_score = node.G + 1; 
      float h_score = ManhattanDistance(n.position, goalNode.position); 
      float f_score = g_score + h_score; 

      if(isValueInList(n, closed) && f_score >= n.F) 
       continue; 

      if(!isValueInList(n, open) || f_score < n.F) { 
       n.parent = node; 
       n.G = g_score; 
       n.G = h_score; 
       if(!isValueInList(n, open)) { 
        map_data[n.position.x, n.position.y] = 4; 
        open.Add(n); 
       } 
      } 
     } 
    } 
}

運行這段代碼的結果是：

藍色是開放清單和綠色的節點是選擇目標節點的路徑。

SOLUTION：

void Pathfinding(Point from, Point destination) { 

    goalNode = new Node(destination, 0, 0); 
    startNode = new Node(from, 0, ManhattanDistance(from, destination)); 

    open = new List<Node>();   //list of nodes 
    closed = new List<Node>(); 
    open.Add(startNode);    //Add starting point 

    while(open.Count > 0) { 

     node = getBestNode();     //Get node with lowest F value 
     if(node.position == goalNode.position) { 
      Debug.Log("Goal reached"); 
      getPath(node); 
      break; 
     } 
     removeNode(node, open); 
     closed.Add(node); 

     List<Node> neighbors = getNeighbors(node); 
     foreach(Node n in neighbors) { 
      float g_score = node.G + 1; 
      float h_score = ManhattanDistance(n.position, goalNode.position); 
      float f_score = g_score + h_score; 

      if(isValueInList(n, closed) && f_score >= n.F) 
       continue; 

      if(!isValueInList(n, open) || f_score < n.F) { 
       n.parent = node; 
       n.G = g_score; 
       n.H = h_score; 
       if(!isValueInList(n, open)) { 
        map_data[n.position.x, n.position.y] = 4; 
        open.Add(n); 
       } 
      } 
     } 
    } 
}

來源

2013-11-02 Mattias

什麼怪異的行爲/選擇？可視化看起來不錯。 – delnan

我指的是它直立起來然後向左移動的事實。如果它向右擴展然後向上增長會不會更好？我一直認爲A *將始終爲實現目標提供最短的路徑。 – Mattias

最好的C＃A *實現可以在這裏找到：http://blogs.msdn.com/b/ericlippert/archive/tags/astar/ –

首先，你打開節點應該是降序排序，而在你的代碼 - 有沒有順序。您計算距離（g）和啓發式（h），但從未實際使用它。您應該考慮使用有序容器不是列表（如在每次迭代排序列表將無法有效）

其次，你不存儲在節點

n.G = h_score;

啓發式值應爲

n.H = h_score;

來源

2013-11-04 11:57:55 lejlot

在二維數組中執行A *路徑查找

回答

相關問題