跳转至

编写 A* 搜索函数

完成 AStarNode 类后，你可以编写实际搜索函数。首先定义函数原型：

template<int WIDTH, int HEIGHT, int BLOCKING>
bool doAStarSearch(
    int map[WIDTH][HEIGHT],
    int startx, int starty,
    int endx, int endy,
    int path[WIDTH][HEIGHT])
{ }

原型把游戏地图的宽和高，以及表示地图上阻挡瓦片的值作为模板参数。doAStarSearch() 函数还接受地图本身（map）、起始坐标（startx 和 starty）、目标坐标（endx 和 endy），以及一个空白地图（path），完成时可以在其中填充计算出的路径。

注　前三个参数是模板参数，所以你可以把它们作为编译时常量传递。我在示例代码中这样做了，以允许为 map 和 path 参数显式声明数组大小，并允许确定性的值表示地图上的阻挡瓦片。实践中，你从游戏读取的地图会有动态大小，你可能需要更健壮的方式传递这些数据。

接下来，doAStarSearch() 函数需要排序列表保存前沿，以及一个容器跟踪所有创建的节点，以便在现有节点作为不同父节点的子节点被打开时更新它的分数和父节点。你可以这样创建它们：

std::vector<AStarNodePtr> allNodes;
std::priority_queue<AStarNodePtr> frontier;

前沿用 std::priority_queue 定义，因为它可以自动按分数排序节点。节点容器 allNodes 定义为 std::vector。

现在，让我们创建第一个节点：

auto node = AStarNode::makePtr(startx, starty, 0, 
nullptr);
node->updateScore(endx, endy);
allNodes.push_back(node);

第一个节点是位置 (startx, starty) 的零成本孤儿节点。节点根据 updateScore() 函数返回的内容获得分数，然后被添加到 allNodes 容器。

容器中有节点后，是时候编写 A* 算法的主体了，从一个简单循环开始：

while (true) {
}

除非另有说明，本节其余代码将按所示顺序出现在这个循环内部。

从这里开始，第一步是检查目标状态。本例中，目标是找到玩家遵循到下一个航点的路径，当节点对象位置是 (endx,endy) 时发生。因此，要检查目标状态，程序需要检查 node 是否到达这些坐标。这个检查应该如下：

if (node->x == endx && node->y == endy) {
    makeList<WIDTH, HEIGHT>(node, allNodes, path);
    return true;
}

目标状态满足时，程序向调用者报告 true，并用最终路径填充 path。现在，假设名为 makeList() 的函数可以为你填充 path；我很快就会展示这个函数。如果目标状态不满足，你需要扩展 node 的子节点，这实际上是一个相当复杂的过程：

auto children = node->getChildren(WIDTH, HEIGHT);
for (auto c = children.begin(); c != 
children.end(); c++) {
  if (map[(*c)->x][(*c)->y] == BLOCKING) continue;
    auto found = std::find(allNodes.rbegin(), 
allNodes.rend(), *c);
  if (found != allNodes.rend()) {
      if (*found > *c) {
          (*found)->g = (*c)->g;
          (*found)->parent = (*c)->parent;
          (*found)->updateScore(endx, endy);
      }
    } else {
        (*c)->updateScore(endx, endy);
      frontier.push(*c);
      allNodes.push_back(*c);
    }
}

调用 node->getChildren 生成可添加到前沿的节点列表后，代码遍历每个子节点，忽略任何在阻挡瓦片上的节点①。接下来，对每个子节点，代码检查相同坐标处是否已经打开节点②。如果是，并且现有节点的分数大于新子节点的分数，③处的 if() 语句把现有节点更新为新子节点的父节点、成本和分数。如果新子节点没有「异父兄弟」，它会按原样添加到前沿④和节点列表⑤。

还要注意 std::find 使用 allNodes 的反向 begin 和反向 end 迭代器，而不是常规迭代器①。示例这样做是因为新节点追加到向量末尾，重复节点会靠得很近，所以重复通常更接近向量末尾。（这一步也可以直接针对前沿完成，但 std::priority_queu e 不允许迭代节点，就地编写排序会让代码太大，无法印刷。）

最终，函数会用完可以添加到前沿的新子节点；以下 if()语句处理这种情况：

if (frontier.size() == 0) return false;
 node = frontier.top();
 frontier.pop();

这段代码把 node 指向前沿中最便宜的节点①，把它从前沿移除②，让循环重复。如果前沿变空，函数向调用者报 false，因为没有剩余可搜索的内容。