java实现A*寻路算法

在Java中实现A*（A-star）寻路算法，首先需要理解其基本原理，它是一种启发式搜索算法，用于在图或网格中寻找从起点到终点的最短路径。A*算法依赖于两部分：代价函数（cost function）和启发函数（heuristic function）。代价函数通常是实际距离，启发函数是对估计距离的一个近似值。

以下是简单的A*算法步骤：

1. 初始化：设置起始节点（start node）为当前节点，并将其加入开放列表（open list）。
2. 检查开放列表：找到F值最小的节点（F = G + H，G是已走过的代价，H是启发函数的估算代价），如果它是目标节点，则结束；否则选取它作为下一个节点。
3. 更新节点状态：访问该节点，并在关闭列表（closed list）中记录。检查所有相邻节点，更新它们的G值和F值（如果有路径比当前更优）。
4. 将未访问的相邻节点加入开放列表。
5. 重复步骤2-4，直到找到目标节点或开放列表为空。

以下是一个简单的Java代码实现，使用邻接矩阵表示图：

import java.util.*;

class Node implements Comparable<Node> {
    int x, y;
    int gScore, fScore;
    Node parent;

    // ... getters and setters

    @Override
    public int compareTo(Node other) {
        return this.fScore - other.fScore; // 根据fScore排序
    }
}

public class AStar {
    public List<Node> findPath(Map<Point, List<Node>> graph, Point start, Point end) {
        // ... 实现启发函数、初始化等
        PriorityQueue<Node> openList = new PriorityQueue<>();
        Node startNode = new Node(start.x, start.y, 0, heuristic(start, end));
        startNode.parent = null;
        openList.offer(startNode);

        while (!openList.isEmpty()) {
            Node current = openList.poll();
            if (current.equals(end)) {
                // Path reconstruction
                List<Node> path = reconstructPath(current);
                return path;
            }

            for (Node neighbor : graph.getOrDefault(current, Collections.emptyList())) {
                // 计算新的GScore和FScore
                int tentativeGScore = current.gScore + distance(current, neighbor);
                if (tentativeGScore < neighbor.gScore) {
                    neighbor.gScore = tentativeGScore;
                    neighbor.fScore = tentativeGScore + heuristic(neighbor, end);
                    neighbor.parent = current;
                    // 若邻居在关闭列表，移除后重新添加
                    openList.removeIf(n -> n.equals(neighbor));
                    openList.offer(neighbor);
                }
            }
        }

        return null; // No path found
    }

    // ... 其他辅助方法如启发函数、距离计算等
}