用Java写一个A*算法
时间: 2023-03-24 09:01:44 浏览: 81
好的,以下是一个Java语言实现的A*算法的示例代码:
```
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class AStarAlgorithm {
public static class Node implements Comparable<Node> {
public int x;
public int y;
public int fCost;
public int gCost;
public int hCost;
public boolean isObstacle;
public Node parent;
public Node(int x, int y, boolean isObstacle) {
this.x = x;
this.y = y;
this.isObstacle = isObstacle;
this.fCost = 0;
this.gCost = 0;
this.hCost = 0;
this.parent = null;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.fCost, other.fCost);
}
}
public static List<Node> findPath(Node[][] grid, Node start, Node end) {
List<Node> path = new ArrayList<>();
PriorityQueue<Node> openSet = new PriorityQueue<>();
List<Node> closedSet = new ArrayList<>();
start.gCost = 0;
start.hCost = calculateHeuristicCost(start, end);
start.fCost = start.gCost + start.hCost;
openSet.add(start);
while (!openSet.isEmpty()) {
Node current = openSet.poll();
if (current == end) {
path = reconstructPath(current);
break;
}
closedSet.add(current);
for (Node neighbor : getNeighbors(grid, current)) {
if (closedSet.contains(neighbor) || neighbor.isObstacle) {
continue;
}
int tentativeGCost = current.gCost + calculateDistanceCost(current, neighbor);
if (!openSet.contains(neighbor) || tentativeGCost < neighbor.gCost) {
neighbor.parent = current;
neighbor.gCost = tentativeGCost;
neighbor.hCost = calculateHeuristicCost(neighbor, end);
neighbor.fCost = neighbor.gCost + neighbor.hCost;
if (!openSet.contains(neighbor)) {
openSet.add(neighbor);
}
}
}
}
return path;
}
private static List<Node> getNeighbors(Node[][] grid, Node node) {
List<Node> neighbors = new ArrayList<>();
int numRows = grid.length;
int numCols = grid[0].length;
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (i == 0 && j == 0) {
continue;
}
int neighborX = node.x + i;
int neighborY = node.y + j;
if (neighborX >= 0 && neighborX < numRows && neighborY >= 0 && neighborY < numCols) {
neighbors.add(grid[neighborX][neighborY]);
}
}
}
return neighbors;
}
private static int calculateDistanceCost(Node nodeA, Node nodeB) {
int distance = 0;
int dx = Math.abs(nodeA.x - nodeB.x);
int dy = Math.abs(nodeA.y - nodeB.y);
if (dx > dy) {
distance = 14 * dy + 10 * (dx - dy);
} else {
distance = 14 * dx + 10 * (dy - dx);
}
return distance;
}
private static int calculateHeuristicCost(Node nodeA, Node nodeB) {
int dx = Math.abs(nodeA.x - node