Heap-Vergleich zwischen Objekt und statischer Position

Question

Ich arbeite an der Pfadfindung für ein 2D-Spiel. Ich habe this similar answer gefunden, aber ich bin mir nicht sicher, wie man den Vergleichsoperator erstellt, wenn heap compares i <> i+i, wenn i need manhattan(i) <> manhattan(i+1)? ich mit cpp wahnsinnig rostig bin, so gehen Sie einfach auf mich.

typedef std::tuple<int, int> coord; 

int manhattan(coord start, coord goal){ 
    return (std::abs(start.get<0> - goal.get<0>) + \ 
      std::abs(start.get<1> - goal.get<1>)) 
} 

bool operator()((const coord& left, const coord& right){ 
    return manhattan(left, ???) < manhattan(right, ???);  
} 

vector pathfinding(coord start, coord goal){ 
    //using A* format 
    vector<coord> open; 

    while(open){ 
     //how can I compare indexes to goal parameter? 
     std::sort_heap(open.begin(), open.end()); 

     current = open.front(); 
    } 

} 

Answer 1

Ich würde vorschlagen, ein lambda function mit einem lokalen Komparator für jeden Aufruf von pathfinding zu erstellen. Vergessen Sie auch nicht, es an std::sort_heap zu übergeben. Versuchen Sie folgendes:

vector pathfinding(coord start, coord goal) { 
    // using A* format 
    vector<coord> open; 
    auto comp = [&goal](const coord& lhs, const coord& rhs) { 
    return manhattan(lhs, goal) > manhattan(rhs, goal); // greater-than, for a min-heap 
    }; 

    while(open){ 
    std::sort_heap(open.begin(), open.end(), comp); 

    ... 
    } 
} 

comp zu einem Lambda-Objekt initialisiert wird (wie ein Lambda in Python oder eine anonyme Funktion in JavaScript). Der [&goal] Teil bedeutet, die goal Variable durch Bezugnahme für die Verwendung im Lambda zu "erfassen". Es ist wie eine benutzerdefinierte Klasse mit einer Mitgliedsvariablen, die einen Verweis auf goal speichert, und hat eine operator(), die zwei coord s unter Verwendung goal vergleicht.

Auch ich glaube nicht, dass Sie std::sort_heap verwenden sollten ... Verwenden Sie std::push_heap und std::pop_heap (die example in der verknüpften Dokumentation). Die Idee ist, einmal am Anfang std::make_heap aufzurufen und push/pop_heap zu verwenden, um den Heap beim Hinzufügen/Entfernen zu verwalten. Keine Notwendigkeit, es bei jeder Iteration zu sortieren. Beispiel:

// to push "direction" onto the heap: 
open.push_back(direction); 
std::push_heap(open.begin(), open.end(), comp); 

// to pop "current" off of the heap: 
std::pop_heap(open.begin(), open.end(), comp); 
current = open.pop_back();