首先定义节点结构体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; // 指向父节点，用于回溯路径
<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 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 <vector>
#include <algorithm>
#include <iostream>
<p>using namespace std;</p><div class="aritcle_card flexRow">
<div class="artcardd flexRow">
<a class="aritcle_card_img" href="/ai/1351" title="云从科技AI开放平台"><img
src="https://img.php.cn/upload/ai_manual/001/431/639/68b6d5e4278fa465.png" alt="云从科技AI开放平台" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a href="/ai/1351" title="云从科技AI开放平台">云从科技AI开放平台</a>
<p>云从AI开放平台</p>
</div>
<a href="/ai/1351" title="云从科技AI开放平台" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span> </a>
</div>
</div><p>// 地图大小和障碍物定义
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}
};</p><p>vector<Node<em>> getNeighbors(Node</em> node) {
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
vector<Node*> neighbors;</p><pre class='brush:php;toolbar:false;'>for (int i = 0; i < 4; ++i) {
int nx = node->x + dx[i];
int ny = node->y + dy[i];
if (nx >= 0 && nx < ROW && ny >= 0 && ny < COL && !maze[nx][ny]) {
neighbors.push_back(new Node(nx, ny));
}
}
return neighbors;}
vector<Node> aStar(int start_x, int start_y, int end_x, int end_y) { vector<Node> openList; vector<Node> 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() < b->f(); });
Node* current = *current_it;
// 到达终点
if (*current == *end) {
vector<Node> 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 < existing->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<Node> path = aStar(0, 0, 4, 4);
<pre class='brush:php;toolbar:false;'>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对象而非指针。
基本上就这些。
