オブジェクトと静的位置のヒープ比較

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

私はpathfindingの呼び出しごとにローカルコンパレータを作成するためにlambda functionを使用してお勧めしたいです。また、それを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は（PythonでラムダまたはJavaScriptで無名関数のような）ラムダオブジェクトに初期化されます。 [&goal]部分は、ラムダでの使用のために参照によって変数goalを「取得」することを意味します。これは、goalへの参照を格納するメンバ変数を持つカスタムクラスのようなもので、を使用する2つのcoordを比較するoperator()を持っています。

また、私はstd::push_heapとstd::pop_heap（リンクドキュメントのexampleを参照）を使用してください...あなたはstd::sort_heapを使用しなければならないということはないと思います。最初に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();