www.pudn.com > Improved-AStar-on-3D-Terrain.rar > main.m, change:2013-02-22,size:8242b


%% 该函数用于演示基于A_Star算法的三维路径规划算法
%% 清空环境
clc
clear

%% 数据初始化
%下载数据
starttime=cputime;
load  HeightData z zx tabu dimao

%起点终点网格点 
startx=8;starty=27;
endx=35;endy=17;

%OPEN LIST STRUCTURE
%IS ON LIST 1/0 |X val |Y val |Parent X val |Parent Y val |g(n) |h(n)|f(n)|
OPEN=[];%开始列表
%CLOSED LIST STRUCTURE
%X val | Y val |
CLOSED=[];%结束列表

%Put all obstacles on the Closed list
k=1;
for i=1:40
    for j=1:40
        if(tabu(j,i) == 0)
            CLOSED(k,1)=i;
            CLOSED(k,2)=j;
            k=k+1;
        end
    end
end
CLOSED_COUNT=size(CLOSED,1);%提前将不可通行点加入到CLOSED表

%% set the starting node as the first node
xNode=startx;
yNode=starty;
OPEN_COUNT=1;
path_cost=0;
goal_distance=sqrt(25*(xNode-endx)^2 + 25*(yNode-endy)^2+(zx(yNode,xNode)-zx(endy,endx))^2)/(5*dimao(yNode,xNode));%欧几里德距离
OPEN(OPEN_COUNT,:)=[1,xNode,yNode,xNode,yNode,path_cost,goal_distance,goal_distance];%向new_row中插入开始列表
OPEN(OPEN_COUNT,1)=0;%表示第1个节点已经从开始列表出来
CLOSED_COUNT=CLOSED_COUNT+1;%表示第1个节点已经进入结束列表
CLOSED(CLOSED_COUNT,1)=xNode;
CLOSED(CLOSED_COUNT,2)=yNode;
NoPath=1;%路径记录号

%% START ALGORITHM
while((xNode ~= endx || yNode ~= endy) && NoPath == 1)%只适用刚出发时候
     %返回exp_array=多行[s_x,s_y,gn, hn, fn]
     %此时OPEN=多行[1,xNode,yNode,xNode,yNode,hn,gn,fn]
     exp_array=expand_array(xNode,yNode,endx,endy,path_cost,zx,CLOSED,dimao,40,40); %计算当前点(xNode,yNode)所有可行的下一点
     exp_count=size(exp_array,1);%求得exp_array行向量的维数

     for i=1:exp_count%可到达的栅格
            flag=0;
            for j=1:OPEN_COUNT %最初OPEN_COUNT只有1行
                if(exp_array(i,1) == OPEN(j,2) && exp_array(i,2) == OPEN(j,3) )%exp_array的节点是OPEN里的节点
                    OPEN(j,8)=min(OPEN(j,8),exp_array(i,5));%f(n)
                    if OPEN(j,8)== exp_array(i,5)%说明原来的OPEN(j,8)>exp_array(i,5),
                        %f(n)=g(n)+h(n)>g(n-1)+D(n-1,n)+h(n),即g(n)>g(n-1)+D(n-1,n)
                        OPEN(j,4)=xNode;%Parent X val 
                        OPEN(j,5)=yNode;%Parent Y val 
                        OPEN(j,6)=exp_array(i,3);%g(n)
                        OPEN(j,7)=exp_array(i,4);%h(n)
                    end;%End of minimum fn check
                    flag=1;
                end;%End of node check
            end;%End of j for
            if flag == 0%说明此时的节点还未添加进open列表,需要将其加入到open表
                OPEN_COUNT = OPEN_COUNT+1;
                OPEN(OPEN_COUNT,:)=[1,exp_array(i,1),exp_array(i,2),xNode,yNode,exp_array(i,3),exp_array(i,4),exp_array(i,5)];
            end;%End of insert new element into the OPEN list
     end;%End of i for

     %Find out the node with the smallest fn 
     index_min_node = min_fn(OPEN,OPEN_COUNT,endx,endy);  %此时 OPEN(j,2) ,OPEN(j,3)与 OPEN(j,4) OPEN(j,5)不一样了
     if (index_min_node ~= -1)    
          %Set xNode and yNode to the node with minimum fn
          xNode=OPEN(index_min_node,2);
          yNode=OPEN(index_min_node,3);
          path_cost=OPEN(index_min_node,6);%Update the cost of reaching the parent node
          %Move the Node to list CLOSED
          CLOSED_COUNT=CLOSED_COUNT+1;
          CLOSED(CLOSED_COUNT,1)=xNode;
          CLOSED(CLOSED_COUNT,2)=yNode;
          OPEN(index_min_node,1)=0;
      else
          %No path exists to the Target!!
          NoPath=0;%Exits the loop!
      end;%End of index_min_node check
end;%End of While Loop

