A * PathFinding Poor Performance

Question

Después de depurar durante unas horas, el algoritmo parece estar funcionando. Ahora mismo para verificar si funciona, estoy comprobando la posición del nodo final a la posición actualNodo cuando el ciclo while se cierra. Hasta ahora, los valores parecen correctos. El problema es que cuanto más me alejo del NPC, que está estacionario, peor es el rendimiento. Llega a un punto en el que el juego no se puede jugar a menos de 10 fps. Mi PathGraph actual es de 2500 nodos, que creo que es bastante pequeño, ¿no? ¿Alguna idea sobre cómo mejorar el rendimiento?

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

Estás usando listas enlazadas por enlaces sencillos, tanto para la "lista abierta" y la "lista cerrada", lo que lleva a las operaciones en tiempo lineal innecesarios.

El primero debe ser un priority queue (heap), mientras que el segundo será más eficaz como una tabla de hash .

Answer 2

utilizando un lista enlazada clasificar como su estructura de datos para empezar

A * se basa en un log (n) insertar el pop y el nodo de actualización para que funcione correctamente

chequeo en un min heap

Answer 3

En la aplicación de A- de Eric Lippert * algoritmo, no he encontrado ninguna diferencia de tiempo entre la aplicación de discernible cerrada con un HashSet <> (con algoritmo de hash retu rn x < < 16^y) o bool [Ancho, alto].

que fue capaz de mejorar el rendimiento mediante la sustitución de ~ 40% de Eric PrioirtyQueue <> (implementado usando SortedDictionary <>) con un enrollado a mano MinHeap <>. Esto fue para un mapa de juegos de guerra de ~ 420x750 hexes, midiendo unos pocos largos recorridos diagonales que acristean el mapa.