對象與靜態位置之間的堆比較

Question

我正在尋找2D瓦片遊戲的路徑查找。我發現this similar answer，但我不知道如何創建比較運算符heap compares i <> i+i，當i need manhattan(i) <> manhattan(i+1)?我瘋狂地生鏽與cpp所以容易對我。

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

我建議使用一個lambda function創建的pathfinding每次調用本地比較。另外，不要忘記將它傳遞給std::sort_heap。嘗試：

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被初始化爲一個lambda對象（像在Python的λ或在JavaScript匿名功能）。 [&goal]部分意味着通過引用「捕獲」goal變量以在lambda中使用。它就像一個帶有成員變量的自定義類，其中存儲對goal的引用，並且具有使用goal比較兩個coord的operator()。

此外，我不認爲你應該使用std::sort_heap ...使用std::push_heap和std::pop_heap（請參閱鏈接文檔中的example）。想法是在開始時調用std::make_heap一次，並在添加/刪除時使用push/pop_heap來維護堆。無需在每次迭代中對其進行排序。例如：

// 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();