首先定义节点结构体Node，包含坐标、g值（起点到当前点代价）、h值（启发式估计终点代价）和父指针；采用曼哈顿距离作为启发函数；在A*主循环中维护openList与closedList，每次从openList中选取f=g+h最小的节点扩展，检查邻居并更新代价，若到达终点则回溯路径；最后返回从起点到终点的最短路径序列。
实现一个简单的A*（A星）寻路算法，核心是结合Dijkstra的广度优先搜索和启发式函数来找到最短路径。下面是一个基于二维网格地图的C++简单实现方法。
1. 定义节点结构
每个格子看作一个节点，记录其位置、代价和父节点。
struct Node { int x, y; int g; // 从起点到当前点的实际代价 int h; // 启发函数估计到终点的代价 int f() const { return g + h; } // 总代价 Node* parent; // 指向父节点，用于回溯路径Node(int x, int y) : x(x), y(y), g(0), h(0), parent(nullptr) {}bool operator==(const Node& other) const { return x == other.x && y == other.y;}
};
2. 启发函数与距离计算
使用曼哈顿距离作为启发函数，适合4方向移动。
立即学习“C++免费学习笔记（深入）”；
int heuristic(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2);}
3. A* 核心逻辑
维护两个列表：openList（待处理）和closedList（已处理）。每次从openList中取出f值最小的节点进行扩展。
#include #include #includeusing namespace std;
// 地图大小和障碍物定义const int ROW = 5, COL = 5;bool maze[ROW][COL] = {{0, 0, 0, 1, 0},{0, 1, 0, 1, 0},{0, 1, 0, 0, 0},{0, 0, 0, 1, 1},{0, 0, 0, 0, 0}};
vector<Node> getNeighbors(Node node) {int dx[] = {-1, 1, 0, 0};int dy[] = {0, 0, -1, 1};vector neighbors;
for (int i = 0; i x + dx[i]; int ny = node->y + dy[i]; if (nx >= 0 && nx = 0 && ny < COL && !maze[nx][ny]) { neighbors.push_back(new Node(nx, ny)); }}return neighbors;
}
vector aStar(int start_x, int start_y, int end_x, int end_y) {vector> openList;vector> closedList;Node start = new Node(start_x, start_y);Node end = new Node(end_x, end_y);
start->h = heuristic(start_x, start_y, end_x, end_y);openList.push_back(start);while (!openList.empty()) { // 找出f最小的节点 auto current_it = min_element(openList.begin(), openList.end(), [](Node* a, Node* b) { return a->f() f(); }); Node* current = *current_it; // 到达终点 if (*current == *end) { vector path; while (current != nullptr) { path.push_back(Node(current->x, current->y)); current = current->parent; } reverse(path.begin(), path.end()); // 释放内存 for (auto node : openList) delete node; for (auto node : closedList) delete node; delete end; return path; } openList.erase(current_it); closedList.push_back(current); for (Node* neighbor : getNeighbors(current)) { // 如果已在closedList，跳过 if (find_if(closedList.begin(), closedList.end(), [neighbor](Node* n) { return *n == *neighbor; }) != closedList.end()) { delete neighbor; continue; } int tentative_g = current->g + 1; auto it = find_if(openList.begin(), openList.end(), [neighbor](Node* n) { return *n == *neighbor; }); if (it == openList.end()) { neighbor->g = tentative_g; neighbor->h = heuristic(neighbor->x, neighbor->y, end_x, end_y); neighbor->parent = current; openList.push_back(neighbor); } else { Node* existing = *it; if (tentative_g g) { existing->g = tentative_g; existing->parent = current; } delete neighbor; } }}// 没有找到路径for (auto node : openList) delete node;for (auto node : closedList) delete node;delete end;return {}; // 返回空路径
}
4. 使用示例
调用aStar函数并输出结果。
int main() { vector path = aStar(0, 0, 4, 4);if (path.empty()) { cout << "No path found!" << endl;} else { cout << "Path found:" << endl; for (const auto& p : path) { cout << "(" << p.x << "," << p.y << ") "; } cout << endl;}return 0;
}
这个实现虽然简单，但包含了A*的核心思想：g值表示真实代价，h值为启发估计，通过优先队列（这里用vector模拟）选择最优节点扩展。适合学习理解A*原理。
注意：为了简化，上面代码手动管理内存。实际项目建议使用智能指针或直接存储Node对象而非指针。
基本上就这些。
以上就是c++++怎么实现一个简单的A寻路算法_c++简单A寻路实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1476857.html
微信扫一扫 
支付宝扫一扫 
