A * PathFinding性能不佳

Question

調試幾個小時後，該算法似乎正在工作。現在檢查它是否工作我在while循環結束時檢查結束節點位置到currentNode位置。迄今爲止，這些值看起來正確。問題是，我從NPC那裏得到的東西越來越平穩，性能越差。它達到了遊戲無法播放低於10 fps的程度。我目前的PathGraph是2500個節點，我認爲它非常小，對嗎？關於如何提高性能的任何想法？

struct Node 
{ 
    bool walkable;  //Whether this node is blocked or open 
    vect2 position;  //The tile's position on the map in pixels 
    int xIndex, yIndex; //The index values of the tile in the array 
    Node*[4] connections; //An array of pointers to nodes this current node connects to 
    Node* parent; 
    int gScore; 
    int hScore; 
    int fScore; 
} 

class AStar 
{ 
    private: 
    SList!Node openList; //List of nodes who have been visited, with F scores but not processed 
    SList!Node closedList; //List of nodes who have had their connections processed 

    //Node*[4] connections;  //The connections of the current node; 

    Node currentNode;   //The current node being processed 

    Node[] Path;  //The path found; 

    const int connectionCost = 10; 

    Node start, end; 

////////////////////////////////////////////////////////// 

    void AddToList(ref SList!Node list, ref Node node) 
    { 
     list.insert(node); 
    } 

    void RemoveFrom(ref SList!Node list, ref Node node) 
    { 
     foreach(elem; list) 
     { 
      if(node.xIndex == elem.xIndex && node.yIndex == elem.yIndex) 
      { 
       auto a = find(list[] , elem); 
       list.linearRemove(take(a, 1)); 
      } 
     } 
    } 


    bool IsInList(SList!Node list, ref Node node) 
    { 
     foreach(elem; list) 
     { 
      if(node.xIndex == elem.xIndex && node.yIndex == elem.yIndex) 
       return true; 
     } 

     return false; 
    } 

    void ClearList(SList!Node list) 
    { 
     list.clear; 
    } 

    void SetParentNode(ref Node parent, ref Node child) 
    { 
     child.parent = &parent; 
    } 

    void SetStartAndEndNode(vect2 vStart, vect2 vEnd, Node[] PathGraph) 
    { 
     int startXIndex, startYIndex; 
     int endXIndex, endYIndex; 

     startXIndex = cast(int)(vStart.x/32); 
     startYIndex = cast(int)(vStart.y/32); 

     endXIndex = cast(int)(vEnd.x/32); 
     endYIndex = cast(int)(vEnd.y/32); 

     foreach(node; PathGraph) 
     { 
      if(node.xIndex == startXIndex && node.yIndex == startYIndex) 
      { 
       start = node; 
      } 
      if(node.xIndex == endXIndex && node.yIndex == endYIndex) 
      { 
       end = node; 
      } 
     } 
    } 

    void SetStartScores(ref Node start) 
    { 
     start.gScore = 0; 

     start.hScore = CalculateHScore(start, end); 

     start.fScore = CalculateFScore(start); 

    } 

    Node GetLowestFScore() 
    { 
     Node lowest; 

     lowest.fScore = 10000; 

     foreach(elem; openList) 
     { 
      if(elem.fScore < lowest.fScore) 
       lowest = elem; 
     } 

     return lowest; 
    } 

    //This function current sets the program into an infinite loop 
    //I still need to debug to figure out why the parent nodes aren't correct 
    void GeneratePath() 
    { 
     while(currentNode.position != start.position) 
     { 
      Path ~= currentNode; 
      currentNode = *currentNode.parent; 
     } 
    } 

    void ReversePath() 
    { 
     Node[] temp; 
     for(int i = Path.length - 1; i >= 0; i--) 
     { 
      temp ~= Path[i]; 
     } 
     Path = temp.dup; 
    } 

    public: 
    //@FIXME It seems to find the path, but now performance is terrible 
    void FindPath(vect2 vStart, vect2 vEnd, Node[] PathGraph) 
    { 
     openList.clear; 
     closedList.clear; 

     SetStartAndEndNode(vStart, vEnd, PathGraph); 
     SetStartScores(start); 
     AddToList(openList, start); 

     while(currentNode.position != end.position) 
     { 
      currentNode = GetLowestFScore(); 

      if(currentNode.position == end.position) 
       break; 
      else 
      { 
       RemoveFrom(openList, currentNode); 
       AddToList(closedList, currentNode); 

       for(int i = 0; i < currentNode.connections.length; i++) 
       { 
        if(currentNode.connections[i] is null) 
         continue; 
        else 
        { 
         if(IsInList(closedList, *currentNode.connections[i]) 
          && currentNode.gScore < currentNode.connections[i].gScore) 
         { 
          currentNode.connections[i].gScore = currentNode.gScore + connectionCost; 
           currentNode.connections[i].hScore = abs(currentNode.connections[i].xIndex - end.xIndex) 
          + abs( currentNode.connections[i].yIndex - end.yIndex); 
          currentNode.connections[i].fScore =  currentNode.connections[i].gScore + currentNode.connections[i].hScore; 
          currentNode.connections[i].parent = &currentNode; 
         } 
         else if(IsInList(openList, *currentNode.connections[i]) 
           && currentNode.gScore < currentNode.connections[i].gScore) 
         { 
          currentNode.connections[i].gScore = currentNode.gScore + connectionCost; 
          currentNode.connections[i].hScore = abs(currentNode.connections[i].xIndex - end.xIndex) 
          + abs( currentNode.connections[i].yIndex - end.yIndex); 
          currentNode.connections[i].fScore = currentNode.connections[i].gScore + currentNode.connections[i].hScore; 
          currentNode.connections[i].parent = &currentNode; 
         } 
         else 
         { 

          currentNode.connections[i].gScore = currentNode.gScore + connectionCost; 
          currentNode.connections[i].hScore = abs(currentNode.connections[i].xIndex - end.xIndex) 
          + abs(currentNode.connections[i].yIndex - end.yIndex); 
          currentNode.connections[i].fScore = currentNode.connections[i].gScore +  currentNode.connections[i].hScore; 
          currentNode.connections[i].parent = &currentNode; 
          AddToList(openList, *currentNode.connections[i]); 
         } 
        } 
       } 
      } 
     } 

     writeln("Current Node Position: ", currentNode.position); 
     writeln("End Node Position: ", end.position); 

     if(currentNode.position == end.position) 
     { 
      writeln("Current Node Parent: ", currentNode.parent); 
      //GeneratePath(); 
      //ReversePath(); 
     } 
    } 

    Node[] GetPath() 
    { 
     return Path; 
    } 
} 

Answer 1

您對「打開列表」和「關閉列表」都使用單向鏈表，導致不必要的線性時間操作。

前者應爲priority queue（heap），而後者最好爲哈希表實現。

Answer 2

使用無序鏈表對於初學者

你的數據結構

A *依靠的log（n）插入彈出和更新節點爲它正常工作

的檢查，在min heap

Answer 3

在實施埃裏克利珀的A- *算法，我發現執行之間沒有明顯的時間差，用一個HashSet <>（與封閉散列算法換貨政... x < < 16^y）或bool [寬度，高度]。

我是能夠提高由〜40％替換Eric的PrioirtyQueue <>與手卷MinHeap <>（使用SortedDIctionary <>實現）的性能。這是一個戰爭遊戲地圖〜420x750格，測量幾條長對角線路徑acrsoss地圖。