A*路径搜索问题的处理(Java)

A路径搜索是一种常用的寻路算法，可以在图形化地图中找到最短路径。以下是一个用Java实现A路径搜索的示例代码：

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

class Node implements Comparable<Node> {
    int x, y;
    int g, h;
    Node parent;

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

    public int f() {
        return g + h;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.f(), other.f());
    }
}

public class AStarPathfinding {
    private int[][] map;
    private int startX, startY;
    private int targetX, targetY;
    private List<Node> openList;
    private List<Node> closedList;

    public AStarPathfinding(int[][] map, int startX, int startY, int targetX, int targetY) {
        this.map = map;
        this.startX = startX;
        this.startY = startY;
        this.targetX = targetX;
        this.targetY = targetY;
        this.openList = new ArrayList<>();
        this.closedList = new ArrayList<>();
    }

    public List<Node> findPath() {
        Node startNode = new Node(startX, startY);
        Node targetNode = new Node(targetX, targetY);
        openList.add(startNode);

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

            if (currentNode.x == targetX && currentNode.y == targetY) {
                return reconstructPath(currentNode);
            }

            List<Node> neighbors = getNeighbors(currentNode);
            for (Node neighbor : neighbors) {
                if (closedList.contains(neighbor)) {
                    continue;
                }

                int cost = currentNode.g + 1;
                boolean isBetter = false;

                if (!openList.contains(neighbor)) {
                    openList.add(neighbor);
                    neighbor.h = heuristic(neighbor, targetNode);
                    isBetter = true;
                } else if (cost < neighbor.g) {
                    isBetter = true;
                }

                if (isBetter) {
                    neighbor.parent = currentNode;
                    neighbor.g = cost;
                }
            }

            Collections.sort(openList);
        }

        return null;
    }

    private List<Node> getNeighbors(Node node) {
        List<Node> neighbors = new ArrayList<>();
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int[] dir : directions) {
            int neighborX = node.x + dir[0];
            int neighborY = node.y + dir[1];

            if (isValidCoordinate(neighborX, neighborY) && map[neighborX][neighborY] == 0) {
                neighbors.add(new Node(neighborX, neighborY));
            }
        }

        return neighbors;
    }

    private boolean isValidCoordinate(int x, int y) {
        return x >= 0 && x < map.length && y >= 0 && y < map[0].length;
    }

    private int heuristic(Node node1, Node node2) {
        return Math.abs(node1.x - node2.x) + Math.abs(node1.y - node2.y);
    }

    private List<Node> reconstructPath(Node node) {
        List<Node> path = new ArrayList<>();
        Node currentNode = node;

        while (currentNode != null) {
            path.add(currentNode);
            currentNode = currentNode.parent;
        }

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        int[][] map = {
                {0, 0, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 0, 0},
        };
        int startX = 0, startY = 0;
        int targetX = 3, targetY = 4;

        AStarPathfinding pathfinding = new AStarPathfinding(map, startX, startY, targetX, targetY);
        List<Node> path = pathfinding.findPath();

        if (path != null) {
            for (Node node : path) {
                System.out.println("(" + node.x + ", " + node.y + ")");
            }
        } else {
            System.out.println("No path found");
        }
    }
}

上述代码实现了一个简单的A*路径搜索算