A Maze Solver in Java – 一个Java中的迷宫求解器

最后修改: 2018年 2月 14日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.介绍

In this article, we’ll explore possible ways to navigate a maze, using Java.

在这篇文章中，我们将探讨使用Java来浏览迷宫的可能方法。

Consider the maze to be a black and white image, with black pixels representing walls, and white pixels representing a path. Two white pixels are special, one being the entry to the maze and another exit.

把迷宫看作是一个黑白图像，黑色像素代表墙壁，白色像素代表路径。两个白色像素很特别，一个是迷宫的入口，另一个是出口。

Given such a maze, we want to find a path from entry to the exit.

给定这样一个迷宫，我们要找到一条从入口到出口的路径。

2. Modelling the Maze

2.建立迷宫模型

We’ll consider the maze to be a 2D integer array. Meaning of numerical values in the array will be as per the following convention:

我们将认为迷宫是一个二维整数阵列。数组中的数值的含义将按照以下惯例。

  • 0 -> Road
  • 1 -> Wall
  • 2 -> Maze entry
  • 3 -> Maze exit
  • 4 -> Cell part of the path from entry to exit

We’ll model the maze as a graph. Entry and exit are the two special nodes, between which path is to be determined.

我们将把迷宫建模为一个图。入口和出口是两个特殊的节点，它们之间的路径将被确定。

A typical graph has two properties, nodes, and edges. An edge determines the connectivity of graph and links one node to another.

一个典型的图有两个属性，节点和边。边决定了图的连通性，将一个节点连接到另一个节点。

Hence we’ll assume four implicit edges from each node, linking the given node to its left, right, top and bottom node.

因此，我们将假设每个节点有四条隐含的边，将给定的节点与它的左、右、顶和底节点连接起来。

Let’s define the method signature:

让我们来定义方法的签名。

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

The input to the method is a maze, which contains the 2D array, with naming convention defined above.

该方法的输入是一个maze，其中包含二维数组，其命名规则如上所述。

The response of the method is a list of nodes, which forms a path from the entry node to the exit node.

该方法的响应是一个节点列表，它形成了一条从入口节点到出口节点的路径。

3. Recursive Backtracker (DFS)

3.递归回溯器（DFS）

3.1. Algorithm

3.1.算法

One fairly obvious approach is to explore all possible paths, which will ultimately find a path if it exists. But such an approach will have exponential complexity and will not scale well.

一个相当明显的方法是探索所有可能的路径，如果存在的话，最终会找到一条路径。但是这种方法的复杂度是指数级的，而且不能很好地扩展。

However, it’s possible to customize the brute force solution mentioned above, by backtracking and marking visited nodes, to obtain a path in a reasonable time. This algorithm is also known as Depth-first search.

然而，通过回溯和标记访问过的节点，有可能定制上述的蛮力解决方案，从而在合理的时间内获得一条路径。这种算法也被称为深度优先搜索。

This algorithm can be outlined as:

这种算法可以概括为：。

  1. If we’re at the wall or an already visited node, return failure
  2. Else if we’re the exit node, then return success
  3. Else, add the node in path list and recursively travel in all four directions. If failure is returned, remove the node from the path and return failure. Path list will contain a unique path when exit is found

Let’s apply this algorithm to the maze shown in Figure-1(a), where S is the starting point, and E is the exit.

让我们把这个算法应用于图-1(a)所示的迷宫，其中S是起点，E是出口。

For each node, we traverse each direction in order: right, bottom, left, top.

对于每个节点，我们按顺序遍历每个方向：右、下、左、上。

In 1(b), we explore a path and hit the wall. Then we backtrack till a node is found which has non-wall neighbors, and explore another path as shown in 1(c).

在1(b)中，我们探索了一条路径并撞到了墙。然后我们回溯，直到找到一个没有墙的邻居的节点，并探索另一条路径，如1（c）所示。

We again hit the wall and repeat the process to finally find the exit, as shown in 1(d):

我们再次撞墙，重复这个过程，最终找到出口，如1（d）所示。

dfs-1dfs-2
dfs-3dfs-4

3.2. Implementation

3.2.实施

Let’s now see the Java implementation:

现在我们来看看Java的实现。

First, we need to define the four directions. We can define this in terms of coordinates. These coordinates, when added to any given coordinate, will return one of the neighboring coordinates:

首先，我们需要定义四个方向。我们可以用坐标来定义。这些坐标，当添加到任何给定的坐标时，将返回相邻的坐标之一。

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

We also need a utility method which will add two coordinates:

我们还需要一个实用的方法，将两个坐标相加。

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

