一、適用場景
在一張地圖中，繪制從起點(diǎn)移動到終點(diǎn)的最優(yōu)路徑，地圖中會有障礙物，必須繞開障礙物。
二、算法思路
1. 回溯法得到路徑
(如果有路徑)采用“結(jié)點(diǎn)與結(jié)點(diǎn)的父節(jié)點(diǎn)”的關(guān)系從最終結(jié)點(diǎn)回溯到起點(diǎn)，得到路徑。
2. 路徑代價的估算：F = G+H
A星算法的代價計算使用了被稱作是啟發(fā)式的代價函數(shù)。
先說明一下各符號意義：G表示的是從起點(diǎn)到當(dāng)前結(jié)點(diǎn)的實際路徑代價(為啥叫實際？就是已經(jīng)走過了，邊走邊將代價計算好了)；H表示當(dāng)前結(jié)點(diǎn)到達(dá)最終結(jié)點(diǎn)的估計代價(為啥叫估計？就是還沒走過，不知道前面有沒障礙、路通不通，所以只能用估計)；F表示當(dāng)前結(jié)點(diǎn)所在路徑從起點(diǎn)到最終點(diǎn)預(yù)估的總路徑代價。
G的計算方式：計算方式有挺多種的，這里我們就用這種吧，假設(shè)每個結(jié)點(diǎn)代表一個正方形，橫豎移動距離：斜移動距離=1：1.4（根號2），我們?nèi)€整數(shù)10和14吧，也就是說當(dāng)前結(jié)點(diǎn)G值=父節(jié)點(diǎn)的G+（10或14）。
H的計算方式：估價計算也有很多種方式，我們這里使用“曼哈頓”法，H=|當(dāng)前結(jié)點(diǎn)x值-最終結(jié)點(diǎn)x值|+|當(dāng)前結(jié)點(diǎn)y值-最終結(jié)點(diǎn)y值|（"||"表示絕對值）。
如下圖
3. 輔助表：Open、Close列表
在A星算法中，需要使用兩個輔助表來記錄結(jié)點(diǎn)。
一個用于記錄可被訪問的結(jié)點(diǎn)，成為Open表；一個是記錄已訪問過的結(jié)點(diǎn)，稱為Close表。
這兩個表決定了算法的結(jié)束：條件是最終結(jié)點(diǎn)在Close表中(找到路徑)或Open表為空(找不到了路徑)。
4. 移動結(jié)點(diǎn)、相鄰結(jié)點(diǎn)的處理
上面的理解的話，現(xiàn)在就來移動當(dāng)前的節(jié)點(diǎn)，尋找路徑。
每次從Open表中取出F值最小的結(jié)點(diǎn)出來（這里我們使用優(yōu)先隊列來處理比較好），作為當(dāng)前結(jié)點(diǎn)；然后將當(dāng)前結(jié)點(diǎn)的所有鄰結(jié)點(diǎn)按照鄰結(jié)點(diǎn)規(guī)則加入到Open表中；最后將當(dāng)前結(jié)點(diǎn)放入Close表中，這里就是每次循環(huán)的執(zhí)行內(nèi)容。
鄰結(jié)點(diǎn)規(guī)則：
(1) 當(dāng)鄰結(jié)點(diǎn)不在地圖中，不加入Open表；
(2) 當(dāng)鄰結(jié)點(diǎn)是障礙物，不加入Open表；
(3) 當(dāng)鄰結(jié)點(diǎn)在Close表中，不加入Open表；
(4) 當(dāng)鄰結(jié)點(diǎn)不在Open中，加入Open表，設(shè)該鄰結(jié)點(diǎn)的父節(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)；
(5) **當(dāng)鄰結(jié)點(diǎn)在Open表中，我們需要做個比較:如果鄰結(jié)點(diǎn)的G值>當(dāng)前結(jié)點(diǎn)的G值+當(dāng)前結(jié)點(diǎn)到這個鄰結(jié)點(diǎn)的代價，那么修改該鄰結(jié)點(diǎn)的父節(jié)點(diǎn)為當(dāng)前的結(jié)點(diǎn)(因為在Open表中的結(jié)點(diǎn)除了起點(diǎn)，都會有父節(jié)點(diǎn))，修改G值=當(dāng)前結(jié)點(diǎn)的G值+當(dāng)前結(jié)點(diǎn)到這個鄰結(jié)點(diǎn)的代價 **
藍(lán)色框框表示在Close表中，綠色的框框表示在Open表中
最后回溯得到路徑
三、代碼實現(xiàn)(Java)
1. 輸入
(1) 代表地圖二值二維數(shù)組(0表示可通路，1表示路障)
int[][] maps = {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }
};
(2) 按照二維數(shù)組的特點(diǎn)，坐標(biāo)原點(diǎn)在左上角，所以y是高，x是寬，y向下遞增，x向右遞增，我們將x和y封裝成一個類，好傳參，重寫equals方法比較坐標(biāo)(x,y)是不是同一個。
public class Coord
{
public int x;
public int y;
public Coord(int x, int y)
{
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj)
{
if (obj == null) return false;
if (obj instanceof Coord)
{
Coord c = (Coord) obj;
return x == c.x && y == c.y;
}
return false;
}
}
(3) 封裝路徑結(jié)點(diǎn)類，字段包括：坐標(biāo)、G值、F值、父結(jié)點(diǎn)，實現(xiàn)Comparable接口，方便優(yōu)先隊列排序。
public class Node implements Comparable<Node>
{
public Coord coord; // 坐標(biāo)
public Node parent; // 父結(jié)點(diǎn)
public int G; // G：是個準(zhǔn)確的值，是起點(diǎn)到當(dāng)前結(jié)點(diǎn)的代價
public int H; // H：是個估值，當(dāng)前結(jié)點(diǎn)到目的結(jié)點(diǎn)的估計代價
public Node(int x, int y)
{
this.coord = new Coord(x, y);
}
public Node(Coord coord, Node parent, int g, int h)
{
this.coord = coord;
this.parent = parent;
G = g;
H = h;
}
@Override
public int compareTo(Node o)
{
if (o == null) return -1;
if (G + H > o.G + o.H)
return 1;
else if (G + H < o.G + o.H) return -1;
return 0;
}
}
(4) 最后一個數(shù)據(jù)結(jié)構(gòu)是A星算法輸入的所有數(shù)據(jù)，封裝在一起，傳參方便。:grin:
public class MapInfo
{
public int[][] maps; // 二維數(shù)組的地圖
public int width; // 地圖的寬
public int hight; // 地圖的高
public Node start; // 起始結(jié)點(diǎn)
public Node end; // 最終結(jié)點(diǎn)
public MapInfo(int[][] maps, int width, int hight, Node start, Node end)
{
this.maps = maps;
this.width = width;
this.hight = hight;
this.start = start;
this.end = end;
}
}
2. 處理
(1) 在算法里需要定義幾個常量來確定：二維數(shù)組中哪個值表示障礙物、二維數(shù)組中繪制路徑的代表值、計算G值需要的橫縱移動代價和斜移動代價。
public final static int BAR = 1; // 障礙值
public final static int PATH = 2; // 路徑
public final static int DIRECT_VALUE = 10; // 橫豎移動代價
public final static int OBLIQUE_VALUE = 14; // 斜移動代價
(2) 定義兩個輔助表：Open表和Close表。Open表的使用是需要取最小值，在這里我們使用Java工具包中的優(yōu)先隊列PriorityQueue，Close只是用來保存結(jié)點(diǎn)，沒其他特殊用途，就用ArrayList。
Queue<Node> openList = new PriorityQueue<Node>(); // 優(yōu)先隊列(升序)
List<Node> closeList = new ArrayList<Node>();
(3) 定義幾個布爾判斷方法：最終結(jié)點(diǎn)的判斷、結(jié)點(diǎn)能否加入open表的判斷、結(jié)點(diǎn)是否在Close表中的判斷。
/**
* 判斷結(jié)點(diǎn)是否是最終結(jié)點(diǎn)
*/
private boolean isEndNode(Coord end,Coord coord)
{
return coord != null && end.equals(coord);
}
/**
* 判斷結(jié)點(diǎn)能否放入Open列表
*/
private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y)
{
// 是否在地圖中
if (x < 0 || x >= mapInfo.width || y < 0 || y >= mapInfo.hight) return false;
// 判斷是否是不可通過的結(jié)點(diǎn)
if (mapInfo.maps[y][x] == BAR) return false;
// 判斷結(jié)點(diǎn)是否存在close表
if (isCoordInClose(x, y)) return false;
return true;
}
/**
* 判斷坐標(biāo)是否在close表中
*/
private boolean isCoordInClose(Coord coord)
{
return coord!=null&&isCoordInClose(coord.x, coord.y);
}
/**
* 判斷坐標(biāo)是否在close表中
*/
private boolean isCoordInClose(int x, int y)
{
if (closeList.isEmpty()) return false;
for (Node node : closeList)
{
if (node.coord.x == x && node.coord.y == y)
{
return true;
}
}
return false;
}
(4) 計算H值，“曼哈頓” 法，坐標(biāo)分別取差值相加
private int calcH(Coord end,Coord coord)
{
return Math.abs(end.x - coord.x) + Math.abs(end.y - coord.y);
}
(5) 從Open列表中查找結(jié)點(diǎn)
private Node findNodeInOpen(Coord coord)
{
if (coord == null || openList.isEmpty()) return null;
for (Node node : openList)
{
if (node.coord.equals(coord))
{
return node;
}
}
return null;
}
(6) 添加鄰結(jié)點(diǎn)到Open表
/**
* 添加所有鄰結(jié)點(diǎn)到open表
*/
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current)
{
int x = current.coord.x;
int y = current.coord.y;
// 左
addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE);
// 上
addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE);
// 右
addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE);
// 下
addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE);
// 左上
addNeighborNodeInOpen(mapInfo,current, x - 1, y - 1, OBLIQUE_VALUE);
// 右上
addNeighborNodeInOpen(mapInfo,current, x + 1, y - 1, OBLIQUE_VALUE);
// 右下
addNeighborNodeInOpen(mapInfo,current, x + 1, y + 1, OBLIQUE_VALUE);
// 左下
addNeighborNodeInOpen(mapInfo,current, x - 1, y + 1, OBLIQUE_VALUE);
}
/**
* 添加一個鄰結(jié)點(diǎn)到open表
*/
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value)
{
if (canAddNodeToOpen(mapInfo,x, y))
{
Node end=mapInfo.end;
Coord coord = new Coord(x, y);
int G = current.G + value; // 計算鄰結(jié)點(diǎn)的G值
Node child = findNodeInOpen(coord);
if (child == null)
{
int H=calcH(end.coord,coord); // 計算H值
if(isEndNode(end.coord,coord))
{
child=end;
child.parent=current;
child.G=G;
child.H=H;
}
else
{
child = new Node(coord, current, G, H);
}
openList.add(child);
}
else if (child.G > G)
{
child.G = G;
child.parent = current;
// 重新調(diào)整堆
openList.add(child);
}
}
}
(7) 回溯法繪制路徑
private void drawPath(int[][] maps, Node end)
{
if(end==null||maps==null) return;
System.out.println("總代價：" + end.G);
while (end != null)
{
Coord c = end.coord;
maps[c.y][c.x] = PATH;
end = end.parent;
}
}
(8) 開始算法，循環(huán)移動結(jié)點(diǎn)尋找路徑，設(shè)定循環(huán)結(jié)束條件，Open表為空或者最終結(jié)點(diǎn)在Close表
public void start(MapInfo mapInfo)
{
if(mapInfo==null) return;
// clean
openList.clear();
closeList.clear();
// 開始搜索
openList.add(mapInfo.start);
moveNodes(mapInfo);
}
/**
* 移動當(dāng)前結(jié)點(diǎn)
*/
private void moveNodes(MapInfo mapInfo)
{
while (!openList.isEmpty())
{
if (isCoordInClose(mapInfo.end.coord))
{
drawPath(mapInfo.maps, mapInfo.end);
break;
}
Node current = openList.poll();
closeList.add(current);
addNeighborNodeInOpen(mapInfo,current);
}
}
