Heap comparision between object and static position

Question

I'm working on pathfinding for a 2D tile game. I've found this similar answer, but I'm not sure how to do create the comparison operator when heap compares i <> i+i, when i need manhattan(i) <> manhattan(i+1)? I'm insanely rusty with cpp so go easy on me.

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

I'd suggest using a lambda function to create a local comparator for each call of pathfinding. Also, don't forget to pass it to std::sort_heap. Try this:

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 is initialized to a lambda object (like a lambda in Python or an anonymous function in JavaScript). The [&goal] part means to "capture" the goal variable by reference for use in the lambda. It's like a custom class with a member variable that stores a reference to goal, and has an operator() that compares two coords using goal.

Also, I don't think that you should be using std::sort_heap... Use std::push_heap and std::pop_heap (see the example in the linked documentation). The idea is to call std::make_heap once at the beginning, and use push/pop_heap to maintain the heap when adding/removing. No need to sort it every iteration. Example:

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