A星算法Java实现详解编程语言

import java.util.ArrayList;   
import java.util.Collections;   
import java.util.Comparator;   
import java.util.List;   
public class AStar {   
private int[][] map;// 地图(1可通过 0不可通过)   
private List<Node> openList;// 开启列表   
private List<Node> closeList;// 关闭列表   
private final int COST_STRAIGHT = 10;// 垂直方向或水平方向移动的路径评分   
private final int COST_DIAGONAL = 14;// 斜方向移动的路径评分   
private int row;// 行   
private int column;// 列   
public AStar(int[][] map, int row, int column) {   
this.map = map;   
this.row = row;   
this.column = column;   
openList = new ArrayList<Node>();   
closeList = new ArrayList<Node>();   
}   
// 查找坐标（-1：错误，0：没找到，1：找到了）   
public int search(int x1, int y1, int x2, int y2) {   
if (x1 < 0 || x1 >= row || x2 < 0 || x2 >= row || y1 < 0   
|| y1 >= column || y2 < 0 || y2 >= column) {   
return -1;   
}   
if (map[x1][y1] == 0 || map[x2][y2] == 0) {   
return -1;   
}   
Node sNode = new Node(x1, y1, null);   
Node eNode = new Node(x2, y2, null);   
openList.add(sNode);   
List<Node> resultList = search(sNode, eNode);   
if (resultList.size() == 0) {   
return 0;   
}   
for (Node node : resultList) {   
map[node.getX()][node.getY()] = -1;   
}   
return 1;   
}   
// 查找核心算法   
private List<Node> search(Node sNode, Node eNode) {   
List<Node> resultList = new ArrayList<Node>();   
boolean isFind = false;   
Node node = null;   
while (openList.size() > 0) {   
// 取出开启列表中最低F值，即第一个存储的值的F为最低的   
node = openList.get(0);   
// 判断是否找到目标点   
if (node.getX() == eNode.getX() && node.getY() == eNode.getY()) {   
isFind = true;   
break;   
}   
// 上   
if ((node.getY() - 1) >= 0) {   
checkPath(node.getX(), node.getY() - 1, node, eNode,   
COST_STRAIGHT);   
}   
// 下   
if ((node.getY() + 1) < column) {   
checkPath(node.getX(), node.getY() + 1, node, eNode,   
COST_STRAIGHT);   
}   
// 左   
if ((node.getX() - 1) >= 0) {   
checkPath(node.getX() - 1, node.getY(), node, eNode,   
COST_STRAIGHT);   
}   
// 右   
if ((node.getX() + 1) < row) {   
checkPath(node.getX() + 1, node.getY(), node, eNode,   
COST_STRAIGHT);   
}   
// 左上   
if ((node.getX() - 1) >= 0 && (node.getY() - 1) >= 0) {   
checkPath(node.getX() - 1, node.getY() - 1, node, eNode,   
COST_DIAGONAL);   
}   
// 左下   
if ((node.getX() - 1) >= 0 && (node.getY() + 1) < column) {   
checkPath(node.getX() - 1, node.getY() + 1, node, eNode,   
COST_DIAGONAL);   
}   
// 右上   
if ((node.getX() + 1) < row && (node.getY() - 1) >= 0) {   
checkPath(node.getX() + 1, node.getY() - 1, node, eNode,   
COST_DIAGONAL);   
}   
// 右下   
if ((node.getX() + 1) < row && (node.getY() + 1) < column) {   
checkPath(node.getX() + 1, node.getY() + 1, node, eNode,   
COST_DIAGONAL);   
}   
// 从开启列表中删除   
// 添加到关闭列表中   
closeList.add(openList.remove(0));   
// 开启列表中排序，把F值最低的放到最底端   
Collections.sort(openList, new NodeFComparator());   
}   
if (isFind) {   
getPath(resultList, node);   
}   
return resultList;   
}   
// 查询此路是否能走通   
private boolean checkPath(int x, int y, Node parentNode, Node eNode,   
int cost) {   
Node node = new Node(x, y, parentNode);   
// 查找地图中是否能通过   
if (map[x][y] == 0) {   
closeList.add(node);   
return false;   
}   
// 查找关闭列表中是否存在   
if (isListContains(closeList, x, y) != -1) {   
return false;   
}   
// 查找开启列表中是否存在   
int index = -1;   
if ((index = isListContains(openList, x, y)) != -1) {   
// G值是否更小，即是否更新G，F值   
if ((parentNode.getG() + cost) < openList.get(index).getG()) {   
node.setParentNode(parentNode);   
countG(node, eNode, cost);   
countF(node);   
openList.set(index, node);   
}   
} else {   
// 添加到开启列表中   
node.setParentNode(parentNode);   
count(node, eNode, cost);   
openList.add(node);   
}   
return true;   
}   
// 集合中是否包含某个元素(-1：没有找到，否则返回所在的索引)   
private int isListContains(List<Node> list, int x, int y) {   
for (int i = 0; i < list.size(); i++) {   
Node node = list.get(i);   
if (node.getX() == x && node.getY() == y) {   
return i;   
}   
}   
return -1;   
}   
// 从终点往返回到起点   
private void getPath(List<Node> resultList, Node node) {   
if (node.getParentNode() != null) {   
getPath(resultList, node.getParentNode());   
}   
resultList.add(node);   
}   
// 计算G,H,F值   
private void count(Node node, Node eNode, int cost) {   
countG(node, eNode, cost);   
countH(node, eNode);   
countF(eNode);   
}   
// 计算G值   
private void countG(Node node, Node eNode, int cost) {   
if (node.getParentNode() == null) {   
node.setG(cost);   
} else {   
node.setG(node.getParentNode().getG() + cost);   
}   
}   
// 计算H值   
private void countH(Node node, Node eNode){   
int x = Math.abs(node.getX() - eNode.getX());   
int y = Math.abs(node.getY() - eNode.getY());   
if(x<y){   
node.setH(x * COST_DIAGONAL + (y-x) * COST_STRAIGHT);   
}else{   
node.setH(y * COST_DIAGONAL + (x-y) * COST_STRAIGHT);   
}   
}   
// 计算F值   
private void countF(Node node) {   
node.setF(node.getG() + node.getH());   
}   
public static void main(String[] args) {   
int[][] map=new int[][]{// 地图数组   
{1,1,1,1,1,1,1,1,1,1},   
{1,1,1,1,0,1,1,1,1,1},   
{1,1,1,1,0,1,1,1,1,1},   
{1,1,1,1,0,1,1,1,1,1},   
{1,1,1,1,0,1,1,1,1,1},   
{1,1,1,1,0,1,1,1,1,1}   
};   
AStar aStar=new AStar(map, 6, 10);   
int flag=aStar.search(4, 0, 3, 8);   
if(flag==-1){   
System.out.println("传输数据有误！");   
}else if(flag==0){   
System.out.println("没找到！");   
}else{   
for(int x=0;x<6;x++){   
for(int y=0;y<10;y++){   
if(map[x][y]==1){   
System.out.print("　");   
}else if(map[x][y]==0){   
System.out.print("〓");   
}else if(map[x][y]==-1){   
System.out.print("※");   
}   
}   
System.out.println();   
}   
}   
}   
}   
// 节点类   
class Node {   
private int x;// X坐标   
private int y;// Y坐标   
private Node parentNode;// 父类节点   
private int g;// 当前点到起点的移动耗费   
private int h;// 当前点到终点的移动耗费，即曼哈顿距离|x1-x2|+|y1-y2|(忽略障碍物)   
private int f;// f=g+h   
public Node(int x, int y, Node parentNode) {   
this.x = x;   
this.y = y;   
this.parentNode = parentNode;   
}   
public int getX() {   
return x;   
}   
public void setX(int x) {   
this.x = x;   
}   
public int getY() {   
return y;   
}   
public void setY(int y) {   
this.y = y;   
}   
public Node getParentNode() {   
return parentNode;   
}   
public void setParentNode(Node parentNode) {   
this.parentNode = parentNode;   
}   
public int getG() {   
return g;   
}   
public void setG(int g) {   
this.g = g;   
}   
public int getH() {   
return h;   
}   
public void setH(int h) {   
this.h = h;   
}   
public int getF() {   
return f;   
}   
public void setF(int f) {   
this.f = f;   
}   
}   
// 节点比较类   
class NodeFComparator implements Comparator<Node> {   
@Override   
public int compare(Node o1, Node o2) {   
return o1.getF() - o2.getF();   
}   
}