개체와 정적 위치 간의 힙 비교

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은 (파이썬에서 람다 나 자바 스크립트에서 익명 함수와 같은) 람다 객체로 초기화된다. [&goal] 부분은 goal 변수를 람다에서 사용하기 위해 참조로 "캡처"하는 것을 의미합니다. 이는 goal에 대한 참조를 저장하는 멤버 변수가있는 사용자 정의 클래스와 비슷하며 을 사용하는 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();