跳转至

创建 A* 节点

首先，定义一个空的 AStarNode 类，如下所示：

typedef std::shared_ptr<class AStarNode> 
AStarNodePtr;
class AStarNode
{
public:
};

这段代码定义 AStarNode 类，以及名为 AStarNodePtr 的 std::shared_ptr 类型定义，让创建指向类的安全指针更容易。

接下来，在类的公共作用域中，声明节点 x 位置、y 位置、成本和节点分数的成员变量：

int x, y;
int g, score;

此外，你需要一个引用父节点的 AStarNodePtr 类型的公共成员：

AStarNodePtr parent;

声明完所有成员变量后，声明一个在创建实例时初始化它们的公共构造函数，如下所示：

AStarNode(int x, int y, int cost, AStarNodePtr p, 
int score = 0)
    : x(x), y(y), g(cost), score(score), parent(p)
{}

现在，为了让创建安全指针更容易，添加一个这样的静态辅助函数：

static AStarNodePtr makePtr(
    int x, int y, int cost,
    AStarNodePtr p,
    int score = 0)
{
    return AStarNodePtr(new AStarNode(x, y, cost, 
p, score));
}

这个 makePtr() 函数创建 AStarNode 的新实例，并返回包装在 AStarNodePtr 中的实例。

让我们回顾一下。AStarNode 类有成员变量 x、y、g、score 和 parent。类构造时，所有这些成员都用传给构造函数的值初始化，score 除外，它是可选的（因为你只在复制 AStarNode 实例时使用它），未提供时设为 0。

接下来，定义目标坐标时计算启发式的公共成员函数：

int heuristic(const int destx, int desty) const
{
    int xd = destx - x;
    int yd = desty - y;
  return abs(xd) + abs(yd);
}

这个函数返回曼哈顿距离启发式①，一种为不允许对角移动的网格设计的距离计算：∆x + ∆y。

要计算允许对角移动的路径，你需要修改这个函数使用欧几里得距离启发式，看起来像这样：

(∆x × ∆x) + (∆y × ∆y)

类还需要一个更新分数的函数。你把那个函数添加到公共作用域，如下所示：

#define TILE_COST 1
void updateScore(int endx, int endy)
{
    auto h = this->heuristic(endx, endy) * 
TILE_COST;
    this->score = g + h;
}

现在，给定计算 h 的目标坐标时，score 应该变为 g + h。

最后，节点类还需要一个能计算其所有子节点的函数。函数可以通过为与当前节点相邻的每个瓦片创建新节点来做到这一点。每个新节点把当前节点作为父节点引用，所以类还需要能够创建指向当前节点副本的 AStarNodePtr。以下展示了这一切如何运作：

AStarNodePtr getCopy()
{
    return AStarNode::makePtr(x, y, g, parent, 
score);
}
std::vector<AStarNodePtr> getChildren(int width, 
int height)
{
    std::vector<AStarNodePtr> ret;
    auto copy = getCopy();
    if (x > 0)
      ret.push_back(AStarNode::makePtr(x - 1, y, 
g + TILE_COST, copy));
    if (y > 0)
      ret.push_back(AStarNode::makePtr(x, y - 1, 
g + TILE_COST, copy));
    if (x < width - 1)
      ret.push_back(AStarNode::makePtr(x + 1, y, 
g + TILE_COST, copy));
    if (y < height - 1)
      ret.push_back(AStarNode::makePtr(x, y + 1, 
g + TILE_COST, copy));
    return ret;
}

这个函数在 (x – 1, y)①、(x, y – 1)②、(x + 1, y)③和 (x, y+ 1)④创建子节点。它们的父节点是调用 getChildren 的节点，它们的 g 是父节点的 g 加 TILE_COST。

要允许对角移动，这个函数需要在 (x – 1, y – 1)、(x + 1,y – 1)、(x + 1, y + 1) 和 (x – 1, y + 1) 添加子节点。此外，如果对角移动成本更高——即角色需要更多时间——你还需要做以下事情：

(cid:127)把 TILE_COST 改为 10。

(cid:127)定义常量 DIAG_TILE_COST 为 TILE_COST 乘以时间增加

量。如果对角步长耗时 1.5 倍，DIAG_TILE_COST 就是 15。

(cid:127)给对角子节点一个父节点 g 加 DIAG_TILE_COST 的 g。

为了完成 AStarNode，声明比较两个节点优先级和平等性的操作符。你可以把这些声明放在类外的全局作用域：

 bool operator<(const AStarNodePtr &a, const 
AStarNodePtr &b)
{
}
 bool operator==(const AStarNodePtr &a, const 
AStarNodePtr &b)
{
    return a.x == b.x && a.y == b.y;
}

这些操作符让 std::priority_queue 按分数排序节点①，让 std::find 按位置确定节点相等性②。