Java 迷宫求解器 | Baeldung中文网

1. 引言

本文将探讨使用 Java 实现迷宫导航的多种方案。我们将迷宫视为黑白图像：黑色像素代表墙壁，白色像素代表路径。其中有两个特殊的白色像素——入口和出口。给定这样的迷宫，我们的目标是从入口找到一条通往出口的路径。

2. 迷宫建模

我们将迷宫表示为二维整数数组，数值含义约定如下：

0 → 道路
1 → 墙壁
2 → 迷宫入口
3 → 迷宫出口
4 → 路径中的节点

将迷宫建模为图结构：入口和出口是两个特殊节点，我们需要找到它们之间的路径。图包含节点和边，边定义了节点间的连接关系。因此我们假设每个节点有四个隐式边，分别连接其左、右、上、下四个相邻节点。

方法签名定义：

public List<Coordinate> solve(Maze maze) {
}

输入参数 maze 包含符合上述约定的二维数组，返回值是从入口到出口的路径节点列表。

3. 递归回溯算法（DFS）

3.1 算法原理

最直观的方案是暴力搜索所有可能路径，但这种方法时间复杂度呈指数级增长，无法扩展到大型迷宫。不过我们可以通过回溯和标记已访问节点来优化暴力搜索，这种算法也称为深度优先搜索。

算法步骤：

如果当前节点是墙壁或已访问节点 → 返回失败
如果当前节点是出口 → 返回成功
否则：
- 将节点加入路径列表
- 递归探索四个方向
- 若所有方向均失败，则从路径中移除当前节点并返回失败
- 当找到出口时，路径列表即为有效路径

以图1(a)的迷宫为例（S=起点，E=出口），按右→下→左→上的顺序探索：

图1(b)：探索路径遇到墙壁，回溯到有未探索邻居的节点
图1(c)：探索新路径再次遇到墙壁
图1(d)：重复回溯过程最终找到出口

3.2 代码实现

首先定义四个移动方向（坐标偏移量）：

private static int[][] DIRECTIONS 
  = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

坐标相加工具方法：

private Coordinate getNextCoordinate(
  int row, int col, int i, int j) {
    return new Coordinate(row + i, col + j);
}

核心求解方法：逻辑简单粗暴——存在路径则返回路径，否则返回空列表

public List<Coordinate> solve(Maze maze) {
    List<Coordinate> path = new ArrayList<>();
    if (
      explore(
        maze, 
        maze.getEntry().getX(),
        maze.getEntry().getY(),
        path
      )
      ) {
        return path;
    }
    return Collections.emptyList();
}

递归探索方法 explore 分三块处理：

无效节点处理：超出边界/墙壁/已访问节点 → 返回失败
节点标记：将当前节点加入路径并标记为已访问
递归探索：若未找到出口，则按顺序探索四个方向

private boolean explore(
  Maze maze, int row, int col, List<Coordinate> path) {
    if (
      !maze.isValidLocation(row, col) 
      || maze.isWall(row, col) 
      || maze.isExplored(row, col)
    ) {
        return false;
    }

    path.add(new Coordinate(row, col));
    maze.setVisited(row, col, true);

    if (maze.isExit(row, col)) {
        return true;
    }

    for (int[] direction : DIRECTIONS) {
        Coordinate coordinate = getNextCoordinate(
          row, col, direction[0], direction[1]);
        if (
          explore(
            maze, 
            coordinate.getX(), 
            coordinate.getY(), 
            path
          )
        ) {
            return true;
        }
    }

    path.remove(path.size() - 1);
    return false;
}

⚠️ 此方案栈空间消耗与迷宫大小成正比，深度过大的迷宫可能导致栈溢出。

4. 变体：最短路径（BFS）

4.1 算法原理

DFS 找到的路径不一定是最短的。要找到最短路径，可使用广度优先搜索。

核心差异：

DFS：优先探索单个子节点及其所有后代
BFS：优先探索所有直接子节点，再处理孙节点

算法步骤：

将起点加入队列
循环处理队列直到为空：
- 跳过墙壁/已访问节点
- 遇到出口时回溯父节点构建路径
- 否则将四个方向的邻居加入队列

关键点：节点必须记录父节点来源，以便找到出口时回溯路径。下图展示了 BFS 的逐层探索过程：

4.2 代码实现

复用 DIRECTIONS 定义。先实现路径回溯工具方法：

private List<Coordinate> backtrackPath(
  Coordinate cur) {
    List<Coordinate> path = new ArrayList<>();
    Coordinate iter = cur;

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

    return path;
}

核心求解方法（使用队列替代递归）：

public List<Coordinate> solve(Maze maze) {
    LinkedList<Coordinate> nextToVisit 
      = new LinkedList<>();
    Coordinate start = maze.getEntry();
    nextToVisit.add(start);

    while (!nextToVisit.isEmpty()) {
        Coordinate cur = nextToVisit.remove();

        if (!maze.isValidLocation(cur.getX(), cur.getY()) 
          || maze.isExplored(cur.getX(), cur.getY())
        ) {
            continue;
        }

        if (maze.isWall(cur.getX(), cur.getY())) {
            maze.setVisited(cur.getX(), cur.getY(), true);
            continue;
        }

        if (maze.isExit(cur.getX(), cur.getY())) {
            return backtrackPath(cur);
        }

        for (int[] direction : DIRECTIONS) {
            Coordinate coordinate 
              = new Coordinate(
                cur.getX() + direction[0], 
                cur.getY() + direction[1], 
                cur
              );
            nextToVisit.add(coordinate);
            maze.setVisited(cur.getX(), cur.getY(), true);
        }
    }
    return Collections.emptyList();
}

✅ BFS 保证找到最短路径，但内存消耗高于 DFS（需存储所有待访问节点）。

5. 总结

本文介绍了两种图算法解决迷宫问题：

深度优先搜索（DFS）：实现简单，但路径不一定最短
广度优先搜索（BFS）：保证最短路径，但内存开销更大

进阶学习建议：研究 A* 和 Dijkstra 算法等更高效的路径规划方案。

完整代码可在 GitHub 获取。

Persistence

REST

Security