c++ - 对象和静态位置之间的堆比较

Question

我正在为一款 2D 方 block 游戏进行寻路。我找到了 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被初始化为一个 lambda 对象(就像 Python 中的 lambda 或 JavaScript 中的匿名函数)。 [&goal]部分意味着“捕获” goal通过引用变量在 lambda 中使用。它就像一个带有成员变量的自定义类，该成员变量存储对 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();