java如何实现AStar

A*（A-Star）算法是一种常用的启发式搜索算法，可以用于解决许多问题，如路径规划、游戏AI等。下面是Java实现A*算法的基本步骤：

1. 定义节点类：包含节点坐标、父节点、起始到当前节点的实际代价G值、当前节点到目标节点的预估代价H值和F值（F值为G值和H值的和）等信息。

public class Node {
    public int x;
    public int y;
    public int f;
    public int g;
    public int h;
    public Node parent;

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

2. 实现A*算法的主函数：设置起始节点和目标节点，将起始节点加入开放列表(openList)，然后进行循环，直到开放列表为空或者找到目标节点为止。每次循环从开放列表中找到F值最小的节点作为当前节点(currentNode)，将其从开放列表中删除并加入到已关闭列表(closedList)中，然后对当前节点的所有相邻节点进行处理，如果相邻节点不在已关闭列表中，则将其加入到开放列表中。对于已经在开放列表中的相邻节点，比较起始节点到当前节点的实际代价G值与起始节点到相邻节点的实际代价G值，如果当前节点到相邻节点的实际代价更小，则更新相邻节点的父节点为当前节点，并重新计算相邻节点的F值。

public static List<Node> aStar(int[][] map, Node startNode, Node endNode) {
    List<Node> openList = new ArrayList<>();
    List<Node> closedList = new ArrayList<>();
    openList.add(startNode);

    while (!openList.isEmpty()) {
        Node currentNode = getLowestFNode(openList);
        openList.remove(currentNode);
        closedList.add(currentNode);

        if (currentNode.x == endNode.x && currentNode.y == endNode.y) {
            return getPath(currentNode);
        }

        List<Node> neighbors = getNeighbors(map, currentNode);
        for (Node neighbor : neighbors) {
            if (closedList.contains(neighbor)) {
                continue;
            }
            int g = currentNode.g + getActualCost(currentNode, neighbor);
            boolean isOpen = openList.contains(neighbor);
            if (!isOpen || g < neighbor.g) {
                neighbor.g = g;
                neighbor.h = getHeuristicCost(neighbor, endNode);
                neighbor.f = neighbor.g + neighbor.h;
                neighbor.parent = currentNode;
                if (!isOpen) {
                    openList.add(neighbor);
                }
            }
        }
    }

    return null;
}

3. 实现各种辅助函数，如计算两个节点之间的实际代价、计算两个节点之间的预估代价、获取某个节点的所有相邻节点等。

完整代码示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class AStar {
    public static void main(String[] args) {
        int[][] map = {
                {0, 0, 0, 0, 0},
                {0, 1, 1, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0},
        };
        Node startNode = new Node(0, 0);
        Node endNode = new Node(4, 4);
        List<Node> path = aStar(map, startNode, endNode);
        if (path != null) {
            for (Node node : path) {
                System.out.println("(" + node.x + ", " + node.y + ")");
            }
        }
    }

    public static List<Node> aStar(int[][] map, Node startNode, Node endNode) {
        List<Node> openList = new ArrayList<>();
        List<Node> closedList = new ArrayList<>();
        openList.add(startNode);

        while (!openList.isEmpty()) {
            Node currentNode = getLowestFNode(openList);
            openList.remove(currentNode);
            closedList.add(currentNode);

            if (currentNode.x == endNode.x && currentNode.y == endNode.y) {
                return getPath(currentNode);
            }

            List<Node> neighbors = getNeighbors(map, currentNode);
            for (Node neighbor : neighbors) {
                if (closedList.contains(neighbor)) {
                    continue;
                }
                int g = currentNode.g + getActualCost(currentNode, neighbor);
                boolean isOpen = openList.contains(neighbor);
                if (!isOpen || g < neighbor.g) {
                    neighbor.g = g;
                    neighbor.h = getHeuristicCost(neighbor, endNode);
                    neighbor.f = neighbor.g + neighbor.h;
                    neighbor.parent = currentNode;
                    if (!isOpen) {
                        openList.add(neighbor);
                    }
                }
            }
        }

        return null;
    }

    private static Node getLowestFNode(List<Node> nodes) {
        Node lowestFNode = nodes.get(0);
        for (Node node : nodes) {
            if (node.f < lowestFNode.f) {
                lowestFNode = node;
            }
        }
        return lowestFNode;
    }

    private static List<Node> getNeighbors(int[][] map, Node node) {
        List<Node> neighbors = new ArrayList<>();
        int x = node.x;
        int y = node.y;
        int maxX = map.length - 1;
        int maxY = map[0].length - 1;
        if (x > 0 && map[x - 1][y] == 0) {
            neighbors.add(new Node(x - 1, y));
        }
        if (x < maxX && map[x + 1][y] == 0) {
            neighbors.add(new Node(x + 1, y));
        }
        if (y > 0 && map[x][y - 1] == 0) {
            neighbors.add(new Node(x, y - 1));
        }
        if (y < maxY && map[x][y + 1] == 0) {
            neighbors.add(new Node(x, y + 1));
        }
        return neighbors;
    }

    private static int getActualCost(Node node1, Node node2) {
        int x = Math.abs(node1.x - node2.x);
        int y = Math.abs(node1.y - node2.y);
        if (x + y == 1) {
            return 10;
        } else if (x + y == 2) {
            return 14;
        } else {
            throw new RuntimeException("Cannot calculate actual cost between non-adjacent nodes");
        }
    }

    private static int getHeuristicCost(Node node1, Node node2) {
        int dx = Math.abs(node1.x - node2.x);
        int dy = Math.abs(node1.y - node2.y);
        return 10 * (dx + dy);
    }

    private static List<Node> getPath(Node endNode) {
        List<Node> path = new ArrayList<>();
        Node currentNode = endNode;
        while (currentNode != null) {
            path.add(currentNode);
            currentNode = currentNode.parent;
        }
        Collections.reverse(path);
        return path;
    }
}

class Node {
    public int x;
    public int y;
    public int f;
    public int g;
    public int h;
    public Node parent;

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