A*算法java代码实现
时间: 2023-09-04 21:06:46 浏览: 69
很高兴回答你的问题!以下是 A* 算法的 Java 代码实现:
```
public class AStar {
private PriorityQueue<Node> openList;
private Set<Node> closedList;
private Map<Node, Node> cameFrom;
private Map<Node, Integer> gScore;
private Map<Node, Integer> fScore;
public List<Node> findPath(Node start, Node end) {
openList = new PriorityQueue<>();
openList.add(start);
closedList = new HashSet<>();
cameFrom = new HashMap<>();
gScore = new HashMap<>();
gScore.put(start, 0);
fScore = new HashMap<>();
fScore.put(start, heuristicCostEstimate(start, end));
while (!openList.isEmpty()) {
Node current = openList.poll();
if (current.equals(end)) {
return reconstructPath(cameFrom, current);
}
closedList.add(current);
for (Node neighbor : current.getNeighbors()) {
if (closedList.contains(neighbor)) {
continue;
}
int tentativeGScore = gScore.get(current) + current.distanceTo(neighbor);
if (!openList.contains(neighbor) || tentativeGScore < gScore.get(neighbor)) {
cameFrom.put(neighbor, current);
gScore.put(neighbor, tentativeGScore);
fScore.put(neighbor, tentativeGScore + heuristicCostEstimate(neighbor, end));
if (!openList.contains(neighbor)) {
openList.add(neighbor);
}
}
}
}
return null;
}
private int heuristicCostEstimate(Node start, Node end) {
int dx = Math.abs(start.getX() - end.getX());
int dy = Math.abs(start.getY() - end.getY());
return dx + dy;
}
private List<Node> reconstructPath(Map<Node, Node> cameFrom, Node current) {
List<Node> path = new ArrayList<>();
path.add(current);
while (cameFrom.containsKey(current)) {
current = cameFrom.get(current);
path.add(0, current);
}
return path;
}
}
```
希望这个代码实现能够帮到你!