前言
A star算法也叫A星(A*)算法，這是一種在圖形平面上，有多個節(jié)點的路徑，求出最低通過成本的算法。常用于游戲中的NPC的移動計算，或網(wǎng)絡(luò)游戲的BOT的移動計算上
該算法綜合了最良優(yōu)先搜索和Dijkstra算法的優(yōu)點：在進行啟發(fā)式搜索提高算法效率的同時，可以保證找到一條最優(yōu)路徑（基于評估函數(shù)）。
A star算法
在A star算法中，如果我們要計算兩點之間的距離，例如上圖中起點到終點的距離，這時我們把兩點之間的直線距離用f(n)表示，而兩點之間的水平距離+豎直距離=曼哈頓距離(這個后面會用到，使用曼哈頓距離可以提高運算的速度，如果使用f(n)那么需要不斷的計算三角函數(shù))
關(guān)于曼哈頓距離的百度解釋
實現(xiàn)思路
如圖，首先假設(shè)我們要從綠色的點走到紅色的點，藍色的點表示障礙物。
那么：
首先我們定義兩個隊列open和close，open表示正在處理或者準(zhǔn)備處理的點，close表示已經(jīng)處理過或者不處理的點
- 綠色點周圍的8個點就是我們第一步可以走的位置
- 首先我們假設(shè)左邊的水平方向和豎直方向的距離都是10，那么45度方向距離就是14(即√200)，
- 所以我們在每個方塊的左下角標(biāo)一個數(shù)字g(n)，它代表這個方塊距離起始點的距離
- 然后在每個方塊的右下角標(biāo)一個數(shù)字h(n)，它代表這個方塊距離終點的曼哈頓距離(先不考慮障礙物)。
- 所以我們可以大致估算出，每個方塊所在路徑到終點的大致距離，就是f(n)=g(n)+h(n)
- 現(xiàn)在我們將起始點周圍的8個點加入到open隊列中去，表示接下來要處理這8個點，然后將起始點加到close隊列中，表示起始點已經(jīng)處理過了
-
然后我們依照f(n)對open隊列進行從小到大進行排序，取出f(n)最小的那個點，當(dāng)作新的起始點，重復(fù)上面1-7步，直到到達終點，就可以得到下圖
最后就可以得到路徑
代碼實現(xiàn)
了解了思路，代碼也很簡單，首先我們需要定義好坐標(biāo)對象
- 坐標(biāo)對象
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 super.equals(obj);
}
}
- 方塊對象,這里實現(xiàn)了Comparable接口是為了第6步的排序，如果想通過別的方式進行排序也可以不實現(xiàn)
public class Node implements Comparable<Node>{
public Coord coord;
public Node parent;
public int g;//g(n)是已經(jīng)走過的距離
public int h;//h(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;
this.g = g;
this.h = h;
}
//實現(xiàn)排序
@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;
}
}
- 定義一個簡單的二維數(shù)組表示地圖
public class MapInfo {
public int[][] map;
public int width;
public int hight;
public Node start;
public Node end;
public MapInfo(int[][] map, int width, int hight, Node start, Node end) {
this.map = map;
this.width = width;
this.hight = hight;
this.start = start;
this.end = end;
}
}
- 以上3步都是準(zhǔn)備工作，接下來就是AStar算法的具體實現(xiàn)了，根據(jù)思路實現(xiàn)，其實也不難
定義好open和close隊列
//PriorityQueue這里用PriorityQueue是可以避免自己在手動調(diào)用一次List中的sort方法進行第6步的排序
Queue<Node> openList = new PriorityQueue<Node>();
//close隊列不需要排序，只需要查詢，所以用線性表效率較高
List<Node> closeList = new ArrayList<Node>();
- 定義好幾個變量
//障礙物
public final static int BAR = Integer.MAX_VALUE;
//徑路
public final static int PATH = 1;
//橫豎上的移動代價
public final static int DIRECT_VALUE = 10;
//斜移動的代價
public final static int OBLIQUE_VALUE = 14;
- 開始做尋路算法
/**
* start方法更多的是在做一些校驗工作，然后開始循環(huán)
*/
public void start(MapInfo mapInfo) {
//先判斷地圖是否存在
if (mapInfo == null) return;
//清空上一次操作的結(jié)果
openList.clear();
closeList.clear();
//開始搜索
//1.把開始節(jié)點加入到open表
openList.add(mapInfo.start);
//2.目標(biāo)判定
moveNodes(mapInfo);
}
- 開始循環(huán)
/**
* 用來移動當(dāng)前結(jié)點
*/
private void moveNodes(MapInfo mapInfo) {
while (!openList.isEmpty()) {
if (isCoordInClose(mapInfo.end.coord)) {//如果終點進入了close表示結(jié)束
//表示，結(jié)果在mapInfo中
return；
}
//把open中的第一個節(jié)點取出來放到close中
Node current = openList.poll();
closeList.add(current);
//3.開始從current開始的地方找鄰近的能走的節(jié)點
addNeighborNodeInOpen(mapInfo, current);
}
}
/**
* 進行八次操作,將周圍的8個點加到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);
}
- 注意，在將點加到open隊列時，必須判斷當(dāng)前點是否可以走(不是障礙物)，當(dāng)前點是否已經(jīng)處理過(在close隊列中),已經(jīng)當(dāng)前點是否在open隊列中，比如先左走，再上走和直接左上走，如果發(fā)現(xiàn)這種繞路的情況，就更新f(n)路徑，保證f(n)路徑最小
/*
* 添加點到open隊列中
*/
private void addNeighborNodeInOpen(MapInfo mapInfo, Node current, int x, int y, int value) {
if (canAddNodeToOpen(mapInfo, x, y)) {//判斷當(dāng)前節(jié)點是否可以添加（不在close,也不是墻）
Node end = mapInfo.end;
Coord coord = new Coord(x, y);
int g = current.g + value;//計算當(dāng)前點到開始點的距離
Node child = findNodeInOpen(coord);//查找當(dāng)前點是否在open中
if (child == null) {//不在open中
//這個if中表示都是從來沒搜過的路
int h = calcManhattan(end.coord, coord);//計算曼哈頓距離
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){//如果在open中(只需要判斷兩個節(jié)點的G值 ,用小的換了
child.g=g;
child.parent=current;
openList.add(child);
}
}
}
/**
* 判斷點是否可以走(在地圖中，不是障礙物)，是否已經(jīng)處理過(在close隊列中)
*/
private boolean canAddNodeToOpen(MapInfo mapInfo, int x, int y) {
//是否在地圖中
if (x < 0 || x >= mapInfo.width || y < 0 || y >= mapInfo.hight) {
return false;
}
//判斷是否是不可通過的位置
if (mapInfo.map[y][x] == BAR) {
return false;
}
//判斷是否在close表中
if (isCoordInClose(x, y)) {
return false;
}
return true;
}
/**
* 判斷當(dāng)前點是否在open隊列中，如果在就要更新f(n)，保證f(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;
}
