a-star java实现
时间: 2023-11-02 14:05:22 浏览: 39
以下是A*算法的Java实现:
首先,需要定义一个节点类Node,包含节点坐标、父节点、起始点到该节点的距离g、该节点到终点的估价距离h和f值(f = g + h)。
```java
public class Node {
public int x; // 节点x坐标
public int y; // 节点y坐标
public Node parent; // 父节点
public int g; // 起始点到该节点的距离
public int h; // 该节点到终点的估价距离
public int f; // f = g + h
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
```
接下来,定义一个AStar类,包含起点、终点、障碍物、地图大小等信息,以及A*算法的实现。
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class AStar {
private int[][] map; // 地图,0表示可以通过,1表示障碍物
private int width; // 地图宽度
private int height; // 地图高度
private Node start; // 起点
private Node end; // 终点
public AStar(int[][] map, Node start, Node end) {
this.map = map;
this.width = map.length;
this.height = map[0].length;
this.start = start;
this.end = end;
}
// 获取从起点到终点的最短路径
public List<Node> findPath() {
List<Node> openList = new ArrayList<>(); // 开启列表,存放待扩展的节点
List<Node> closeList = new ArrayList<>(); // 关闭列表,存放已扩展的节点
openList.add(start); // 将起点加入开启列表
while (!openList.isEmpty()) {
Node current = findLowestFNode(openList); // 选择f值最小的节点进行扩展
openList.remove(current);
closeList.add(current);
if (current.x == end.x && current.y == end.y) { // 当前节点为终点,路径已找到
return buildPath(current);
}
for (Node neighbor : getNeighbors(current)) { // 扩展当前节点的邻居节点
if (closeList.contains(neighbor)) { // 如果邻居节点已经在关闭列表中,跳过
continue;
}
int g = current.g + 1; // 计算起始点到邻居节点的距离
if (!openList.contains(neighbor)) { // 如果邻居节点不在开启列表中,加入开启列表
neighbor.g = g;
neighbor.h = estimateDistance(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current;
openList.add(neighbor);
} else if (g < neighbor.g) { // 如果邻居节点已经在开启列表中,更新g值和父节点
neighbor.g = g;
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current;
}
}
}
return null; // 开启列表为空,无法到达终点,返回null
}
// 获取当前节点的邻居节点
private List<Node> getNeighbors(Node node) {
List<Node> neighbors = new ArrayList<>();
if (node.x > 0 && map[node.x - 1][node.y] == 0) { // 左
neighbors.add(new Node(node.x - 1, node.y));
}
if (node.y > 0 && map[node.x][node.y - 1] == 0) { // 上
neighbors.add(new Node(node.x, node.y - 1));
}
if (node.x < width - 1 && map[node.x + 1][node.y] == 0) { // 右
neighbors.add(new Node(node.x + 1, node.y));
}
if (node.y < height - 1 && map[node.x][node.y + 1] == 0) { // 下
neighbors.add(new Node(node.x, node.y + 1));
}
return neighbors;
}
// 估算从当前节点到终点的距离
private int estimateDistance(Node from, Node to) {
return Math.abs(from.x - to.x) + Math.abs(from.y - to.y);
}
// 从开启列表中找到f值最小的节点
private Node findLowestFNode(List<Node> openList) {
Node lowestFNode = openList.get(0);
for (Node node : openList) {
if (node.f < lowestFNode.f) {
lowestFNode = node;
}
}
return lowestFNode;
}
// 构建从起点到终点的路径
private List<Node> buildPath(Node end) {
List<Node> path = new ArrayList<>();
Node current = end;
while (current != null) {
path.add(current);
current = current.parent;
}
Collections.reverse(path);
return path;
}
}
```
最后,可以使用以下代码测试A*算法的实现。
```java
public class Main {
public static void main(String[] args) {
int[][] map = {
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 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, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
};
Node start = new Node(1, 1);
Node end = new Node(6, 6);
AStar aStar = new AStar(map, start, end);
List<Node> path = aStar.findPath();
if (path != null) {
for (Node node : path) {
System.out.println("(" + node.x + ", " + node.y + ")");
}
} else {
System.out.println("No path found.");
}
}
}
```