A*算法与matlab实现
A*算法是一种寻路算法，常常被用在游戏智能ai的自动寻路过程等等，它较之于图论的最短路算法而言，更加适用于节点巨大的情况下，但是该算法是一种启发式搜索算法，并不能保证总是找到最优路径。
A*的算法思想如下：
定义两个函数：f和g，其中f揭示当前点到出发点的距离，g揭示当前点到终点的距离。
对于每个将要遍历的点，h=f+g是其启发函数，每次选择待选择节点中启发函数值最大的节点放入路径之中，重复此步骤。
算法具体步骤如下：
- 将方块添加到open列表中，该列表有最小的和值。且将这个方块称为S吧。
- 将S从open列表移除，然后添加S到closed列表中。
- 对于与S相邻的每一块可通行的方块T：
-
- 如果T在closed列表中：不管它。
- 如果T不在open列表中：添加它然后计算出它的和值。
- 如果T已经在open列表中：当我们使用当前生成的路径到达那里时，检查F G和值是否更小。如果是，更新它的和值和它的前继。
因为matlab的画图功能比较强大，所以下面使用matlab实现最基本的A*算法：
function[open,close]=Astar(map)
[row,col]=size(map);
close=struct('row',-1,'col',-1,'g',0,'h',0);%????????????????????????
closelen=1;
open=struct('row',-1,'col',-1,'g',-1,'h',-1);%????????????????????????
openlen=0;
bindex=1;
fork=1:row
forj=1:col
ifmap(k,j)==1
barrierrow(bindex)=-k;
barriercol(bindex)=j;
bindex=bindex+1;
end
end
end
%????????????
fori=1:row
forj=1:col
ifmap(i,j)==2
endrow=i;
endcol=j;
break;
end
end
end
%????????????????????close
fori=1:row
forj=1:col
ifmap(i,j)==5
startrow=i;
startcol=j;
close(1).row=i;
close(1).col=j;
break;
end
end
end
%??????????????????open
%????????
direct=[0 -1;0 1;-1 0;1 0];
fori=1:4
ifall([close(1).row,close(1).col]+direct(i,:)>0) && close(1).row+direct(i,1)<=row && close(1).col+direct(i,2)<=col && map(close(1).row+direct(i,1),close(1).col+direct(i,2))~=1
open(openlen+1).row=close(1).row+direct(i,1);
open(openlen+1).col=close(1).col+direct(i,2);
openlen=openlen+1;
%????g??????h????????
open(openlen).g=1;
open(openlen).h=abs(endrow-open(openlen).row)+abs(endcol-open(openlen).col);
end
end
% close
% open.h
%????????open??colse????????????????????????????????????
whileopenlen>0
%????????????g+h????open????????
min = realmax;
fori=1:openlen
ifopen(i).g+open(i).h<=min
min=open(i).g+open(i).h;
sindex=i;
end
end
%??s????????close????????open??
close(closelen+1).row=open(sindex).row;
close(closelen+1).col=open(sindex).col;
close(closelen+1).g=open(sindex).g;
close(closelen+1).h=open(sindex).h;
closelen=closelen+1;
% openlen=openlen-1;
% for i=sindex:openlen
% open(i)=open(i+1);
% end
% open(openlen+1)=[];
openlen=0;
%??????????
pause(0.3)
img = zeros(row,col);
img(startrow,startcol)=10;
fork=1:row
forj=1:col
ifmap(k,j)==1
img(k,j)=5;
end
end
end
fork=2:closelen
img(close(k).row,close(k).col)=3;
end
img(endrow,endcol)=10;
imagesc(img*10);
%??????????????????????
ifclose(closelen).row == endrow && close(closelen).col==endcol
break;
end
%??????????????????????????????????????????open??
fori=1:4
ifall([close(closelen).row,close(closelen).col]+direct(i,:)>0) && close(closelen).row+direct(i,1)<=row && close(closelen).col+direct(i,2)<=col && map(close(closelen).row+direct(i,1),close(closelen).col+direct(i,2))~=1
%????????????close??
flag=false;
form=1:closelen
ifclose(m).row==close(closelen).row+direct(i,1) && close(m).col==close(closelen).col+direct(i,2)
flag=true;
break;
end
end
ifflag
continue;
end
%????????????open??
flag=false;
form=1:openlen
ifopen(m).row==close(closelen).row+direct(i,1) && open(m).col==close(closelen).col+direct(i,2)
flag=true;
break;
end
end
ifflag
%more????????
continue;
else %open??????????
open(openlen+1).row=close(closelen).row+direct(i,1);
open(openlen+1).col=close(closelen).col+direct(i,2);
openlen=openlen+1;
%????g??????h????????
open(openlen).g=close(closelen).g+1;
open(openlen).h=abs(endrow-open(openlen).row)+abs(endcol-open(openlen).col);
h=open(openlen).h
end
end
end
end
运行截图如下：