基于Astar算法的智能避障最短路径搜索matlab仿真,可以任意选择起点和终点

1.算法仿真效果 matlab2022a仿真结果如下：

2.算法涉及理论知识概要 Astar算法是一种图形搜索算法,常用于寻路。它是个以广度优先搜索为基础,集Dijkstra算法与最佳优先(best fit)算法特点于一身的一种 算法。它通过下面这个函数来计算每个节点的优先级,然后选择优先级最高的节点作为下一个待遍历的节点。

   AStar（又称 A*），它结合了 Dijkstra 算法的节点信息（倾向于距离起点较近的节点）和贪心算法的最好优先搜索算法信息（倾向于距离目标较近的节点）。可以像 Dijkstra 算法一样保证找到最短路径，同时也像贪心最好优先搜索算法一样使用启发值对算法进行引导。简单点说，AStar的核心在于将游戏背景分为一个又一个格子，每个格子有自己的靠谱值，然后通过遍历起点的格子去找到周围靠谱的格子，接着继续遍历周围…… 最终找到终点。

实现步骤:

1.把起始格添加到开启列表。

2.重复如下的工作：

a) 寻找开启列表中估量代价F值最低的格子。我们称它为当前格。

b) 把它切换到关闭列表。

c) 对相邻的8格中的每一个进行如下操作

• 如果它不可通过或者已经在关闭列表中，略过它。反之如下。

• 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。

• 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。

d) 停止，

• 把目标格添加进了关闭列表(注解)，这时候路径被找到，或者

• 没有找到目标格，开启列表已经空了。这时候，路径不存在。

3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。

3.MATLAB核心程序

while((xNode ~= xTarget || yNode ~= yTarget) && NoPath == 1)       %%%  判断当前点是否等于目标点
 
 exp_array=expand_array(xNode,yNode,path_cost,xTarget,yTarget,CLOSED,MAX_X,MAX_Y);  %%% 不在关闭列表的子节点，（x,y,gn,hn,fn）,列数是个数
 exp_count=size(exp_array,1);   %%%  可选择的子节点个数
 
 for i=1:exp_count         %%% 把exp_array内的元素添加到 开启列表 里面
    flag=0;                %%% 将exp_array内的点的标志位设为0
    for j=1:OPEN_COUNT         %%% OPEN_COUNT 从1开始，自加
        if(exp_array(i,1) == OPEN(j,2) && exp_array(i,2) == OPEN(j,3) )    %%%判断可选子节点是否与OPEN[]中的点相同
            OPEN(j,8)=min(OPEN(j,8),exp_array(i,5));                       %%%如果相同，比较两个fn的值的大小，并将fn小的坐标点赋值给OPEN(j,8)
......................................................................................
 
  else
      NoPath=0;
  end
end
 
i=size(CLOSED,1);    %%%CLOSE里面的长度
Optimal_path=[];     %%%路径数组
xval=CLOSED(i,1);    %%%把CLOSE最后一组数提出来，最后一组数为目标点
yval=CLOSED(i,2);
i=1;
Optimal_path(i,1)=xval; %%%把目标点的坐标赋给 路径数组的 第一组
Optimal_path(i,2)=yval;
i=i+1;                  
 
if ( (xval == xTarget) && (yval == yTarget))  %%%检测CLOSE最后一组是否为目标点
    inode=0;
   %Traverse OPEN and determine the parent nodes 遍历OPEN并确定父节点
   parent_x=OPEN(node_index(OPEN,xval,yval),4); %node_index returns the index of the node  node_index返回节点的索引
   parent_y=OPEN(node_index(OPEN,xval,yval),5);%%% 将当前点的父节点提出来
   
   while( parent_x ~= xStart || parent_y ~= yStart)   %%% 判断父节点是否为起始点
           Optimal_path(i,1) = parent_x;             %%% 不是 则将父节点送给路径数组
           Optimal_path(i,2) = parent_y;
           %Get the grandparents:-)
           inode=node_index(OPEN,parent_x,parent_y); 
           parent_x=OPEN(inode,4);%node_index returns the index of the node
           parent_y=OPEN(inode,5);
           i=i+1;
    end;
 toc
    
  j = size(Optimal_path,1) + 1;
  Optimal_path(j,1) = xStart;           
  Optimal_path(j,2) = yStart; %%%把起始点加进去
 
 
 p=plot(Optimal_path(j,1)+.5,Optimal_path(j,2)+.5,'bo'); %%
 j=j-1;
 for i=j:-1:1
  pause(.25);
  set(p,'XData',Optimal_path(i,1)+.5,'YData',Optimal_path(i,2)+.5);
 drawnow ;
 end;