做机器人路径规划、扫地机、无人机仿真或者单纯是学校课程设计A星算法A*基本都是绕不过去的第一道坎。我最早接触就是在Matlab里跑栅格地图手动摆障碍、改起点终点看那条蓝色路径怎么绕出来的。这篇就把完整的Matlab实现思路写一遍从核心原理、数学公式到可以直接改的地图与障碍生成、自定义起点终点的完整脚本最后是常见的坑。适合要跑课设、做毕设或者刚入门路径规划需要在Matlab里快速搭一套A*验证环境的朋友。说句实在话A这个名字听起来学术味很重但它的思想特别朴素人在一个陌生小区里找路不也会优先挑那些“看起来离出口更近”的方向走吗A就是把这种直觉量化成公式再用代码一步步执行。真正动手写下来你会发现完整实现也就一百行左右难的不是代码而是把地图建模、启发函数、邻域选择这些细节理顺。1. 这个项目到底在解决什么问题核心需求拆解1.1 一个最朴素的需求从A点到B点怎么走先说个生活场景。早上出门从小区门口到地铁站你肯定不乐意走最远的直线绕弯也不会选择一条被早市摊位挡死的路。要的是距离短、没有障碍、走起来顺畅。机器人、游戏里的NPC、自动导引小车本质上都在解决同一个问题已知地图和障碍从起点到终点找一条最优或近似最优的路。这就是路径规划。路径规划算法里A星也就是A*是最经典、最常被用作入门的第一课也是大量工程系统里真正落地使用的基础模块。它用“启发式搜索”这么一种思路把盲目搜索变成了有方向感的搜索效果和速度都很直观也好调试。那么这个项目在做什么标题说得很明白用Matlab实现A星路径规划算法地图、障碍物、起点、终点都能自己改。拆开看就是三件事一是把地图离散成栅格二是把A*算法跑通三是整个流程可视化随时改参数看结果。对课程设计、毕业设计、甚至是刚接触移动机器人导航的开发人员来说这套小系统是很好的试验台。算法本身不复杂但能让你在最短时间内把路径规划从概念变成可运行的代码。1.2 A*算法的基本逻辑f g h两张表走完搜索A的核心是一句话每一步都选f值最小的节点去扩展。f代表这个节点“总的预计代价”等于g加h。g是从起点走到当前节点已经花掉的代价h是当前节点到终点还需要的预估代价。A每走一步都会把当前能到达的节点放进open list待检查列表把已经检查过的节点放进close list关闭列表然后不断从open list里挑f最小的那个节点拿出来看看它的邻居们能不能用更小代价到达能就更新直到把终点从open list里挑出来为止。理解这个逻辑的关键在h。h是我们“猜”的剩余距离猜得越准搜索越有方向越少走弯路猜过头了就可能漏掉真正的最短路径。这里有很多可以调整的细节比如曼哈顿距离、欧氏距离、对角线距离我在后面专门说。总之A*能火这么多年就是因为它在“找到最优”和“搜索够快”之间给了你一个非常直观的调节旋钮。1.3 为什么要把地图、障碍、起终点都做成可配置我见过不少同学写路径规划第一版通常是把地图写死在主脚本里测试一个场景改一次代码。这种写法不是不行但验证算法效果、展示结果、跟别人讨论方案的时候非常别扭。想象一下你要给老师或者同事演示A*在不同障碍布局下的表现每换一个场景都得去翻矩阵、改数字、重新调试效率极低。把地图和起终点作为输入参数抽出来是这个项目真正的小设计。它的好处有两个一是你可以在同一份代码上快速做大量实验观测算法在不同障碍密度、不同起点终点组合下的路径形状、搜索节点数、耗时变化二是代码结构更接近真实工程——真实系统里地图来自传感器或者地图服务起点终点来自任务调度器算法模块永远不应该假设“地图是某个固定矩阵”。所以这个“可配置”的需求并不是额外加戏而是一种正确的模块化思路。2. A星算法核心原理先把 f g h 吃透2.1 地图建模栅格地图为什么是最顺手的选择路径规划里的地图有好几种表示方式。常见的有栅格地图把空间划成等间距的格子、拓扑地图只保留节点和边、几何地图用几何形状描述环境轮廓。A*最常用的就是栅格地图。原因很朴素矩阵天然就是格子Matlab里一个二维矩阵直接就是一张图1表示可通过0表示障碍显示出来黑白分明非常直观。栅格地图的代价就是格子粒度粒度越细路径越平滑但计算量越大这个在真实机器人里要根据车体尺寸和定位精度权衡。作为学习和仿真用20乘30、50乘50这种规模的地图足够了。写代码时有个容易踩的坐标坑Matlab矩阵的索引是行和列行对应图像里的纵坐标从上往下递增列对应横坐标从左往右递增。而很多人习惯x和y的笛卡尔坐标画图时plot(横坐标, 纵坐标)。一旦搞混路径会显示得扭曲起点终点也会对不上。我的经验是在代码内部一律用[row, col]来思考和处理只在最后可视化时把col当成x、row当成y去plot。2.2 三种距离函数怎么选曼哈顿、欧氏、对角线距离对比启发函数h的选择直接决定搜索效率和路径质量。栅格地图里三种距离最常用我列个对比表距离函数公式适合的邻域特点曼哈顿距离h abs(dx) abs(dy)4邻域计算最快栅格A*最常用在有对角线移动的地图上会略微低估代价欧氏距离h sqrt(dx^2 dy^2)8邻域/任意方向符合几何直觉但相对于栅格代价偏低搜索范围偏大对角线距离h max(dx, dy) (sqrt(2)-1) * min(dx, dy)8邻域精确匹配对角线移动代价效果最均衡我个人的默认选择是如果只允许上下左右走用曼哈顿距离如果允许斜着走用对角线距离。欧氏距离在8邻域里能用但效率上没优势。还要记住一个原则h不能大于实际的最小可能代价否则A不再保证找到最优路径。h越大搜索越快但越“激进”h越小搜索越慢但越“保守”当h等于0的时候A就退化成了Dijkstra算法。2.3 邻域选择4邻域还是8邻域这个决定路径形态地图上从一个格子到另一个格子每一步能走的方向数是另一个关键设计。4邻域只允许上下左右走每一步代价设为1路径必然是直角折线型适合模拟普通轮式机器人或者只能在巷道里行驶的AGV。8邻域多了四个对角线方向路径可以斜着走更接近人走路的习惯但代价处理要让对角线方向的移动是根号2否则斜走和直走等代价路径会显得很怪。8邻域有一个必须处理的问题斜着穿墙。如果当前格子右方是墙下方是墙右下方却是空地算法可能直接从右上角穿到右下角视觉上就是穿过了墙角。解决办法是在允许对角移动前做一次检查只有当水平方向和垂直方向的两个邻居都可行时才允许走斜对角。这个检查成本极低但效果立竿见影。下面在实现代码里我会把我常用的写法放进去。2.4 open list和close list数据结构决定搜索效率A*逻辑上就靠两张表open list存“还没被最终确定的候选节点”close list存“已经确定最短路径代价的节点”。每次从open list中取f最小的节点把它移入close list再扩展邻居。如果新路径让某个邻居的g更小就更新它的g、f和父节点。这套机制理解起来不难但用Matlab实现时有一个性能上的坑如果每次都用矩阵存储open list然后min找最小的f在几百个格子里没问题但地图到几百乘几百时就会越来越慢。更快的做法是使用优先队列最小堆管理open list这样取最小值和插入节点的时间复杂度从O(n)降到了O(logn)。Matlab没有内置的堆结构但可以用containers.Map、自定义类或者干脆继续用矩阵但多做剪枝。对大部分学习和课设场景用矩阵加min函数就够用我在代码里先用最直观的写法后面再讲怎么优化。3. Matlab完整实现从地图生成到路径可视化3.1 生成地图的三种方式写死障碍、随机障碍、鼠标画障碍先把最基本的地图生成做了。我建议把地图初始化写成一个独立脚本或者函数方便随时换场景。最简单的方式是直接对矩阵赋值map ones(20, 30); % 20行30列1表示可通行 map(3:4, 8:12) 0; % 一堵横向墙 map(10:15, 18:20) 0; % 一堵竖向墙 map(17:18, 6:9) 0; % 左下角墙 map(7:9, 24:27) 0; % 右上角墙如果想把边界也封起来可以直接把map最外圈置0避免算法跑出地图边界不过我的代码里本身有边界检查所以不封也没关系。需要随机障碍的话可以按一定概率把格子置0再结合形态学处理避免障碍太碎。更直观的方式是用Matlab的ginput鼠标点击画障碍区域figure; imagesc(map); colormap(gray); axis image; disp(鼠标左键点击画障碍右键结束); while true [x, y, button] ginput(1); if button ~ 1, break; end row round(y); col round(x); if row 1 row size(map,1) col 1 col size(map,2) map(row, col) 0; imagesc(map); colormap(gray); axis image; end end注意这里ginput返回的x是横坐标对应矩阵的列y是纵坐标对应矩阵的行。很多人随手一写就把行列搞反了然后发现画的障碍和实际位置对不上。3.2 核心A*函数主循环、邻居扩展和路径回溯下面把核心函数写出来。我尽量保持代码短小易读注释写在关键位置。这个函数支持8邻域、对角线穿墙检查、曼哈顿距离启发函数function [path, totalCost] myAstar(map, start, goal) [rows, cols] size(map); if map(start(1), start(2)) 0 || map(goal(1), goal(2)) 0 error(起点或终点在障碍物里); end % 8个搜索方向以及对应移动代价 dirs [-1 -1; -1 0; -1 1; 0 -1; 0 1; 1 -1; 1 0; 1 1]; moveCost [sqrt(2) 1 sqrt(2) 1 1 sqrt(2) 1 sqrt(2)]; % 初始化代价表和父节点表 gScore inf(rows, cols); fScore inf(rows, cols); cameFrom cell(rows, cols); gScore(start(1), start(2)) 0; fScore(start(1), start(2)) calH(start, goal); % open list每一行是 [行, 列, f值] openSet [start(1) start(2) fScore(start(1), start(2))]; closedSet false(rows, cols); while ~isempty(openSet) % 取f最小的节点 [~, idx] min(openSet(:, 3)); current openSet(idx, 1:2); if isequal(current, goal) path backtrace(cameFrom, start, goal); totalCost gScore(goal(1), goal(2)); return; end openSet(idx, :) []; closedSet(current(1), current(2)) true; % 扩展8个邻居 for k 1:size(dirs, 1) nr current(1) dirs(k, 1); nc current(2) dirs(k, 2); if nr 1 || nr rows || nc 1 || nc cols continue; end if map(nr, nc) 0 || closedSet(nr, nc) continue; end % 斜向移动穿墙检测 if abs(dirs(k,1)) 1 abs(dirs(k,2