Сравнение кучи объекта и статического положения

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 инициализируется объект лямбда (например, лямбда в Python или анонимной функции в JavaScript). Часть [&goal] означает «захват» переменной goal по ссылке для использования в лямбда. Это похоже на пользовательский класс с переменной-членом, которая хранит ссылку на goal и имеет operator(), которая сравнивает два coord с использованием goal.

Кроме того, я не думаю, что вы должны использовать 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();