对象与静态位置的堆比较

Question

我正在为一款2D瓷砖游戏寻找路径。我已经找到了这个类似的答案，但我不知道如何创建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函数为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被初始化为lambda对象(类似于Python中的lambda或JavaScript中的匿名函数)。[&goal]部件意味着通过引用“捕获”goal变量，以便在lambda中使用。这就像一个自定义类，其中包含一个成员变量，它存储对goal的引用，并且有一个operator()，它使用goal比较两个coord。

而且，我不认为你应该使用std::sort_heap.使用std::push_heap和std::pop_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();