我如何加快我的A *尋路？

-1

在沒有任何障礙物移動或從障礙物的頂部移動到障礙物的一側時，我的路徑檢測工作正常，但是當它需要從障礙物的頂部到底部找到障礙物時，它的速度太慢。我如何加快我的A *尋路？

我相當肯定這是我整理的每個循環或循環雖然閉集的方式，但我不知道如何避免這種情況的SortedLists並非適用於Windows Phone 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(); 
}

來源

2012-04-15 Joel

剖析你的代碼，讓你更清楚哪些部分是最慢的。 – Torious 2012-04-15 18:32:51

這樣做，謝謝 – Joel 2012-04-15 18:35:24

這是一個非常低效的實現;有關如何在C＃中有效實現此算法的討論，請參閱我關於此主題的一系列文章：http://blogs.msdn.com/b/ericlippert/archive/tags/astar/ – 2012-04-15 20:59:13

什麼你正在做的事情是非常低效的。列表的排序需要n * log（n）的時間，並且對圖中的每個頂點排序一次。這導致算法需要V^2 * log（V）時間，其中V是頂點的數量。如果你只是保留一個未排序的列表，那麼你可以通過遍歷所有項目並保持到目前爲止的最低值來計算線性時間的最小值。在這種情況下，時間成爲V^2。這只是一個小小的改進。當然，如果您使用適當的優先級隊列（如基於Binary Heap的優先級隊列），那麼該算法將運行得非常快很多，此後操作僅花費log（n）。對自己的二進制堆進行編碼並不太困難，如果平臺不支持本地二進制堆，我強烈建議您這樣做。在這種情況下，插入和找到最小值只需要log（n）時間，導致E log V時間（其中E是邊的數量，在平面圖中它與V成正比）。

來源

2012-04-15 18:36:26

我如何加快我的A *尋路？

回答

相關問題