A * Leistung bei großen Karten

Question

ich möchte etwas Hilfe für meine AStar-Algorithmus-Suche, die aus meiner Sicht weit zu lang dauert. Auch wenn meine Karte mit 500 * 400 Koordinaten (objektiv ist mein Kacheldiagramm etwas kleiner, da ich die Wände nicht in den TileGraph aufgenommen habe.) Groß wäre, würde ich das Ergebnis nach ein paar Sekunden erwarten. Die Welt sieht wie folgt aus, trotz der Aufgabe nicht von mir sein

ich von markierten Koordinaten "Start" suchen möchten (120 | 180) auf "Ziel" (320 | 220), die 48 zur Zeit dauert Protokoll. Und tut mir leid für alle, die kein Deutsch sprechen, aber der Text auf dem Bild ist nicht wichtig.

Zuerst möchte ich Ihnen zeigen, was ich für A * programmiert habe. Im Allgemeinen habe ich mich an den Pseudocode unter https://en.wikipedia.org/wiki/A * _search_algorithm angepasst.

bool AStarPath::Processing(Node* Start, Node* End) 
m_Start = Start; 
m_End = End; 
for (Node* n : m_SearchRoom->GetAllNodes()) 
{ 
    DistanceToStart[n] = std::numeric_limits<float>::infinity(); 
    CameFrom[n] = nullptr; 
} 
DistanceToStart[m_Start] = 0; 
NotEvaluatedNodes.AddElement(0, m_Start); 
while (NotEvaluatedNodes.IsEmpty() == false) 
{ 
    Node* currentNode = NotEvaluatedNodes.GetElement(); 
    NotEvaluatedNodes.DeleteElement(); 
    if (currentNode == m_End) 
    { 
     ReconstructPath(); 
     return true; 
    } 
    EvaluatedNodes.insert(currentNode); 
    ExamineNeighbours(currentNode); 
} 
return false; 
//End Processing 

void AStarPath::ExamineNeighbours(Node* current) 
for (Node* neighbour : m_SearchRoom->GetNeighbours(current)) 
{ 

    if (std::find(EvaluatedNodes.begin(), EvaluatedNodes.end(), neighbour) != EvaluatedNodes.end()) 
    { 
     continue; 
    } 

    bool InOpenSet = NotEvaluatedNodes.ContainsElement(neighbour); 

    float tentative_g_score = DistanceToStart[current] + DistanceBetween(current, neighbour); 

    if (InOpenSet == true && tentative_g_score >= DistanceToStart[neighbour]) 
    { 
     continue; 
    } 

    CameFrom[neighbour] = current; 

    DistanceToStart[neighbour] = tentative_g_score; 

    float Valuation = tentative_g_score + DistanceBetween(neighbour, m_End); 

    if (InOpenSet == false) 
    { 
     NotEvaluatedNodes.AddElement(Valuation, neighbour); 
    } 
    else 
    { 
     NotEvaluatedNodes.UpdatePriority(neighbour, Valuation); 
    } 
} 

// END ExamineNeighbours

double AStarPath::DistanceBetween(Node* a, Node* b) 

return sqrt(pow(m_SearchRoom->GetNodeX(a) - m_SearchRoom->GetNodeX(b), 2) 
    + pow(m_SearchRoom->GetNodeY(a) - m_SearchRoom->GetNodeY(b), 2)); 
//END DistanceBetween 

Es tut mir leid für die schlechte Formatierung, aber ich weiß wirklich nicht, wie man mit den Codeblöcke, hier zu arbeiten.

Klasse AStarPath

privat:

std::unordered_set<Node*> EvaluatedNodes; 


Binary_Heap NotEvaluatedNodes; 


std::unordered_map<Node*, float> DistanceToStart; 


std::unordered_map<Node*, Node*> CameFrom; 

std::vector<Node*> m_path; 

TileGraph* m_SearchRoom; 

// END Klasse AStarPath

Wie auch immer, ich habe bereits mein Problem dachte ich über und einige Dinge geändert. Erstens habe ich einen binären Heap anstelle der std :: priority_queue implementiert. Ich habe dafür eine Seite bei Policyalmanac benutzt, aber ich darf keinen weiteren Link hinzufügen, daher kann ich Ihnen die Adresse nicht wirklich geben. Es hat die Leistung verbessert, aber es dauert immer noch ziemlich lange, wie ich zu Beginn gesagt habe. Zweitens habe ich ungeordnete Container verwendet (wenn es zwei Optionen gibt), so dass die Container nach den Änderungen nicht sortiert werden müssen. Für meine EvaluatedNodes habe ich das std :: unordered_set genommen, da es meines Wissens nach am schnellsten für std :: find ist, das ich für Containment-Checks verwende. Die Verwendung von std :: unordered_map wird durch die Notwendigkeit von separaten Schlüsseln und Werten verursacht. Drittens dachte ich darüber nach, meine Karte in Knoten zu teilen, die mehrere Koordinaten repräsentieren (statt jetzt wo ein Knoten eine Koordinate repräsentiert), aber ich bin mir nicht sicher, wie ich sie wählen soll. Ich dachte über das Setzen von Punkten an der Position, dass der Algorithmus basierend auf der Länge und Breite der Karte entscheidet und benachbarte Koordinaten hinzufügt, wenn es keine bestimmte Distanz oder mehr Abstand vom Basisknoten/Koordinaten gibt und ich sie nur von erreichen kann vorherige hinzugefügte Koordinaten Um zu überprüfen, ob es eine Gehfähigkeit gibt, hätte ich das reguläre A * verwendet, mit nur den Koordinaten (umgewandelt in A * Knoten), die sich in diesen großen Knoten befinden. Trotzdem bin ich mir unsicher, welche Koordinaten ich für Anfang und Ende der Pfadfindung wählen sollte. Dies würde wahrscheinlich die Anzahl der Knoten/Koordinaten reduzieren, die überprüft werden, wenn ich nur die Koordinaten/Knoten verwende, die Teil der großen Knoten waren (so dass nur Knoten verwendet werden, die einen Teil der größeren Knoten an einem oberen Knoten haben) Level)

