A *算法System.StackOverflowException

Question

public List<Location2D> Path(Location2D start, Location2D goal) 
{ 
    openset = new List<NodeInfo>(); // The set of tentative nodes to be evaluated, initially containing the start node. 
    closedset = new List<NodeInfo>(); // The set of nodes already evaluated. 
    path = new List<Location2D>(); // The path result. 
    came_from = new Dictionary<Location2D, Location2D>(); 

    NodeInfo Start = new NodeInfo(); 
    Start.SetLoction(start.X, start.Y); 
    Start.H = GetHValue(start, goal); 
    openset.Add(Start); 

    while (openset.Count > 0) { // while openset is not empty 
     NodeInfo current = CheckBestNode(); //the node in openset having the lowest f_score[] value 

     if (current.Location.Equals(goal)) { 
      ReconstructPathRecursive(current.Location); 
      return path; 
     } 

     for (int i = 0; i < 8; i++) { // neighbor nodes. 
      NodeInfo neighbor = new NodeInfo(); 
      neighbor.SetLoction((ushort)(current.Location.X + ArrayX[i]), (ushort)(current.Location.Y + ArrayY[i])); 

      bool tentative_is_better = false; 

      if (closedset.Contains(neighbor)) 
       continue; 
      if (!map.Cells[neighbor.Location.X, neighbor.Location.Y].Walkable) { closedset.Add(neighbor); continue; } 

      Double tentative_g_score = current.G + DistanceBetween(current.Location, neighbor.Location); 

      if (!openset.Contains(neighbor)) { 
       openset.Add(neighbor); 
       neighbor.H = GetHValue(neighbor.Location, goal); 
       tentative_is_better = true; 
      } else if (tentative_g_score < neighbor.G) { 
       tentative_is_better = true; 
      } else { 
       tentative_is_better = false; 
      } 

      if (tentative_is_better) { 
       came_from[neighbor.Location] = current.Location; 
       neighbor.G = tentative_g_score; 
      } 
     } 
    } 
    return null; 
} 

private void ReconstructPathRecursive(Location2D current_node) 
{ 
    Location2D temp; 
    if (came_from.TryGetValue(current_node, out temp)) { 
     path.Add(temp); 
     ReconstructPathRecursive(temp); 
    } else { 
     path.Add(current_node); 
    } 
} 

所以我实现A *算法，当它发现目标就转到ReconstructPathRecursive ，然后应用程序崩溃，并抛出该异常An unhandled exception of type 'System.StackOverflowException' occurred in mscorlib.dll

和This thread is stopped with only external code frames on the call stack. External code frames are typically from framework code but can also include other optimized modules which are loaded in the target process.

idk有什么问题！

Answer 1

我固定它通过添加NodeInfo Parent {get; set; }作为该NodeInfo类中提交，我添加新List<NodeInfo>称为Nodes时试探性更好： -

if (tentative_is_better) { 
         neighbor.Parent = current; 
         nodes.Add(neighbor); 
         neighbor.G = tentative_g_score; 
        } 

那么当它发现目标： -

if (current.Location.Equals(goal)){ 
        ReconstructPath(current); 
        path.Reverse(); 
        return path; 
       } 

其中ReconstructPath： -

private void ReconstructPath(NodeInfo current) { 
      if (current.Parent == null) return; 
      path.Add(current.Parent.Location); 
      ReconstructPath(current.Parent); 
     } 

现在它工作正常。

Answer 2

它并不一定是递归的，因为它是尾递归的。所以，你可以把它改写这样的：

private void ReconstructPathIterative(Location2D current_node) 
{ 
    Location2D temp; 
    while (came_from.TryGetValue(current_node, out temp)) 
    { 
     path.Add(temp); 
     current_node = temp; 
    } 
    path.Add(current_node); 
} 

这不仅有利于如果路径只是太长，不适合在堆栈上，而不是是否是无限的。