A*算法通过评估函数f=g+h结合Dijkstra的完备性和贪心搜索的高效性，在二维网格中寻最优路径；使用优先队列扩展节点，曼哈顿距离作启发函数，记录g、h、f值及父节点回溯路径，最终实现从起点到终点的完整路径规划。
在C++游戏AI开发中，A*（A星）寻路算法是路径规划的核心技术之一。它结合了Dijkstra算法的完备性和贪心搜索的高效性，通过评估函数快速找到从起点到终点的最优路径。下面用简洁的方式实现一个基础但可用的A*算法，适用于二维网格地图。
1. 定义地图与节点结构
假设地图是一个二维网格，0表示可通过，1表示障碍物。每个节点记录坐标、代价信息以及父节点用于回溯路径。
#include <vector>
#include <queue>
#include <cmath>
#include <iostream>
<p>struct Node {
int x, y;
float g, h; // g: 实际代价，h: 启发值
float f() const { return g + h; }
Node* parent;</p><pre class='brush:php;toolbar:false;'>Node(int x, int y) : x(x), y(y), g(0), h(0), parent(nullptr) {}
bool operator<(const Node& other) const {
return f() > other.f(); // 优先队列需要最小堆
}};
2. 启发函数与邻居生成
使用曼哈顿距离作为启发函数，适合四方向移动。若支持八方向，可改用对角线距离或欧几里得距离。
立即学习“C++免费学习笔记（深入）”；
float heuristic(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2); // 曼哈顿距离
}
<p>std::vector<std::pair<int, int>> getNeighbors(int x, int y) {
return {{x+1,y}, {x-1,y}, {x,y+1}, {x,y-1}};
// 若允许斜向移动，可加入 {x+1,y+1}, {x+1,y-1} 等
}</p>3. A* 核心算法实现
使用优先队列管理待处理节点，集合记录已访问位置，避免重复扩展。
std::vector<Node*> aStar(const std::vector<std::vector<int>>& grid,
Node* start, Node* end) {
int rows = grid.size();
int cols = grid[0].size();
<pre class='brush:php;toolbar:false;'>auto isValid = [&](int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 0;
};
std::priority_queue<Node> openList;
std::vector<std::vector<bool>> closedList(rows, std::vector<bool>(cols, false));
std::vector<std::vector<Node*>> nodeMap(rows, std::vector<Node*>(cols, nullptr));
for (int i = 0; i < rows; ++i)
for (int j = 0; j < cols; ++j)
if (grid[i][j] == 0)
nodeMap[i][j] = new Node(i, j);
start = nodeMap[start->x][start->y];
end = nodeMap[end->x][end->y];
start->h = heuristic(start->x, start->y, end->x, end->y);
openList.push(*start);
while (!openList.empty()) {
Node current = openList.top(); openList.pop();
if (closedList[current.x][current.y]) continue;
closedList[current.x][current.y] = true;
if (current.x == end->x && current.y == end->y) {
// 回溯路径
std::vector<Node*> path;
Node* p = end;
while (p != nullptr) {
path.push_back(p);
p = p->parent;
}
return path;
}
for (auto& [nx, ny] : getNeighbors(current.x, current.y)) {
if (!isValid(nx, ny) || closedList[nx][ny]) continue;
Node* neighbor = nodeMap[nx][ny];
float tentativeG = current.g + 1; // 假设每步代价为1
if (tentativeG < neighbor->g || !closedList[nx][ny]) {
neighbor->parent = &const_cast<Node&>(current);
neighbor->g = tentativeG;
neighbor->h = heuristic(nx, ny, end->x, end->y);
openList.push(*neighbor);
}
}
}
return {}; // 无路径}
4. 使用示例与清理资源
演示如何调用并输出结果。注意实际项目中建议使用智能指针或对象池管理内存。
int main() {
std::vector<std::vector<int>> grid = {
{0, 0, 0, 1, 0},
{0, 1, 0, 1, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 0}
};
<pre class='brush:php;toolbar:false;'>Node* start = new Node(0, 0);
Node* end = new Node(4, 4);
auto path = aStar(grid, start, end);
if (!path.empty()) {
std::cout << "Found path:\n";
for (auto it = path.rbegin(); it != path.rend(); ++it) {
std::cout << "(" << (*it)->x << "," << (*it)->y << ") ";
}
std::cout << "\n";
} else {
std::cout << "No path found.\n";
}
// 简单释放（实际应遍历所有创建的节点）
for (auto& row : grid)
for (auto val : row)
if (val == 0) /* 伪代码 */ delete /* 对应节点 */;
delete start; delete end;
return 0;}
基本上就这些。这个实现虽然简单，但展示了A*在C++中的核心逻辑：代价评估、优先扩展、路径回溯。在真实游戏中，你可以进一步优化数据结构（如使用索引代替指针）、支持动态障碍、多单位协同避让等。不复杂但容易忽略细节，比如防止重复入队和正确更新g值。掌握基础后，扩展性强。
