Unity A * Pathfinding Crashes

Question

私はA *アルゴリズムを実装しようとしていました。基本ロジックはほぼ完成していますが、私はこの問題を解決できません。

パスをリクエストするとUnityが応答を停止し、PCがハングアップするまで遅くなり、シャットダウンする必要があります。ここで

は単純化されたコードです：

public static List<Node> ReturnPath(Vector3 pointA, Vector3 pointB) 
{ 
    /* A Bunch of initializations */ 

    while (!pathFound) 
    { 
     //add walkable neighbours to openlist 
     foreach (Node n in GetNeighbours(currentNode)) 
     { 
      if (!n.walkable) 
       continue; 
      n.gCost = currentNode.gCost + GetManDist (currentNode, n); 
      n.hCost = GetManDist (n, B); 
      openList.Add (n); 
      n.parent = currentNode; 

     } 

     //check openList for lowest fcost or lower hCost 
     for (int i = 0; i < openList.Count; i++) 
     { 
      if ((openList [i].fCost < currentNode.fCost) || (openList [i].fCost == currentNode.fCost && openList [i].hCost < currentNode.hCost)) 
      { 
       //make the currentNode = node with lowest fcost 
       currentNode = openList [i]; 
      } 
      openList.Remove (currentNode); 
      if(!closedList.Contains(currentNode)) 
       closedList.Add (currentNode); 
     } 

     //Check if the currentNode it destination 
     if (currentNode == B) 
     { 
      Debug.Log ("Path Detected"); 
      path = RetracePath (A, B); 
      pathFound = true; 
     } 

    } 
    return path; 
} 

これは限り先には2つのノード離れていると正常に動作します。それ以上あれば、上記の問題が発生します。何故ですか？最初に私がopenListにあまりにも多くを入れていたと思います。

メモ：30 x 30単位のプラットフォーム（床）を「ノード」と呼ばれる1x1の正方形に分割します。 GetManDist（）2ノード間のマンハッタン距離を取得します。

更新：ここに作業コードがあります。コメントが長すぎました

public List<Node> ReturnPath(Vector3 pointA, Vector3 pointB) 
{ 
    List<Node> openList = new List<Node>(); 
    List<Node> closedList = new List<Node>(); 
    List<Node> path = new List<Node>(); 

    Node A = ToNode (pointA); 
    Node B = ToNode (pointB); 
    Node currentNode; 

    bool pathFound = false; 

    A.hCost = GetManDist(A, B); 
    A.gCost = 0; 

    openList.Add (A); 

    while (!pathFound) // while(openList.Count > 0) might be better because it handles the possibility of a non existant path 
    { 
     //Set to arbitrary element 
     currentNode = openList [0]; 

     //Check openList for lowest fcost or lower hCost 
     for (int i = 0; i < openList.Count; i++) 
     { 
      if ((openList [i].fCost < currentNode.fCost) || ((openList [i].fCost == currentNode.fCost && openList [i].hCost < currentNode.hCost))) 
      { 
       //Make the currentNode = node with lowest fcost 
       currentNode = openList [i]; 
      } 
     } 

     //Check if the currentNode is destination 
     if (currentNode.hCost == 0) //Better than if(currentNode == B) 
     { 
      path = RetracePath (A, B); 
      pathFound = true; 
     } 

     //Add walkable neighbours to openlist 
     foreach (Node n in GetNeighbours(currentNode)) 
     { 
      //Avoid wasting time checking unwalkable and those already checked 
      if (!n.walkable || closedList.Contains(n)) 
       continue; 

      //Movement Cost to neighbour 
      int newGCost = currentNode.gCost + GetManDist (currentNode, n); 

      //Calculate g_Cost, Update if new g_cost to neighbour is less than an already calculated one 
      if (n.gCost > newGCost || !openList.Contains (n)) 
      { 
       n.gCost = newGCost; 
       n.hCost = GetManDist (n, B); 
       n.parent = currentNode; //So we can retrace 
       openList.Add (n); 
      } 
     } 
     //We don't need you no more... 
     openList.Remove (currentNode); 

     //Avoid redundancy of nodes in closedList 
     if(!closedList.Contains(currentNode)) 
      closedList.Add (currentNode); 

    } 

    return path; 
} 

Answer 1

問題はcurrentNodeの値にありました。私たちは、経路探索が壁に遭遇したときに、いくつかのケースでは、それが戻って行くか、その結果、ターンを取るために持っている、currentNodeのに対するopenlistで最低f_Cost以下h_Costとのノードをチェックしているので、 f_Costとh_Cost（両方ともcurrentNodeのものよりも大きい）を増加させる。したがって、openlistにはf_Cost/h_Costの値が小さいノードがなくなり、無限ループになります。簡単な解決策は、毎回openList内の任意の要素にcurrentNodeを設定することでした。ループの先頭に

currentNode = openlist[0]; 

追加

。