Es tut mir leid für mein Englisch, aber hoffe, dass alles verständlich sein wird. Ich freue mich auf deine Antworten und lerne neue Techniken und Wege, mit Problemen umzugehen und lerne auch all die vielen dummen Fehler kennen, die ich produziert habe. Wenn ein wichtiger Aspekt unklar ist oder wenn ich mehr Code/Informationen hinzufügen sollte, zögern Sie nicht zu fragen.

EDIT: Binary_Heap

class Binary_Heap 

private: 

std::vector<int> Index; 
std::vector<int> m_Valuation; 
std::vector<Node*> elements; 

int NodesChecked; 

int m_NumberOfHeapItems; 

void TryToMoveElementUp(int i_pos); 

void TryToMoveElementDown(int i_pos); 

public: 

Binary_Heap(int i_numberOfElements); 


void AddElement(int Valuation, Node* element); 


void DeleteElement(); 


Node* GetElement(); 

bool IsEmpty(); 

bool ContainsElement(Node* i_node); 

void UpdatePriority(Node* i_node, float newValuation); 


Binary_Heap::Binary_Heap(int i_numberOfElements) 

Index.resize(i_numberOfElements); 
elements.resize(i_numberOfElements); 
m_Valuation.resize(i_numberOfElements); 

NodesChecked = 0; 

m_NumberOfHeapItems = 0; 

Leere Binary_Heap :: AddElement (int Bewertungs, Knoten * Element)

++NodesChecked; 
++m_NumberOfHeapItems; 

Index[m_NumberOfHeapItems] = NodesChecked; 

m_Valuation[NodesChecked] = valuation; 

elements[NodesChecked] = element; 

TryToMoveElementUp(m_NumberOfHeapItems); 

Leere Binary_Heap :: DeleteElement()

elements[Index[1]] = nullptr; 
m_Valuation[Index[1]] = 0; 

Index[1] = Index[m_NumberOfHeapItems]; 
--m_NumberOfHeapItems; 

TryToMoveElementDown(1); 

Bool Binary_Heap :: IsEmpty()

return m_NumberOfHeapItems == 0; 

Knoten * Binary_Heap :: GetElement()

return elements[Index[1]]; 

Bool Binary_Heap :: ContainsElement (Node * i_element)

return std::find(elements.begin(), elements.end(), i_element) != elements.end(); 

Leere Binary_Heap :: UpdatePriority (Node * i_node, float newValuation)

if (ContainsElement(i_node) == false) 
{ 
    AddElement(newValuation, i_node); 
} 
else 
{ 
    int treePosition; 

    for (int i = 1; i < Index.size(); i++) 
    { 
     if (elements[Index[i]] == i_node) 
     { 
      treePosition = i; 

      break; 
     } 
    } 

    //Won't influence each other, since only one of them will change the position 
    TryToMoveElementUp(treePosition); 
    TryToMoveElementDown(treePosition); 
} 

Leere Binary_Heap :: TryToMoveElementDown (int i_pos)

int nextPosition = i_pos; 

while (true) 
{ 
    int currentPosition = nextPosition; 

    if (2 * currentPosition + 1 <= m_NumberOfHeapItems) 
    { 
     if (m_Valuation[Index[currentPosition]] >= m_Valuation[Index[2 * currentPosition]]) 
     { 
      nextPosition = 2 * currentPosition; 
     } 
     if (m_Valuation[Index[currentPosition]] >= m_Valuation[Index[2 * currentPosition + 1]]) 
     { 
      nextPosition = 2 * currentPosition + 1; 
     } 
    } 
    else 
    { 
     if (2 * currentPosition <= m_NumberOfHeapItems) 
     { 
      if (m_Valuation[Index[currentPosition]] >= m_Valuation[Index[2 * currentPosition]]) 
      { 
       nextPosition = 2 * currentPosition; 
      } 
     } 
    } 

    if (currentPosition != nextPosition) 
    { 
     int tmp = Index[currentPosition]; 
     Index[currentPosition] = Index[nextPosition]; 
     Index[nextPosition] = tmp; 
    } 
    else 
    { 
     break; 
    } 
} 

Hohlraum Binary_Heap :: TryToMoveElementUp (int i_pos)

int treePosition = i_pos; 

while (treePosition != 1) 
{ 
    if (m_Valuation[Index[treePosition]] <= m_Valuation[Index[treePosition/2]]) 
    { 
     int tmp = Index[treePosition/2]; 

     Index[treePosition/2] = Index[treePosition]; 

     Index[treePosition] = tmp; 

     treePosition = treePosition/2; 
    } 
    else 
    { 
     break; 
    } 
} 

Answer 1

Diese Linie große Ineffizienz führt, wie es über alle in jeder Iteration, die die Knoten in der Warteschlange, iterieren muss.

bool InOpenSet = NotEvaluatedNodes.ContainsElement(neighbour); 

Versuchen Sie es mit einer effizienteren Datenstruktur, z. das ungeordnete_set, das Sie für EvaluatedNodes verwenden. Jedes Mal, wenn Sie einen Knoten aus dem Heap verschieben oder entfernen, ändern Sie den Satz entsprechend so, dass immer nur die Knoten im Heap enthalten sind.