Tony Tony - 19 days ago 8
C++ Question

Heap comparision between object and static position

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

}

qxz qxz
Answer

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);
  };

  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.