%% Once algorithm has run The optimal path is generated by starting of at the
%last node(if it is the target node) and then identifying its parent node
%until it reaches the start node.This is the optimal path
i=size(CLOSED,1);
Optimal_path=[];
xval=CLOSED(i,1);
yval=CLOSED(i,2);
% xval=endx;
% yval=endy;
j=1;
Optimal_path(j,1)=xval;
Optimal_path(j,2)=yval;
j=j+1;

   %Traverse OPEN and determine the parent nodes
   %返回(xval,yval)在OPEN中的序号
   jj=1;
   while(OPEN(jj,2) ~= xval || OPEN(jj,3) ~= yval )
        jj=jj+1;
   end;
   parent_x=OPEN(jj,4);%node_index returns the index of the node
   parent_y=OPEN(jj,5);

   while( parent_x ~= startx || parent_y ~= starty)
           Optimal_path(j,1) = parent_x;
           Optimal_path(j,2) = parent_y;
           %返回节点在open表中的序号
           k=1;
           while(OPEN(k,2) ~= parent_x || OPEN(k,3) ~= parent_y )
             k=k+1;
           end;
           parent_x=OPEN(k,4);%node_index returns the index of the node
           parent_y=OPEN(k,5);
           j=j+1;
    end;   
    Optimal_path(j,1)=startx;
    Optimal_path(j,2)=starty;
    
    figure(1)
    x=1:41;
    y=1:41;
    [x1,y1]=meshgrid(x,y); %不能少,少了死循环
    mesh(x1*5,y1*5,z);  %加了这个,坐标轴就有了栅格划分
    axis([0,220,0,220,0,220]);  %加了这个,怎么旋转,坐标轴的最小最大值不变
    xlabel('X:m','fontsize',12);
    ylabel('Y:m','fontsize',12);
    zlabel('Z:m','fontsize',12);
    
    hold on %不能少,在此基础上画图,放在哪里,就从哪里状态开始定格       
    %能通过是绿色点,不能通过是红色点
    
%针对轮式车辆
    for i=1:40
        for j=1:40
            A=5*[j,j,j+1,j+1];
            B=5*[i,i+1,i+1,i];
            C=[z(j,i),z(j,i+1),z(j+1,i+1),z(j+1,i)];
            if  dimao(j,i)==1%硬质路面
                 fill3(B,A,C,'B');
            elseif  dimao(j,i)==0.8%土质路面0.9
                 fill3(B,A,C,[0.8,0.8,0.8]);
            elseif  dimao(j,i)==0.4%草地0.8
                 fill3(B,A,C,'G');
            elseif  dimao(j,i)==0.2%沙地0.5
                 fill3(B,A,C,'Y');
            elseif dimao(j,i)==0.1%树林0.3
                 fill3(B,A,C,'M');
            elseif  dimao(j,i)==0%沼泽/湖泊
                 fill3(B,A,C,'R');
            end
        end
    end
    
%针对履带式车辆
%     for i=1:40
%         for j=1:40
%             A=5*[j,j,j+1,j+1];
%             B=5*[i,i+1,i+1,i];
%             C=[z(j,i),z(j,i+1),z(j+1,i+1),z(j+1,i)];
%             if  dimao(j,i)==1%硬质路面
%                  fill3(B,A,C,'B');
%             elseif  dimao(j,i)==0.9%土质路面
%                  fill3(B,A,C,[0.8,0.8,0.8]);
%             elseif  dimao(j,i)==0.8%草地
%                  fill3(B,A,C,'G');
%             elseif  dimao(j,i)==0.5%沙地
%                  fill3(B,A,C,'Y');
%             elseif dimao(j,i)==0.3%树林
%                  fill3(B,A,C,'M');
%             elseif  dimao(j,i)==0%沼泽/湖泊
%                  fill3(B,A,C,'R');
%             end
%         end
%     end
    
    for i=1:40
        for j=1:40
            if(tabu(j,i)==1)
%                 plot3(i*5+2.5,j*5+2.5,zx(j,i),'g.');
            else
                plot3(i*5+2.5,j*5+2.5,zx(j,i)+3,'KX','LineWidth',1);
            end
        end
    end

    plot3(5*startx+2.5,5*starty+2.5,zx(starty,startx),'--o','LineWidth',2,...
                           'MarkerEdgeColor','k',...
                           'MarkerFaceColor','g',...
                           'MarkerSize',10);
    plot3(5*endx+2.5,5*endy+2.5,zx(endy,endx),'--o','LineWidth',2,...
                           'MarkerEdgeColor','k',...
                           'MarkerFaceColor','g',...
                           'MarkerSize',10);
    text(5*startx+2.5,5*starty+2.5,zx(starty,startx)+5,'S');
    text(5*endx+2.5,5*endy+2.5,zx(endy,endx)+5,'T');

    j=size(Optimal_path,1);
    time=0;distance=0; %分别计算时间和路程
    for i=j:-1:2
       time=time+sqrt(25*(Optimal_path(i,1)-Optimal_path(i-1,1))^2+25*(Optimal_path(i,2)-Optimal_path(i-1,2))^2+...
            (zx(Optimal_path(i,2),Optimal_path(i,1))-zx(Optimal_path(i-1,2),Optimal_path(i-1,1)))^2)/(5*dimao(Optimal_path(i,2),Optimal_path(i,1)));    
       distance=distance+sqrt(25*(Optimal_path(i,1)-Optimal_path(i-1,1))^2+25*(Optimal_path(i,2)-Optimal_path(i-1,2))^2+...
            (zx(Optimal_path(i,2),Optimal_path(i,1))-zx(Optimal_path(i-1,2),Optimal_path(i-1,1)))^2);
       plot3(5*[Optimal_path(i,1) Optimal_path(i-1,1)]+2.5,5*[Optimal_path(i,2) Optimal_path(i-1,2)]+2.5,...
           [zx(Optimal_path(i,2),Optimal_path(i,1)) zx(Optimal_path(i-1,2),Optimal_path(i-1,1))],'-W.','LineWidth',2);
    end
    runtime=cputime-starttime;
    title({['A__Star--最少时间:',num2str(time,4),',  行驶路程:',num2str(distance,7)];['运行时间:',num2str(runtime,4)]},'fontsize',15);