Tony - 1 year ago 64
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();
}

}
``````

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 `coord`s 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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download