Блог

Я пытаюсь рекурсивно решить лабиринт с помощью Javascript, как мне вернуть мое решение из моего рекурсивного вызова функции?

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

 let rawMaze = 
    [
      [0, 1, 3], 
      [0, 1, 0], 
      [2, 1, 0]
    ],
  

Где

 0: wall
1: valid path
2: start
3: end
  

Я создаю объект из исходного массива,

 let maze = []
constructMaze() {
    for (let i = 0; i < 3; i  ) {
      maze[i] = [];
      for (let j = 0; j < 3; j  ) {
        const Cell = {
          x: j,
          y: i,
          state: rawMaze[i][j],
          id: uniqueId()
        };
        this.maze[i].push(Cell);
      }
    }
    console.table(this.maze);
  }
  

Я также использую вспомогательную функцию для получения соседей любой заданной ячейки,

 getNeighbours(x, y) {
    let maze = this.maze;
    let neighbours = [];
    maze.forEach(row => {
      row.forEach(cell => {
        if (
          (cell.x == x amp;amp; cell.y == y   1) ||
          (cell.x == x amp;amp; cell.y == y - 1) ||
          (cell.y == y amp;amp; cell.x == x   1) ||
          (cell.y == y amp;amp; cell.x == x - 1)
        ) {
          neighbours.push(cell);
        }
      });
    });

    return neighbours;
  }
  

Основная логика происходит в моей функции checkNeighbours, где я определяю следующие возможные ходы и выполняю их,

 checkNeighbours(neighbours, path, visited) {
    let validMoves = [];
    neighbours.forEach(potentialMove => {
      if (visited.indexOf(potentialMove.id) < 0) {
        if (potentialMove.state !== 0) {
          validMoves.push(potentialMove);
        }
      }
    });

    if (validMoves.length === 0) {
      return;
    } else {
      let finish = validMoves.filter(cell => cell.state === 3);
      console.log(finish);
      if (finish.length === 1) {
        return path;
      }
    }
    validMoves.forEach(validMove => {
      path.push(validMove);
      visited.push(validMove.id);
      this.checkNeighbours(
        this.getNeighbours(validMove.x, validMove.y),
        path,
        visited
      );
    });
  }
  

I then proceed to try and put this all together and solve the maze,

 initSolve(maze) {
    let maze = maze;
    let start = [];
    let paths = [];
    let visited = [];
    let current = null;

    maze.forEach(row => {
      row.forEach(cell => {
        // Is start?
        if ((start.length == 0) amp; (cell.state == 2)) {
          start.push(cell);
          visited.push(cell.id);
          current = cell;
        }
      });
    });
    let result = this.checkNeighbours(
      this.getNeighbours(current.x, current.y),
      paths,
      visited
    );
    console.log("test", result);
  }
  

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

 checkNeighbours()
  

функция рекурсивно прибудет в конце. На этом этапе функция имеет массив (переменную path), который содержит правильные шаги по лабиринту. Как мне вернуть эту ветвь, если хотите, из рекурсивного вызова? Что происходит, когда существует несколько ветвей?
Единственное, что я могу придумать, это использовать глобальную переменную, но я чувствую, что это не может быть правильным.

Это взято из интерфейса React , вот исполняемый код:

 let rawMaze = [
            [0, 1, 3],
            [0, 1, 0],
            [2, 1, 0]
        ]
        let maze = []


        function constructMaze() {
            let counter = 0
            for (let i = 0; i < 3; i  ) {
                maze[i] = [];
                for (let j = 0; j < 3; j  ) {
                    const Cell = {
                        x: j,
                        y: i,
                        state: rawMaze[i][j],
                        id: counter
                    };
                    maze[i].push(Cell);
                    counter  
                }
            }
        }

        function getNeighbours(x, y) {
            let maze = this.maze;
            let neighbours = [];
            maze.forEach(row => {
                row.forEach(cell => {
                    if (
                        (cell.x == x amp;amp; cell.y == y   1) ||
                        (cell.x == x amp;amp; cell.y == y - 1) ||
                        (cell.y == y amp;amp; cell.x == x   1) ||
                        (cell.y == y amp;amp; cell.x == x - 1)
                    ) {
                        neighbours.push(cell);
                    }
                });
            });

            return neighbours;
        }

        function checkNeighbours(neighbours, path, visited) {
            let validMoves = [];
            neighbours.forEach(potentialMove => {
                if (visited.indexOf(potentialMove.id) < 0) {
                    if (potentialMove.state !== 0) {
                        validMoves.push(potentialMove);
                    }
                }
            });

            if (validMoves.length === 0) {
                return;
            } else {
                let finish = validMoves.filter(cell => cell.state === 3);
                console.log(finish);
                if (finish.length === 1) {
                    return path;
                }
            }
            validMoves.forEach(validMove => {
                path.push(validMove);
                visited.push(validMove.id);
                this.checkNeighbours(
                    this.getNeighbours(validMove.x, validMove.y),
                    path,
                    visited
                );
            });
        }

        function initSolve() {
            let maze = constructMaze()
            let start = [];
            let paths = [];
            let visited = [];
            let current = null;

            maze.forEach(row => {
                row.forEach(cell => {
                    // Is start?
                    if ((start.length == 0) amp; (cell.state == 2)) {
                        start.push(cell);
                        visited.push(cell.id);
                        current = cell;
                    }
                });
            });
            let result = this.checkNeighbours(
                this.getNeighbours(current.x, current.y),
                paths,
                visited
            );
            console.log("test", result);
        }
  

Могу ли я порекомендовать добавить другой класс:

 function Path() {
    this.isValidPath = false;
    this.pathArray = [];
}
  

А также переработать checkNeighbours функцию, чтобы переименовать / включить эти параметры?

 checkNeighbours(neighbours, paths, currentPathIndex, visited)
  

Таким образом, paths мог бы содержать массив Path классов, и вы могли бы установить isValidPath флаг в значение true, когда вы нашли допустимый путь (при условии, что вы хотите также включить недопустимые и допустимые пути в массив). Это позволило бы вам возвращать все пути (ветви). Каждая ветвь будет находиться в paths массиве в позиции currentPathIndex , которую вы увеличите в коде, как только один путь будет завершен, и вы захотите начать поиск другого пути.

Кроме того, в настоящее время checkNeighbours функция, похоже, выполняет поиск по ширине допустимых ходов. Возможно, если бы вы переработали его в более глубокий обход, то вы могли бы добавить каждый допустимый путь (и исключить любые недопустимые пути) в возвращаемый вами массив путей.