依据象限搜索及混合预计耗费的A*改进算法，包含8邻域及24邻域的改进

注： 以下改进皆为在传统 A* 算法基础下的改进，请先了解传统 A* 算法后再对本文进行了解。

1 邻域改进

当终点相对于当前点在不同象限时，采取不同的搜索邻域能够减小检验节点数量。

首先要确定终点相对于当前节点象限，我们定义向量： V = [ g o a l . x − c u r . x 2 ， g o a l . y − c u r . y 2 ] V=[\frac{goal.x-cur.x}{2}，\frac{goal.y-cur.y}{2}] V=[2goal.x−cur.x​，2goal.y−cur.y​] 其中 g o a l goal goal为目标结点， c u r cur cur为当前节点，则： { V ( 1 ) ≥ 0 , V ( 2 ) ≥ 0 第 一 象 限 V ( 1 ) ≤ 0 , V ( 2 ) ≥ 0 第 二 象 限 V ( 1 ) ≤ 0 , V ( 2 ) ≤ 0 第 三 象 限 V ( 1 ) ≥ 0 , V ( 2 ) ≤ 0 第 四 象 限 \begin{cases} V(1)\geq0,V(2)\geq0 & 第一象限 \\ V(1)\leq0,V(2)\geq0 & 第二象限 \\ V(1)\leq0,V(2)\leq0 & 第三象限 \\ V(1)\geq0,V(2)\leq0 & 第四象限 \\ \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​V(1)≥0,V(2)≥0V(1)≤0,V(2)≥0V(1)≤0,V(2)≤0V(1)≥0,V(2)≤0​第一象限第二象限第三象限第四象限​

依据象限不同我们对搜索邻域做如下改进

1.1 [8]邻域改进

对于不同象限，将传统的8邻域改为5邻域： 如图所示黑色方块代表当前点，蓝色方块表示依据象限搜索的邻域：

1.2 [24]邻域改进

对于不同象限，将24邻域改为13邻域： 如图所示黑色方块代表当前点，蓝色方块表示依据象限搜索的邻域：

2 混合预计耗费估计 2.1 欧几里德距离

当前节点与目标点间无障碍时 采取欧几里德距离x10作为预计耗费 ： H = 10 ∗ ( g x − c x ) 2 + ( g y − c y ) 2 H=10*\sqrt{(g_x-c_x)^2+(g_y-c_y)^2} H=10∗(gx​−cx​)2+(gy​−cy​)2 ​

2.2 半圆周距离

如图所示，当起点终点连线穿过障碍物，但至少有一个以当前点和终点的中点为圆心的半圆弧能够无障碍的连接当前点和终点，则采用圆弧长度x10作为预计耗费:

若 A C ‾ = 2 R \overline{AC}=2R AC=2R，则 H = 10 π R H=10\pi R H=10πR

2.3 弧+半径距离

若起点终点间有障碍，且过以中心点为圆心得圆弧两侧都有障碍，则考虑以终点为圆心，当前点及终点距离为半径做圆，若存在圆弧可连接当前点及终点，则考虑(圆弧+半径距离)x10为预计耗费： 若 A C ‾ = 2 R \overline{AC}=2R AC=2R，则 H = 10 ( 2 θ R + 2 R ) H=10(2\theta R+2R) H=10(2θR+2R)

2.4 曼哈顿距离

在以上任意一种类型路径上均存在障碍物，则采用曼哈顿距离： H = 10 ∗ ( ∣ g x − c x ∣ + ∣ g y − c y ∣ ) H=10*(|g_x-c_x|+|g_y-c_y|) H=10∗(∣gx​−cx​∣+∣gy​−cy​∣)

3 结果展示 3.1 [5]邻域及[13]邻域效果

5邻域：

13邻域：

3.2 [13]邻域与传统A*对比一

可以看出改进后的算法搜索范围对比传统方法小了很多 13邻域(左)，传统8邻域(右)

3.2 [13]邻域与传统A*对比二

13邻域(左)，传统8邻域(右)

4 主要部分代码 4.1 预计耗费部分代码

function H=getH(pnt1,pnt2,obstacle)
%pnt1,pnt2,obstacle


% =========================================================================
% 情况一，起始点和终点之间无障碍物
flag1=false;

% 先删除明显离直线过远或者垂直点不在起点终点之间的点
tempSet=obstacle;
tempSet(tempSet(:,1)max(pnt1(1),pnt2(1)),:)=[];
tempSet(tempSet(:,2)max(pnt1(2),pnt2(2)),:)=[];

% 找到垂直于起始终止点之间单位向量
tempV=pnt2-pnt1;
tempV=[tempV(2),-tempV(1)]./norm(tempV);

% 障碍点到直线距离
dis_L=(tempSet-pnt1)*tempV';
tempSet(abs(dis_L)>sqrt(2)/2,:)=[];
dis_L(abs(dis_L)>sqrt(2)/2)=[];

if any(abs(dis_L)