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); 
    } 
} 

はそう*アルゴリズムを実装していますし、それが目標を見つけたとき、それは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クラス内で提出されたとして、私はNodeInfo Parent {get; set; }を追加することによって、それを修正し、私はNodes時に仮呼ばれる新しいList<NodeInfo>を追加するには優れている： - ：

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

-

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

それが目標を見つけたとき

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); 
} 

パスが、それは無限ではなかった場合は、単にスタックに合わせて長すぎた場合にのみ役立つこと：だから、このようにそれを書き換えることができます。