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 *。

并回答您的实际问题：该算法可能不会产生路径，因为有错误，阻止搜索算法实际到达目标节点。