对于迷宫路径查找器，我如何打破 JavaScript 中的这种递归性？

Question

我一直在练习一些练习，其中我现在正在尝试创建一个代码，用于在 js 创建的迷宫矩阵中寻找路径。现在，这段代码有效，它找到了正确的路径，我什至打印它以确保它是正确的，但我遇到了一个问题。如果我的路径无法到达目的地，我不确定该怎么办。例如，这是我的两个样本，正确的路径用 1 标记，“墙壁”用 0 标记：

[
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
            [0, 1, 1, 1, 0, 1, 1, 1, 0, 0],
            [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        ]

但是，如果我切断一条路径，阻止我的 fidner 到达目的地，我将无法找到打破递归的方法。

[
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 1, 0, 0, 0, 0, 0, 2],
            [0, 1, 1, 1, 0, 1, 1, 0, 0, 0],
            [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        ]

简而言之，我可以 return 正确的路径，但我不确定，以防万一找不到通往“出口”的路，到 return “无效路径”，或者“没有到达目的地的路径”

下面是完整的代码：

class mazeSolver {
    constructor() {


        this.myMaze = [
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
            [0, 1, 1, 1, 0, 1, 1, 1, 0, 0],
            [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        ];


        this.traverse = function (column, row) {
            if (this.myMaze[column][row] === 2) {
                console.log("You found the exit at: " + column + "-" + row);
                console.log("Path: ")
                for (let i = 0; i < this.myMaze.length; i++) {
                    console.log(this.myMaze[i])
                }
            }
            else if (this.myMaze[column][row] === 1) {
                this.myMaze[column][row] = 8;
                console.log("You passed by " + row + "-" + column);
                if (column < this.myMaze.length - 1) {
                    this.traverse(column + 1, row);
                }
                if (row < this.myMaze[column].length - 1) {
                    this.traverse(column, row + 1);
                }

                if (column > 0) {
                    this.traverse(column - 1, row);

                }
                if (row > 0) {
                    this.traverse(column, row - 1);
                }

            }
        };

    }
}

感谢任何意见。谢谢！

Answer 1

您的解决方案在某些情况下不起作用，举个例子

        this.myMaze = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
        [0, 1, 1, 1, 0, 1, 1, 1, 0, 0],
        [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    ];

结果：

    You passed by 3-0
You passed by 3-1
You passed by 4-1
You passed by 5-1
You passed by 5-2
You passed by 5-3
You passed by 6-3
You passed by 7-3
You passed by 8-3
You passed by 9-3
     maze.js:39
            if (this.myMaze[row][column] === 2) {
                                ^

TypeError: Cannot read property '3' of undefined
    at mazeSolver.traverse (maze.js:39:33)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:53:26)
    at mazeSolver.traverse (maze.js:53:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)

关于您的算法，我首先要说的是它是一种急切的算法，也就是说您选择了第一个可用路径。

关于递归的第二件事是你必须有一个在某个时候为真的退出条件，你没有它，你甚至没有在任何时候退出函数。

第三你在列和行之间切换，列是垂直排列，行是水平排列。

这是一个急切解决方案的代码，至少可以避免上述错误

class mazeSolver {
    constructor() {
        this.solution_found=false;
        this.myMaze = [
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
            [0, 1, 1, 1, 0, 1, 0, 1, 0, 0],
            [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        ];
    this.traverse = function (row, column) {
        if (this.myMaze[row][column] === 2) {
            this.solution_found=true;
            console.log("You found the exit at: " + row + "-" + column);
            console.log("Path: ")
            for (let i = 0; i < this.myMaze.length; i++) {
                console.log(this.myMaze[i])
            }
        }
        else if (this.myMaze[row][column] === 1) {
            this.myMaze[row][column] = 8;
            console.log("You passed by " + row + "-" + column);
            if (column < this.myMaze.length - 1) {
                if(row +1> this.myMaze.length - 1)
                    return
                this.traverse(row + 1, column);

            }
            if (row < this.myMaze[row].length - 1) {
                if(column+1 > this.myMaze.length - 1)
                    return
                this.traverse(row, column + 1);

            }

            if (row > 0) {
                if(row-1 < 0){
                    return
                }
                this.traverse(row - 1, column);

            }
            if (column > 0) {
                if(column-1 < 0){
                    return
                }
                this.traverse(row, column - 1);
            }

        }
    };

    }
} 
maze = new mazeSolver();
maze.traverse(3, 0)
if(!maze.solution_found){
    console.log('solution not found')
}

要开发一种算法，如果路径存在，将 100% 找到路径，请尝试对搜索算法进行一些研究，主要是路径查找，例如 A* 启发式算法或 Dijkstra 算法。

Answer 2

对您的代码的一些评论：

在 traverse 方法中使用 console.log 仅用于调试，而不用于报告找到的路径等重要的事情。这实际上应该留给 caller 去做。
如果递归调用找到目标，则不应进行其他递归调用。相反，成功应该立即 returned 给调用者，调用者应该做同样的事情...
可以在回溯期间收集路径。如果成功，此路径可能是 return 值（否则未定义）。
不要在构造函数中初始化硬编码矩阵。而是将矩阵作为参数传递给构造函数。
使 traverse 成为原型方法，而不是在实例上定义它。
在矩阵中，我们通常认为第一维是行，第二维是列。你反其道而行之。
通过使用 ?. 运算符可以更轻松地保护您的遍历免受 out-of-range 访问。

这是更新后的代码：

class MazeSolver {
    constructor(matrix) {
        this.myMaze = matrix;
    }
    traverse(column, row) {
        if (this.myMaze[row]?.[column] === 2) {
            return [[column, row]]; // Return path. Caller can extend it
        } else if (this.myMaze[row]?.[column] === 1) {
            this.myMaze[row][column] = 8;
            console.log("You passed by " + column + "," + row);
            const path = this.traverse(column + 1, row)
                      ?? this.traverse(column, row + 1)
                      ?? this.traverse(column - 1, row)
                      ?? this.traverse(column, row - 1);
            if (path) path.unshift([column, row]); // Extend the path found
            return path;
        }
    }
} 

// Maze without solution:
const solver = new MazeSolver([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
    [0, 1, 1, 1, 0, 1, 0, 1, 0, 0],
    [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]);

const path = solver.traverse(0, 3);
if (path) {
    console.log("found a path (column, row):")
    console.log(JSON.stringify(path));
} else {
    console.log("No path found");
}

对于迷宫路径查找器，我如何打破 JavaScript 中的这种递归性？

How I may break from this recursivity in JavaScript for a maze path finder?

javascript

arrays

maze

matrix