A * Pathfindingをどのようにスピードアップできますか？

Question

障害物がない状態で移動する場合や、障害物の上か​​ら下に移動する場合は、パスの検出がうまく動作しますが、障害物の上か​​ら下に向かう途中にある場合は遅すぎます。

は、私はそれは私が各ループを並べ替えたり、閉じセットをループしています方法ですかなり確信しているが、私はSortedListsは、Windows携帯電話で利用できないとしてこれを避けるするかどうかはわかりません7

//This Vivid Destination means it doesn't have to find the exact location 
//which is helpful as it is continuous environment 
Rectangle vividDestination = new Rectangle((int)character.destination.X - 10, (int)character.destination.Y - 10, 20, 20); 

while (!vividDestination.Contains(Maths.vectorToPoint(OpenNodes[0].position))) 
{ 
    Node Current = OpenNodes[0]; 
    OpenNodes.RemoveAt(0); 
    ClosedNodes.Add(Current); 
    Current.calculateNeightbours(); 

    foreach (Node neighbour in Current.neighbours) 
    { 
     neighbour.parents = Current.parents + 1; 
     //The cost of the node is the amount of parent nodes + the distance to destination 
     neighbour.cost = calculateCost(neighbour.position, character.destination, neighbour.parents); 

     for (int i = 0; i < OpenNodes.Count; i++) 
     { 
      //Round Vector rounds the floats in the Vector to the nearest integer 
      if (Maths.roundVector(OpenNodes[i].position) == Maths.roundVector(neighbour.position) && OpenNodes[i].parents < neighbour.parents) 
      { 
       break; 
      } 
      else 
      { 
       OpenNodes.RemoveAt(i); 
       OpenNodes.Add(neighbour); 
       i--; 
       break; 
      } 
     } 

     bool closedNode = false; 
     for (int i = 0; i < ClosedNodes.Count; i++) 
     { 
      if (Maths.roundVector(ClosedNodes[i].position) == Maths.roundVector(neighbour.position)) 
      { 
       closedNode = true; 
       break; 
      } 
     } 

     if (!closedNode) 
     { 
      OpenNodes.Add(neighbour); 
     } 
    } 

    OpenNodes = OpenNodes.OrderBy(item => item.cost).ToList(); 
} 

Answer 1

何あなたがやっていることはひどく非効率です。リストのソートにはn * log（n）時間がかかり、グラフの各頂点ごとにリストをソートします。この結果、V^2 * log（V）時間を要するアルゴリズムが得られます。ここで、Vは頂点の数です。 ソートされていないリストを保持するだけであれば、すべてのアイテムをループしてこれまでの最低のアイテムの数を維持することで、線形時間の最小値を抽出できます。この場合、時間はV^2になります。これはほんの少しの改善です。 もちろん、適切な優先順位のキュー（Binary Heapに基づくキューのような）を使用すると、アルゴリズムはそれよりもはるかに速く実行されます。それ以来、操作はlog（n）のコストしかかかりません。独自のバイナリヒープをコーディングすることはあまり難しくありません。プラットフォームがネイティブにサポートしていない場合は、これを強くお勧めします。この場合、最小値を挿入して求めるにはlog（n）時間しかかかりません。その結果、E log V時間が得られます（Eはエッジの数で、平面グラフではVに比例します）。