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

Question

我正在为一款 2D 方块游戏寻找路径。我找到了 this similar answer，但我不确定如何在 heap compares i <> i+i 时创建比较运算符，当 i need manhattan(i) <> manhattan(i+1)? 我对 cpp 非常生疏，所以对我放轻松。 =14=]

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 to create a local comparator for each call of pathfinding. Also, don't forget to pass it to 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] 部分表示通过引用 "capture" goal 变量以供在 lambda 中使用。它就像一个自定义 class，带有一个存储对 goal 的引用的成员变量，并且有一个 operator() 使用 goal 比较两个 coord。

此外，我认为您不应该使用 std::sort_heap...在链接文档中使用 std::push_heap and std::pop_heap (see the example）。思路是一开始调用一次std::make_heap，adding/removing的时候用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();

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

Heap comparision between object and static position

c++

heap

a-star

comparison-operators