✨简介A*算法是人工智能、游戏开发、机器人路径规划中最经典的启发式寻路算法。相比于BFS盲目搜索A*通过启发函数定向搜索效率更高、路径最优。本文基于C语言实现4方向A*寻路附带完整源码、逐行解析、案例演示、优缺点总结零基础也能看懂[TOC](文章目录)一、A*算法核心介绍1.1 算法定位A*A-Star是一种基于启发式搜索的最优路径算法结合了Dijkstra算法的稳定性和贪心算法的高效性BFS盲目遍历所有节点无方向效率低贪心算法只看终点距离容易绕路无法保证最优解A*算法综合实际代价预估代价高效且保证最短路径1.2 核心公式A*算法通过代价函数F G H筛选最优节点G(g)实际代价从起点移动到当前节点的真实步数H(h)启发预估代价当前节点到终点的预估距离本文使用曼哈顿距离F(f)综合代价F值越小节点优先级越高优先遍历曼哈顿距离公式4方向移动专用$$H |x_1 - x_2| |y_1 - y_2|$$二、算法执行流程初始化地图、节点信息、开启列表、关闭列表将起点加入开启列表初始化起点代价G0循环遍历开启列表选出F值最小的节点作为当前节点若当前节点是终点回溯父节点生成最优路径若开启列表为空判定无可行路径遍历当前节点上下左右四个方向邻节点更新代价与父节点信息将当前节点移入关闭列表重复循环直至找到终点。三、测试地图案例本文采用5×5网格地图0代表可通行区域1代表障碍物起点(0,0) nbsp;终点(4,4)地图布局行0: 0 0 0 0 0 行1: 0 1 0 1 0 行2: 0 0 0 1 0 行3: 0 1 1 1 0 行4: 0 0 0 0 0障碍物坐标(1,1)、(1,3)、(2,3)、(3,1)、(3,2)、(3,3)四、完整可运行源码代码纯C语言实现无依赖库支持任意尺寸网格地图直接复制即可编译运行#include stdio.h #include stdlib.h #include stdbool.h #include limits.h // 定义地图行列数 #define ROWS 5 #define COLS 5 // 全局地图0可通行 1障碍物 int grid[ROWS][COLS] { {0, 0, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 0, 0} }; // 节点结构体存储每个网格的代价、父节点、状态 typedef struct { int r, c; // 当前节点坐标 int g; // 起点到当前点实际代价 int h; // 当前点到终点预估代价 int parent_r, parent_c; // 父节点坐标用于回溯路径 bool in_open; // 是否在开启列表中 } Node; /** * brief 曼哈顿距离启发函数 * param r1,c1 当前节点坐标 * param r2,c2 终点坐标 * return 预估距离 */ int heuristic(int r1, int c1, int r2, int c2) { return abs(r1 - r2) abs(c1 - c2); } /** * brief A*寻路核心函数 * param sr,sc 起点坐标 * param er,ec 终点坐标 */ void astar(int sr, int sc, int er, int ec) { Node nodes[ROWS][COLS]; bool closed[ROWS][COLS] {false}; // 关闭列表已遍历节点 // 1. 初始化所有节点信息 for (int i 0; i ROWS; i) { for (int j 0; j COLS; j) { nodes[i][j].r i; nodes[i][j].c j; nodes[i][j].g INT_MAX; // 初始实际代价无穷大 nodes[i][j].h heuristic(i, j, er, ec); // 初始化启发代价 nodes[i][j].parent_r -1; nodes[i][j].parent_c -1; nodes[i][j].in_open false; } } // 初始化起点 nodes[sr][sc].g 0; nodes[sr][sc].in_open true; // 上下左右4个移动方向 int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // A*主循环 while (1) { // 2. 遍历开启列表找到F值最小的节点 int minF INT_MAX; int cr -1, cc -1; for (int i 0; i ROWS; i) { for (int j 0; j COLS; j) { if (nodes[i][j].in_open !closed[i][j]) { int f nodes[i][j].g nodes[i][j].h; if (f minF) { minF f; cr i; cc j; } } } } // 开启列表为空无路径 if (cr -1) { printf(无可行路径\n); return; } // 3. 到达终点回溯输出路径 if (cr er cc ec) { int path_r[100], path_c[100]; int len 0; int r er, c ec; // 从终点反向回溯到起点 while (r ! -1) { path_r[len] r; path_c[len] c; len; int pr nodes[r][c].parent_r; int pc nodes[r][c].parent_c; r pr; c pc; } // 正向输出路径 printf(✅ A*最优寻路路径\n); for (int i len - 1; i 0; i--) { printf((%d,%d) , path_r[i], path_c[i]); } printf(\n 路径总长度%d\n, len); return; } // 当前节点加入关闭列表不再重复遍历 closed[cr][cc] true; nodes[cr][cc].in_open false; // 4. 遍历四个方向邻节点更新代价 for (int d 0; d 4; d) { int nr cr dirs[d][0]; int nc cc dirs[d][1]; // 边界判断、障碍物判断、已关闭节点判断 if (nr 0 || nr ROWS || nc 0 || nc COLS) continue; if (grid[nr][nc] 1 || closed[nr][nc]) continue; // 计算新的实际代价 int ng nodes[cr][cc].g 1; // 新路径更优则更新节点信息 if (ng nodes[nr][nc].g) { nodes[nr][nc].g ng; nodes[nr][nc].parent_r cr; nodes[nr][nc].parent_c cc; nodes[nr][nc].in_open true; } } } } int main(void) { // 起点(0,0) 终点(4,4) astar(0, 0, 4, 4); return 0; }五、代码逐模块解析5.1 结构体设计自定义Node结构体封装每个网格节点的所有属性统一管理代价、坐标、父节点、遍历状态逻辑清晰便于维护。5.2 启发函数设计采用曼哈顿距离适配上下左右4方向移动场景计算简单、效率高是网格寻路的最优启发函数。5.3 核心遍历逻辑每次迭代筛选F值最小的节点优先扩展保证搜索方向始终朝向终点避免无效遍历兼顾搜索效率与路径最优性。5.4 路径回溯机制到达终点后通过父节点坐标反向回溯整条路径再反转输出正向行走路线完美还原完整寻路轨迹。六、程序运行结果编译运行代码后输出最优路径如下✅ A*最优寻路路径 (0,0) (0,1) (0,2) (0,3) (0,4) (1,4) (2,4) (3,4) (4,4) 路径总长度9结果分析算法成功避开所有障碍物规划出最短可行路径无绕路、无死角完美验证A*算法最优性。七、算法优缺点总结✅ 优点具备启发搜索能力相比BFS效率大幅提升在启发函数合理的前提下一定能找到全局最优路径逻辑清晰、实现简单适配网格地图场景广泛应用于游戏寻路、机器人导航、自动驾驶路径规划❌ 缺点本文采用暴力遍历查找最小F值大数据场景效率较低可优化为最小堆仅支持4方向移动无法适配斜向移动场景依赖启发函数设计H值不合理会导致丢失最优解八、优化拓展方向最小堆优化替换暴力遍历将时间复杂度大幅降低8方向移动增加对角线移动方向适配更多场景可视化输出打印带路径标记的地图直观展示寻路轨迹动态地图支持动态修改障碍物实现实时寻路。九、总结A*算法是路径规划领域的入门必学算法相比传统暴力搜索通过FGH的启发策略实现了高效且精准的最优路径搜索。本文的C语言实现代码简洁、注释详细、适配新手可直接用于课程作业、算法入门学习与项目二次开发。