We can now define the method signature solve. The logic here is simple – if there is a path from entry to exit, then return the path, else, return an empty list:

我们现在可以定义方法签名solve. 这里的逻辑很简单–如果有一条从入口到出口的路径，那么返回该路径，否则，返回一个空列表。

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();
}

Let’s define the explore method referenced above. If there’s a path then return true, with the list of coordinates in the argument path. This method has three main blocks.

我们来定义上面提到的explore方法。如果有一个路径，那么返回true，参数path中的坐标列表。这个方法有三个主要块。

First, we discard invalid nodes i.e. the nodes which are outside the maze or are part of the wall. After that, we mark the current node as visited so that we don’t visit the same node again and again.

首先，我们丢弃无效的节点，即在迷宫之外或属于墙的一部分的节点。之后，我们将当前节点标记为已访问过的节点，这样我们就不会再重复访问同一个节点。

Finally, we recursively move in all directions if the exit is not found:

最后，如果没有找到出口，我们就向所有方向递归移动。

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;
}

This solution uses stack size up to the size of the maze.

这个解决方案使用堆栈大小，直到迷宫的大小。

4. Variant – Shortest Path (BFS)

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

4.1. Algorithm

4.1.算法

The recursive algorithm described above finds the path, but it isn’t necessarily the shortest path. To find the shortest path, we can use another graph traversal approach known as Breadth-first search.

上面描述的递归算法找到了路径，但它不一定是最短路径。为了找到最短路径，我们可以使用另一种图的遍历方法，即宽度优先搜索。

In DFS, one child and all its grandchildren were explored first, before moving on to another child. Whereas in BFS, we’ll explore all the immediate children before moving on to the grandchildren. This will ensure that all nodes at a particular distance from the parent node, are explored at the same time.

在DFS中，首先探索一个孩子和它的所有孙子，然后再转到另一个孩子。而在BFS中，我们将先探索所有的直系子节点，然后再转到孙节点。这将确保与父节点有特定距离的所有节点，在同一时间被探索。

The algorithm can be outlined as follows:

该算法可概述如下。

  1. Add the starting node in queue
  2. While the queue is not empty, pop a node, do following:
    1. If we reach the wall or the node is already visited, skip to next iteration
    2. If exit node is reached, backtrack from current node till start node to find the shortest path
    3. Else, add all immediate neighbors in the four directions in queue

One important thing here is that the nodes must keep track of their parent, i.e. from where they were added to the queue. This is important to find the path once exit node is encountered.

这里很重要的一点是，节点必须跟踪它们的父节点，即从哪里被添加到队列的。这对于在遇到出口节点时找到路径很重要。

Following animation shows all the steps when exploring a maze using this algorithm. We can observe that all the nodes at same distance are explored first before moving onto the next level:

下面的动画显示了使用该算法探索迷宫时的所有步骤。我们可以观察到，在进入下一层之前，所有距离相同的节点都会先被探索到。

bfs-1

4.2. Implementation

4.2.实施

Lets now implement this algorithm in Java. We will reuse the DIRECTIONS variable defined in previous section.

现在让我们在Java中实现这个算法。我们将重新使用上一节中定义的DIRECTIONS变量。

Lets first define a utility method to backtrack from a given node to its root. This will be used to trace the path once exit is found:

让我们首先定义一个实用方法，从一个给定的节点回溯到它的根。一旦找到出口，这将被用来追踪路径。

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;
}

Let’s now define the core method solve. We’ll reuse the three blocks used in DFS implementation i.e. validate node, mark visited node and traverse neighboring nodes.

现在让我们来定义核心方法solve.我们将重新使用DFS实现中使用的三个块，即验证节点、标记访问过的节点和遍历邻近节点。

We’ll just make one slight modification. Instead of recursive traversal, we’ll use a FIFO data structure to track neighbors and iterate over them:

我们只需做一个小小的修改。我们将使用一个FIFO数据结构来跟踪邻居并对其进行迭代，而不是递归遍历。

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();
}

5. Conclusion

5.结论

In this tutorial, we described two major graph algorithms Depth-first search and Breadth-first search to solve a maze. We also touched upon how BFS gives the shortest path from the entry to the exit.

在本教程中，我们描述了两种主要的图算法深度优先搜索和广度优先搜索来解决迷宫。我们还谈到了BFS如何给出从入口到出口的最短路径。

For further reading, look up other methods to solve a maze, like A* and Dijkstra algorithm.

要进一步阅读，请查阅其他解决迷宫的方法，如A*和Dijkstra算法。

As always, the full code can be found over on GitHub.

一如既往，完整的代码可以在GitHub上找到，。