Java 实现astar算法代码

下面是 Java 实现 A* 算法的示例代码，其中假设地图是一个二维数组，0 表示可以通过，1 表示障碍物，起点为 (startX, startY)，终点为 (endX, endY)：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class AStar {
    static class Node {
        int x; // 当前节点的 x 坐标
        int y; // 当前节点的 y 坐标
        int g; // 从起点到当前节点的实际距离
        int h; // 从当前节点到终点的估计距离
        Node parent; // 当前节点的父节点

        Node(int x, int y) {
            this.x = x;
            this.y = y;
            this.g = 0;
            this.h = 0;
            this.parent = null;
        }

        // 计算当前节点到终点的估计距离
        int estimateDistance(Node endNode) {
            return Math.abs(endNode.x - this.x) + Math.abs(endNode.y - this.y);
        }

        // 计算从起点到当前节点的总距离
        int getDistance() {
            int distance = this.g;
            Node node = this.parent;
            while (node != null) {
                distance += node.g;
                node = node.parent;
            }
            return distance;
        }
    }

    // A* 算法
    public static List<Node> aStar(int[][] map, int startX, int startY, int endX, int endY) {
        int rows = map.length;
        int cols = map[0].length;

        // 初始化起点和终点节点
        Node startNode = new Node(startX, startY);
        Node endNode = new Node(endX, endY);

        // 用优先队列保存待访问的节点
        PriorityQueue<Node> openList = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.g + o1.h - o2.g - o2.h;
            }
        });

        // 用列表保存已经访问过的节点
        List<Node> closeList = new ArrayList<>();

        // 将起点加入待访问队列
        openList.offer(startNode);

        while (!openList.isEmpty()) {
            // 取出 f 值最小的节点
            Node currentNode = openList.poll();

            // 如果当前节点为终点，返回路径
            if (currentNode.x == endNode.x && currentNode.y == endNode.y) {
                List<Node> path = new ArrayList<>();
                while (currentNode != null) {
                    path.add(currentNode);
                    currentNode = currentNode.parent;
                }
                return path;
            }

            // 将当前节点加入已访问列表
            closeList.add(currentNode);

            // 计算当前节点周围可访问的节点
            List<Node> neighbors = new ArrayList<>();
            if (currentNode.x > 0 && map[currentNode.x - 1][currentNode.y] == 0) {
                neighbors.add(new Node(currentNode.x - 1, currentNode.y));
            }
            if (currentNode.x < rows - 1 && map[currentNode.x + 1][currentNode.y] == 0) {
                neighbors.add(new Node(currentNode.x + 1, currentNode.y));
            }
            if (currentNode.y > 0 && map[currentNode.x][currentNode.y - 1] == 0) {
                neighbors.add(new Node(currentNode.x, currentNode.y - 1));
            }
            if (currentNode.y < cols - 1 && map[currentNode.x][currentNode.y + 1] == 0) {
                neighbors.add(new Node(currentNode.x, currentNode.y + 1));
            }

            // 遍历当前节点可访问的节点
            for (Node neighbor : neighbors) {
                // 如果已经访问过，跳过
                if (closeList.contains(neighbor)) {
                    continue;
                }

                // 计算从起点到当前节点的实际距离
                int g = currentNode.g + 1;

                // 如果当前节点不在待访问列表中，或者到当前节点的距离更小，则更新节点信息
                if (!openList.contains(neighbor) || g < neighbor.g) {
                    neighbor.g = g;
                    neighbor.h = neighbor.estimateDistance(endNode);
                    neighbor.parent = currentNode;

                    // 如果当前节点不在待访问列表中，则加入待访问列表
                    if (!openList.contains(neighbor)) {
                        openList.offer(neighbor);
                    }
                }
            }
        }

        // 如果无法到达终点，返回空路径
        return new ArrayList<>();
    }
}

使用方式如下：

int[][] map = {
    {0, 0, 0, 0, 0},
    {0, 1, 1, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
};
int startX = 0;
int startY = 0;
int endX = 4;
int endY = 4;
List<Node> path = AStar.aStar(map, startX, startY, endX, endY);
if (path.size() == 0) {
    System.out.println("无法到达终点");
} else {
    System.out.println("路径：");
    for (int i = path.size() - 1; i >= 0; i--) {
        System.out.println("(" + path.get(i).x + ", " + path.get(i).y + ")");
    }
}

输出结果如下：

路径：
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(3, 3)
(4, 3)
(4, 4)