A*算法在游戏自动化中的应用与实践
传统路径算法的局限性与A*算法的诞生
在路径搜索问题中，某些算法虽然能找到最快路径，但代价巨大。例如，若围绕障碍物的路径长度为 50 个单位，该算法可能会打开约 7,854 个节点（通过公式 π × 50² = 7,854 计算）。而贪心最佳优先搜索虽能较快计算出路径，但并非最优解。
为快速计算出最优路径，人们将 Dijkstra 算法与贪心最佳优先搜索融合，得到了 A搜索算法（常简称为 A）。A* 算法使用代价 g 和启发式函数 h 的和（即 score = g + h）来选择节点，既能像 Dijkstra 算法一样计算出从 a 到 b 的最优路径，又能像贪心最佳优先搜索一样相对快速地完成计算。
实现 A* 算法
以下是实现 A* 算法的详细步骤和代码：
创建 A* 节点类
typedef std::shared_ptr<class AStarNode> AStarNodePtr; class AStarNode { public: int x, y; int g, score; 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(
