Java地图导航如何根据第一个点获取下一个点

Question

想做一个Java地图导航，选择某条路线后根据第一个起点获取下一个点，该如何操作

Answer 1

引自免费微信小程序：皆我百晓生

在Java中实现地图导航功能，你需要一个数据结构来表示地图以及路径。这里我们可以使用邻接矩阵或邻接表来表示地图，然后使用路径查找算法（例如Dijkstra或A*）来找到最佳路径。在这个例子中，我们将使用一个简单的邻接列表和Dijkstra算法来找出两个点之间的最短路径。

首先，我们需要创建一个Node类来表示地图上的每个位置，并包含其坐标和与相邻节点的连接信息。接下来，我们实现一个Graph类来维护节点和它们之间的关系。然后，我们定义一个方法getNearestNeighbor(Node current, List<Node> visited)来获取给定点的下一个最近点。最后，我们将这些部分组合在一起，实现一个主函数来演示如何使用这个系统。

以下是完整的Java代码示例：

import java.util.*;

class Node {
    int x;
    int y;
    
    // 用于存储到相邻节点的距离
    Map<Node, Integer> neighbors;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
        this.neighbors = new HashMap<>();
    }

    void addNeighbor(Node neighbor, int distance) {
        this.neighbors.put(neighbor, distance);
    }
}

public class Graph {
    private List<Node> nodes;

    public Graph(List<Node> nodes) {
        this.nodes = nodes;
    }

    // Dijkstra算法实现
    public List<Node> dijkstra(Node start, Node end) {
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.distanceFrom(start)));
        Set<Node> visited = new HashSet<>();

        for (Node node : nodes) {
            if (node.equals(start)) {
                node.distanceFrom(start) = 0;
                queue.offer(node);
            } else {
                node.distanceFrom(start) = Integer.MAX_VALUE;
            }
        }

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            visited.add(current);

            if (current.equals(end)) {
                break;
            }

            for (Map.Entry<Node, Integer> entry : current.neighbors.entrySet()) {
                Node neighbor = entry.getKey();
                int distance = entry.getValue();

                if (!visited.contains(neighbor)) {
                    int newDistance = current.distanceFrom(start) + distance;
                    if (newDistance < neighbor.distanceFrom(start)) {
                        neighbor.distanceFrom(start) = newDistance;
                        queue.offer(neighbor);
                    }
                }
            }
        }

        return getShortestPath(start, end, visited);
    }

    // 获取从start到end的最短路径
    private List<Node> getShortestPath(Node start, Node end, Set<Node> visited) {
        List<Node> path = new ArrayList<>();
        Node current = end;

        while (!current.equals(start)) {
            path.add(current);
            visited.remove(current);
            for (Map.Entry<Node, Integer> entry : current.neighbors.entrySet()) {
                Node neighbor = entry.getKey();
                if (visited.contains(neighbor)) {
                    current = neighbor;
                    break;
                }
            }
        }

        Collections.reverse(path);
        path.add(start);
        return path;
    }

    // 获取当前点的下一个最近点
    public Node getNearestNeighbor(Node current, List<Node> visited) {
        int minDistance = Integer.MAX_VALUE;
        Node nearest = null;

        for (Node node : nodes) {
            if (!visited.contains(node) && node != current) {
                int distance = current.distanceTo(node);
                if (distance < minDistance) {
                    minDistance = distance;
                    nearest = node;
                }
            }
        }

        return nearest;
    }
}

public class Main {
    public static void main(String[] args) {
        // 创建节点并添加边
        List<Node> nodes = Arrays.asList(
            new Node(1, 1),
            new Node(2, 1),
            new Node(3, 1),
            new Node(1, 2),
            new Node(2, 2),
            new Node(3, 2)
        );

        nodes.get(0).addNeighbor(nodes.get(1), 1);
        nodes.get(0).addNeighbor(nodes.get(4), 1);
        nodes.get(1).addNeighbor(nodes.get(2), 1);
        nodes.get(1).addNeighbor(nodes.get(5), 1);
        nodes.get(2).addNeighbor(nodes.get(3), 1);
        nodes.get(4).addNeighbor(nodes.get(5), 1);
        nodes.get(4).addNeighbor(nodes.get(6), 1);
        nodes.get(5).addNeighbor(nodes.get(7), 1);

        Graph graph = new Graph(nodes);

        // 指定起始点和终点
        Node start = nodes.get(0);
        Node end = nodes.get(7);

        // 找出最短路径
        List<Node> shortestPath = graph.dijkstra(start, end);

        System.out.println("Shortest Path:");
        for (Node node : shortestPath) {
            System.out.print("(" + node.x + ", " + node.y + ") ");
        }

        // 根据第一个点获取下一个点
        List<Node> visited = new ArrayList<>();
        visited.add(start);
        Node nextPoint = graph.getNearestNeighbor(start, visited);
        System.out.println("\nNext point after the start: (" + nextPoint.x + ", " + nextPoint.y + ")");
    }
}

这段代码首先创建了一个简单的网格地图，然后使用Dijkstra算法找出从起点到终点的最短路径。接着，它会根据已访问过的点列表，找到离当前点最近且未被访问的下一个点。你可以根据实际需求修改地图、起点和终点。注意，这个例子中的地图是二维的，对于更复杂的情况，可以扩展为三维或其他维度。