基于matlab的双向A*算法

A*算法是从起始点开始向目标点搜索，而双向A*是在A*的基础上由起始点和目标点同时搜索，当一方检测到另一方的已检查节点时，搜索结束，在搜索时间效率上，双向A*更快。

function bidirectional_ASTAR
clc;
clear;
%% 初始化界面
n = 11;   % field size n x n tiles  20*20的界面
%wallpercent = 0.3;  % this percent of field is walls   15%的界面作为阻碍物（墙）
cmap = [1 1 1; ...%  1 - white - 空地
        0 0 0; ...% 2 - black - 障碍 
        1 0 0; ...% 3 - red - 已搜索过的地方
        0 0 1; ...% 4 - blue - 下次搜索备选中心 
        0 1 0; ...% 5 - green - 起始点
        1 1 0;...% 6 - yellow -  到目 标点的路径 
       1 0 1];% 7 - -  目标点 
colormap（cmap）; 
field = ones（n）;
startposind =10;   %sub2ind用来将行列坐标转换为线性坐标，这里是必要的，因为如果把startposind设置成[xy]的形式，访问field（[xy]）的时候
goalposind =12;    %它并不是访问x行y列元素，而是访问线性坐标为x和y的两个元素
% field（ceil（n^2.*rand（floor（n*n*wallpercent）1） ）） = Inf;
field（1:5 7） = 2;
field（81:3） = 2; 
field（2:53:5）=2;
   field（810）=2;
% startposind = sub2ind（[nn]ceil（n.*rand）ceil（n.*rand））;   %sub2ind用来将行列坐标转换为线性坐标，这里是必要的，因为如果把startposind设置成[xy]的形式，访问field（[xy]）的时候
%goalposind = sub2ind（[nn]ceil（n.*rand）ceil（n.*rand））;    %它并不是访问x行y列元素，而是访问线性坐标为x和y的两个元素
field（startposind ）=5;
field（goalposind ）=7;
costchart = NaN*ones（n）;      %costchart用来存储各个点的实际代价，NaN代表不是数据（不明确的操作）
costchart（startposind） = 0;     %起点的实际代价
fieldpointers = zeros（n）;
fieldpointers1 = zeros（n）;
    global setOpenCosts;
    global setOpenCosts1;
    global setOpen;
    global setOpen1;
    global setOpenHeuristics;
    global setOpenHeuristics1;
setOpen = （startposind）; setOpenCosts = （0）; setOpenHeuristics = （Inf）;
setClosed = []; setClosedCosts = [];%初始化起点的open表和close表
setOpen1 = （goalposind）; setOpenCosts1 = （0）; setOpenHeuristics1 = （Inf）;
setClosed1 = []; setClosedCosts1 = [];%初始化目标点的open表和close表

[goalpos（1） goalpos（2）] = ind2sub（[n n]goalposind）;       %获得目标点的行列坐标
[startpos（1） startpos（2）] = ind2sub（[n n]startposind）;
uicontrol（‘style‘‘pushbutton‘‘String‘‘RE-DO‘ ‘FontSize‘12 ...
         ‘Position‘ [10 10 60 40] ‘Callback‘‘bidirectional_ASTAR‘）;
tic
while true %ismember（AB）返回与A同大小的矩阵，其中元素1表示A中相应位置的元素在B中也出现，0则是没有出现
   field（startposind ）=5;
   field（goalposind ）=7;
   image（1.51.5field）; 
    grid on; 
    axis image; 
    set（gca‘gridline‘‘-‘‘gridcolor‘‘r‘‘linewidth‘2）;
    set（gca‘xtick‘1:1:12‘ytick‘1:1:12）;
    drawnow;
  if（max（ismember（setOpensetOpen1）））
       break;
   end;  
   
    [~ ii] = min（setOpenCosts + setOpenHeuristics）;   %从OPEN表中选择花费最低的点tempii是其下标（也就是标号索引）
    [~ ii1] = min（setOpenCosts1 + setOpenHeuristics1）;
    field（setOpen（ii））=3;
    field（setOpen1（ii1））=6;
    [currentpos（1） currentpos（2）] = ind2sub（[n n]setOpen（ii））;
    [currentpos1（1） currentpos1（2）] = ind2sub（[n n]setOpen1（ii1））;%获得以起点扩展的当前点的行列坐标，注意currentpos（1）是行坐标，currentpos（2）是列坐标
    %% 获得当前点的邻居
    [posindsposinds1costcost1heuristicheuristic1]=get_neighbors（niiii1currentpos（1）currentpos（2）currentpos1（1）currentpos1（2）goalpos（1）goalpos（2）startpos（1）startpos（2））;
    
     setClosed = [setClosed; setOpen（ii）];     %将temp插入CLOSE表中
     setClosedCosts = [setClosedCosts; setOpenCost

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件       14485  2019-04-30 15:44  bidirectional_ASTAR.m