阅读量:2
Java中的寻路算法可以使用图的搜索算法来实现。以下是一个简单的示例,使用BFS(广度优先搜索)算法来寻找路径。
import java.util.*; public class PathFinding { // 定义图的大小 private static final int ROW = 5; private static final int COL = 5; // 定义图的节点 private static class Node { int x; int y; Node parent; public Node(int x, int y, Node parent) { this.x = x; this.y = y; this.parent = parent; } } // 定义可移动的方向 private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 判断点是否在图内 private static boolean isValid(int x, int y) { return x >= 0 && x < ROW && y >= 0 && y < COL; } // 判断点是否为障碍物(1表示障碍物) private static boolean isObstacle(int[][] grid, int x, int y) { return grid[x][y] == 1; } // 寻找路径 public static List<Node> findPath(int[][] grid, Node start, Node end) { List<Node> path = new ArrayList<>(); // 使用BFS算法 Queue<Node> queue = new LinkedList<>(); queue.offer(start); boolean[][] visited = new boolean[ROW][COL]; visited[start.x][start.y] = true; while (!queue.isEmpty()) { Node curr = queue.poll(); if (curr.x == end.x && curr.y == end.y) { // 找到目标节点,构建路径 while (curr != null) { path.add(0, curr); curr = curr.parent; } break; } // 遍历可移动的方向 for (int[] direction : DIRECTIONS) { int newX = curr.x + direction[0]; int newY = curr.y + direction[1]; if (isValid(newX, newY) && !isObstacle(grid, newX, newY) && !visited[newX][newY]) { Node next = new Node(newX, newY, curr); queue.offer(next); visited[newX][newY] = true; } } } return path; } public static void main(String[] args) { // 定义一个示例地图 int[][] grid = { {0, 0, 0, 0, 0}, {1, 1, 1, 1, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 1, 1}, {0, 0, 0, 0, 0} }; Node start = new Node(0, 0, null); Node end = new Node(4, 4, null); List<Node> path = findPath(grid, start, end); if (path.isEmpty()) { System.out.println("No path found."); } else { System.out.println("Path found:"); for (Node node : path) { System.out.println("(" + node.x + ", " + node.y + ")"); } } } }
这个示例中,使用一个二维数组来表示地图,0表示可通行的区域,1表示障碍物。findPath
方法使用BFS算法来寻找路径,返回一个包含节点的列表。最后在main
方法中进行测试,输出找到的路径。