import java.util.Comparator;
// 節(jié)點(diǎn)類(lèi)
public class Node implements Comparable<Node>, Comparator<Node> {
/**
* 節(jié)點(diǎn)坐標(biāo)
*/
public int x, y;
/**
* F(n)=G(n)+H(n)
*/
public int f;
/**
* 起點(diǎn)到當(dāng)前點(diǎn)的移動(dòng)耗費(fèi)
*/
public int g;
/**
* 當(dāng)前點(diǎn)到終點(diǎn)的移動(dòng)耗費(fèi)，即
* 曼哈頓距離|x1-x2|*水平方向單元格寬度+
* |y1-y2|*垂直方向單元格寬度(忽略障礙物)
*/
public int h;
/**
* 父節(jié)點(diǎn)
*/
public Node parent;
/**
* 通過(guò)給定值構(gòu)造一個(gè)節(jié)點(diǎn)對(duì)象
*/
public Node(int x, int y, Node parent) {
this.x = x;
this.y = y;
this.parent = parent;
}
/**
* 通過(guò)給定節(jié)點(diǎn)構(gòu)造一個(gè)新的節(jié)點(diǎn)對(duì)象
*/
public Node(Node node) {
x = node.x;
y = node.y;
f = node.f;
g = node.g;
h = node.h;
parent = node.parent;
}
/**
* 將節(jié)點(diǎn)重新賦值
*/
public void reset(Node node) {
x = node.x;
y = node.y;
f = node.f;
g = node.g;
h = node.h;
parent = node.parent;
}
@Override
public int compareTo(Node node) {
if (f > node.f) return 1;
else if (f < node.f) return -1;
else return 0;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (!(obj instanceof Node)) return false;
Node other = (Node) obj;
if (x != other.x) return false;
if (y != other.y) return false;
return true;
}
@Override
public int hashCode() {
int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public String toString() {
return "(" + x + "," + y + ") F=" + f + "";
}
@Override
public int compare(Node node, Node other) {
if (node.f > other.f) return 1;
else if (node.f < other.f) return -1;
else return 0;
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* A星算法步驟：
* 1.起點(diǎn)先添加到開(kāi)啟列表中
* 2.開(kāi)啟列表中有節(jié)點(diǎn)的話恢准，取出第一個(gè)節(jié)點(diǎn)魂挂，即最小F值的節(jié)點(diǎn),
* ->判斷此節(jié)點(diǎn)是否是目標(biāo)點(diǎn)，是則找到了馁筐，跳出;
* ->根據(jù)此節(jié)點(diǎn)取得八個(gè)方向的節(jié)點(diǎn)涂召，求出G，H敏沉，F(xiàn)值果正；
* ->判斷每個(gè)節(jié)點(diǎn)在地圖中是否能通過(guò)炎码，不能通過(guò)則加入關(guān)閉列表中，跳出;
* ->判斷每個(gè)節(jié)點(diǎn)是否在關(guān)閉列表中秋泳，在則跳出辅肾；
* ->判斷每個(gè)節(jié)點(diǎn)是否在開(kāi)啟列表中，在則更新G值轮锥，F(xiàn)值矫钓，還更新其父節(jié)點(diǎn)；不在則將其添加到開(kāi)啟列表中舍杜，計(jì)算G值新娜，H值，F(xiàn)值既绩，添加其節(jié)點(diǎn)概龄。
* 3.把此節(jié)點(diǎn)從開(kāi)啟列表中刪除，再添加到關(guān)閉列表中饲握；
* 4.把開(kāi)啟列表中按照F值最小的節(jié)點(diǎn)進(jìn)行排序私杜，最小的F值在第一個(gè)；
* 5.重復(fù)2救欧，3衰粹，4步驟，直到目標(biāo)點(diǎn)在開(kāi)啟列表中笆怠，即找到了铝耻；目標(biāo)點(diǎn)不在開(kāi)啟列表中，開(kāi)啟列表為空蹬刷，即沒(méi)找到
*/
public class AStar {
/**
* 地圖數(shù)組
*/
private int[][] map;
/**
* 障礙物數(shù)組
*/
private int[] limit;
/**
* 不可達(dá)區(qū)域數(shù)組
*/
private boolean[][] close;
/**
* 存放未關(guān)閉節(jié)點(diǎn)的集合
*/
private List<Node> open;
/**
* 結(jié)果集
*/
private List<Node> result;
/**
* 垂直或水平方向移動(dòng)的路徑評(píng)分
*/
private final int COST_STRAIGHT = 64;
/**
* 斜方向移動(dòng)的路徑評(píng)分
*/
private final int COST_DIAGONAL = 90;
/**
* 地圖數(shù)組的寬度
*/
private int mapW;
/**
* 地圖數(shù)組的高度
*/
private int mapH;
/**
* 是否能斜向移動(dòng)
*/
public boolean isObliqueable;
/**
* 是否能直線移動(dòng)
*/
public boolean isStraightable;
/**
* 起點(diǎn)節(jié)點(diǎn)對(duì)象
*/
private Node startNode;
/**
* 當(dāng)前節(jié)點(diǎn)對(duì)象
*/
private Node current;
/**
* 判斷通行的通用節(jié)點(diǎn)(另一個(gè)作用:Map所有key對(duì)應(yīng)的鍵 )
*/
private Node tempNode;
int count;
/**
* @param map 地圖數(shù)組
* @param limit 不可通行區(qū)域編號(hào)的數(shù)組
*/
public AStar(int[][] map, int... limit) {
tempNode = new Node(0, 0, null);
startNode = new Node(0, 0, null);
open = new ArrayList<Node>();
result = new ArrayList<Node>();
isObliqueable = true;
isStraightable = true;
init(map, limit);
}
/**
* 重新初始化 提高類(lèi)的復(fù)用性
*
* @param map 地圖數(shù)組
* @param limit 不可通行區(qū)域編號(hào)的數(shù)組
*/
public AStar init(int[][] map, int... limit) {
this.map = map;
this.limit = limit;
if (close == null || mapW != map[0].length || mapH != map.length) {
mapW = map[0].length;
mapH = map.length;
close = new boolean[mapH][mapW];
}
return this;
}
/**
* 程序入口
* 查找核心算法
*/
public List<Node> searchPath(int startX, int startY,
int targetX, int targetY) {
if (startX < 0 || startX >= mapW || targetX < 0 || targetX >= mapW
|| startY < 0 || startY >= mapH || targetY < 0 || targetY >= mapH)
return null;
// 查找障礙集合是否存在下一步的坐標(biāo)
for (int i = 0, y, x, h = close.length, w = close[0].length, len = limit.length; i < len; i++) {
/** 將地圖數(shù)組映射到一個(gè)布爾二維數(shù)組(可通行為true其他為false) */
for (y = 0; y < h; y++) {
for (x = 0; x < w; x++) {
if (map[y][x] == limit[i]) {
close[y][x] = false;
} else {
close[y][x] = true;
}
}
}
}
count = 0;
// 每次調(diào)用尋徑時(shí) 先清空所有集合中的原有數(shù)據(jù)
open.clear();
// 起點(diǎn)先添加到開(kāi)啟列表中
startNode.x = startX;
startNode.y = startY;
open.add(startNode);
while (!open.isEmpty()) {
// 開(kāi)啟列表中排序瓢捉，把F值最低的放到最底端
Collections.sort(open);
// 從開(kāi)啟列表中取出并刪除第一個(gè)節(jié)點(diǎn)(F為最低的)
current = open.remove(0);
// 判斷是否找到目標(biāo)點(diǎn)
if (current.x == targetX && current.y == targetY) {
result.clear();
// 將終點(diǎn)到起點(diǎn)的路徑添加到結(jié)果集中
while (current.parent != null) {
result.add(current);
current = current.parent;
}
return result;
}
// 左
if (isStraightable && current.x - 1 >= 0) {
createNextStep(current.x - 1, current.y, targetX, targetY,
COST_STRAIGHT);
}
// 上
if (isStraightable && current.y - 1 >= 0) {
createNextStep(current.x, current.y - 1, targetX, targetY,
COST_STRAIGHT);
}
// 右
if (isStraightable && current.x + 1 < mapW) {
createNextStep(current.x + 1, current.y, targetX, targetY,
COST_STRAIGHT);
}
// 下
if (isStraightable && current.y + 1 < mapH) {
createNextStep(current.x, current.y + 1, targetX, targetY,
COST_STRAIGHT);
}
// 左上
if (isObliqueable && current.x - 1 >= 0 && current.y - 1 >= 0) {
createNextStep(current.x - 1, current.y - 1, targetX, targetY,
COST_DIAGONAL);
}
// 左下
if (isObliqueable && current.x - 1 >= 0 && current.y + 1 < mapH) {
createNextStep(current.x - 1, current.y + 1, targetX, targetY,
COST_DIAGONAL);
}
// 右上
if (isObliqueable && current.x + 1 < mapW && current.y - 1 >= 0) {
createNextStep(current.x + 1, current.y - 1, targetX, targetY,
COST_DIAGONAL);
}
// 右下
if (isObliqueable && current.x + 1 < mapW && current.y + 1 < mapH) {
createNextStep(current.x + 1, current.y + 1, targetX, targetY,
COST_DIAGONAL);
}
// 添加到關(guān)閉列表中
close[current.y][current.x] = false;
}
return null;
}
/**
* 根據(jù)坐標(biāo)可否通行創(chuàng)建下一步
*/
private boolean createNextStep(int x, int y,
int targetX, int targetY, int cost) {
// 查找關(guān)閉集合中是否存在下一步的坐標(biāo)
if (!close[y][x]) return false;
// 查找開(kāi)啟列表中是否存在
tempNode.x = x;
tempNode.y = y;
int index = open.indexOf(tempNode);
Node node;
if (index != -1) {
// G值是否更小，即是否更新G办成，F(xiàn)值
if (current.g + cost < open.get(index).g) {
// 計(jì)算G F值
tempNode.g = current.g + cost;
tempNode.h = 0;
tempNode.f = tempNode.g + tempNode.h;
tempNode.parent = current;
node = new Node(tempNode);
// 替換原有節(jié)點(diǎn)
open.set(index, node);
++count;
}
} else {
// 計(jì)算G H F值
tempNode.g = current.g + cost;
tempNode.h = ((tempNode.x > targetX ? tempNode.x - targetX : targetX
- tempNode.x) << 6)
+ ((tempNode.y > targetY ? tempNode.y - targetY : targetY - tempNode.y) << 6);
tempNode.f = tempNode.g + tempNode.h;
tempNode.parent = current;
// 添加到開(kāi)啟列表中
node = new Node(tempNode);
open.add(node);
++count;
}
return true;
}
}
