java实现的A星算法A星算法原理:
⽤法：
这⾥是⼋⽅寻路，如果想改成四⽅寻路，把AStar中对应的四⾏搜索代码注释掉就好了。
public class test {
public static void main(String[] arg) {
//创建⼀个寻路的⼆维数组，0是可⾏⾛区域，⾮0是障碍
int[][] map2d = new int[10][10];
//设置⼀些障碍
map2d[4][0]= 1;
刘若英后来歌词
map2d[4][1] = 1;
map2d[4][2] = 1;
map2d[4][3] = 1;
map2d[4][4] = 1;
map2d[4][5] = 1;
map2d[4][6] = 1;
//创建A星对象
AStar astar = new AStar(map2d,new Point(0,0),new Point(9,0));
//开始寻路
ArrayList<Point> pointList = astar.start();
//打印寻路结果
for(Point point:pointList){
System.out.println(point.x+","+ point.y);
}
}
}
炸芋头的做法
运⾏结果：
1,1
2,2
3,3
3,4
3,5
3,6
4,7
5,7
5,6
6,6
7,6
8,6
8,5
9,5
9,4
9,3
9,2
9,1
9,0
源码：
⼀共3个java⽂件：AStar.java、Node.java、Point.java
Point.java:
//表⽰⼀个⼆维点
public class Point {问卷调查问题
public int x;公司规定
public int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
//判断两个点是不是相同
public boolean eq(Point p) {
return this.x == p.x && this.y == p.y;
}
}
Node.java:
public class Node implements Comparable<Node>{
public Point point; //节点⾃⼰的坐标
public Node father; //⽗节点
//f=g+h
int g;
int h;
public Node(Point point, Point endPoint, int g) {
this.point = point;
this.g = g;
this.h = (Math.abs(endPoint.x - point.x) + Math.abs(endPoint.y - point.y)) * 10; }
@Override
关于梦想的励志句子public int compareTo(Node o) {
if(o==null) return -1;
if(this.g+this.h>o.g+o.h){
return 1;
}el if(this.g+this.h<o.g+o.h){
return -1;
}el{
return 0;
}
}
}
AStar.java:
s.AStar;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
public class AStar {
private PriorityQueue<Node> openList = new PriorityQueue<>();
private ArrayList<Node> cloList = new ArrayList<>();
private int[][] map;
private Point startPoint;
private Point endPoint;
private int w;
private int h;
private int h;
public AStar(int[][] map, Point startPoint, Point endPoint) {
this.map = map;
this.w = map.length;
this.h = map[0].length;
this.startPoint = startPoint;
}
//判断point是不是在关闭表中
public Node pointInCloList(Point point) {
for (Node node : this.cloList) {
if (node.point.eq(point)) {
return node;
}
}
return null;
}
//判断point是否在开启表中，如果在就返回它（不取出）
public Node pointInOpenList(Point point) {
for (Node node : this.openList) {
if (node.point.eq(point)) {
return node;
}
}
return null;
}
//搜索周围节点
private void archNear(Node minNode, int offtX, int offtY) {
//越界检测
if (minNode.point.x + offtX < 0 || minNode.point.x + offtX >= this.w || minNode.point.y + offtY < 0 || minNode.point.y + offtY >= this.h) { return;
}
//如果是障碍就忽略
if (this.map[minNode.point.x + offtX][minNode.point.y + offtY] != 0) {
return;
}
//如果在clolist中就忽略
Point currentPoint = new Point(minNode.point.x + offtX, minNode.point.y + offtY);
女子防身if (this.pointInCloList(currentPoint)!=null) {
return;
石渠记}
//设置单位花费
int step;
if (offtX == 0 || offtY == 0) {
step = 10;
} el {
step = 14;
}
Node currentNode = this.pointInOpenList(currentPoint);
//如果不在openList中，就把它加⼊openList
if (currentNode == null) {
currentNode = new Node(currentPoint, dPoint, minNode.g + step);
currentNode.father = minNode;
this.openList.add(currentNode);
return;
}
//如果在openList中，判断minNode到当前点的G是否更⼩
if (minNode.g + step < currentNode.g) {
/
/g值更⼩，重新计算g值并且改变father
currentNode.g = minNode.g + step;
currentNode.father = minNode;
currentNode.father = minNode;
}
}
public ArrayList<Point> start() {
//寻路结果
ArrayList<Point> pointList = new ArrayList<>();
//如果寻路终点是障碍，就直接中断寻路
if (this.dPoint.x][dPoint.y] == 1) {
return null;
}
//1.把起点放⼊开启表
Node startNode = new Node(this.startPoint, dPoint, 0); this.openList.add(startNode);
//2.主循环寻路
while (true) {
//从openlist中取出F值最⼩的节点
Node minNode = this.openList.poll();
//把这个点加⼊到cloList
this.cloList.add(minNode);
郭为//搜索当前节点周围的节点
this.archNear(minNode, 0, -1);
this.archNear(minNode, 0, 1);
this.archNear(minNode, -1, 0);
this.archNear(minNode, 1, 0);
this.archNear(minNode, -1, -1);
this.archNear(minNode, 1, 1);
this.archNear(minNode, -1, 1);
this.archNear(minNode, 1, -1);
//判断是否终⽌
Node node = this.dPoint);
if(node!=null){
/
/终点在关闭表中，说明寻路成功
while(true){
if(node.father!=null){
pointList.add(node.point);
node = node.father;
}el{
return pointList;
}
}
}
if (this.openList.size() == 0) {
return null;
}
}
}
}
