«1. Введение

В этой статье мы рассмотрим возможные способы навигации по лабиринту с помощью Java.

Считайте лабиринт черно-белым изображением, где черные пиксели представляют собой стены, а белые пиксели представляют путь. Два белых пикселя являются особыми, один — это вход в лабиринт, а другой — выход.

Учитывая такой лабиринт, мы хотим найти путь от входа к выходу.

2. Моделирование лабиринта

Мы будем рассматривать лабиринт как двумерный массив целых чисел. Значение числовых значений в массиве будет соответствовать следующему соглашению:

    0 -\u003e Дорога 1 -\u003e Стена 2 -\u003e Вход в лабиринт 3 -\u003e Выход из лабиринта 4 -\u003e Ячеечная часть пути от входа до выхода ~~ ~ Мы будем моделировать лабиринт в виде графа. Вход и выход — это два специальных узла, между которыми необходимо определить путь.

Типичный граф имеет два свойства: узлы и ребра. Ребро определяет связность графа и связывает один узел с другим.

Следовательно, мы предполагаем четыре неявных ребра из каждого узла, связывающих данный узел с его левым, правым, верхним и нижним узлами.

Давайте определим сигнатуру метода:

Входными данными для метода является лабиринт, который содержит двумерный массив с определенным выше соглашением об именах. 

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

Ответом метода является список узлов, который образует путь от узла входа к узлу выхода.

3. Рекурсивный возврат (DFS)

3.1. Алгоритм

Один довольно очевидный подход состоит в том, чтобы исследовать все возможные пути, которые в конечном итоге найдут путь, если он существует. Но такой подход будет иметь экспоненциальную сложность и не будет хорошо масштабироваться.

Тем не менее, можно настроить упомянутое выше решение грубой силы, отслеживая и отмечая посещенные узлы, чтобы получить путь за разумное время. Этот алгоритм также известен как поиск в глубину.

Этот алгоритм можно описать так:

Давайте применим этот алгоритм к лабиринту, показанному на рис. 1(a), где S — начальная точка, а E — выход.

  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

Для каждого узла мы проходим в каждом направлении по порядку: вправо, вниз, влево, вверх.

В 1(b) мы исследуем путь и врезаемся в стену. Затем мы возвращаемся назад до тех пор, пока не будет найден узел, у которого есть соседи, отличные от стены, и исследуем другой путь, как показано в 1(c).

Мы снова ударяемся о стену и повторяем процесс, чтобы наконец найти выход, как показано на 1(d):

3.2. Реализация

Теперь давайте посмотрим на реализацию Java:

Во-первых, нам нужно определить четыре направления. Мы можем определить это в терминах координат. Эти координаты при добавлении к любой заданной координате вернут одну из соседних координат:

Нам также нужен служебный метод, который добавит две координаты: 

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

Теперь мы можем определить сигнатуру методаsolve . Логика здесь проста — если есть путь от входа к выходу, то вернуть путь, иначе вернуть пустой список: 

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

Давайте определим метод explore, упомянутый выше. Если есть путь, верните true со списком координат в пути аргумента. Этот метод состоит из трех основных блоков. 

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

Во-первых, мы отбрасываем недопустимые узлы, то есть узлы, которые находятся за пределами лабиринта или являются частью стены. После этого мы помечаем текущий узел как посещенный, чтобы не посещать один и тот же узел снова и снова.

Наконец, мы рекурсивно движемся во всех направлениях, если выход не найден:

Это решение использует размер стека до размера лабиринта. 

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 сначала исследовались один дочерний элемент и все его внуки, а затем переходили к другому дочернему элементу. В то время как в BFS мы исследуем всех непосредственных потомков, прежде чем переходить к внукам. Это гарантирует, что все узлы на определенном расстоянии от родительского узла будут исследоваться одновременно.

Алгоритм можно описать следующим образом:

«Здесь важно то, что узлы должны отслеживать своего родителя, то есть откуда они были добавлены в очередь. Это важно, чтобы найти путь, когда встретится выходной узел.

  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

Следующая анимация показывает все этапы исследования лабиринта с использованием этого алгоритма. Мы можем заметить, что сначала исследуются все узлы на одинаковом расстоянии, прежде чем перейти на следующий уровень:

4.2. Реализация

Давайте теперь реализуем этот алгоритм на Java. Мы будем повторно использовать переменную DIRECTIONS, определенную в предыдущем разделе.

Давайте сначала определим служебный метод для возврата от заданного узла к его корню. Это будет использоваться для трассировки пути после того, как будет найден выход:

Давайте теперь определим основной метод решения. Мы будем повторно использовать три блока, используемые в реализации DFS, т. е. проверка узла, отметка посещенного узла и обход соседних узлов. 

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

Сделаем небольшую модификацию. Вместо рекурсивного обхода мы будем использовать структуру данных FIFO для отслеживания соседей и перебора их:

5. Заключение 

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 определяет кратчайший путь от входа до выхода.

Для дальнейшего чтения поищите другие методы решения лабиринта, такие как A* и алгоритм Дейкстры.

Как всегда, полный код можно найти на GitHub.

«