用java语言实现A*算法

以下是一个简单的Java实现A*算法的示例代码：

import java.util.*;

public class AStar {
    private static final int DIAGONAL_COST = 14;
    private static final int VERTICAL_COST = 10;

    private Queue<Node> openList;
    private Set<Node> closedSet;
    private Map<Node, Node> parentNodes;
    private Map<Node, Integer> gScore;
    private Map<Node, Integer> fScore;

    public AStar() {
        this.openList = new PriorityQueue<>(Comparator.comparingInt(Node::getfScore));
        this.closedSet = new HashSet<>();
        this.parentNodes = new HashMap<>();
        this.gScore = new HashMap<>();
        this.fScore = new HashMap<>();
    }

    public List<Node> findPath(Node startNode, Node goalNode, Map<Node, List<Node>> adjacencyList) {
        openList.add(startNode);
        gScore.put(startNode, 0);
        fScore.put(startNode, calculateHeuristic(startNode, goalNode));
        while (!openList.isEmpty()) {
            Node currentNode = openList.poll();
            if (currentNode.equals(goalNode)) {
                return reconstructPath(currentNode);
            }
            closedSet.add(currentNode);
            for (Node neighbor : adjacencyList.get(currentNode)) {
                if (closedSet.contains(neighbor)) {
                    continue;
                }
                int tentativeGScore = gScore.get(currentNode) + getDistance(currentNode, neighbor);
                if (!openList.contains(neighbor)) {
                    openList.add(neighbor);
                } else if (tentativeGScore >= gScore.get(neighbor)) {
                    continue;
                }
                parentNodes.put(neighbor, currentNode);
                gScore.put(neighbor, tentativeGScore);
                fScore.put(neighbor, tentativeGScore + calculateHeuristic(neighbor, goalNode));
            }
        }
        return Collections.emptyList();
    }

    private int getDistance(Node nodeA, Node nodeB) {
        int distanceX = Math.abs(nodeA.getX() - nodeB.getX());
        int distanceY = Math.abs(nodeA.getY() - nodeB.getY());
        if (distanceX > distanceY) {
            return DIAGONAL_COST * distanceY + VERTICAL_COST * (distanceX - distanceY);
        } else {
            return DIAGONAL_COST * distanceX + VERTICAL_COST * (distanceY - distanceX);
        }
    }

    private int calculateHeuristic(Node nodeA, Node nodeB) {
        return Math.abs(nodeA.getX() - nodeB.getX()) + Math.abs(nodeA.getY() - nodeB.getY());
    }

    private List<Node> reconstructPath(Node currentNode) {
        List<Node> path = new ArrayList<>();
        path.add(currentNode);
        while (parentNodes.containsKey(currentNode)) {
            currentNode = parentNodes.get(currentNode);
            path.add(0, currentNode);
        }
        return path;
    }
}

class Node {
    private final int x;
    private final int y;
    private int fScore;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
        this.fScore = Integer.MAX_VALUE;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getfScore() {
        return fScore;
    }

    public void setfScore(int fScore) {
        this.fScore = fScore;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return x == node.x && y == node.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

在这个实现中，`AStar`类包含了A*算法的实现。在`findPath`方法中，我们传递起始节点、目标节点和一个邻接列表，该列表表示每个节点的相邻节点。

在A*算法的实现中，我们使用几个数据结构来跟踪算法的状态。我们使用一个优先队列（`openList`）来保存所有尚未扩展的节点，该队列按f分数从低到高排序。我们还使用一个集合（`closedSet`）来跟踪已经扩展过的节点。我们使用两个Map（`parentNodes`和`gScore`）来跟踪每个节点的父节点和g分数。最后，我们使用一个Map（`fScore`）来跟踪每个节点的f分数。

在`findPath`方法的主循环中，我们从`openList`中获取具有最低f分数的节点，将其添加到`closedSet`中，并考虑其每个相邻节点。对于每个相邻节点，我们计算新的g分数并更新父节点，g分数和f分数。如果相邻节点不在`openList`中，则将其添加到`openList`中。否则，如果新的g分数不比现有的g分数更好，则跳过该节点。

如果我们成功找到目标节点，则返回重构的路径。在重构路径时，我们从目标节点开始，并沿着每个节点的父节点向后遍历，直到达到起始节点。这将产生一条路径，其中第一个节点是起始节点，最后一个节点是目标节点。

在这个示例代码中，我们只考虑了水平和垂直移动，而没有考虑对角线移动。我们还假设每个节点都是相同的大小。如果需要考虑对角线移动或不同大小的节点，请相应地更改`getDistance`和`calculateHeuristic`方法。