A *（A-Star）算法幫助

Question

嗯，這是我更新的代碼。它不減速，但沒有路徑出現。

public static IntPosition[] GetPath(BlockType[,] blocks, IntPosition start, IntPosition end, int threshhold) 
    { 
     List<Node> MapNodes = new List<Node>(); 
     MapNodes.Add(new Node() { Position = start }); 

     bool[,] explored = new bool[blocks.GetLength(0), blocks.GetLength(1)]; 

     explored[start.X, start.Y] = true; 

     int? endNode = null; 

     int index = 0; 
     while (endNode == null && index < threshhold) 
     { 
      List<Node> addNodes = new List<Node>(); 


      foreach (Node n in MapNodes) 
      { 
       //left 
       if (n.Position.X - 1 >= 0) 
        if (explored[n.Position.X - 1, n.Position.Y] == false) 
         if (blocks[n.Position.X - 1, n.Position.Y] == BlockType.Open) 
         { 
          int i = addNodes.Count; 
          addNodes.Add(new Node() { Position = new IntPosition(n.Position.X - 1, n.Position.Y), ParentNode = n }); 

          explored[n.Position.X - 1, n.Position.Y] = true; 

          if (addNodes[i].Position == end) 
           endNode = i; 
         } 

       //right 
       if (n.Position.X + 1 <= blocks.GetLength(0) - 1) 
        if (explored[n.Position.X + 1, n.Position.Y] == false) 
         if (blocks[n.Position.X + 1, n.Position.Y] == BlockType.Open) 
         { 
          int i = addNodes.Count; 
          addNodes.Add(new Node() { Position = new IntPosition(n.Position.X + 1, n.Position.Y), ParentNode = n }); 

          explored[n.Position.X + 1, n.Position.Y] = true; 

          if (addNodes[i].Position == end) 
           endNode = i; 
         } 

       //up 
       if (n.Position.Y - 1 >= 0) 
        if (explored[n.Position.X, n.Position.Y - 1] == false) 
         if (blocks[n.Position.X, n.Position.Y - 1] == BlockType.Open) 
         { 
          int i = addNodes.Count; 
          addNodes.Add(new Node() { Position = new IntPosition(n.Position.X, n.Position.Y - 1), ParentNode = n }); 

          explored[n.Position.X, n.Position.Y - 1] = true; 

          if (addNodes[i].Position == end) 
           endNode = i; 
         } 

       //down 
       if (n.Position.Y + 1 <= blocks.GetLength(1)) 
        if (explored[n.Position.X, n.Position.Y + 1] == false) 
         if (blocks[n.Position.X, n.Position.Y + 1] == BlockType.Open) 
         { 
          int i = addNodes.Count; 
          addNodes.Add(new Node() { Position = new IntPosition(n.Position.X, n.Position.Y + 1), ParentNode = n }); 

          explored[n.Position.X, n.Position.Y + 1] = true; 

          if (addNodes[i].Position == end) 
           endNode = i; 
         } 
      } 

      MapNodes.AddRange(addNodes); 

      index++; 
     } 

     if (endNode == null) 
      return new IntPosition[] { }; 
     else 
     { 
      List<IntPosition> path = new List<IntPosition>(); 

      path.Add(end); 

      Node CurrentNode = (MapNodes[(int)endNode].ParentNode); 
      bool endReached = false; 

      while (endReached == false) 
      { 
       path.Add(CurrentNode.Position); 

       if (CurrentNode.Position == start) 
        endReached = true; 
       else 
        CurrentNode = CurrentNode.ParentNode; 
      } 


      path.Reverse(); 
      return path.ToArray(); 
     } 
    } 



public class IntPosition 
{ 
    public int X; 
    public int Y; 

    public IntPosition(int x, int y) 
    { 
     X = x; 
     Y = y; 
    } 

    public IntPosition() { X = 0; Y = 0; } 

    public override bool Equals(object obj) 
    { 
     return ((IntPosition)obj).X == X && ((IntPosition)obj).Y == Y; 
    } 
} 

Answer 1

代碼有幾個問題。首先，你的X + 1和Y + 1檢查有比較錯誤的方式（大於而不是小於）。我懷疑這是導致算法失敗的原因。其次，雖然我對算法不熟悉，但我懷疑你需要做一些事情來確保你已經檢查過的節點在後續迭代中不會被再次檢查。另外，您需要確保不要將已添加的節點添加到MapNodes。這些組合可能是您看到速度緩慢的原因，因爲它會導致帶有許多冗餘節點的MapNodes呈指數級增長。

Answer 2

除了Chris提到的內容，您的MapNodes的使用還有其他問題。它需要進行排序，幷包含所有成員，包括放在列表addNodes上的所有節點。緩存所有需要添加到MapNodes的節點不是有效的A *實現。當將節點添加到addNodes時，實際上應將其添加到MapNodes，然後MapNodes應該按F排序，F是與節點關聯的數字，F是起始節點到該節點的總成本與該節點的總和爲該節點評估的啓發式功能。互聯網上有啓發式功能的多種描述，我建議你嘗試閱讀。

而順便說一句，你的代碼中的啓發式在哪裏？一個A *算法只是一個沒有啓發式的慢Dijkstra算法。恐怕你已經實現了類似迪克斯特拉那樣的A *。

並回答您的實際問題：該算法可能不會產生路徑，因爲有錯誤，阻止搜索算法實際到達目標節點。