1.完整项目描述和程序获取
>面包多安全交易平台:https://mbd.pub/o/bread/Y52VmJhv
>如果链接失效，可以直接打开本站店铺搜索相关店铺：
>如果链接失效，程序调试报错或者项目合作也可以加微信或者QQ联系。
2.部分仿真图预览
3.算法概述
Astar算法是一种图形搜索算法,常用于寻路。它是个以广度优先搜索为基础,集Dijkstra算法与最佳优先(best fit)算法特点于一身的一种 算法。它通过下面这个函数来计算每个节点的优先级,然后选择优先级最高的节点作为下一个待遍历的节点。AStar（又称 A*），它结合了 Dijkstra 算法的节点信息（倾向于距离起点较近的节点）和贪心算法的最好优先搜索算法信息（倾向于距离目标较近的节点）。可以像 Dijkstra 算法一样保证找到最短路径，同时也像贪心最好优先搜索算法一样使用启发值对算法进行引导。简单点说，AStar的核心在于将游戏背景分为一个又一个格子，每个格子有自己的靠谱值，然后通过遍历起点的格子去找到周围靠谱的格子，接着继续遍历周围…… 最终找到终点。
4.部分源码
function [PathTake, Found]=A_Star_Search(grid,init,goal)
tic;
cost=1;
Found=false;
Resign=false;
Heuristic=CalculateHeuristic(grid,goal); %Calculate the Heuristic
ExpansionGrid(1:size(grid,1),1:size(grid,2)) = -1; % to show the path of expansion
ActionTaken=zeros(size(grid)); %Matrix to store the action taken to reach that particular cell
OptimalPath(1:size(grid,1),1:size(grid,2))={' '}; %Optimal Path derived from A Star
%how to move in the grid
delta = [-1, 0; % go up
0, -1; % go left
1, 0; %go down
0, 1]; % go right
for i=1:size(grid,1)
for j=1:size(grid,2)
gridCell=search();
if(grid(i,j)>0)
gridCell=gridCell.Set(i,j,1,Heuristic(i,j));
else
gridCell=gridCell.Set(i,j,0,Heuristic(i,j));
end
GRID(i,j)=gridCell;
clear gridCell;
end
end
Start=search();
Start=Start.Set(init(1),init(2),grid(init(1),init(2)),Heuristic(init(1),init(2)));
Start.isChecked=1;
GRID(Start.currX,Start.currY).isChecked=1;
Goal=search();
Goal=Goal.Set(goal(1),goal(2),grid(goal(1),goal(2)),0);
OpenList=[Start];
ExpansionGrid(Start.currX,Start.currY)=0;
small=Start.gValue+Start.hValue;
count=0;
while(Found==false || Resign==false)
small=OpenList(1).gValue+OpenList(1).hValue+cost;
for i=1:size(OpenList,2)
fValue=OpenList(i).gValue+OpenList(i).hValue;
if(fValue<=small)
small=fValue;
ExpandNode=OpenList(i);
OpenListIndex=i;
end
end
OpenList(OpenListIndex)=[];
ExpansionGrid(ExpandNode.currX,ExpandNode.currY)=count;
count=count+1;
for i=1:size(delta,1)
direction=delta(i,:);
if(ExpandNode.currX+ direction(1)<1 || ExpandNode.currX+direction(1)>size(grid,1)|| ExpandNode.currY+ direction(2)<1 || ExpandNode.currY+direction(2)>size(grid,2))
continue;
else
NewCell=GRID(ExpandNode.currX+direction(1),ExpandNode.currY+direction(2));
if(NewCell.isChecked~=1 && NewCell.isEmpty~=1)
GRID(NewCell.currX,NewCell.currY).gValue=GRID(ExpandNode.currX,ExpandNode.currY).gValue+cost;
GRID(NewCell.currX,NewCell.currY).isChecked=1; %modified line from the v1
OpenList=[OpenList,GRID(NewCell.currX,NewCell.currY)];
ActionTaken(NewCell.currX,NewCell.currY)=i;
end
if(NewCell.currX==Goal.currX && NewCell.currY==Goal.currY && NewCell.isEmpty~=1)
Found=true;
Resign=true;
disp('Search Successful');
GRID(NewCell.currX,NewCell.currY).isChecked=1;
ExpansionGrid(NewCell.currX,NewCell.currY)=count;
GRID(NewCell.currX,NewCell.currY);
break;
end
end
end
if(isempty(OpenList) && Found==false)
Resign=true;
disp('Search Failed');
break;
end
end
PathTake=[]; %For stroring the values taken for the path.
if(Found==true) %further process only if there is a path
Policy={'Up','Left','Down','Right','Diag Down','Diag Up'};
X=goal(1);Y=goal(2);
OptimalPath(X,Y)={'GOAL'};
while(X~=init(1)|| Y~=init(2))
x2=X-delta(ActionTaken(X,Y),1);
y2=Y-delta(ActionTaken(X,Y),2);
OptimalPath(x2,y2)=Policy(ActionTaken(X,Y));
PathTake=[PathTake;[X,Y]];
X=x2;
Y=y2;
end
PathTake=[PathTake;[init(1),init(2)]]; % add the start state to the end
Total_Elapsed_Time=toc
plot(fliplr((PathTake(:,2))'),fliplr((PathTake(:,1))'));
set(gca,'XLim',[-1,size(grid,2)+2],'YLim',[-1,size(grid,1)+2]);
set(gca,'YDir','reverse');
else
disp('No Path to Display');
Total_Elapsed_Time=toc
end
end
A103
