jps算法,java实例

JPS（Jump Point Search）算法是一种优化版的A*算法，用于在网格图中寻找最短路径。与A*算法相比，JPS算法在搜索效率和路径长度上都有很大的提升。

JPS算法的主要思想是，在进行路径搜索时，对于某个节点，我们不仅考虑直接相邻的节点，还需要考虑跳跃点（Jump Point）。跳跃点是指从该节点出发，可以一次性跳过多个相邻节点的点。通过预先计算和记录跳跃点，可以大大减少搜索时需要遍历的节点数量，从而提高搜索效率。

以下是Java实现JPS算法的示例代码：

import java.util.*;

public class JPS {

    private int[][] grid;
    private int rows, cols;
    private PriorityQueue<Node> openSet;

    public JPS(int[][] grid) {
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
        this.openSet = new PriorityQueue<Node>(new Comparator<Node>() {
            public int compare(Node n1, Node n2) {
                return n1.f - n2.f;
            }
        });
    }

    public List<int[]> findPath(int[] start, int[] end) {
        Node startNode = new Node(start, start);
        Node endNode = new Node(end, end);

        Map<String, Node> cameFrom = new HashMap<String, Node>();
        Map<String, Integer> gScore = new HashMap<String, Integer>();
        Map<String, Integer> fScore = new HashMap<String, Integer>();

        gScore.put(startNode.toString(), 0);
        fScore.put(startNode.toString(), heuristic(startNode, endNode));
        openSet.add(startNode);

        while (!openSet.isEmpty()) {
            Node current = openSet.poll();
            if (current.equals(endNode)) {
                return reconstructPath(cameFrom, current);
            }

            for (Node neighbor : getNeighbors(current)) {
                int tentativeGScore = gScore.get(current.toString()) + distance(current, neighbor);
                if (!gScore.containsKey(neighbor.toString()) || tentativeGScore < gScore.get(neighbor.toString())) {
                    cameFrom.put(neighbor.toString(), current);
                    gScore.put(neighbor.toString(), tentativeGScore);
                    fScore.put(neighbor.toString(), tentativeGScore + heuristic(neighbor, endNode));
                    if (!openSet.contains(neighbor)) {
                        openSet.add(neighbor);
                    }
                }
            }
        }

        return null;
    }

    private List<int[]> reconstructPath(Map<String, Node> cameFrom, Node current) {
        List<int[]> path = new ArrayList<int[]>();
        path.add(new int[] { current.x, current.y });
        while (cameFrom.containsKey(current.toString())) {
            current = cameFrom.get(current.toString());
            path.add(new int[] { current.x, current.y });
        }
        Collections.reverse(path);
        return path;
    }

    private List<Node> getNeighbors(Node node) {
        List<Node> neighbors = new ArrayList<Node>();
        List<int[]> jumpPoints = identifySuccessors(node);

        for (int[] jp : jumpPoints) {
            Node jumpPoint = new Node(jp, jp);
            if (isValid(jumpPoint)) {
                neighbors.add(jumpPoint);
            }
        }

        return neighbors;
    }

    private List<int[]> identifySuccessors(Node node) {
        List<int[]> jumpPoints = new ArrayList<int[]>();

        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (dx == 0 && dy == 0) {
                    continue;
                }

                if (jump(node, dx, dy) != null) {
                    jumpPoints.add(jump(node, dx, dy));
                }
            }
        }

        return jumpPoints;
    }

    private int distance(Node n1, Node n2) {
        int dx = Math.abs(n1.x - n2.x);
        int dy = Math.abs(n1.y - n2.y);
        return Math.max(dx, dy);
    }

    private int heuristic(Node n1, Node n2) {
        int dx = Math.abs(n1.x - n2.x);
        int dy = Math.abs(n1.y - n2.y);
        return dx + dy;
    }

    private boolean isValid(Node node) {
        return node.x >= 0 && node.x < rows && node.y >= 0 && node.y < cols && grid[node.x][node.y] == 0;
    }

    private Node jump(Node node, int dx, int dy) {
        int x = node.x + dx;
        int y = node.y + dy;

        if (!isValid(new Node(x, y))) {
            return null;
        }

        if (new Node(x, y).equals(new Node(cols-1, rows-1))) {
            return new Node(x, y);
        }

        if (dx != 0 && dy != 0) {
            if ((isValid(new Node(x-dx, y+dy)) && !isValid(new Node(x-dx, y))) ||
                (isValid(new Node(x+dx, y-dy)) && !isValid(new Node(x, y-dy)))) {
                return new Node(x, y);
            }
            Node jumpDiagonal = jump(new Node(x, y), dx, 0);
            if (jumpDiagonal != null) {
                return new Node(x, y);
            }
            jumpDiagonal = jump(new Node(x, y), 0, dy);
            if (jumpDiagonal != null) {
                return new Node(x, y);
            }
        } else {
            if (dx != 0) {
                if ((isValid(new Node(x+dx, y+1)) && !isValid(new Node(x, y+1))) ||
                    (isValid(new Node(x+dx, y-1)) && !isValid(new Node(x, y-1)))) {
                    return new Node(x, y);
                }
            } else {
                if ((isValid(new Node(x+1, y+dy)) && !isValid(new Node(x+1, y))) ||
                    (isValid(new Node(x-1, y+dy)) && !isValid(new Node(x-1, y)))) {
                    return new Node(x, y);
                }
            }
        }

        return jump(new Node(x, y), dx, dy);
    }

    private class Node {

        public int x;
        public int y;
        public int f;

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

        public String toString() {
            return x + "," + y;
        }

        public boolean equals(Object obj) {
            if (!(obj instanceof Node)) {
                return false;
            }
            if (obj == this) {
                return true;
            }
            Node rhs = (Node)obj;
            return x == rhs.x && y == rhs.y;
        }

    }
}