Unity A * Pathfinding stürzt ab

Question

Also habe ich versucht, den A * -Algorithmus zu implementieren. Die Basic Logic ist fast fertig, aber es gibt ein Problem, das ich einfach nicht lösen kann.

Wenn ein Pfad angefordert wird Unity reagiert nicht mehr und mein PC wird immer langsamer, bis er aufhört und ich erzwinge, dass er heruntergefahren wird. Hier

ist der vereinfachte Code:

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; 
} 

Dies funktioniert gut, solange das Ziel zwei Knoten entfernt ist. Wenn es mehr als das ist, tritt das oben erwähnte Problem auf. Warum das? Meine erste Vermutung, dass ich zu viel in die OpenList gesetzt habe.

HINWEISE: Im brechen eine 30 x 30-Einheit Plattform (Stock) in 1x1 Quadrate namens "Knoten" GetManDist() Ruft die Manhattan-Entfernung zwischen 2 Knoten.

UPDATE: Hier ist der Arbeitscode. War zu lang für einen Kommentar

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

Das Problem war mit dem Wert von currentNode. Da wir für den Knoten mit dem niedrigsten f_Cost oder niedriger h_Cost im Openlist gegen currentNode, in einigen Fällen überprüft, wenn die Wegfindung eine Wand trifft, hat es zurück zu gehen oder eine Wendung nehmen, was dazu führt Erhöhen von f_Cost und h_Cost (beide größer als die des aktuellen Knotens). Daher gibt es keinen Knoten in der Openlist mit einem niedrigeren f_Cost/h_Cost, was zu einer Endlosschleife führt. Die einfache Lösung bestand darin, den currentNode jedesmal auf ein beliebiges Element in der openList zu setzen.

Hinzufügen

currentNode = openlist[0]; 

am Anfang der Schleife.